Golang 一致性Hash算法实现

<blockquote> ❝

一致性 hash 算法是在分布式应用中使用广泛。其主要作用是为了解决服务中的热点问题。例如在分布式数据存储，比如Redis缓存集群、有状态的任务作业等，通过其解决请求的热点问题，并且可以缓解当发生服务变动时出现的负载不平衡情况。

❞ </blockquote>

本文将简单介绍一致性HASH算法，并分析golang的一个开源实现包(<code>github.com/stathat/consistent</code>)

<h2>一致性hash算法原理</h2> <h3>解决的问题</h3>

在分布式存储中，为了保证不同机器缓存的数据均衡性以及负载的均衡性，一般会在代理层先做一次hash。正常情况下，我们会做取模操作，然后将服务分配给不同的机器。但是这种情况下当某台服务宕机或者有新机器加入时，会直接影响到所有机器的缓存。为了解决这个问题，所以出现了一致性hash算法。

<h3>如何解决</h3>

一致性hash算法，主要是解决如何将hash后的值映射到既定的机器中。下面是hash步骤：

1，将hash值构造为一个圆环，一般为 [0,2^32 - 1] 2. 在圆环上均匀的挑选hash点，作为机器的节点 3. 在访问机器时，hash到圆环的某个点上，然后顺时针访问到的第一个节点即为需要访问的机器。

这样，当某台机器宕机时，宕机机器的下一台机器将承包宕机机器的存储任务。如果hash环中的两个机器节点中添加了一个机器节点，那原有的节点存储任务将被分一部分存储任务给新增加的节点。

<h3>升华</h3>

正常情况下，如果使用上面说的一致性hash算法，出现宕机时，一台机器将干两台机器的活，这显然是不科学的。因此还需要有虚拟节点的概念。将虚拟节点放在圆环上，然后真正的服务节点维护多个虚拟节点（并且需要保证一台服务节点上的多个虚拟节点需要离散分布）。这样，当一个服务节点宕机后，其实是多个离散的虚拟节点从hash环中消失，这样可以保证正常的机器在保留原有数据的基础上，还能承载宕机对应的离散节点的负载。

<h2>一致性hash算法的golang实现</h2>

<code>github.com/stathat/consistent</code> 是golang实现的一个一致性hash算法。

<h2>数据结构</h2>

在实现中，增加了分布式缓存中较为实用的副本的概念。结构如下：

<pre class="has"><code class="language-go">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  // 读写锁标记 } </code></pre> <h3>设置节点</h3>

初始化节点时，需要提供各个节点的名称，以及副本的数量。初始化将进行如下操作：

<ol><li>

将hash与node名的映射存入circle中

</li><li>

将members 标记为true

</li><li>

将hash值放入有序的sortedHashes中

</li></ol><pre class="has"><code class="language-go">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)   } } </code></pre> <pre class="has"><code class="language-go">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 } </code></pre> <h3>访问</h3>

当通过name映射一个node时，首先计算hash值，然后通过二分查找的方法从sortedHashes slice中拿到对应的node的hash值，最后通过circle映射出对应的node name.

<pre class="has"><code class="language-go">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 } </code></pre> <h3>删除</h3>

当某台机器宕机时，可以删除对应的node 节点，以释放快速调整服务请求。

<pre class="has"><code class="language-go">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-- } </code></pre> <h2>总结</h2>

从代码的实现中，我们可以看出：

<ul><li>

从环中查找下一个节点，只需要将所有节点的hash值存放在一个有序的slice中，做二分查找即可。为了保证每个节点数据的均衡性，一般会添加较多的虚拟节点，为了保证访问请求的速度，又不能过多。例如，在Codis中，虚拟节点默认一般有1024个（当然也可以配置更多的槽）

</li><li>

一致性hash对服务在做调整时可以做平滑过度

</li><li>

比较常见的应用,例如分布式缓存服务 Redis-Cluster, Codis；或者 服务代理 twemproxy 等

</li></ul>