一致性哈希汇总-阿里云开发者社区

一致性哈希汇总

[TOC]

本文主要介绍如下一致性哈希算法：

Consistent Hashing Ring：published by D. Karger et al. in 1997
Rendezvous：published by Thaler and Ravishankar in 1996.
Jump：published by Lamping and Veach in 2014.
Multi-probe：published by Appleton and O’Reilly in 2015.
Maglev：published by D. E. Eisenbud in 2016.
Anchor：published by Gal Mendelson et al. in 2020.
Dx：published by Chaos Dong and Fang Wang in 2021.

分类

Ring hashing

Ring hashing是一种比较常用的一致性哈希算法，也被称为ketama。Ring hashing存在的一个问题是其负载并不均衡(主要是在节点增删的时候原节点的key会被映射到下一个节点上)，如果每个服务有100个虚拟节点，那么负载的标准差为10%，此时平均负载(总keys/服务数)的99%置信区间为(0.76, 1.28)。如果将每个服务的虚拟节点增加到1000，此时标准差将减低约3.2%，而99%的置信区间为(0.92, 1.09)。

ring hashing中可以通过增加个别服务的虚拟节点来增加其权重。

func (m *Map) Add(nodes ...string) {
   
    for _, n := range nodes {
   
        for i := 0; i < m.replicas; i++ {
   
            hash := int(m.hash([]byte(strconv.Itoa(i) + " " + n)))
            m.nodes = append(m.nodes, hash)
            m.hashMap[hash] = n
        }
    }
    sort.Ints(m.nodes)
}

func (m *Map) Get(key string) string {
   
    hash := int(m.hash([]byte(key)))
    idx := sort.Search(len(m.keys),
        func(i int) bool {
    return m.keys[i] >= hash }
    )
    if idx == len(m.keys) {
   
        idx = 0
    }
    return m.hashMap[m.keys[idx]]
}

Rendezvous Hashing

这一篇有对Rendezvous Hashing做过详细介绍。Rendezvous Hashing中每个key会对应一个有序的服务器列表，并选择第一个服务器作为目标服务器，如果第一服务器出现故障，则会选择第二服务器作为目标服务器。此外Rendezvous Hashing还支持通过权重来对服务器进行排序。

由于添加节点会打乱key的有序(从大到小或从小到大)服务器列表，因此Rendezvous Hashing只适用于包含少量节点的集群，并不适合节点添加的场景。

Jump Hash

