transfer通过一致性hash算法，决定一条指标应该发送到哪个graph节点。

transfer应用了toolkits/consistent提供的一致性hash实现，调用办法很简略：

//结构hash环GraphNodeRing = rings.NewConsistentHashNodesRing(int32(cfg.Graph.Replicas), cutils.KeysOfMap(cfg.Graph.Cluster))//查找key对应的nodenode, err := GraphNodeRing.GetNode(pk)

本文解说一致性hash算法是什么，联合代码解说一下toolkits/consistent如何实现一致性hash算法。

1. 一般的 mod N hash算法

最简略的hash是mod N：

group = key % N

mod N hash算法的毛病；只有集群N的数量发生变化，绝大部分的key的映射关系生效(翻倍的扩容/缩容，可维持50%的失效率)。

2. 一致性hash算法是什么

一致性hash通过构建环状hash空间，代替了线性hash空间的办法，解决了hash映射下绝大部分映射生效的问题：

整个hash空间被构建成一个首尾相接的环，应用一致性hash时须要进行2次映射：

  • 每个节点计算hash，确定其在hash环上的地位(uint32的整数)；
  • 每个key计算hash(uint32的整数)，而后顺时针找环上的第一个点，该key就存储到该节点上；

一致性hash的长处是，当减少节点/删除节点时，只有一部分key的映射产生生效：

一致性hash的特点是满足枯燥性要求：

  • 假如key调配在节点A上，当有新节点N退出集群时，key会映射到节点A或节点N上，不会映射到其它节点；

一致性hash算法有2个问题：

  • 数据歪斜：如果节点的数量很少，可能会呈现大部分key拥挤的散布在某个节点上的状况；
  • 缓存雪崩：当node1故障退出时，原来node1负责的key将由node2解决，意味着node2的压力会霎时增大；若node2因为压力过大而解体，那么更大的压力将冲向node3，造成雪崩；

一致性hash引入虚构节点解决了这一问题：

  • 一个理论节点映射为多个虚构节点，这样hash空间会绝对平均；
  • 一个实在的节点退出，它原来承当的压力会平均的扩散到其它节点；

3. 一致性hash算法的实现(toolkits/consistent)

toolkits/consistent的实现也很简略：

  • 应用CRC32结构了一个hash环(unit32)；
  • 对nodeKey进行hash失去value=A(uint32)，对应hash环的一个地位；
  • 对itemKey进行hash失去value=B(uint32)，二分查问hash环中第一个 > B的节点，该节点就负载该item；
// Consistent holds the information about the members of the consistent hash circle.type Consistent struct {    circle           map[uint32]string    members          map[string]bool    sortedHashes     uints    NumberOfReplicas int    count            int64    scratch          [64]byte    sync.RWMutex}

增加节点：每个node有若干个replica，对每个replica都hash失去nodeKey，放入circle中：

// Add inserts a string element in the consistent hash.func (c *Consistent) Add(elt string) {    c.Lock()    defer c.Unlock()    c.add(elt)}// need c.Lock() before callingfunc (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()    c.count++}

查问itemKey映射到哪个node:先算itemKey的hash，而后二分查找circle，找第一个 > hash的节点即为指标节点：

// Get returns an element close to where name hashes to in the circle.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}func (c *Consistent) search(key uint32) (i int) {    f := func(x int) bool {        return c.sortedHashes[x] > key    }    i = sort.Search(len(c.sortedHashes), f)    if i >= len(c.sortedHashes) {        i = 0    }    return}

参考：
1.一致性hash: https://mp.weixin.qq.com/s/WP...