一致性 Hash 算法 - JumpHash
google 提出了 Jump consistent hash 算法,跳转一致性哈希不需要存储,速度更快,并且在均匀划分 key 方面做得更好。它的主要限制是桶必须按顺序编号,这使得它 比分布式 Web 缓存更适合数据存储应用程序
算法说明
先令 f (key, n) 为一致性哈希算法,输出的为 [0,n) 之间的数字,代表数据在对应的节点上。
- n=1 时,对于任意的 key,输出应该都是 0。
- n=2 时,为了保持均匀,应该有 1/2 的结果保持为 0,1/2 的结果输出为 1。
- n=3 时,应该有 1/3 的结果保持为 0,1/3 的结果保持为 1,1/3 的结果保持为 2。
- 依次递推,节点数由 n 变为 n+1 时,f (key, n) 里面应该有 n/(n+1) 的结果不变,有 1/(n+1) 的结果变为 n。
这个使用概率公式来表示,就是这样的代码:
1 | int ch(int key, int num_buckets) { |
下面我们来演示下数据在扩容时的变化。
n=1 时,一定输出 0,即落到桶 0
n 扩容到 2 时,为了保持均匀,应该有 1/2 的结果保持为 0,1/2 的结果输出为 1。
n 扩容到 3 时,应该有 1/3 的结果保持为 0,1/3 的结果保持为 1,1/3 的结果保持为 2。
关键在于 n=2 到 n=3 的过程,每个数字的概率从 1/2 转化到了 1/3。
之后,我们可以得出一个规律:增加一个节点,数据不发生变化的概率是 n/(n+1) 再乘以之前每个数字的概率 1/n,就可以得出每个数字最新的概率 1/(n+1).
这个算法唯一的缺点是复杂度太高,是 O (n) 的。所以需要进行优化。
算法优化
在上一小节中,我们了解到 f (key, n) 算法的正确性。除了复杂度是 O (n) 外,我们还可以确定,循环越往后,结果改变的概率会越来越低。
结果改变指的是,增加一个节点后,一个固定的 key 输出的结果发生了改变。如果我们能够快速计算出这个固定的 key 在哪些节点下发生了改变,就可以快速计算出最终答案 (跳过这些不变 key)。
假设某一次结果是 b,经过若干次概率测试,下一次改变为 a,则从 b+1 到 a-1 这中间,不管节点如何变化,这个 key 的结果都是不会变化的。根据上一小节的到的概率变化公式,新增一个节点数字不变化的概率是 n/(n+1)。那从 b+1 到 i 不变化的概率就是 (b+1)/i(中间的抵消了)。
如果我们有一个均匀的随机函数 r,可以确定当 r<(b+1)/i 时 (触发了不变化的概率),f (i)=f (b+1)。
那么 i 的上界就是 (b+1)/r 向上取整。这个上限也是下一次 key 发生变化的节点数量。
1 | int ch(int key, int num_buckets) { |
现在来分析下它的时间复杂度。 因为 r 的分布是均匀的, 在槽位数将变化为 i 的时候跳跃发生的概率是 1/i, 那么预期的跳跃次数就是 1/2+…+1/i+…+1/n, 调和级数和自然对数的差是收敛到一个小数的, 所以复杂度是 .
考虑退出条件是 j >= num_buckets.j 每次大约是原来的 2 倍(由于 r 是均匀的,所以期望是 1/2),
j = floor((j + 1) * 2)
1 | // 7 = 0x0111 |
跳跃一致性哈希在执行速度、内存消耗、映射均匀性上都比经典的哈希环法要好。 这一点也可以理解, 跳跃一致性哈希的算法设计就是源于对均匀性的推理。关于内存消耗上的对比结果, 其实已然不言自明。 经典的一致性哈希环需要数据结构的支撑, 空间复杂度是 的, 而跳跃一致性哈希算法几乎没有额外内存消耗。一切看上去都很美好,但是,跳跃一致性哈希算法有两个显著缺点:
- 无法自定义槽位标号:跳跃一致性哈希算法中, 因为我们没有存储任何数据结构, 所以我们无法自定义槽位标号, 标号是从 0 开始数过来的。
- 只能在尾部增删节点:假如我们在非尾部添加一个新的槽位, 会导致这个位置后续的槽位的标号全部发生变化。 所以在非尾部插入新槽位没有意义, 我们只能在尾部插入。对于在非尾部删除一个槽位也是一样的,我们只能在尾部删除.
跳跃一致性哈希下的热扩容和容灾
新加一个全新的节点时, 必然要迁移数据才可以服务。 可以采用和一致性哈希环法类似的办法, 即数据备份 + 请求中继。
新加入的节点对于读取不到的数据,可以把请求中继 (relay) 到老节点,并把这个数据迁移过来。「老节点」是什么? 假如此次扩容时,节点数目由 n 变为 n+1,老节点的标号则可以由 ch (k,n) 计算得出, 即节点数量为 n 的时候的 k 的槽位标号。
当我们移除一个节点时(节点数目由 n+1 变为 n),会造成什么影响?如果是移除尾结点,和上面新增时的方法类似,通过计算出老节点 (老节点的标号则可以由 ch (k,n+1) 计算得出) 和数据备份即可。但是现实情况下,不可能保证异常节点就是尾结点,如果这种情况发生,我们该怎么办?
显然对于容灾,冗余是必不可少的,在执行数据写操作时,同时写一份数据到备份节点。 备份节点这样选定:
- 尾部节点备份一份数据到老节点。
- 非尾部节点备份一份数据到右侧邻居节点。
这样,当移除一个非尾部节点 i 时,通过请求中继和备份,我们仍可以正确请求值。
我们同样可以尝试虚拟节点 (影子节点) 的办法来做权重。增加一层虚拟桶,使用 jump consistent hash 来将 key 分配到虚拟桶中,然后在虚拟桶和实际桶之间建立一个映射关系。这样我们就可以通过映射关系来设置实际桶的权重;也可以在任意位置删除和添加实际桶,只需要维护好映射关系即可。当然,这样做的代价就是,算法本来可以的无内存占用的,现在需要有一块内存来维护映射关系了。
跳跃一致性哈希法最显著的特点是: 实现轻巧、快速、内存占用小、映射均匀、算法精妙。 但是,原始的跳跃一致性哈希算法的缺点也很明显,不支持自定义的槽位标号、而且只能在尾部增删槽位。在这个算法下做热扩容和容灾也是有路可循的, 但是不及哈希环直观。
算法实现
1 | /** |