一致性 hash 算法( consistent hashing )

consistent hashing 算法早在 1997 年即使以论文 Consistent hashing and random
trees 
饱受于提出,目前于 cache 系统遭到利用更加广阔;

1 基本状况

遵照您发出 N 个 cache 服务器(后面简称 cache ),那么哪些拿一个对象 object 映射到 N 个 cache 上为,你非常可能会见动用类似下面的通用方算 object 的 hash 值,然后都匀的映照到到 N 个 cache ;

hash(object)%N

周还运行正常化,再考虑如下的片种植状态;

1 一个 cache 服务器 m
down 掉了(在实际用被须要考虑这种状况),这样有着映射到 cache m 的对象还见面失效,怎么处置,需要将 cache m 从 cache 中移除,这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ;

2 由于看加重,需要丰富 cache ,这时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;

1 和 2 意味着什么?这代表突然之间几乎所有的 cache 都失效了。对于服务器而言,这是均等集市灾难,洪水般的访问都见面一直冲向后台服务器;

再次来考虑第三单问题,由于硬件能力更强,你或许想为后面长的节点多开点在,显然上面的 hash 算法也举行不至。

  有啊点子好变动这情景也,这即是 consistent hashing…

2 hash 算法和单调性

   Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:

  单调性是依如果既生一部分内容通过哈希分派到了相应的休息冲面临,又产生新的缓冲在到系统受到。哈希的结果应会确保原有已分配的情可叫射到新的休养冲面临失去,而不见面被射到原始的缓冲集合中之其它缓冲区。

易见到,上面的概括 hash 算法 hash(object)%N 难以满足单调性要求。

3 consistent hashing 算法的规律

consistent hashing 是同一栽 hash 算法,简单的游说,在移除 / 添加一个 cache 时,它能尽可能小之改动都在 key 映射关系,尽可能的满足单调性的要求。

下面就是来仍 5 单步骤省略讲说 consistent hashing 算法的基本原理。

3.1 环形hash 空间

