? ? ? ? consistent hashing算法早在1997年就在論文Consistent hashing and random trees中被提出，目前在cache系統(tǒng)中應用越來越廣泛砸喻；
? ? ? ? 比如你有N個cache服務器（后面簡稱node），那么如何將一個數(shù)據(jù)集合映射到N個node上呢通铲，你很可能會采用類似下面的通用方法計算data的hash值官辈，然后映射到相應的node上援岩；
hash(data)%N
問題的引入:
1、一個cache服務器node0 宕掉了（在實際應用中必須要考慮這種情況）箱熬，這樣所有映射到node0的數(shù)據(jù)都會失效类垦，怎么辦，需要把node0從服務器列表中移除城须，這時候cache是N-1臺蚤认，映射公式變成了hash(data)%(N-1)；
2糕伐、由于訪問加重砰琢，需要添加node，這時候cache是N+1臺良瞧，映射公式變成了hash(data)%(N+1)陪汽；
1和2意味著什么？這意味著突然之間幾乎所有的映射關(guān)系都失效了褥蚯。對于服務器而言挚冤，這是一場災難，洪水般的訪問都會直接沖向后臺服務器赞庶；
再來考慮第三個問題训挡，由于硬件能力越來越強澳骤，你可能想讓后面添加的節(jié)點多做點活，顯然上面的hash算法也做不到澜薄。
hash算法和單調(diào)性
? ? ? ? Hash算法的一個衡量指標是單調(diào)性（Monotonicity）为肮，定義如下：
? ? ? ? 單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統(tǒng)中肤京。哈希的結(jié)果應能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去颊艳，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。
? ? ? ? consistent hashing是一種hash算法忘分，簡單的說棋枕，在移除/添加一個node時，它能夠盡可能小的改變已存在key映射關(guān)系饭庞，盡可能的滿足單調(diào)性的要求戒悠。
下面就來按照5個步驟簡單講講consistent hashing算法的基本原理。
環(huán)形Hash空間
按照常用的hash算法來將對應的key哈希到一個具有2^32次方個桶的空間中舟山，即0~(2^32)-1的數(shù)字空間中。現(xiàn)在我們可以將這些數(shù)字頭尾相連卤恳，想象成一個閉合的環(huán)形累盗。如下圖
把數(shù)據(jù)映射到hash空間
? ? ? ? 現(xiàn)在我們將object1、object2突琳、object3若债、object4四個數(shù)據(jù)對象通過特定的Hash函數(shù)計算出對應的key值，然后散列到Hash環(huán)上拆融。如下圖：
Hash(object1) = key1蠢琳；
Hash(object2) = key2；
Hash(object3) = key3镜豹；
Hash(object4) = key4傲须；
把node映射到hash空間
? ? ? ? 在采用一致性哈希算法的分布式集群中將新的機器加入，其原理是通過使用與對象存儲一樣的Hash算法將機器也映射到環(huán)中（一般情況下對機器的hash計算是采用機器的IP或者機器唯一的別名作為輸入值）趟脂，然后以順時針的方向計算泰讽，將所有對象存儲到離自己最近的機器中。
假設現(xiàn)在有NODE1昔期，NODE2已卸，NODE3三臺機器，通過Hash算法得到對應的KEY值硼一，映射到環(huán)中累澡，其示意圖如下：
Hash(NODE1) = KEY1;(這里是大寫的KEY，數(shù)據(jù)是小寫的key)
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;
把data映射到node
? ? ? 現(xiàn)在node和data都已經(jīng)通過同一個hash算法映射到hash數(shù)值空間中了般贼，接下來要考慮的就是如何將數(shù)據(jù)映射到node上面了愧哟。
? ? ? 在這個環(huán)形空間中惑申，如果沿著順時針方向從data的key值出發(fā)，直到遇見一個node翅雏，那么就將該對象存儲在這個node上圈驼，因為data和node的hash值是固定的，因此這個node必然是唯一和確定的望几。
node的變動
? ? ? ? 前面講過绩脆，通過hash然后求余的方法帶來的最大問題就在于不能滿足單調(diào)性，當node有變動時橄抹，所有的data映射都會失效靴迫，進而對后臺服務器造成巨大的沖擊，現(xiàn)在就來分析分析consistent hashing算法楼誓。
? ? 移除node
? ? ? ? 以上面的分布為例玉锌，如果NODE2出現(xiàn)故障被刪除了，那么按照順時針遷移的方法疟羹，object3將會被遷移到NODE3中主守，這樣僅僅是object3的映射位置發(fā)生了變化，其它的對象沒有任何的改動榄融。如下圖：
添加node
? ? ? 如果往集群中添加一個新的節(jié)點NODE4参淫，通過對應的哈希算法得到KEY4，并映射到環(huán)中愧杯，如下圖：
? ? ? ?通過按順時針遷移的規(guī)則涎才，那么object2被遷移到了NODE4中，其它對象還保持這原有的存儲位置力九。通過對節(jié)點的添加和刪除的分析耍铜，一致性哈希算法在保持了單調(diào)性的同時，還是數(shù)據(jù)的遷移達到了最小跌前，這樣的算法對分布式集群來說是非常合適的棕兼，避免了大量數(shù)據(jù)遷移，減小了服務器的的壓力舒萎。
平衡性
? ? ? ?根據(jù)上面的圖解分析程储，一致性哈希算法滿足了單調(diào)性和負載均衡的特性以及一般hash算法的分散性，但這還并不能當做其被廣泛應用的原由臂寝，因為還缺少了平衡性章鲤。下面將分析一致性哈希算法是如何滿足平衡性的。hash算法是不保證平衡的咆贬，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）败徊，object1存儲到了NODE1中，而object2掏缎、object3皱蹦、object4都存儲到了NODE3中煤杀，這樣就照成了非常不平衡的狀態(tài)。在一致性哈希算法中沪哺，為了盡可能的滿足平衡性沈自，其引入了虛擬節(jié)點。
? ? ? ? “虛擬節(jié)點”（virtual node）是實際節(jié)點（機器）在hash空間的復制品（replica）辜妓，一實際個節(jié)點（機器）對應了若干個“虛擬節(jié)點”枯途，這個對應個數(shù)也成為“復制個數(shù)”，“虛擬節(jié)點”在hash空間中以hash值排列籍滴。
? ? ? ? 以上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）為例酪夷，之前的對象在機器上的分布很不均衡，現(xiàn)在我們以2個副本（復制個數(shù)）為例孽惰，這樣整個hash環(huán)中就存在了4個虛擬節(jié)點晚岭，最后對象映射的關(guān)系圖如下：
? ? ? 根據(jù)上圖可知對象的映射關(guān)系：object1->NODE1-1，object2->NODE1-2勋功，object3->NODE3-2坦报，object4->NODE3-1。通過虛擬節(jié)點的引入酝润，對象的分布就比較均衡了燎竖。那么在實際操作中，正真的對象查詢是如何工作的呢要销？對象從hash到虛擬節(jié)點到實際節(jié)點的轉(zhuǎn)換如下圖：
“虛擬節(jié)點”的hash計算可以采用對應節(jié)點的IP地址加數(shù)字后綴的方式。例如假設NODE1的IP地址為192.168.1.100夏块。引入“虛擬節(jié)點”前疏咐，計算cache A的hash值：
Hash(“192.168.1.100”);
引入“虛擬節(jié)點”后，計算“虛擬節(jié)”點NODE1-1和NODE1-2的hash值：
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2
總結(jié)：
一致性hash算法解決的問題：節(jié)點增加或移除對原有數(shù)據(jù)分布的最小沖擊脐供，即使用原來的查詢或插入方法都不會有問題浑塞，頂多是查詢不到。
java算法實現(xiàn)：
http://blog.csdn.net/wuhuan_wp/article/details/7010071
一致性hash算法提出了在動態(tài)變化的Cache環(huán)境中政己，判定哈希算法好壞的四個定義：
1酌壕、平衡性(Balance)：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用歇由。很多哈希算法都能夠滿足這一條件卵牍。
2、單調(diào)性(Monotonicity)：單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應的緩沖中沦泌，又有新的緩沖加入到系統(tǒng)中糊昙。哈希的結(jié)果應能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)谢谦。
3释牺、分散性(Spread)：在分布式環(huán)境中萝衩，終端有可能看不到所有的緩沖，而是只能看到其中的一部分没咙。當終端希望通過哈希過程將內(nèi)容映射到緩沖上時猩谊，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結(jié)果不一致祭刚，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中牌捷。這種情況顯然是應該避免的，因為它導致相同內(nèi)容被存儲到不同緩沖中去袁梗，降低了系統(tǒng)存儲的效率宜鸯。分散性的定義就是上述情況發(fā)生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發(fā)生遮怜，也就是盡量降低分散性淋袖。
4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題锯梁。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中即碗，那么對于一個特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同 的內(nèi)容陌凳。與分散性一樣剥懒，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷合敦。
