C语言壹致性 hash 算法( consistent hashing )

consistent hashing 算法早在 19九七 年就在杂文 Consistent hashing and random
trees
 
中被提议,近年来在 cache 系统中接纳越来越广阔;

一 基本气象

比如您有 N 个 cache 服务器(前面简称 cache ),那么什么样将1个目的 object 映射到 N 个 cache 上啊,你很恐怕会选取类似上面包车型大巴通用方法计算 object 的 hash 值,然后均匀的照射到到 N 个 cache ;

hash(object)%N

壹体都运维如常,再挂念如下的三种情况;

一 二个 cache 服务器 m
down 掉了(在骨子里运用中必供给怀恋那种情状),那样有着映射到 cache m 的靶子都会失效,怎么做,需求把 cache m 从 cache 中移除,这时候 cache 是 N-一 台,映射公式变成了 hash(object)%(N-一) ;

贰 由于访问加重,须要充裕 cache ,那时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;

一 和 二 意味着什么样?那意味着突然之间差不离拥有的 cache 都失效了。对于服务器而言,那是一场横祸,洪涝般的访问都会一向冲向后台服务器;

再来思索第5个难题,由于硬件能力尤其强,你只怕想让前面添加的节点多做点活,明显上边包车型地铁 hash 算法也做不到。

  有怎么着格局能够变更那些情景呢,那便是 consistent hashing…

二 hash 算法和单调性

   Hash 算法的叁个权衡目标是单调性( Monotonicity ),定义如下:

  单调性是指要是已经有1部分内容通过哈希分派到了相应的缓冲中,又有新的缓冲参预到系统中。哈希的结果应能够有限补助原有已分配的剧情能够被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其余缓冲区。

简单见到,上边的不难 hash 算法 hash(object)%N 难以知足单调性要求。

叁 consistent hashing 算法的规律

consistent hashing 是壹种 hash 算法,简单的说,在移除 / 添加1个 cache 时,它亦可尽只怕小的变动已存在 key 映射关系,尽只怕的知足单调性的渴求。

上边就来依据 伍 个步骤省略讲讲 consistent hashing 算法的基本原理。

3.1 环形hash 空间

思量平日的 hash 算法都是将 value 映射到3个 3二 为的 key 值,也便是 0~2^3二-一 次方的数值空间;咱们可以将这几个空间想象成1个首( 0 )尾( 2^32-壹 )相接的圆环,如下面图 一 所示的那么。

C语言 1

图 1 环形 hash 空间

三.2 把目的映射到hash 空间

接下去缅想 肆 个指标 object一~object四 ,通过 hash 函数总括出的 hash 值 key 在环上的遍布如图 2 所示。

hash(object1) = key1;

… …

hash(object4) = key4;

C语言 2

图 二肆 个目的的 key 值分布

3.3 把cache 映射到hash 空间

Consistent hashing 的核心情维正是将目的和 cache 都映射到同1个 hash 数值空间中,并且利用同1的hash 算法。

倘使当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 三 所示,他们在 hash 空间中,以对应的 hash值排列。

hash(cache A) = key A;

… …

hash(cache C) = key C;

C语言 3

图 3cache 和目的的 key 值分布

 

谈起此地,顺便提一下 cache 的 hash 总计,一般的不二秘籍能够接纳 cache 机器的 IP 地址恐怕机器名作为hash 输入。

三.四 把对象映射到cache

今天 cache 和对象都早已经过同四个 hash 算法映射到 hash 数值空间中了,接下去要思索的正是什么样将对象映射到 cache 上边了。

在那几个环形空间中,假如沿着顺时针方向从目的的 key 值出发,直到遇到三个 cache ,那么就将该指标存款和储蓄在那些 cache 上,因为对象和 cache 的 hash 值是固定的,由此这几个 cache 必然是绝无仅有和分明的。那样不就找到了对象和 cache 的照耀方法了啊?!

依旧三番7遍上边的事例(参见图 三 ),那么依照上边的办法,对象 object一 将被积存到 cache
A 上; object二和 object三 对应到 cache
C ; object四 对应到 cache
B ;

3.5 考察cache 的变动

日前讲过,通过 hash 然后求余的艺术带来的最大题材就在于不能够满意单调性,当 cache 有所变更时,cache 会失效,进而对后台服务器造成巨大的冲击,未来就来分析分析 consistent hashing 算法。

3.5.1 移除 cache

思量要是 cache B 挂掉了,根据地点讲到的映射方法,这时受影响的将仅是那1个沿 cache B 逆时针遍历直到下3个 cache ( cache
C )之间的目的,相当于本来映射到 cache B 上的那多少个对象。

所以那里仅供给转移对象 object四 ,将其重新照射到 cache C 上即可;参见图 肆 。

C语言 4

图 4 Cache
B 被移除后的 cache 映射

3.5.2 添加 cache

再思索添加1台新的 cache D 的意况,若是在这几个环形 hash 空间中, cache
D 被映射在目的 object贰 和object三 之间。那时受影响的将仅是那三个沿 cache D 逆时针遍历直到下叁个 cache ( cache
B )之间的对象(它们是也当然映射到 cache C 上对象的一有的),将这个目的重新照射到 cache D 上即可。

 

之所以那里仅须要改变对象 object二 ,将其重新照射到 cache D 上;参见图 5 。

C语言 5

图 伍 添加 cache
D 后的照射关系

四 虚拟节点

勘查 Hash 算法的另2个目标是平衡性 (Balance) ,定义如下:

平衡性

  平衡性是指哈希的结果可知尽恐怕分布到具备的缓冲中去,那样能够使得全体的缓冲空间都拿走运用。

hash 算法并不是保险绝对的平衡,假设 cache 较少的话,对象并无法被均匀的照射到 cache 上,比如在上边的事例中,仅安插 cache A 和 cache
C 的地方下,在 四 个对象中, cache
A 仅存储了 object1 ,而 cache
C 则存储了 object二 、 object三 和 object四 ;分布是很不均衡的。

为了缓解那种气象, consistent hashing 引入了“虚拟节点”的概念,它能够如下概念:

“虚拟节点”( virtual node )是事实上节点在 hash 空间的仿制品( replica ),一实际个节点对应了若干个“虚拟节点”,那个相应个数也改成“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

仍以仅安顿 cache A 和 cache
C 的情事为例,在图 肆 中我们早已观看, cache 分布并不均匀。未来我们引入虚拟节点,并安装“复制个数”为 贰 ,那就象征一共会设有 肆 个“虚拟节点”, cache A一, cache A二 代表了 cache
A ; cache C一, cache C2 代表了 cache
C ;假诺壹种相比不错的场馆,参见图 陆 。

C语言 6

图 陆 引入“虚拟节点”后的照耀关系

 

那时,对象到“虚拟节点”的照射关系为:

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

故此对象 object一 和 object2 都被映射到了 cache
A 上,而 object叁 和 object四 映射到了 cache
C 上;平衡性有了相当的大增强。

引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换来了 { 对象 -> 虚拟节点 } 。查询物体所在 cache时的投射关系如图 柒 所示。

C语言 7

图 7 查询对象所在 cache

 

“虚拟节点”的 hash 总计可以行使对应节点的 IP 地址加数字后缀的不二等秘书诀。例倘诺是 cache A 的 IP 地址为20二.16八.1四.贰4壹 。

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

Hash(“202.168.14.241”);

引入“虚拟节点”后,计算“虚拟节”点 cache A一 和 cache
A二 的 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/