设想通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也就凡是 0~2^32-1 次方的数值空间;我们可以这个空间想象成一个篇( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所著之那么。

C语言 1

图 1 环形 hash 空间

3.2 把对象映射到hash 空间

对接下考虑 4 只目标 object1~object4 ,通过 hash 函数计算起之 hash 值 key 在环上的遍布如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

C语言 2

希冀 2
4 个目标的 key 值分布

3.3 把cache 映射到hash 空间

Consistent hashing 的主干考虑便是以对象与 cache 都映射到同一个 hash 数值空间被,并且采用同一的hash 算法。

假如当前来 A,B 和 C 共 3 台 cache ,那么该映射结果将如图 3 所著,他们以 hash 空间被,以对应之 hash值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

C语言 3

祈求 3
cache 和目标的 key 值分布

 

说交此处,顺便取一下 cache 的 hash 计算,一般的道可以应用 cache 机器的 IP 地址或者机器名作为hash 输入。

3.4 把对象映射到cache

今 cache 和目标都曾由此跟一个 hash 算法映射到 hash 数值空间受到了,接下要考虑的就算是哪以对象映射到 cache 上面了。

在这环形空间受到,如果顺着顺时针方向由目标的 key 值出发,直到碰到一个 cache ,那么就算拿拖欠目标存储于是 cache 上,因为对象和 cache 的 hash 值是稳的,因此这 cache 必然是绝无仅有跟规定的。这样不就是找到了目标及 cache 的投方法了邪?!

依然继续上面的例子(参见图 3 ),那么根据地方的点子,对象 object1 将让贮存到 cache
A 上; object2和 object3 对承诺到 cache
C ; object4 对承诺到 cache
B ;

3.5 考察cache 的变动

眼前说了,通过 hash 然后求余的道带来的极特别题目就是在不克满足单调性,当 cache 有所变更时,cache 会失效,进而对后台服务器造成巨大的相撞,现在尽管来分析分析 consistent hashing 算法。

3.5.1 移除 cache

考虑而 cache B 挂掉了,根据上面说到之映照方法,这时吃影响的以只是是那些沿 cache B 逆时针遍历直到下一个 cache ( cache
C )之间的对象,也就凡是本映射到 cache B 上之那些对象。

用此才用转移对象 object4 ,将该更照射到 cache C 上即可;参见图 4 。

C语言 4

贪图 4 Cache
B 被移除后底 cache 映射

3.5.2 添加 cache

重新考虑添加同高新的 cache D 的情状,假要于此环形 hash 空间中, cache
D 被射在靶 object2 与object3 之间。这时被影响之用仅是那些沿 cache D 逆时针遍历直到下一个 cache ( cache
B )之间的对象(它们是啊当映射到 cache C 上对象的一致片),将这些目标还照射到 cache D 上即可。

 

故此此就得改对象 object2 ,将那个更照射到 cache D 上;参见图 5 。

C语言 5

贪图 5 添加 cache
D 后之映照关系

4 虚拟节点

勘察 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:

平衡性

  平衡性是乘哈希的结果会尽可能分布及持有的休养生息冲着去,这样可以使得所有的复苏冲空间都收获运用。

hash 算法并无是管绝对的平衡,如果 cache 较少之言语,对象并无可知被统统匀的映照到 cache 上,比如在方的例子中,仅配备 cache A 和 cache
C 的图景下,在 4 独对象吃, cache
A 仅存储了 object1 ,而 cache
C 则存储了 object2 、 object3 和 object4 ;分布是格外无均衡的。

为了解决这种情景, consistent hashing 引入了“虚拟节点”的概念,它可如下概念:

“虚拟节点”( virtual node )是实际上节点在 hash 空间的复制品( replica ),一实际只节点对承诺了几单“虚拟节点”,这个相应个数也改为“复制个数”,“虚拟节点”在 hash 空间中盖 hash 值排列。

照因只配备 cache A 和 cache
C 的情呢例,在图 4 中我们早已见到, cache 分布并无都匀。现在咱们引入虚拟节点,并安装“复制个数”为 2 ,这就象征一共会有 4 独“虚拟节点”, cache A1, cache A2 代表了 cache
A ; cache C1, cache C2 代表了 cache
C ;假设一种植于漂亮之气象,参见图 6 。

C语言 6

贪图 6 引入“虚拟节点”后底投关系

 

此时,对象及“虚拟节点”的投射关系吗:

objec1->cache A2 ; objec2->cache A1 ; objec3->cache C1 ; objec4->cache C2 ;

为此对象 object1 和 object2 都深受射到了 cache
A 上,而 object3 和 object4 映射到了 cache
C 上;平衡性有矣大可怜增长。

引入“虚拟节点”后,映射关系虽起 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所当 cache时底炫耀关系而图 7 所著。

C语言 7

图 7 查询对象所于 cache

 

“虚拟节点”的 hash 计算好下对诺节点的 IP 地址加数字后缀的点子。例如假设 cache A 的 IP 地址也202.168.14.241 。

引入“虚拟节点”前,计算 cache A 的 hash 值:

Hash(“202.168.14.241”);

引入“虚拟节点”后,计算“虚拟节”点 cache A1 和 cache
A2 的 hash 值:

Hash(“202.168.14.241#1”);  // cache A1

Hash(“202.168.14.241#2”);  // cache A2

5 小结

Consistent hashing 的基本原理就是这些,具体的分布性等理论分析该是甚复杂的,不过貌似为为此非顶。

http://weblogs.java.net/blog/2007/11/27/consistent-hashing 上面来一个 java 版本的事例,可以参见。

http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx 转载了一个 PHP 版的兑现代码。

http://www.codeproject.com/KB/recipes/lib-conhash.aspx C语言版

 

有的参考资料地址:

http://portal.acm.org/citation.cfm?id=258660

http://en.wikipedia.org/wiki/Consistent_hashing

http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

 http://weblogs.java.net/blog/2007/11/27/consistent-hashing

http://tech.idv2.com/2008/07/24/memcached-004/

http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx

 

http://hbluojiahui.blog.163.com/blog/static/31064767201098114026211/