程序员必须掌握的算法：一致性哈希算法

作者：MOOC

一致性哈希算法背景

一致性哈希算法是由Karger等人于19年从MIT Formula97 C发行版开发出来的，设计目的是解决互联网热点问题。初衷和CARP很相似。一致哈希修复了CARP使用的简单哈希算法带来的问题，使得DHT能够真正用于P2P环境中。

但是现在一致性哈希算法也广泛应用于分布式系统中。研究过memcached缓存数据库的人都知道，memcached服务器本身并不提供分布式缓存的一致性，而是客户端提供。具体来说，计算一致性哈希的步骤如下：

1. 首先，在memcached中找到服务器（节点）的哈希值，并将其配置在从0到232的循环（连续体）中。
2. 然后使用用同样的方法找到存储数据的键的哈希值，并映射到同一个圆。
3. 然后从数据映射的地方开始顺时针查找，并将数据保存到找到的第一个服务器上。如果超过232后找不到服务器，则保存到memcached中的第一台服务器。

从上面的状态将服务器添加到memcached中。由于存储密钥的服务器发生巨大变化，分布式算法的其余部分会影响缓存访问速度，但在一致散列中，只有从服务器添加到连续体的逆时针方向的第一台服务器上的密钥。会受到影响。 ，如下图：

一致的哈希属性

考虑到分布式系统中每个节点都可能发生故障，并且很可能动态添加新节点，如何保证当系统中节点数量发生变化时？值得考虑的是它仍然可以为外界提供良好的服务，尤其是在设计分布式平衡系统时。如果服务器出现故障，如果没有采用合适的算法来保证整个系统的一致性，那么就可能会出现系统中的缓存失效的情况（即系统的节点数减少，客户端请求对象时必须重新计算其哈希值（通常与系统中的节点数量有关）。由于哈希值发生了变化，很可能找不到存储该对象的服务器节点，因此一致性哈希是一个好的分布式cahce系统中的一致性哈希算法应该满足以下几个方面：

• Balance（平衡）

Balance意味着哈希结果可以尽可能的分布到所有的buffer中，这样所有的buffer空间都可以被分配到。许多哈希算法都满足这个条件。

• 单调性（Monotonicity）

单调性是指，如果某些内容已经通过哈希分配到相应的缓冲区，并且系统中添加了一个新的缓冲区，则哈希的结果应该能够保证原来分配的内容可以映射到新的缓冲区，而不会映射到旧的缓存集中的其他缓冲区。简单的 哈希 算法往往无法满足单调性要求，比如最简单的线性 哈希：x = (ax + b) mod (P)。上式中，P代表整个缓冲区的大小。不难看出，当缓冲区大小发生变化时（从P1变为P2），原来的哈希结果全部发生变化，从而无法满足单调性要求。哈希结果的变化意味着当缓冲区空间发生变化时，系统中所有的映射关系都需要更新。在P2P系统中，缓存的改变相当于一个peer加入或离开系统。这种情况在P2P系统中会经常发生，因此会带来巨大的计算和传输负载。单调性要求哈希的算法能够处理这种情况。

• 分散（Spread）

在分布式环境中，终端可能看不到所有缓存，而只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲区时，不同终端看到的缓冲区范围可能不同，导致哈希结果不一致。最终的结果是相同的内容被映射到不同的终端。在不同的保险杠中。这种情况当然应该避免，因为它会导致相同的内容存储在不同的缓冲区中，降低系统存储的效率。离散度定义为上述事件的严重程度。一个好的哈希算法应该能够尽可能的避免差异，即尽可能的减少方差。

• 加载

负载问题其实是换个角度看分散问题。由于不同的终端可能将相同的内容映射到不同的缓冲区，因此特定的缓冲区也可能被不同的用户映射到不同的内容。与分散一样，应该避免这种情况，因此好的哈希算法应该最大限度地减少缓冲区负载。

• 平滑度（Smoothness）

平滑度是指缓冲服务器数量的平滑变化与缓存对象的平滑变化一致。

原理

基本概念

一致性哈希算法最早在《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》文章中提出。简而言之，一贯的哈希将哈希价值观的整个空间组织成一个虚拟的环。例如，假设某个哈希函数H的值空间为0-2^32-1（即哈希值为一个32位无符号整数），则整个哈希空间环是这样的：

整个空间是顺时针排列的。方向 0 和 232-1 在零点处重合。

下一步是使用哈希在每台服务器上执行 哈希。具体来说，可以选择服务器的IP或主机名作为执行哈希的关键字，这样每台机器就可以确定自己在哈希环上的位置。这里假设上述四台服务器都使用哈希的IP地址，它们在循环空间中的位置如下：

接下来使用如下算法定位数据并访问对应的服务器：使用相同的Hash函数来计算数据密钥的哈希值并确定该数据在环上的位置。从这个位置开始，顺时针“走”一圈，遇到的第一个服务器就是他应该找到的服务器。

比如我们有四个数据对象，对象A、对象B、对象C、对象D，计算出哈希后，它们在环空间中的位置如下：

根据一致的哈希算法，数据A将被分配给节点A，B将被分配给节点B，C将被分配给节点C，D将被分配给节点D。

下面分析一致性哈希算法的容错性和可扩展性。现在我们假设节点 C 不幸宕机了。可以看到，此时对象A、B、D不会受到影响，只有对象C会被移动到节点D。一般来说，在一致的哈希算法中，如果某个服务器不可用，只有之前的服务器不可用。该服务器的受影响数据受到影响。圆形空间（即逆时针行走时遇到的第一个服务器）。服务器之间的数据），其他不会受到影响。

考虑下面的另一种情况。如果服务器是NodeX。一般来说，在一致哈希算法中，如果添加了一个服务器，只有新服务器环空间中的前一个服务器（即逆时针行走时遇到的第一个服务器）受到影响。服务器之间的数据），其他数据不会受到影响。

综上所述，一致性哈希算法只需要移动循环空间中的一小部分数据即可增加或减少节点，并且具有良好的容错性和可扩展性。

另外，当一致性哈希算法的服务节点过少时，很容易因节点分布不均匀而导致数据失真问题。例如，系统中只有两台服务器，环分布如下。

这个时候，大量的数据必然会集中在节点A，而只有极少量的数据会在节点B。为了解决这个数据失真的问题，哈希一致性算法引入了虚拟节点机制，即即，对于每个服务节点，计算多个王牌，计算结果的每个位置放置一个服务器节点，称为虚拟节点。具体方法可以通过在服务器IP或主机名后添加数字来实现。例如，在上述情况下，每个服务器可以计算出三个虚拟节点，因此“Node A#1”、“Node A#2”、“Node A#3”、“Node B#1”、“Node B “#2”和“Node B#3”哈希值，创建六个虚拟节点：

同时数据定位算法不变，只是多了一步从虚拟节点到真实节点的映射，比如如放入“三个虚拟节点“Node A#1”、“Node A#2”和“Node A#3”的数据都位于Node A中。这就解决了当服务节点较少时数据失真的问题实际应用中，虚拟节点的数量通常设置为32个甚至更多，这样即使服务节点数量很少，也能实现数据相对均匀的分布。