分布式緩存作為緩存水平擴(kuò)充的最佳辦法病曾，當(dāng)前很實(shí)用。
假設(shè)一臺(tái)機(jī)器可支撐4GB的數(shù)據(jù)的緩存钳降，如果需要支撐24GB厚宰，則需要6臺(tái)機(jī)器，采用分布式緩存后遂填，當(dāng)用戶登錄時(shí)铲觉，系統(tǒng)行為就會(huì)如下：
從而可見，對(duì)于分布式緩存而言吓坚，需要解決的是NodeA和NodeB在操作同一用戶在登錄信息時(shí)能到分布式緩存集群的同一機(jī)器上操作撵幽。最簡(jiǎn)單的方法是對(duì)于用戶ID進(jìn)行HASH，根據(jù)HASH對(duì)緩存機(jī)器取模礁击，這種方法為HASH取模盐杂，缺點(diǎn)是當(dāng)前緩存集群機(jī)器發(fā)生增減時(shí)會(huì)出現(xiàn)大量緩存未命中的現(xiàn)象。（緩存節(jié)點(diǎn)HA的除外）
一致性HASH可緩解上述問題哆窿。
原理：
① 求出緩存集群機(jī)器的HASH值链烈，分布在一個(gè)2的32次方的圓環(huán)上
②緩存Key存儲(chǔ)時(shí)同理求出HASH，亦分布在上面的圓環(huán)上
③順時(shí)針尋找第一個(gè)圓環(huán)上的節(jié)點(diǎn)機(jī)器作為存儲(chǔ)機(jī)器
好處：
增減Cache集群機(jī)器時(shí)挚躯，影響的Cache值僅僅只是節(jié)點(diǎn)逆時(shí)針方向的一小段范圍Key
下面引入理論詳解：
環(huán)形Hash空間
按照常用的hash算法來(lái)將對(duì)應(yīng)的key哈希到一個(gè)具有232次方個(gè)桶的空間中强衡，即0~(232)-1的數(shù)字空間中。現(xiàn)在我們可以將這些數(shù)字頭尾相連码荔，想象成一個(gè)閉合的環(huán)形漩勤。如下圖
把數(shù)據(jù)通過(guò)一定的hash算法處理后映射到環(huán)上
現(xiàn)在我們將object1、object2缩搅、object3越败、object4四個(gè)對(duì)象通過(guò)特定的Hash函數(shù)計(jì)算出對(duì)應(yīng)的key值，然后散列到Hash環(huán)上誉己。如下圖：
Hash(object1) = key1眉尸；
Hash(object2) = key2域蜗；
Hash(object3) = key3巨双；
Hash(object4) = key4噪猾；
將機(jī)器通過(guò)hash算法映射到環(huán)上
在采用一致性哈希算法的分布式集群中將新的機(jī)器加入，其原理是通過(guò)使用與對(duì)象存儲(chǔ)一樣的Hash算法將機(jī)器也映射到環(huán)中（一般情況下對(duì)機(jī)器的hash計(jì)算是采用機(jī)器的IP或者機(jī)器唯一的別名作為輸入值）筑累，然后以順時(shí)針的方向計(jì)算袱蜡，將所有對(duì)象存儲(chǔ)到離自己最近的機(jī)器中。
假設(shè)現(xiàn)在有NODE1慢宗，NODE2坪蚁，NODE3三臺(tái)機(jī)器，通過(guò)Hash算法得到對(duì)應(yīng)的KEY值镜沽，映射到環(huán)中敏晤，其示意圖如下：
Hash(NODE1) = KEY1;
Hash(NODE2) = KEY2;
Hash(NODE3) = KEY3;
通過(guò)上圖可以看出對(duì)象與機(jī)器處于同一哈希空間中缅茉，這樣按順時(shí)針轉(zhuǎn)動(dòng)object1存儲(chǔ)到了NODE1中嘴脾，object3存儲(chǔ)到了NODE2中，object2蔬墩、object4存儲(chǔ)到了NODE3中译打。在這樣的部署環(huán)境中，hash環(huán)是不會(huì)變更的拇颅，因此奏司，通過(guò)算出對(duì)象的hash值就能快速的定位到對(duì)應(yīng)的機(jī)器中，這樣就能找到對(duì)象真正的存儲(chǔ)位置了樟插。
機(jī)器的刪除與添加
普通hash求余算法最為不妥的地方就是在有機(jī)器的添加或者刪除之后會(huì)照成大量的對(duì)象存儲(chǔ)位置失效韵洋，這樣就大大的不滿足單調(diào)性了。下面來(lái)分析一下一致性哈希算法是如何處理的黄锤。
-
節(jié)點(diǎn)（機(jī)器）的刪除
以上面的分布為例麻献，如果NODE2出現(xiàn)故障被刪除了，那么按照順時(shí)針遷移的方法猜扮，object3將會(huì)被遷移到NODE3中勉吻，這樣僅僅是object3的映射位置發(fā)生了變化，其它的對(duì)象沒有任何的改動(dòng)旅赢。如下圖：
Paste_Image.png -
節(jié)點(diǎn)（機(jī)器）的添加
如果往集群中添加一個(gè)新的節(jié)點(diǎn)NODE4齿桃，通過(guò)對(duì)應(yīng)的哈希算法得到KEY4，并映射到環(huán)中煮盼，如下圖：
Paste_Image.png通過(guò)按順時(shí)針遷移的規(guī)則短纵，那么object2被遷移到了NODE4中，其它對(duì)象還保持這原有的存儲(chǔ)位置僵控。通過(guò)對(duì)節(jié)點(diǎn)的添加和刪除的分析香到，一致性哈希算法在保持了單調(diào)性的同時(shí)，還是數(shù)據(jù)的遷移達(dá)到了最小，這樣的算法對(duì)分布式集群來(lái)說(shuō)是非常合適的悠就，避免了大量數(shù)據(jù)遷移千绪，減小了服務(wù)器的的壓力。
平衡性
根據(jù)上面的圖解分析梗脾，一致性哈希算法滿足了單調(diào)性和負(fù)載均衡的特性以及一般hash算法的分散性荸型，但這還并不能當(dāng)做其被廣泛應(yīng)用的原由，因?yàn)檫€缺少了平衡性炸茧。下面將分析一致性哈希算法是如何滿足平衡性的瑞妇。hash算法是不保證平衡的，如上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）梭冠，object1存儲(chǔ)到了NODE1中辕狰，而object2、object3控漠、object4都存儲(chǔ)到了NODE3中柳琢，這樣就照成了非常不平衡的狀態(tài)。在一致性哈希算法中润脸，為了盡可能的滿足平衡性柬脸，其引入了虛擬節(jié)點(diǎn)。
——“虛擬節(jié)點(diǎn)”（ virtual node ）是實(shí)際節(jié)點(diǎn)（機(jī)器）在 hash 空間的復(fù)制品（ replica ）毙驯，一實(shí)際個(gè)節(jié)點(diǎn)（機(jī)器）對(duì)應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”倒堕，這個(gè)對(duì)應(yīng)個(gè)數(shù)也成為“復(fù)制個(gè)數(shù)”，“虛擬節(jié)點(diǎn)”在 hash 空間中以hash值排列爆价。
以上面只部署了NODE1和NODE3的情況（NODE2被刪除的圖）為例垦巴，之前的對(duì)象在機(jī)器上的分布很不均衡，現(xiàn)在我們以2個(gè)副本（復(fù)制個(gè)數(shù)）為例铭段，這樣整個(gè)hash環(huán)中就存在了4個(gè)虛擬節(jié)點(diǎn)骤宣，最后對(duì)象映射的關(guān)系圖如下：
根據(jù)上圖可知對(duì)象的映射關(guān)系：object1->NODE1-1，object2->NODE1-2序愚，object3->NODE3-2憔披，object4->NODE3-1。通過(guò)虛擬節(jié)點(diǎn)的引入爸吮，對(duì)象的分布就比較均衡了芬膝。那么在實(shí)際操作中，正真的對(duì)象查詢是如何工作的呢形娇？對(duì)象從hash到虛擬節(jié)點(diǎn)到實(shí)際節(jié)點(diǎn)的轉(zhuǎn)換如下圖：
“虛擬節(jié)點(diǎn)”的hash計(jì)算可以采用對(duì)應(yīng)節(jié)點(diǎn)的IP地址加數(shù)字后綴的方式锰霜。例如假設(shè)NODE1的IP地址為192.168.1.100。引入“虛擬節(jié)點(diǎn)”前桐早，計(jì)算 cache A 的 hash 值：
Hash(“192.168.1.100”);
引入“虛擬節(jié)點(diǎn)”后癣缅，計(jì)算“虛擬節(jié)”點(diǎn)NODE1-1和NODE1-2的hash值：
Hash(“192.168.1.100#1”); // NODE1-1
Hash(“192.168.1.100#2”); // NODE1-2
理論轉(zhuǎn)自：
http://blog.csdn.net/cywosp/article/details/23397179
