乐趣区

关于监控工具:Openfalcon-transfer中的一致性hash算法及其源码实现

jiezi

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=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…

退出移动版