请选择 进入手机版 | 继续访问电脑版

人工智能论坛

 找回密码
 立即注册
查看: 2559|回复: 7

一致性 hash 算法( consistent hashing )

  [复制链接]
发表于 2013-5-6 10:20:20 | 显示全部楼层 |阅读模式
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所示的那样。

图1环形hash空间


3.2把对象映射到hash空间接下来考虑4个对象object1~object4,通过hash函数计算出的hash值key在环上的分布如图2所示。

hash(object1) = key1;

… …

hash(object4) = key4;

图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;

图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。

图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。


图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。

图6引入“虚拟节点”后的映射关系


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

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

因此对象object1和object2都被映射到了cache A上,而object3和object4映射到了cache C上;平衡性有了很大提高。

引入“虚拟节点”后,映射关系就从{对象->节点}转换到了{对象->虚拟节点}。查询物体所在cache时的映射关系如图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.aspxC语言版本





一些参考资料地址:

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

回复

使用道具 举报

发表于 2013-8-23 09:38:49 | 显示全部楼层
回复 支持 反对

使用道具 举报

发表于 2013-9-18 00:34:33 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

发表于 2013-11-12 14:20:13 | 显示全部楼层

den Pipes vorschl?gt.

"Der 21-Gentest bestimmt den Nutzen einer Chemotherapie für die sehr niedrigen oder sehr hohen Werte ziemlich genau", so Krebsspezialist Eiermann.  Mit 2:4 (1:2) verloren die Westfalen gegen den 1.  Weiterhin wird hier ancheinend von allen Leuten vergessen,tommy hilfiger sale, dass bereits eine BT-Tastatur und Maus im Kaufpreis mit inbegriffen sind.  Die werden,tommy hilfiger jeans, auf den Boden gestellt oder an die Wand geh?ngt,tommy hilfiger t shirt, zu wahren Schatzkisten für Blumensaat, Pflanzenstecker und allerlei sch?ne Gartenutensilien.  Und damit vor exakt der Art von Luftschlag gefeit ist,tommy hilfiger shop, den Pipes vorschl?gt.
    An zweiter Stelle stehen die mehr als eine Milliarde Euro Kosten für die Verlege- und Spezialschiffe.  Ein Warmduscher ist noch nie weit gekommen im Leben. "Der Superstar dieser Mannschaft": Rudi V?ller lobt Bernd Schneider.  Beim Spielen macht sich die leistungsf?hige Nvidia-Karte - es ist die zweitst?rkste Grafik  im Testfeld - positiv bemerkbar. Im Zuge mehrerer kleiner Facelifts stieg der Hubraum von drei auf 3,2 Liter, eine Targa-Version folgte und dann die letzte Serie ohne Klappscheinwerfer.
    Vergaser habe ich mit 2 Uhren synchronisiert.  Das Doppelkupplungsgetriebe wechselt seine sechs G?nge nicht nur blitzschnell,tommy hilfiger shop, sondern bei normaler Fahrweise auch nahezu unbemerkt.  Und machen Sie sich bewusst,tommy hilfiger jacke, dass diese Umgebung sie eher zum Essen und Trinken verführt als ein cooles, helles Ambiente.  Naturally, the successor model also provides this special feature.  wir nahmen teil am ansegeln des svk, das programm wurde von anne und andreas organisiert - hervorragend gemacht!
    Der Stick war am Ende sehr Schwer und hat so auch nicht so viele Steckzyklen überlebt. " Und so spricht sie auch für die anderen Studierenden aus dieser Geschichte, denen es allen nicht darum geht,tommy hilfiger sale, sich mit Statussymbolen zu umgeben, sondern mit Dingen, die einen pers?nlichen Wert für sie haben. 000/ min-H?he der 260 PS muss sich der Motor kaum aufschwingen, vorher zuckt der Gasfu? - und das Heck. Ich muss sagen langsam wird man etwas nerv?s.  "Wired - ein Anlass für olle Kamellen"Nikolaus Roettger,tommy hilfiger sale, Chefredakteur von "Business Punk",tommy hilfiger outlet, wendet sich gegen einen vor rund zwei Jahren erschienenen Text von Thomas Knüwer,tommy hilfiger denim, in dem er das damals neu herausgekommene Magazin in "ungerechtfertigter Weise der Lüge" bezichtigte.
    2,4 Umdrehungen sind insgesamt drin, das hei?t, für eine 90-Grad-Kurve reicht weniger als eine viertel Umdrehung.  Sozialministerin Christine Clau? (CDU) sieht dabei in der ambulanten ?rztlichen . "Eigentlich eine Doppel-Parodie: Die Politik der irdischen Gegenwart spiegelt sich in den B?nden genauso wie die in der Regel primitiven und auch nicht wissenschaftlich begründbaren Regeln der Science Fiction,Tommy Hilfiger, wie sie in den diversen Space-Operas angewendet w n.  Doch bevor die ihren Hintern hochkriegen ist es zu sp?t, darum muss jetzt was geschehen.  Nach mir die Sintflut,tommy hilfiger denim, ist der bevorzugte Fahrstil.
   ) sind nicht unbedingt natürlich, sondern unter Umst?nden nur, was man "naturidentisch" nennt (kommen also natürlich vor,tommy hilfiger sale, sind aber nicht natürlich entstanden).  September 2009 ruft Matthew Herbert im Vorfeld zwecks Materialbeschaffung dazu auf,tommy hilfiger jeans, in den Frankfurter Technoclub Robert Johnson zu kommen, um dort aktiv zu einer weiteren Soundcollage beizutragen: "Der Club wird mit Mikrofonen ausstaffiert sein, sowohl drau?en wie drinnen und auf der Toilette, um jedes Ger?usch festzuhalten.  Das l?sst mich hoffen, dass ich die Jungs vor mir angreifen kann.  ?Die Idee dahinter war:  en nehmen gern den Rat von schwulen M?nnern an. Zug am rechten Leichtmetall-Paddel hinter dem Kranz des unten abgeflachten Lenkrads,tommy hilfiger jeans, die erste Fahrtstufe im Siebengang-Doppelkupplungsgetriebe nimmt ihre Arbeit auf.
回复 支持 反对

使用道具 举报

发表于 2013-12-13 06:03:50 | 显示全部楼层
楼主辛苦了,鼓励一下











网上彩票,网上彩票投注站记住网址www.wscptz.com
回复 支持 反对

使用道具 举报

发表于 2014-1-1 07:01:17 | 显示全部楼层
好帖要顶,楼主的头像还是不错滴
回复 支持 反对

使用道具 举报

发表于 2014-3-13 15:10:17 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

发表于 2014-4-9 10:22:34 | 显示全部楼层
好帖要顶,楼主的头像还是不错滴
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|积分充值|小黑屋|手机浏览|人工智能实验室 ( 苏ICP备12079930号

GMT+8, 2017-10-23 19:31 , Processed in 0.746131 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表