一致性哈希算法的原理,哈希一致性算法的作用

　　一致哈希算法的背景一致哈希算法是由MIT的Karger等人在1997年为解决分布式缓存而提出的。它的设计目标是解决互联网中的热点问题，初衷和鲤鱼很像。一致性哈希纠正了CARP使用的简单哈希算法带来的问题，使DHT能够真正应用于P2P环境。

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

　　1.首先获取memcached服务器(节点)的哈希值，配置在0 ~ 232的圆(连续统)上。

　　2.然后用同样的方法得到存储数据的键的哈希值，映射到同一个圆。

　　3.然后从数据映射的位置开始顺时针搜索，并将数据保存到找到的第一个服务器。如果超过232次后找不到服务器，它将被保存到第一个memcached服务器。

　　从上图中的状态添加一个memcached服务器。分布式余数算法会因持有密钥的服务器发生巨大变化而影响缓存命中率，但在一致哈希中，只有连续体上服务器添加位置逆时针方向第一个服务器上的密钥会受到影响，如下图所示：

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

　　Balance Balance Balance是指哈希结果可以尽可能的分布到所有的缓冲区，这样所有的缓冲区空间都可以被利用。很多哈希算法都可以满足这个条件。

　　单调性单调性是指如果已经通过哈希将一些内容分配到了相应的缓冲区，并且向系统中添加了新的缓冲区，那么哈希的结果应该能够保证原来分配的内容能够映射到新的缓冲区，而不能映射到旧缓冲区集中的其他缓冲区。简单的哈希算法往往不能满足单调性要求，比如最简单的线性哈希：x=(ax b) mod (P)。在上面的公式中，p代表所有缓冲区的大小。不难看出，当缓冲区大小发生变化时(从P1到P2)，所有原始哈希结果都会发生变化，从而不满足单调性要求。哈希结果的变化意味着当缓冲区空间发生变化时，系统中所有的映射关系都需要更新。但是在P2P系统中，缓冲区的变化相当于对等节点加入或退出系统，这在P2P系统中会经常发生，因此会带来很大的计算和传输负载。单调性意味着哈希算法应该能够处理这种情况。

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

　　负载(Load)负载的问题其实就是换个角度看色散的问题。由于不同的终端可以将相同的内容映射到不同的缓冲器，所以不同的用户也可以将特定的缓冲器映射到不同的内容。和分散一样，这种情况是应该避免的，所以好的哈希算法应该能够尽可能的减少缓冲负载。

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

　　原理一致性散列算法的基本概念首先在论文《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》中提出。简单来说，一致性哈希将整个哈希空间组织成一个虚拟的圆圈。例如，假设一个hash函数H的值空间是0-2 SUP32/SUP-1(即hash值是一个32位无符号整数)，整个hash空间循环如下：

　　整个空间按顺时针方向组织。0sp32/sup-1方向在零点重合。

　　在下一步中，将使用hash对每个服务器进行哈希处理。具体来说，可以选择服务器的ip或主机名作为哈希的关键字，这样每台机器都可以确定自己在哈希环上的位置。这里，假设使用ip地址哈希后，四个服务器在环空间中的位置如下：

　　接下来用下面的算法定位数据，访问对应的服务器：用同一个函数hash计算数据键的Hash值，确定这个数据在环上的位置。从这个位置开始，它沿着环顺时针“行走”，遇到的第一个服务器就是它应该定位的服务器。

　　例如，我们有四个数据对象，对象A、对象B、对象C和对象d。经过哈希计算后，它们在环空间中的位置如下：

　　根据一致性哈希算法，数据A将位于节点A，B位于节点B，C位于节点C，D位于节点D。

　　下面分析一致性哈希算法的容错性和可扩展性。现在假设节点C不幸宕机，可以看到此时对象A、B、D不会受到影响，只有C对象会被重定位到节点D，一般在一致哈希算法中，如果一个服务器不可用，受影响的数据只是该服务器到其环空间中前一个服务器的数据(即逆时针行走时遇到的第一个服务器)，其他的不会受到影响。

　　考虑下面的另一种情况，如果服务器节点X被添加到系统中，如下图所示：

　　此时，对象A、B、D不受影响，只有对象C需要重定位到新的节点x，一般在一致哈希算法中，如果增加一个服务器，受影响的数据只是其环空间中新服务器与前一个服务器之间的数据(即逆时针行走时遇到的第一个服务器)，其他数据不会受到影响。

　　综上所述，一致性哈希算法对于节点的增加或减少只需要在环空间中重新定位一小部分数据，因此具有良好的容错性和可扩展性。

　　此外，当一致性哈希算法中的服务节点太少时，容易因为节点划分不均匀而造成数据倾斜的问题。例如，系统中只有两台服务器，它们的环分布如下。

　　这个时候大量的数据会集中在节点A上，而只有少量的数据会位于节点b上，为了解决数据偏斜的问题，一致哈希算法引入了虚拟节点机制，即对每个服务节点计算多个哈希，每个计算结果位置放置一个服务节点，称为虚拟节点。具体方法可以通过在服务器的ip或主机名后面加一个数字来实现。例如，在上述情况下，每个服务器可以计算三个虚拟节点，因此可以分别计算节点A#1、节点A#2、节点A#3、节点B#1、节点B#2和节点B#3的哈希值，从而形成六个虚拟节点：

　　同时，数据定位算法保持不变，只增加了一步虚拟节点到实际节点的映射。例如，定位到三个虚拟节点(节点A#1、节点A#2和节点A#3)的数据位于节点A上。这解决了当服务节点很少时的数据倾斜问题。在实际应用中，虚拟节点的数量通常设置为32个甚至更多，因此即使很少的服务节点也可以实现相对均匀的数据分布。

　　参考：

　　https://www.cnblogs.com/lpfuture/p/5796398.html

　　版权归作者所有：原创作品来自博主肖波，转载请联系作者取得授权，否则将追究法律责任。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。