See also Hash

Algorithm/Consistent Hashing

一致性哈希是一种特殊的哈希算法。在使用一致哈希算法后,哈希表槽位数(大小)的改变平均只需要对 K / n {\displaystyle K/n} K/n 个关键字重新映射,其中 K {\displaystyle K} K是关键字的数量, n {\displaystyle n} n是槽位数量。然而在传统的哈希表中,添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

1. 历史

一致哈希由MIT的Karger及其合作者提出,现在这一思想已经扩展到其它领域。在这篇1997年发表的学术论文中介绍了“一致哈希”如何应用于用户易变的分布式Web服务中。哈希表中的每一个代表分布式系统中一个节点,在系统添加或删除节点只需要移动 K / n {\displaystyle K/n} K/n项。

一致哈希也可用于实现健壮缓存来减少大型Web应用中系统部分失效带来的负面影响。

一致哈希的概念还被应用于分布式散列表(DHT)的设计。DHT使用一致哈希来划分分布式系统的节点。所有关键字都可以通过一个连接所有节点的覆盖网络高效地定位到某个节点。

2. 需求

在使用n台缓存服务器时,一种常用的负载均衡方式是,对资源o的请求使用 hash ( o ) = o mod n 来映射到某一台缓存服务器。当增加或减少一台缓存服务器时这种方式可能会改变所有资源对应的hash值,也就是所有的缓存都失效了,这会使得缓存服务器大量集中地向原始内容服务器更新缓存。因此需要一致哈希算法来避免这样的问题。 一致哈希尽可能使同一个资源映射到同一台缓存服务器。这种方式要求增加一台缓存服务器时,新的服务器尽量分担存储其他所有服务器的缓存资源。减少一台缓存服务器时,其他所有服务器也可以尽量分担存储它的缓存资源。 一致哈希算法的主要思想是将每个缓存服务器与一个或多个哈希值域区间关联起来,其中区间边界通过计算缓存服务器对应的哈希值来决定。(定义区间的哈希函数不一定和计算缓存服务器哈希值的函数相同,但是两个函数的返回值的范围需要匹配。)如果一个缓存服务器被移除,则它所对应的区间会被并入到邻近的区间,其他的缓存服务器不需要任何改变。

3. 实现

一致哈希将每个对象映射到圆环边上的一个点,系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时,需要用一致哈希算法计算得到对象对应圆环边上位置,沿着圆环边上查找直到遇到某个节点机器,这台机器即为对象应该保存的位置。 当删除一台节点机器时,这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时,这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。

3.1. Hash space

一致性hash算法通过一个叫作一致性hash空间的数据结构实现。这个空间是一个环形结构,起点是0,终点是232 - 1,并且起点与终点连接,环的中间的整数按逆时针分布,故这个环的整数分布范围是[0, 232-1]。

circle.jpg

3.2. Map object into hash space

hash(object1) = key1;
.....
hash(object4) = key4;

object.jpg

3.3. Map the cache into hash space

hash(cache A) = key A;
....
hash(cache C) = key C;

将对象和缓存都按照一样的hash算法映射到一个0~2^32的环形空间中:4 个对象和 3 个缓存

cache.jpg

3.4. Map objects into cache

现在所有的缓存和对象都散列到同一个空间中,因此我们可以确定如何将对象映射到缓存中。以对象obj为例,从obj所在的位置开始,顺时针方向旋转,直到找到服务器。如果服务器坏了,你就去下一个服务器,等等。参见上一张图。

例如,将object1缓存到缓存A中;object2和object3将被缓存到缓存C中,而object4将被缓存到缓存B中。

3.5. Add or remove cache

现在考虑这两种情况,缓存关闭并删除;添加了一个新的缓存。

如果缓存B被移除,那么只有缓存在B中的对象会被重新散列并移动到C;在示例中,请参见下图所示的object4。

如果添加了一个新的缓存D,并且在环中的object2和object3之间散列了D,那么只会重新散列D和B之间的对象;在示例中,请参见object2,如下图所示。

3.6. Virtual nodes

如果没有部署足够的缓存,在缓存之间可能会有非常不均匀的对象分布。解决方案是引入“虚拟节点”的概念。

虚拟节点是圆内缓存点的复制品,每个真实缓存对应圆内的多个虚拟节点;当我们添加缓存时,实际上,我们在圈中为它创建了一些虚拟节点;当一个缓存被移除时,我们将它的所有虚拟节点从圆圈中移除。

考虑上面的例子。系统中有两个缓存A和C,现在我们引入虚拟节点,副本为2,那么一共就是4个虚拟节点。缓存A1和缓存A2表示缓存A;缓存C1和缓存C2表示缓存C,如下图所示。

那么,对象到虚拟节点的映射为:

当获得虚拟节点时,也就获得了缓存,如上图所示。

object1和object2被缓存到缓存A中,object3和object4被缓存到缓存中。结果现在更加平衡了。

4. Reference


CategoryAlgorithm

MainWiki: Consistent_Hashing (last edited 2015-02-02 05:17:53 by twotwo)