一致哈希算法介绍参考本站文章《一致哈希算法理解(一致哈希学习笔记一）》

回顾一致哈希算法步骤：
0、将每一个服务器节点按照ip或者server_name, 通过hash函数(eg: crc32)得到对应的一组hash整数值，这里称做hash_servers，并对得到的整数值按由小到大进行排序。
1、将key也通过上面同一个hash函数计算得到对应hash整数值, 这里称为hash_key。

2、遍历hash_servers，用hash_key与hash_servers中的数逐个比较，当hash_key最后小于hash_servers中的那个数存在时，这个数对应的节点就是这个key所存储的节点，否则存在第一个节点。

一、Go实现
这里主要是一致哈希算法Go的一种实现笔记，PHP的实现参考本站文章《一致哈希PHP实现及应用(一致哈希学习笔记二)》

package main

import (
	"fmt"
	"hash/crc32"
	"sort"
)

const (
	// 虚拟节点数
	VirualNodes = 32
)

// 定义存储所有slot的切片，实现sort.Sort()的接口用于排序
type slots []uint32

func (s slots) Len() int {
	return len(s)
}

func (s slots) Less(i, j int) bool {
	return s[i] < s[j]
}

func (s slots) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

type ConsistentHashing struct {
	nodesMap        map[uint32]string
	nodesSlots      slots
}

// 自定义哈希函数，使用crc32
func (h *ConsistentHashing) myHash(key string) uint32 {
	return crc32.ChecksumIEEE([]byte(key))
}

// 添加节点
func (c *ConsistentHashing) AddNode(node string) {	
	for i := 0; i < VirualNodes; i++ {
		slot := c.myHash(fmt.Sprintf("%s-%d", node, i))
		//fmt.Println(node, slot)
		c.nodesMap[slot] = node
	}
	c.sortNodesSlots()
}

// 将slot保存到切片中并升序
func (c *ConsistentHashing) sortNodesSlots() {
	slotst := slots{}
	for slot := range c.nodesMap {
		slotst = append(slotst, slot)
	}
	sort.Sort(slotst)
	c.nodesSlots = slotst
}

// 删除节点
func (c *ConsistentHashing) DelNode(node string) {	
	for i := 0; i < VirualNodes; i++ {
		slot := c.myHash(fmt.Sprintf("%s-%d", node, i))
		delete(c.nodesMap, slot)
	}
	c.sortNodesSlots()
}

// 定位key所属节点
func (c *ConsistentHashing) Lookup(key string) string {
	slot := c.myHash(key)
	
	index := uint32(0)
	for _, nodesSlot := range c.nodesSlots {
		if nodesSlot >= slot {
			index = nodesSlot
			break
		}
	}
	if node, ok := c.nodesMap[index]; ok {
		return node
	} else {
		return "不存在"
	}
	
}


func main() {
	ch := ConsistentHashing {
		nodesMap: map[uint32]string{},
	}
	
	// test case
	ch.AddNode("N1")
	ch.AddNode("N2")
	ch.AddNode("N3")
	
	k1, k2 := "niliu_k1", "niliu_k2"
	
	fmt.Println(fmt.Sprintf("key: %s, 落在 %s 节点上", k1, ch.Lookup(k1)))
	fmt.Println(fmt.Sprintf("key: %s, 落在 %s 节点上", k2, ch.Lookup(k2)))
	
	ch.DelNode("N1")
	
	//fmt.Println(ch.nodesSlots)
	//fmt.Println(ch.nodesMap)
	
	fmt.Println("after delete node")
	fmt.Println(fmt.Sprintf("key: %s, 落在 %s 节点上", k1, ch.Lookup(k1)))
	fmt.Println(fmt.Sprintf("key: %s, 落在 %s 节点上", k2, ch.Lookup(k2)))
}

测试结果

key: niliu_k1, 落在 N1 节点上
key: niliu_k2, 落在 N3 节点上
after delete node
key: niliu_k1, 落在 N3 节点上
key: niliu_k2, 落在 N3 节点上

二、TODO
1、查找节点的时候使用的顺序查找，效率比较低，可以考虑二分查找
2、更新节点的方法未实现
3、实现一致哈希的方法放到单独的package中
4、优化使用读写锁
5、补充更多的测试case

三、参考
https://github.com/g4zhuj/hashring/blob/master/hashring.go