需求
当集群提供缓存服务时，key应该路由到哪一个服务.这里假如采用最通用的方式key%N(N为服务器数目)，看上去是没问题的但是一旦服务器数目发生增加或减少时, 分配方式则变为key%(N+1)或key%(N-1).这里将会有大量的key失效, 为了解决类问题,一致性hash算法应运而生.
一致性hash算法特点
- 均衡性(Balance)
- 单调性(Monotonicity)
- 分散性(Spread)
- 负载(Load)
一致性hash详解
- 一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 K/n个关键字重新映射，其中 K是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。
- 一致性哈希算法将整个哈希值空间映射成一个虚拟的圆环，整个哈希空间的取值范围为0~2的32次方-1。整个空间按顺时针方向组织。0~2的32次方-1在零点中方向重合。接下来使用如下算法对服务请求进行映射，将服务请求使用哈希算法算出对应的hash值，然后根据hash值的位置沿圆环顺时针查找，第一台遇到的服务器就是所对应的处理请求服务器。当增加一台新的服务器，受影响的数据仅仅是新添加的服务器到其环空间中前一台的服务器（也就是顺着逆时针方向遇到的第一台服务器）之间的数据，其他都不会受到影响。综上所述，一致性哈希算法对于节点的增减都只需重定位环空间中的一小部分数据，具有较好的容错性和可扩展性
改进
如果服务器节点较少，存在某些节点所在位置周围有大量的hash点从而导致分配到这些节点到key要比其他节点多的多，这样会导致集群中各节点负载不均衡，为解决这个问题，引入虚拟节点， 即一个实节点对应多个虚拟节点。缓存的key作映射时，先找到对应的虚拟节点，再对应到实节点
代码实现
type Consistent struct {
nodesReplicas int //添加虚拟节点数量
hashSortNodes []uint32 //所有节点的排序数组
circle map[uint32]string //所有节点对应的node
nodes map[string]bool //node是否存在
}
func NewConsistent() *Consistent {
return &Consistent{
nodesReplicas: 20,
circle: make(map[uint32]string),
nodes: make(map[string]bool),
}
}
func (c *Consistent) Add(node string) error {
if _, ok := c.nodes[node]; ok { //判断新加节点是否存在
return fmt.Errorf("%s already existed", node)
}
c.nodes[node] = true
for i := 0; i < c.nodesReplicas; i++ { //添加虚拟节点
replicasKey := getReplicasKey(i, node) //虚拟节点
c.circle[replicasKey] = node
c.hashSortNodes = append(c.hashSortNodes, replicasKey) //所有节点ID
}
sort.Slice(c.hashSortNodes, func(i, j int) bool { //排序
return c.hashSortNodes[i] < c.hashSortNodes[j]
})
return nil
}
func (c *Consistent) Get(key string) (string, error) {
if len(c.nodes) == 0 {
return "", errors.New("not add node")
}
index := c.searchNearbyIndex(key)
host := c.circle[c.hashSortNodes[index]]
return host, nil
}