jump Hash解决了ring hashing的两个缺点：它没有内存开销，且具有完美的key分布性(bucket的标准差为0.000000764%，99%置信区间为(0.99999998, 1.00000002)。

jump hash中的bucket就是节点的位置顺序。

jump Hash的算法如下，该算法使用key的哈希作为随机数生成器的种子，然后，使用随机数在bucket列表中"向前跳"，直到for循环结束，落入的最后一个bucket就是key所在的bucket。

func Hash(key uint64, numBuckets int) int32 {
   
  var b int64 = -1
  var j int64
  for j < int64(numBuckets) {
   
    b = j
    key = key*2862933555777941757 + 1
    j = int64(float64(b+1) *
      (float64(int64(1)<<31) / float64((key>>33)+1)))
  }
  return int32(b)
}

jump hash的缺点是它不能像ring hashing一样使用任意的节点名称，且节点必须是有序的(从上面算法中可以看到，jump中的节点并没有单独的节点ID，它只是个位置顺序值)，因此不支持在任意位置删除或添加节点，否则会完全打乱节点映射关系，只能在bucket范围内具有较高值的一端添加或删除节点(但这种有限制的添加删除其实际意义不大)，因此不适用于可能会出现节点故障的场景。可以使用的场景如数据存储应用，并依赖多副本保证可用性。

Multi-Probe 一致性哈希(MPCH)

Multi-Probe hash可以和ring hashing一样灵活调节节点大小，并降低了方差。MPCH中没有使用虚拟节点，但为了获得较好的均衡性，它需要对key进行多次哈希，影响了key的查询效率。

在查找key所在的节点时，会对key进行k次哈希，然后找到最近的节点。k决定了期望的方差，如果要达到峰均比为1.05(即负载最高的节点最多比平均负载高5%)，则k需要为21。下面给出了k为2和21时的峰均比。

MPCH和ring hashing的区别在于，前者对key进行了多次哈希，而后者相当于对node进行了多次哈希形成虚拟节点。

Maglev Hashing

Maglev Hashing确定key所在的节点槽(B0、B1、B2)的方式为entry[hash(k)%M]，其中entry为查找表，M为查找表的大小。查找表中填充了节点槽。下图中k的节点槽为B2。

为了构建查找表，首先需要为每个节点槽构建一个permutation序列。下图左侧给出了节点B0、B1、B2的permutation序列，序列长度为6，右侧给出了查询表。然后按照B0->B1->B2的顺序，并按照各个节点槽的permutation序列顺序将其填充到查询表中。

permutation序列的生成方式如下：

使用两个无关的哈希函数 h₁ 和 h₂，假设一个节点槽的名字是 b，先用这两个哈希函数算出一个 offset和 skip
$$ offset=h_1(b)\%M $$

$$ skip=h_2\%(M-1)+1 $$
分别对每个 j，计算出 permutation中的所有数字，即为节点槽b生成了一个permutation序列：
$$ permutation[j]=(offset+j×skip)\%M $$

Maglev Hashing在添加和删除节点槽时需要重新构建查询表，因此会对查询表造成干扰。在 Google 的实践过程中，一般选择 M(查找表大小)为一个大于 100×N(节点槽数目)的质数，这样各个槽位在查找表上的分布的差异就不会超过 1%。

此外由于Maglev Hashing无法在节点变动时做到最小化重映射，即在移除一个节点时，可能会导致同时导致其他节点槽的位置发生变化，破坏了Minimal Disruption属性，因此在数据迁移备份上会有一定困难。谷歌的论文中将该算法用于网络负载均衡等无状态场景。

AnchorHash

个人认为AnchorHash是对jump hash的一种改进。

假设有一个working set 𝒲，使用哈希函数H_𝒲 将keys映射到𝒲中。对于每个key，都有均等的几率选择𝒲中的每个成员，以此来达到均衡。

移除bucket

假设要移除一个bucket 𝘣 ∈ 𝒲，如果此时使用新的哈希函数𝘏_𝒲\b 将key映射到𝒲\𝘣中，则可能会跟原先使用𝘏_𝒲的映射冲突(对于相同key都映射到了𝒲\𝘣中的某个bucket)，造成重复映射，破坏了Minimal Disruption属性(指如果有节点被删除,应该只会影响到该节点)。

𝒲\𝘣表示集合𝒲中除去𝘣以外的元素

为了解决该问题，AnchorHash会在𝘏_𝒲(𝑘) ≠ 𝘣的情况下保持使用𝘏_𝒲(𝑘)，否则将使用𝘏_𝒲\b 将key映射到𝒲\𝘣中。例如，一个𝒲= {0, . . . , 6}，此时使用𝘏_{0,...,6}(𝑘)对key进行哈希。假设删除了删除了bucket 6，此时仍然使用𝘏_{0,...,6}(𝑘)进行哈希，如果哈希结果范围为 {0, . . . , 5}，则结束运算，否则使用𝘏_{0,...,5}(𝑘)进行重哈希。

通过这种方式保证了哈希的一致性，首先，只有映射到𝘣的keys才会被重哈希，减小了对哈希的影响，此外，不属于𝘣的keys会被均匀分布到𝒲\𝘣中，而属于b的keys也会通过重哈希均匀分布到𝒲\𝘣中

当移除多个buckets时，会重复上述步骤，通过多个哈希函数找到working set中的某个bucket。从下面例子中看到，删除位置会对哈希次数有影响(需要选择不同的集合空间)：

添加bucket

AnchorHash在添加bucket时会优先考虑将其回填到最后一个被移除的bucket中。假设最后一个被移除的bucket为 𝘣，且当前的working set为𝒲，当添加一个bucket时，会选择将其回填到bucket 𝘣的位置。

这种添加方式主要考虑到了AnchorHash的迭代方式，当将新的bucket回填到被移除的bucket 𝘣之后，AnchorHash的状态也被恢复到了移除bucket 𝘣之前，其查询的哈希也会相应减少。

实现

AnchorHash的实现如下。其中𝒜表示bucket的数目上限，𝓡表示一个栈空间，用于保存未使用的buckets(不在𝒲中的buckets，即除𝒲以外以及被移除的buckets)，𝒲_𝘣表示未使用的bucket。注意下面算法中仅针对bucket，不针对实际场景(如数据服务器在节点增删情况下的数据迁移)：

AnchorHash可以支持任意添加和删除节点，其节点数据的备份迁移也比较简单，即重新对key执行哈希即可。

AnchorHash的问题是，它需要对集群大小有所规划，这就限制了集群的上限，无法进行扩容。此外由于该算法是有状态的，因此无法对集群状态进行并行更新。

DxHash

DxHash结合了前面的几种算法的思想。例如，它像Anchor一样使用bit数组来标记节点是否工作，并利用类似Jump的伪随机生成器来确定目标bucket。

如下图所示，DxHash使用了一个数组，称为NSArray，表示节点在集群或网络中的状态，数组的长度为大于当前集群中活动的节点数的2的最小幂，如当前节点数为4，则NSArray长度为8(即2³)。每个节点对应数据中的一项。

下图a中描述了包含4个活动节点的集群，标记为0,1,2,3，对应数组中的白色框0,1,2,3，其他位置(灰色部分4,5,6,7)用于新节点或非活动节点。

查询

DxHash通过伪随机数生成器(PRNG)来将对象映射到节点上。PRNG是一种在给定范围内生成由伪随机数组成的无限序列的算法。生成的序列并不是完全随机的，它们由一个称为随机种子(random seed)的值确定的。PRNG同时具有随机性和可再现性，即生成的数字可以在整个范围内均匀随机地分布，且当种子相同时可以再次生成相同的序列。

通过将key的哈希值作为种子，PRNG可以为每个key生成唯一且可再现的随机数序列。通过对生成的随机序列取模(底为NSArray的长度)，就可以得到一个包含活动和非活动节点的节点ID序列，称为𝑆，使用𝑆[𝑖] 表示序列中的第𝑖个位置，key所在的节点位置为序列中的第一个活动节点。

上图a描述了在4个节点的集群中查询𝑘1和𝑘2的情况。对于𝑘1，其生成𝑆为1,4,5,2，由于第一个活动节点的序列为1，则𝑘1映射到节点1，对于𝑘2，其生成𝑆为6,4,7,3，第一个活动节点的序列为3，则𝑘2映射到节点3。

更新

NSArray的长度通常要大于集群的大小。当新增一个节点时，会分片一个非激活的节点ID。图b中新增了一个节点4，并更新了NSArray，同时这种变更使得𝑘2映射的节点ID从3变为了4。

DxHash在移除节点时，会将其在NSArray中对应的项变为非活动状态。图c中移除了节点1，NSArray中的节点1对应的项变为了非活动状态，同时𝑘1映射的节点ID从1变为了4。

DxHash的代码实现中，查询key所在的节点的实现如下：

uint32_t DxHash::getNodeID(uint32_t key, uint32_t* numHash){
    uint32_t key2 = gen32bitRandNumber(key);     //通过key生成一个随机种子key2
    uint32_t bs = crc32c_sse42_u64(key, key2); //通过key和种子生成第一个序列
    uint32_t index = bs % size;                   //通过对序列取模获取节点的索引
    uint32_t i = 1;       //将初始的哈希次数设置为1
    while(!nodes[index]){ //查询index所在的节点是否是活动节点，如果是，则返回该节点索引，否则继续重复上述操作
        bs = crc32c_sse42_u64(bs, key2); //再次生成序列取模
        index = bs % size;
        i += 1;             //每查找一次，增加哈希计数
        if (i >= 4 * size){ //查找次数达到上限，查找失败，返回错误
            return -1;
        }
    };
    *numHash = i;         //出参numHash表示总的哈希次数
    return index;         //返回节点索引
}

在查询中，有一个查询上限i >= 4 * size，该限制出自论文的3.4 Boundary cases章节，是在查询效率和匹配结果上做出的一个折衷方案，当n足够大时，𝕡的值接近1/e⁸，即只有0.03%会受到边界的影响。
$$ 𝕡=(\frac{n-1}n)^{8n} $$
扩容

当NSArray满且需要添加一个新的节点时，会执行扩容，此时DxHash将NSArray的大小增加一倍，并将新增项设置为非活动状态。

缩容

缩容会带来比扩容更多的重映射。建议只有在active_nodes_number/NSArray_length的比率接近1%才考虑缩容。

Tips

DxHash存在查找边界问题，即如果集群较小的情况下，可能会出现无法为key找到活动节点的问题。
尽管DxHash支持扩缩容，但仍然建议初始化时使用足够大的NSArray，避免对象重映射带来的迁移问题。

算法复杂度

𝑉：ring中每个物理节点对应的虚拟节点个数
𝑊：集群中的working节点数目
𝑃：Multi-probe中的探针(哈希)个数
𝑀：Maglev中每个节点在查询表中的位置数
𝐴：集群中的所有节点数(包括working和非working的节点)

Benchmark

Benchmark1

来自Consistently Faster: A survey and fair comparison of consistent hashing algorithms

内存使用

可以看到Ring和Maglev使用的内存了最大，原因是Ring为每个物理创建了1000个虚拟节点，而Maglev创建的查询表是节点数的100倍。虽然Maglev是内存使用量第二大的算法，但仍然比Ring小100倍。

jump使用的内存最少，为常数。Multi-probe, Rendezvous和 Anchor内存使用量处于中间位置，Dx则优于这三种算法。

初始化时间

初始化主要用于作节点映射。初始化性能最好的是Rendezvous 和 Jump。Ring仍然是最慢的，它需要创建𝑉 * 𝑊个虚拟节点。

查询时间

查询key所在的节点。在下图(a)中可以看出，Rendezvous是最慢的，它需要为key生成一个节点列表，然后才能找出最佳的节点，查询效率和working节点数呈线性关系。

在Multi-probe中，使用了21个探针，算法复杂度为𝑂(21𝑙𝑜𝑔₂(𝑊)).；在Ring中，使得𝑉=1000，算法复杂度为𝑂(𝑙𝑜𝑔₂(1000𝑊)) 。

Anchor的复杂度为𝑂(𝑙𝑛(𝐴/𝑊)) ，Dx的复杂度为 𝑂(𝐴/𝑊)，因此当𝑊远小于𝐴时，会对这两个算法性能造成影响。在图(b)中创建了10000个节点的集群，并测算了移除从10%到90%节点下的算法性能。可以看到Dx受影响最大。

调整集群大小

指添加或删除bucket时算法更新数据结构的时间。这里测算了添加和移除初始集群下10%到50%的buckets的场景，并计算了所使用的平均时间。除Maglev外的算法都支持同时删除多个buckets。下面展示了添加或删除单个bucket的性能。

可以看到，Maglev的性能是最差的，因为每个集群大小变更时，都需要重新构建查询表。第二差的是Ring，在添加或删除特定的物理节点时，需要同时处理对应的虚拟节点。jump是最快的，Anchor, Dx和 Rendezvous 稍慢，但仍然是常数时间。Multi-probe维护了有序的节点列表，resize下的复杂度为𝑂(𝑙𝑜𝑔₂(𝑊))。

均衡性

即每个key都有均等的概率映射到各个节点上，从而在节点之间达到负载均衡。

这里对三种分布情况进行了测试：

均匀(keys已经均匀分布的最佳情况)
正常(keys按照高斯曲线分布的平均情况)
集群(keys集中在某些区间而其他区域为空的最坏情况)。

在最佳和平均情况下，除Multi-probe外的算法的均衡性都很好，而Multi-probe则似乎完全忽略了某些节点。

下图展示了在最坏场景下的分布情况(约接近100%越好)。可以看到Anchor, Dx和 Jump表现了很好的均衡性，而y, Rendezvous, Ring和 Maglev随着集群的增大而逐渐丧失了均衡性。可以看到，Rendezvous即使在较小集群下，其均衡性也不佳，而Multi-probe的均衡性是最差的。

此外还对随机增删节点下的场景进行了验证，发现，对集群大小的调整并不影响所选择的算法的均衡性。

单调性

单调性，即当删除或新增一个节点时，只会将该节点的对象重映射到其他节点(删除节点)，或者其他节点的对象重映射到该节点(新增节点)。该属性用于避免不必要的对象重映射。

测试结果表明所有的算法都具有单调性(具体区别可以参考下面的Benchmark2)

结论

从下面可以看到表项最佳的是Anchor, Dx和 Jump，下面展示了这三种算法的性能对比。

下面给出了所有算法的性能排名，其中jump算法由于无法支持任意位置的节点增删，限制了其使用场景：

Benchmark2

来自DxHash

忽略SACH算法

各个哈希的比较维度：

Balance：均衡性
Monotonicity：单调性
Statelessness：无状态，即哈希算法不会受历史操作(如查询、节点删除或添加)的影响。无状态减少了分布式环境中操作顺序带来的开销。
Lookup throughput：查询吞吐量，衡量对象映射到节点的速率，作为衡量CH算法的核心性能指标。
Update overhead：更新开销，值节点状态变更带来的开销，如节点故障/恢复或集群扩容/缩容。理想的CH算法可以快速响应状态变更。
Memory footprint：内存占用，即CH算法所需的内存量。较小的内存占用可以减少费用，并避免大量内存带来的性能降级问题。

① Maglev 和 DxHash 在移除节点时是无状态的，且节点移除的顺序不会影响算法的查询结果

② Karger Ring通过引入虚拟节点来达到均衡性，Karger Ring中的𝑐表示每个物理节点的虚拟节点数，𝑛表示物理节点数

③ Maglev 中的𝓂表示查询表长度，𝓂的值建议不小于100𝑛

④ JCH 仅允许移除最后一个插入的节点，其更新受限

⑤ 略

⑥ 𝑛表示集群大小的上限，𝑎表示活动节点数

⑦ AnchorHash 的上限是不可变的，而 DxHash 可以通过扩容操作将上限加倍。

⑧ DxHash的更新操作中的复杂度和内存用量取决于具体的实现

策略

副本

一致性哈希使用副本机制来为特定的key选择备用节点，用于规避节点故障，或用于降低查询中的尾部延迟。

有些算法可以直接选择多个节点作为备用节点。如ring hashing可以使用哈希环的下一个节点，Multi-Probe则选择下一个最近的节点，Rendezvous选择有序服务器列表中的第二服务器等。

权重

不同的算法有不同的权重实现方式。ring hashing中可以通过增加虚拟节点的方式来做加权；jump Hash 和Multi-Probe中可以通过增加原始节点的影子节点来做加权；Maglev hash可以通过改变槽位间填查询表的相对频率来做加权；DxHash通过增加权重值来做加权。

负载均衡

除Maglev算法外还有如下几种支持负载均衡的一致性哈希算法：

Bounded Loads：主要思路是，根据当前负载情况对所有节点限制一个最大负载，在一致性哈希中对 hash 环进行查找时将跳过达到最大负载限制的节点，通过把过载的请求转移到其他节点上来解决热点和不均衡问题：
- R: 当前所有节点的总负载（正在处理的总请求数）
- T: 节点总个数
- L: 当前所有节点的平均负载，L = R/T
- ε: 一个参数用于表示在平均负载的基础上能够承受的额外负载上限，可以按照实际需求进行设置(根据 vimeo 分享的经验这个值推荐设置为 0.25~1)
- M: 节点的最大负载上限，M = L*(1+ε) = R*(1+ε)/T
  
  一致性哈希中进行节点查找时，增加检查匹配的节点的负载(正在处理的请求数)是否达到负载上限 M 的操作，如果是，则跳过当前节点继续往后查找。
这种算法存在级联溢出，即在存放一个key时可能会跳过多个满载的节点。Revisiting Consistent Hashing with Bounded Loads一文中通过随机跳跃的方式解决该问题。
deterministic subsetting：有点像jump hash，该算法要求给所有服务分配连续ID。

一致性哈希汇总