第如何用PHP實現分布算法之一致性哈希算法目錄傳統算法缺陷算法思想算法實現總結

傳統算法缺陷

對于服務器分布，我們要考慮的東西有如下三點：數據平均分布，查找定位準確，降低宕機影響。

傳統算法一般是將數據的鍵用算法映射出數字，對其用服務器數量取模，并根據結果選擇要存儲的服務器。其能達到數據平均分布和查找定位準確的要求，并且優點是算法簡單，存取時的計算量都比較?。ㄔ跀祿浅４髸r才會明顯）。

但其有一個致命缺點，即一個服務器宕機后的影響很大，我們可以推算一下一臺服務器宕機后的影響：

原有數據大部分丟失：服務器數量減少一臺，取模數減1導致取模值錯亂，如果以前有N臺服務器，那么宕機后數據只有1/(n*(n-1))的數據能夠被準確查找到。

負載無法均衡導致集體宕機：如果沒有及時處理宕機的服務器，那么他的存儲任務將會被順序積累給它的下一個服務器，那么下一個服務器也會很快被壓致宕機，如此一來，服務器組很快會集體宕機。

算法思想

一致性哈希算法是使用一定的哈希算法，將大量的數據平均映射到不同的存儲目標上，在保證其查找準確性的同時，還要考慮其中一個存儲目標失效時，其他存儲目標對其責任存儲內容的負載均衡。

一致性哈希算法的實現思想不難理解，如圖：

1.用一定的哈希算法（哈希函數等）將一組服務器的多個（數目自己設定）節點隨機映射分散到0-232之間，由于其隨機分布，保證了其數據平均分布的特點；

2.用同一算法計算要存儲數據的鍵，根據服務器節點確定其存儲的服務器結點，由于每次用同一算法計算，所以得出的結果是相同的，使其查找定位準確；

3.查找數據時，再次用同一算法計算鍵，并查找服務器的數據結點；

4.如果有一個服務器宕機，消除其服務器結點，并將數據放在下一個結點上，由于隨機節點位置的隨機性，所以數據被其他服務器平均負載，也就降低了宕機影響。

需要注意的是，這個環形空間只是一個虛擬空間，只是表示了服務器存儲的范圍和數據的落點，在進行存儲時，我們還要通過查找到的落點，將數據放入對應的服務器進行查改。

算法實現

編程語言我們使用PHP來實現一致性哈希算法：

我們主要用到以下函數：

intcrc32(string$str)

生成str的32位循環冗余校驗碼多項式。這通常用于檢查傳輸的數據是否完整。

stringsprintf(string$format[,mixed$args[,mixed$...]])

通過傳入的格式產生字符串的特定格式形態。

實現如下：

classConsistance

protected$num=24;//設定每一個服務器的節點數，數量越多，宕機時服務器負載就會分布得越平均，但也增大數據查找消耗。

protected$nodes=array();//當前服務器組的結點列表。

//計算一個數據的哈希值，用以確定位置

publicfunctionmake_hash($data)

returnsprintf('%u',crc32($data));

//遍歷當前服務器組的節點列表，確定需要存儲/查找的服務器

publicfunctionset_loc($data)

$loc=self::make_hash($data);

foreach($this-nodesas$key=$val)

if($loc=$key)

return$val;

//添加一個服務器，將其結點添加到服務器組的節點列表內。

publicfunctionadd_host($host)

for($i=0;$i$this-$i++)

$key=sprintf('%u',crc32($host.'_'.$i));

$this-nodes[$key]=$host;

ksort($this-nodes);//對結點排序，這樣便于查找。

//刪除一個服務器，并將其對應節點從服務器組的節點列表內移除。

publicfunctionremove_host($host)

for($i=0;$i$this-$i++)

$key=sprintf('%u',crc32($host.'_'.$i));

unset($this-nodes[$key]);

}

我們用以下代碼進行測試：

結果如下：

總結

算法的實現到此，我們還可以對算法進行優化，如在服務器數量和每個服務器節點數都很多的情況下，對查找結點的過程進行優化，因為排序好的，可以用二分法進行查找，加快查詢效率，這些，仁智各見吧。

另外，雖然nginx服務器有一致性算法的插件，memcache和redis也都有相應的插件，MySQL的中間件有相應的集成，但是了解一