如何理解一致性hash算法和实现

本文是关于如何理解一致哈希算法及其实现。边肖觉得很实用，所以分享给大家学习。希望你看完这篇文章能有所收获。让我们和边肖一起看看。

一致性hash算法是什么？

一致性哈希算法是MIT于1997年提出的一种算法，目前主要用于分布式缓存。

一致性哈希算法可以有效解决分布式存储结构中动态添加和删除节点带来的问题。

在Memcached、键值存储、Bittorrent DHT和LVS中使用了一致的哈希算法。可以说，一致性哈希算法是分布式系统负载均衡的首选算法。

00-1010常用的算法是取哈希结果的余数(hash() mod N):对于编号从0到N-1的机器，根据用户自定义的哈希算法，将每个请求的哈希值取N的模得到余数I，然后将请求分发到编号为I的机器上，但是这种算法有一个致命的问题。如果某台机器发生故障，应该落在这台机器上的请求将无法正确处理。此时需要使用算法移除掉的服务器，需要重新计算(N-1)/N个服务器的缓存数据。如果添加新机器，则需要重新计算N/(N+1)台服务器的缓存数据。对于系统来说，这通常是一个不可接受的冲击(因为这意味着大量缓存出现故障或需要传输数据)。

在传统的负载均衡算法中，缓存节点数量从3个变为4个，缓存未命中率为75%。计算方法：将哈希值为1-12的12个数字分别枚举到模3和模4，然后对比发现只有前三个缓存节点的对应结果和之前一样，所以75%的节点缓存会失效，可能会造成缓存雪崩。

传统hash算法的弊端

首先，我们把hash算法的范围映射到一个232桶到幂的空间，也就是0~(232)-1的数字空间。现在我们可以把这些数字首尾相连，组合成一个闭环。

每个缓存键都可以通过Hash算法转换成32位二进制数，对应环形空间中的一个缓存区。我们将所有缓存键映射到环形空间中的不同位置。

我们的每个缓存节点也遵循相同的哈希算法，例如，使用IP或主机名作为哈希，并将其映射到环形空间，如下图所示。

如何让密钥对应缓存节点？很简单，每个键最近的顺时针节点是该键所属的缓存节点。因此，在图中，key1存储在node1，key2，key3存储在node2，key4存储在node3。

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

添加节点

当缓存簇中的节点数量增加时，整个环形空间的映射仍然会保持一致哈希的顺时针规则，因此会影响少量键的归属。

哪些按键会受到影响？在图中，在节点1和节点2之间添加了一个新节点node4。根据顺时针规则，从节点1到节点4的缓存不再属于节点2，而是属于新节点node4。因此，只有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算法的计算效率就会高一些。

2. 数据结构的选择。根据算法原理，我们的算法有几个要求：

• 要能根据hash值排序存储

• 排序存储要被快速查找 （List不行）

• 排序查找还要能方便变更 （Array不行）

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

以上就是如何理解一致性hash算法和实现，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注行业资讯频道。