乐趣区

图解一致性hash算法和实现

jiezi

更多内容，欢迎关注微信公众号：全菜工程师小辉。公众号回复关键词，领取免费学习资料。

一致性 hash 算法是什么？

一致性 hash 算法，是麻省理工学院 1997 年提出的一种算法，目前主要应用于分布式缓存当中。
一致性 hash 算法可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。
在 Memcached、Key-Value Store、Bittorrent DHT、LVS 中都采用了一致性 hash 算法，可以说一致性 hash 算法是分布式系统负载均衡的首选算法。

传统 hash 算法的弊端

常用的算法是对 hash 结果取余数 (hash() mod N)：对机器编号从 0 到 N -1，按照自定义的 hash 算法，对每个请求的 hash 值按 N 取模，得到余数 i，然后将请求分发到编号为 i 的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将宕掉的服务器使用算法去除，此时候会有 (N-1)/ N 的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有 N /(N+1) 的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。

传统求余做负载均衡算法，缓存节点数由 3 个变成 4 个，缓存不命中率为 75%。计算方法：穷举 hash 值为 1 -12 的 12 个数字分别对 3 和 4 取模，然后比较发现只有前 3 个缓存节点对应结果和之前相同，所以有 75% 的节点缓存会失效，可能会引起缓存雪崩。

一致性 hash 算法

  1. 首先，我们将 hash 算法的值域映射成一个具有 2 32 次方个桶的空间中，即 0~（232）- 1 的数字空间。现在我们可以将这些数字头尾相连，组合成一个闭合的环形。
  2. 每一个缓存 key 都可以通过 Hash 算法转化为一个 32 位的二进制数，也就对应着环形空间的某一个缓存区。我们把所有的缓存 key 映射到环形空间的不同位置。
  3. 我们的每一个缓存节点也遵循同样的 Hash 算法，比如利用 IP 或者主机名做 Hash，映射到环形空间当中，如下图

  1. 如何让 key 和缓存节点对应起来呢？很简单，每一个 key 的顺时针方向最近节点，就是 key 所归属的缓存节点。所以图中 key1 存储于 node1，key2，key3 存储于 node2，key4 存储于 node3。

  1. 当缓存的节点有增加或删除的时候，一致性哈希的优势就显现出来了。让我们来看看实现的细节：
  • 增加节点

当缓存集群的节点有所增加的时候，整个环形空间的映射仍然会保持一致性哈希的顺时针规则，所以有一小部分 key 的归属会受到影响。

有哪些 key 会受到影响呢？图中加入了新节点 node4，处于 node1 和 node2 之间，按照顺时针规则，从 node1 到 node4 之间的缓存不再归属于 node2，而是归属于新节点 node4。因此受影响的 key 只有 key2。

最终把 key2 的缓存数据从 node2 迁移到 node4，就形成了新的符合一致性哈希规则的缓存结构。

  • 删除节点

当缓存集群的节点需要删除的时候（比如节点挂掉），整个环形空间的映射同样会保持一致性哈希的顺时针规则，同样有一小部分 key 的归属会受到影响。

有哪些 key 会受到影响呢？图中删除了原节点 node3，按照顺时针规则，原本 node3 所拥有的缓存数据就需要“托付”给 node3 的顺时针后继节点 node1。因此受影响的 key 只有 key4。

最终把 key4 的缓存数据从 node3 迁移到 node1，就形成了新的符合一致性哈希规则的缓存结构。

说明：这里所说的迁移并不是直接的数据迁移，而是在查找时去找顺时针的后继节点，因缓存未命中而刷新缓存。

计算方法：假设节点 hash 散列均匀（由于 hash 是散列表，所以并不是很理想），采用一致性 hash 算法，缓存节点从 3 个增加到 4 个时，会有 0 -33% 的缓存失效，此外新增节点不会环节所有原有节点的压力。

一致性 hash 算法的结果相比传统 hash 求余算法已经进步很多，但可不可以改进一下呢？或者如果出现分布不均匀的情况怎么办？比如下图这样，按顺时针规则，所有的 key 都归属于统一个节点。

一致性 hash 算法 + 虚拟节点

为了优化这种节点太少而产生的不均衡情况。一致性哈希算法引入了 虚拟节点 的概念。
所谓虚拟节点，就是基于原来的物理节点映射出 N 个子节点，最后把所有的子节点映射到环形空间上。

虚拟节点越多，分布越均匀。使用一致性 hash 算法 + 虚拟节点这种情况下，缓存节点从 3 个变成 4 个，缓存失效率为 25%，而且每个节点都平均的承担了压力。

一致性 hash 算法 + 虚拟节点的实现

原理理解了，实现并不难，主要是一些细节：

  1. hash 算法的选择。Java 代码不要使用 hashcode 函数，这个函数结果不够散列，而且会有负值需要处理。

这种计算 Hash 值的算法有很多，比如 CRC32_HASH、FNV1_32_HASH、KETAMA_HASH 等，其中 KETAMA_HASH 是默认的 MemCache 推荐的一致性 Hash 算法，用别的 Hash 算法也可以，比如 FNV1_32_HASH 算法的计算效率就会高一些。

  1. 数据结构的选择。根据算法原理，我们的算法有几个要求：
  • 要能根据 hash 值排序存储
  • 排序存储要被快速查找（List 不行）
  • 排序查找还要能方便变更（Array 不行）

另外，由于二叉树可能极度不平衡。所以采用红黑树是最稳妥的实现方法。Java 中直接使用 TreeMap 即可。

更多内容，欢迎关注微信公众号：全菜工程师小辉。公众号回复关键词，领取免费学习资料。

退出移动版