Consistent Hash 一致性哈希算法¶
Keywords: Consistent Hash, Load Balancer, Scale
背景¶
负载均衡算法的功能主要是 “将流量均匀地或是按照算力加权依概率分配到 N 个负载上”. 而在实现上通常是对流量进行 hash, 然后使用负载均衡算法函数将 hash 结果映射到 N 个负载的序号上.
举例来说, 我们用 MD5 作为我们的 hash 函数, 计算得到一个整数, 然后对 N 取余数, 余数的结果就是负载的序号.
这个算法有一个致命的问题, 当需要增加或减少节点的时候, 由于除数 N 改变了, 所有的余数也会改变, 所以就不可避免的需要将数据从原来的负载迁徙到新的负载上. 如下图所示. 如果你目前已经有 K 个节点, 每增加一台机器, 你就需要迁徙 K / (K+1) 比例的数据. 一般的分布式系统为了保证稳定性起码要有 3 个节点, 那么每次增加节点就要迁徙至少 75% 的数据, 随着 K 的增加这个迁徙量会越来越多. 在数据迁徙期间, 负载节点如果继续提供服务, 则数据可能会出错. 所以常见的做法是在迁徙期间只允许读, 不允许写. 由于迁徙量很大, 这使得服务不可用的时间较长, 显然这是不可接受的.
于是, 1997 年 麻省理工大学提出了该算法, 用于解决这一问题
一致性哈希算法在分布式系统中应用广泛, 凡是可以通过添加机器扩容的系统大部分采用了 一致性哈希算法 进行负载均衡. 解决了增加和减少机器时, 由于数据迁徙带来的服务不可用的时间过长的问题.
一致性哈希算法¶
取一个 0 ~ 2 ^ 32 - 1 的整数环 M, 环上的数 12 点钟方向为 0, 数字沿着顺时针递增. 对 hash(id) 求 mod(2 ^ 32) = x. 将 M 平均划分为 N 段, N 为分布式节点数. 第 i 段的终点为 i * 2 ^ 32 / N. 对于负载 x 沿着顺时针方向寻找最近的一个终点, 该终点是第 i 段, 那么负载就放到第 i 个机器上进行.
如果需要增加节点, 就在这些 段 中找到最长的那个, 然后将其一分为二. 如果需要减少节点, 就在这些 段 中找到相邻的两个 段 的总长度最短的那个合二为一. 从下面第二个图到第三个图的变化可以看出 (从 3 个节点增加到 4 个节点), 总迁徙量为 25%, ( 1 / (K+1) )比之前的 75% 有了大幅改善.
引入了虚拟节点的一致性哈希算法¶
在上面的算法中, 只有那个被一分为二的段所对应的节点的负载被分流了, 另外的节点的负载并没有降低, 这样会导致负载不均衡. 也就是扩容后总会有的节点的负载是其他节点负载的 2 倍. 在生产环境中通常使用的是改进后的 引入了虚拟节点的一致性哈希算法.
这里我们引入一个虚拟节点系数 R, 例如 4. 也就是每一个物理节点会对应 4 个虚拟节点. 在增加和减少节点的时候, 算法和之前一样, 只不过每增加一个物理节点, 就要增加 4 个虚拟节点. 从概率上每次增加节点后虽然每个物理节点的流量不可能完全相等, 但是相差的比例并不会很大. 根据下图, 在 2 节点扩容 3 节点的时候有 10/32 和 12/32, 也就是一个节点比别的节点多 20% 的流量, 这个差距并不影响性能.
一致性哈希的 Python 实现¶
Python 社区的 Consistent Hash 的实现是 uhashring 这个包.
具体的用法可以参考 示例代码