Golang 一致性Hash算法实现
❝一致性 hash 算法是在分布式应用中使用广泛。其主要作用是为了解决服务中的热点问题。例如在分布式数据存储，比如Redis缓存集群、有状态的任务作业等，通过其解决请求的热点问题，并且可以缓解当发生服务变动时出现的负载不平衡情况。
❞
本文将简单介绍一致性HASH算法，并分析golang的一个开源实现包(github.com/stathat/consistent)
一致性hash算法原理
解决的问题
在分布式存储中，为了保证不同机器缓存的数据均衡性以及负载的均衡性，一般会在代理层先做一次hash。正常情况下，我们会做取模操作，然后将服务分配给不同的机器。但是这种情况下当某台服务宕机或者有新机器加入时，会直接影响到所有机器的缓存。为了解决这个问题，所以出现了一致性hash算法。
如何解决
一致性hash算法，主要是解决如何将hash后的值映射到既定的机器中。下面是hash步骤：
1，将hash值构造为一个圆环，一般为 [0,2^32 - 1] 2. 在圆环上均匀的挑选hash点，作为机器的节点 3. 在访问机器时，hash到圆环的某个点上，然后顺时针访问到的第一个节点即为需要访问的机器。
这样，当某台机器宕机时，宕机机器的下一台机器将承包宕机机器的存储任务。如果hash环中的两个机器节点中添加了一个机器节点，那原有的节点存储任务将被分一部分存储任务给新增加的节点。
升华
正常情况下，如果使用上面说的一致性hash算法，出现宕机时，一台机器将干两台机器的活，这显然是不科学的。因此还需要有虚拟节点的概念。将虚拟节点放在圆环上，然后真正的服务节点维护多个虚拟节点（并且需要保证一台服务节点上的多个虚拟节点需要离散分布）。这样，当一个服务节点宕机后，其实是多个离散的虚拟节点从hash环中消失，这样可以保证正常的机器在保留原有数据的基础上，还能承载宕机对应的离散节点的负载。
一致性hash算法的golang实现
github.com/stathat/consistent 是golang实现的一个一致性hash算法。
数据结构
在实现中，增加了分布式缓存中较为实用的副本的概念。结构如下：
type Consistent struct {
circle map[uint32]string // 保存环
members map[string]bool // 成员标记
sortedHashes uints // []int32 类型 标记了环上的虚拟节点，有序的slice
NumberOfReplicas int // 副本数量
count int64 // 节点数量
scratch [64]byte // 未使用
UseFnv bool // 标记使用 FNV-1a hash
sync.RWMutex // 读写锁标记
}
设置节点
初始化节点时，需要提供各个节点的名称，以及副本的数量。初始化将进行如下操作：
-
将hash与node名的映射存入circle中 -
将members 标记为true -
将hash值放入有序的sortedHashes中
func (c *Consistent) Set(elts []string) {
c.Lock()
defer c.Unlock()
for k := range c.members { // 首先将清除不在elts 集合中的数据
found := false
for _, v := range elts {
if k == v {
found = true
break
}
}
if !found {
c.remove(k)
}
}
for _, v := range elts { // 之后依次添加
_, exists := c.members[v]
if exists {
continue
}
c.add(v)
}
}
func (c *Consistent) add(elt string) {
for i := 0; i < c.NumberOfReplicas; i++ {
c.circle[c.hashKey(c.eltKey(elt, i))] = elt
}
c.members[elt] = true
c.updateSortedHashes() // 更新sortedHashes 字段，保证有序
c.count++
}
访问
当通过name映射一个node时，首先计算hash值，然后通过二分查找的方法从sortedHashes slice中拿到对应的node的hash值，最后通过circle映射出对应的node name.
func (c *Consistent) Get(name string) (string, error) {
c.RLock()
defer c.RUnlock()
if len(c.circle) == 0 {
return "", ErrEmptyCircle
}
key := c.hashKey(name)
i := c.search(key)
return c.circle[c.sortedHashes[i]], nil
}
删除
当某台机器宕机时，可以删除对应的node 节点，以释放快速调整服务请求。
func (c *Consistent) remove(elt string) {
// 代码中有加锁
for i := 0; i < c.NumberOfReplicas; i++ {
delete(c.circle, c.hashKey(c.eltKey(elt, i)))
}
delete(c.members, elt)
c.updateSortedHashes()
c.count--
}
总结
从代码的实现中，我们可以看出：
-
从环中查找下一个节点，只需要将所有节点的hash值存放在一个有序的slice中，做二分查找即可。为了保证每个节点数据的均衡性，一般会添加较多的虚拟节点，为了保证访问请求的速度，又不能过多。例如，在Codis中，虚拟节点默认一般有1024个（当然也可以配置更多的槽） -
一致性hash对服务在做调整时可以做平滑过度 -
比较常见的应用,例如分布式缓存服务 Redis-Cluster, Codis；或者 服务代理 twemproxy 等