本文實例講述了PHP實現(xiàn)的一致性Hash算法。分享給大家供大家參考，具體如下：

一致性哈希算法是分布式系統(tǒng)中常用的算法，為什么要用這個算法？

比如：一個分布式存儲系統(tǒng)，要將數(shù)據(jù)存儲到具體的節(jié)點（服務器）上， 在服務器數(shù)量不發(fā)生改變的情況下，如果采用普通的hash再對服務器總數(shù)量取模的方法（如key%服務器總數(shù)量），如果期間有服務器宕機了或者需要增加服務器，問題就出來了。 同一個key經(jīng)過hash之后，再與服務器總數(shù)量取模的結果跟之前的結果會不一樣，這就導致了之前保存數(shù)據(jù)的丟失。因此，引入了一致性Hash（Consistent Hashing）分布算法

把數(shù)據(jù)用hash函數(shù)（如md5，sha1)，映射到一個圓環(huán)上，如上圖所示，數(shù)據(jù)在存儲時，先根據(jù)hash算法算出key的hash值，對應到這個環(huán)中的位置，如k1對應圖中所示的位置同，然后沿著順時針方向找到服務器節(jié)點B，然后把k1在存到B這個節(jié)點中。

如果B節(jié)點宕機了，則B上的數(shù)據(jù)就會落到C節(jié)點上，如下圖所示

這樣，只會影響C節(jié)點，對于其他節(jié)點A、D的數(shù)據(jù)不會造成影響。但是問題來了，這樣會造成C節(jié)點負載過重的情況，因為C節(jié)點承擔了B節(jié)點的數(shù)據(jù)，所以C節(jié)點容易宕機，這樣造成了分布不均勻。

為了解決這個問題，引入了“虛擬節(jié)點“的概念：即想象空上環(huán)上有很多”虛擬節(jié)點“，一個真實的服務器節(jié)點對應多個虛擬節(jié)點，數(shù)據(jù)存儲的時候沿著環(huán)的順時針方向找到虛擬節(jié)點，就找到了對應的真實服務器節(jié)點。如下圖

圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節(jié)點，機器A負載存儲A1、A2的數(shù)據(jù)，機器B負載存儲B1、B2的數(shù)據(jù)，機器C負載存儲C1、C2的數(shù)據(jù)。由于這些虛擬節(jié)點數(shù)量很多，均勻分布，因此不會造成“雪崩”現(xiàn)象。

一致性哈希算法的PHP實現(xiàn)

下面給出一個接口

/**
 * 一致性哈希實現(xiàn)接口
 * Interface ConsistentHash
 */
interface ConsistentHash
{
 //將字符串轉為hash值
 public function cHash($str);
 //添加一臺服務器到服務器列表中
 public function addServer($server);
 //從服務器刪除一臺服務器
 public function removeServer($server);
 //在當前的服務器列表中找到合適的服務器存放數(shù)據(jù)
 public function lookup($key);
}