在做服務(wù)器負(fù)載均衡時候可供選擇的負(fù)載均衡的算法有很多，包括：  輪循算法（Round Robin）、哈希算法（HASH）、最少連接算法（Least Connection）、響應(yīng)速度算法（Response Time）、加權(quán)法（Weighted ）等。其中哈希算法是最為常用的算法.

典型的應(yīng)用場景是： 有N臺服務(wù)器提供緩存服務(wù)，需要對服務(wù)器進(jìn)行負(fù)載均衡，將請求平均分發(fā)到每臺服務(wù)器上，每臺機(jī)器負(fù)責(zé)1/N的服務(wù)。

常用的算法是對hash結(jié)果取余數(shù) (hash() mod N)：對機(jī)器編號從0到N-1，按照自定義的hash()算法，對每個請求的hash()值按N取模，得到余數(shù)i，然后將請求分發(fā)到編號為i的機(jī)器。但這樣的算法方法存在致命問題，如果某一臺機(jī)器宕機(jī)，那么應(yīng)該落在該機(jī)器的請求就無法得到正確的處理，這時需要將當(dāng)?shù)舻?a href=/yuedu/fuwuqi/ target=_blank class=infotextkey>服務(wù)器從算法從去除，此時候會有(N-1)/N的服務(wù)器的緩存數(shù)據(jù)需要重新進(jìn)行計(jì)算；如果新增一臺機(jī)器，會有N /(N+1)的服務(wù)器的緩存數(shù)據(jù)需要進(jìn)行重新計(jì)算。對于系統(tǒng)而言，這通常是不可接受的顛簸（因?yàn)檫@意味著大量緩存的失效或者數(shù)據(jù)需要轉(zhuǎn)移）。那么，如何設(shè)計(jì)一個負(fù)載均衡策略，使得受到影響的請求盡可能的少呢？

在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以說Consistent Hashing 是分布式系統(tǒng)負(fù)載均衡的首選算法。

下面以Memcached中的Consisten Hashing算法為例說明。
由于hash算法結(jié)果一般為unsigned int型，因此對于hash函數(shù)的結(jié)果應(yīng)該均勻分布在[0,232-1]間，如果我們把一個圓環(huán)用232 個點(diǎn)來進(jìn)行均勻切割，首先按照hash(key)函數(shù)算出服務(wù)器（節(jié)點(diǎn)）的哈希值， 并將其分布到0～232的圓上。

用同樣的hash(key)函數(shù)求出需要存儲數(shù)據(jù)的鍵的哈希值，并映射到圓上。然后從數(shù)據(jù)映射到的位置開始順時針查找，將數(shù)據(jù)保存到找到的第一個服務(wù)器（節(jié)點(diǎn)）上。

 Consistent Hashing原理示意圖

新增一個節(jié)點(diǎn)的時候，只有在圓環(huán)上新增節(jié)點(diǎn)逆時針方向的第一個節(jié)點(diǎn)的數(shù)據(jù)會受到影響。刪除一個節(jié)點(diǎn)的時候，只有在圓環(huán)上原來刪除節(jié)點(diǎn)順時針方向的第一個節(jié)點(diǎn)的數(shù)據(jù)會受到影響，因此通過Consistent Hashing很好地解決了負(fù)載均衡中由于新增節(jié)點(diǎn)、刪除節(jié)點(diǎn)引起的hash值顛簸問題。

 Consistent Hashing添加服務(wù)器示意圖

虛擬節(jié)點(diǎn)（virtual nodes）：之所以要引進(jìn)虛擬節(jié)點(diǎn)是因?yàn)樵?a href=/yuedu/fuwuqi/ target=_blank class=infotextkey>服務(wù)器（節(jié)點(diǎn)）數(shù)較少的情況下（例如只有3臺服務(wù)器），通過hash(key)算出節(jié)點(diǎn)的哈希值在圓環(huán)上并不是均勻分布的（稀疏的），仍然會出現(xiàn)各節(jié)點(diǎn)負(fù)載不均衡的問題。虛擬節(jié)點(diǎn)可以認(rèn)為是實(shí)際節(jié)點(diǎn)的復(fù)制品（replicas），本質(zhì)上與實(shí)際節(jié)點(diǎn)實(shí)際上是一樣的（key并不相同）。引入虛擬節(jié)點(diǎn)后，通過將每個實(shí)際的服務(wù)器（節(jié)點(diǎn)）數(shù)按照一定的比例(例如200倍)擴(kuò)大后并計(jì)算其hash(key)值以均勻分布到圓環(huán)上。在進(jìn)行負(fù)載均衡時候，落到虛擬節(jié)點(diǎn)的哈希值實(shí)際就落到了實(shí)際的節(jié)點(diǎn)上。由于所有的實(shí)際節(jié)點(diǎn)是按照相同的比例復(fù)制成虛擬節(jié)點(diǎn)的，因此解決了節(jié)點(diǎn)數(shù)較少的情況下哈希值在圓環(huán)上均勻分布的問題。

虛擬節(jié)點(diǎn)對Consistent Hashing結(jié)果的影響

從上圖可以看出，在節(jié)點(diǎn)數(shù)為10個的情況下，每個實(shí)際節(jié)點(diǎn)的虛擬節(jié)點(diǎn)數(shù)為實(shí)際節(jié)點(diǎn)的100-200倍的時候，結(jié)果還是很均衡的。

第3段中有這些文字：“但這樣的算法方法存在致命問題，如果某一臺機(jī)器宕機(jī)，那么應(yīng)該落在該機(jī)器的請求就無法得到正確的處理，這時需要將當(dāng)?shù)舻?a href=/yuedu/fuwuqi/ target=_blank class=infotextkey>服務(wù)器從算法從去除，此時候會有(N-1)/N的服務(wù)器的緩存數(shù)據(jù)需要重新進(jìn)行計(jì)算；”

為何是 (N-1)/N 呢？解釋如下：

比如有 3 臺機(jī)器，hash值 1-6 在這3臺上的分布就是：
host 1: 1 4
host 2: 2 5
host 3: 3 6
如果掛掉一臺，只剩兩臺，模數(shù)取 2 ，那么分布情況就變成：
host 1: 1 3 5
host 2: 2 4 6

可以看到，還在數(shù)據(jù)位置不變的只有2個： 1，2，位置發(fā)生改變的有4個，占共6個數(shù)據(jù)的比率是 4/6 = 2/3這樣的話，受影響的數(shù)據(jù)太多了，勢必太多的數(shù)據(jù)需要重新從 DB 加載到 cache 中，嚴(yán)重影響性能

【consistent hashing 的辦法】
上面提到的 hash 取模，模數(shù)取的比較小，一般是負(fù)載的數(shù)量，而 consistent hashing 的本質(zhì)是將模數(shù)取的比較大，為 2的32次方減1，即一個最大的 32 位整數(shù)。然后，就可以從容的安排數(shù)據(jù)導(dǎo)向了，那個圖還是挺直觀的。
以下部分為一致性哈希算法的一種php實(shí)現(xiàn)。點(diǎn)擊下載

php技術(shù)：一致性哈希算法以及其PHP實(shí)現(xiàn)詳細(xì)解析，轉(zhuǎn)載需保留來源！

鄭重聲明：本文版權(quán)歸原作者所有，轉(zhuǎn)載文章僅為傳播更多信息之目的，如作者信息標(biāo)記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。