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

Open-falcon transfer中的一致性hash算法及其源码实现_第1张图片

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

2. 一致性hash算法是什么

一致性hash通过构建环状hash空间,替代了线性hash空间的方法,解决了hash映射下绝大部分映射失效的问题:

Open-falcon transfer中的一致性hash算法及其源码实现_第2张图片

整个hash空间被构建成一个首尾相接的环,使用一致性hash时需要进行2次映射:

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

一致性hash的优点是,当增加节点/删除节点时,只有一部分key的映射发生失效:

Open-falcon transfer中的一致性hash算法及其源码实现_第3张图片

一致性hash的特点是满足单调性要求:

  • 假设key分配在节点A上,当有新节点N加入集群时,key会映射到节点A或节点N上,不会映射到其它节点;

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

  • 数据倾斜:如果节点的数量很少,可能会出现大部分key拥挤的分布在某个节点上的情况;
  • 缓存雪崩:当node1故障退出时,原来node1负责的key将由node2处理,意味着node2的压力会瞬间增大;若node2因为压力过大而崩溃,那么更大的压力将冲向node3,造成雪崩;

一致性hash引入虚拟节点解决了这一问题:

  • 一个实际节点映射为多个虚拟节点,这样hash空间会相对均匀;
  • 一个真实的节点退出,它原来承担的压力会均匀的分散到其它节点;

Open-falcon transfer中的一致性hash算法及其源码实现_第4张图片

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 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
}

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

你可能感兴趣的