一致性hash算法详解

技术  /  管理员 发布于 1年前   514

一致性hash算法介绍详解

一致性hash算法缘起

一致性哈希算法在1997年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hot spot)问题，初衷和CARP十分类似。一致性哈希修正了CARP使用的简 单哈希算法带来的问题，使得分布式哈希（DHT）可以在P2P环境中真正得到应用。 

一致性hash算法提出了在动态变化的Cache环境中，判定哈希算法好坏的四个定义：

1. 平衡性(Balance)：
平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。
2. 单调性(Monotonicity)：
单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。 
3. 分散性(Spread)：
在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。 
4. 负载(Load)：
负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的hash(object)%N算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。

一致性hash算法介绍

一致性哈希是一种特殊的哈希方式。传统的哈希方式在当节点数目发生变化时，会引起大量的数据迁移，而使用一致性哈希则不会产生这种问题。一致性哈希最早是一个分布式缓存（Distributed Caching）系统的放置算法（现在很热门的Memcached就用的是一致性哈希）。但是现在它已经被广泛应用到了其它各个领域。对于任何一个哈希函数，其输出值都有一个取值范围，我们可以将这个取值区间画成一个环，如下图所示： 

通过哈希函数，每个节点都会被分配到环上的一个位置，每个键值也会被映射到环上的一个位置。这个键值最终被放置在距离该它的位置最近的，且位置编号大于等于该值的节点上面，即放置到顺时针的下一个节点上面。下图形象的表示了这种放置方案，其中Node 0上面放置Range 0上面的数据，以此类推。 

由于采用的哈希函数通常是与输入无关的均匀函数，因此当键值和节点都非常的多的时候，一致性哈希可以达到很好的分布式均匀性。并且由于特殊的放置规则，一致性哈希在节点数据发生变动时可以将影响控制在局部区间内，从而保证非常少的数据迁移（接近理论上的最小值）。当增加一个节点时，只有这个节点所在的区间内的数据需要被重新划分，如下图中，只需要将range 2上面的数据会从node 1中迁移到node 3上面。当删除一个节点时，只需要将这个节点上面的数据迁移到下一个节点上面，比如删除node 3，只把range 2上面的数据迁移到node 1上面就可以并，而其它的数据是不需要迁移变动的。

一致性哈希有非常广泛的应用，Key-Value系统，文档数据库或者分布式关系数据库都可以使用。Amazon的NoSQL系统Dynamo应用采用的就是一种改进的一致性哈希算法。在这个系统中又引入了虚拟节点的概念，使得这个算法的load balance更加的好，并且同时考虑了复制技术。环上的点就变成了虚拟节点，然后再采用其它的方式将这些虚拟节点映射到实际的物理节点上面去。这使得系统有很好的可扩展性和可用性。