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

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

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

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

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

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

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

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

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

下面給出一個(gè)接口

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