Open-falcon transfer中的一致性hash算法及其源码实现监控工具

transfer通过一致性hash算法，决定一条指标应该发送到哪个graph节点。
transfer使用了toolkits/consistent提供的一致性hash实现，调用方法很简单：

//构造hash环 GraphNodeRing = rings.NewConsistentHashNodesRing(int32(cfg.Graph.Replicas), cutils.KeysOfMap(cfg.Graph.Cluster))//查找key对应的node node, 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=https://www.it610.com/article/A(uint32)，对应hash环的一个位置；
对itemKey进行hash得到value=https://www.it610.com/article/B(uint32)，二分查询hash环中第一个> B的节点，该节点就负载该item；

// Consistent holds the information about the members of the consistent hash circle. type Consistent struct { circlemap[uint32]string membersmap[string]bool sortedHashesuints NumberOfReplicas int countint64 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 calling 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() 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 }

【Open-falcon transfer中的一致性hash算法及其源码实现】参考：
1.一致性hash: https://mp.weixin.qq.com/s/WP...