如何用PHP實(shí)現(xiàn)分布算法之一致性哈希算法

第如何用PHP實(shí)現(xiàn)分布算法之一致性哈希算法目錄傳統(tǒng)算法缺陷算法思想算法實(shí)現(xiàn)總結(jié)

傳統(tǒng)算法缺陷

對(duì)于服務(wù)器分布，我們要考慮的東西有如下三點(diǎn)：數(shù)據(jù)平均分布，查找定位準(zhǔn)確，降低宕機(jī)影響。

傳統(tǒng)算法一般是將數(shù)據(jù)的鍵用算法映射出數(shù)字，對(duì)其用服務(wù)器數(shù)量取模，并根據(jù)結(jié)果選擇要存儲(chǔ)的服務(wù)器。其能達(dá)到數(shù)據(jù)平均分布和查找定位準(zhǔn)確的要求，并且優(yōu)點(diǎn)是算法簡單，存取時(shí)的計(jì)算量都比較?。ㄔ跀?shù)據(jù)非常大時(shí)才會(huì)明顯）。

但其有一個(gè)致命缺點(diǎn)，即一個(gè)服務(wù)器宕機(jī)后的影響很大，我們可以推算一下一臺(tái)服務(wù)器宕機(jī)后的影響：

原有數(shù)據(jù)大部分丟失：服務(wù)器數(shù)量減少一臺(tái)，取模數(shù)減1導(dǎo)致取模值錯(cuò)亂，如果以前有N臺(tái)服務(wù)器，那么宕機(jī)后數(shù)據(jù)只有1/(n*(n-1))的數(shù)據(jù)能夠被準(zhǔn)確查找到。

負(fù)載無法均衡導(dǎo)致集體宕機(jī)：如果沒有及時(shí)處理宕機(jī)的服務(wù)器，那么他的存儲(chǔ)任務(wù)將會(huì)被順序積累給它的下一個(gè)服務(wù)器，那么下一個(gè)服務(wù)器也會(huì)很快被壓致宕機(jī)，如此一來，服務(wù)器組很快會(huì)集體宕機(jī)。

算法思想

一致性哈希算法是使用一定的哈希算法，將大量的數(shù)據(jù)平均映射到不同的存儲(chǔ)目標(biāo)上，在保證其查找準(zhǔn)確性的同時(shí)，還要考慮其中一個(gè)存儲(chǔ)目標(biāo)失效時(shí)，其他存儲(chǔ)目標(biāo)對(duì)其責(zé)任存儲(chǔ)內(nèi)容的負(fù)載均衡。

一致性哈希算法的實(shí)現(xiàn)思想不難理解，如圖：

1.用一定的哈希算法（哈希函數(shù)等）將一組服務(wù)器的多個(gè)（數(shù)目自己設(shè)定）節(jié)點(diǎn)隨機(jī)映射分散到0-232之間，由于其隨機(jī)分布，保證了其數(shù)據(jù)平均分布的特點(diǎn)；

2.用同一算法計(jì)算要存儲(chǔ)數(shù)據(jù)的鍵，根據(jù)服務(wù)器節(jié)點(diǎn)確定其存儲(chǔ)的服務(wù)器結(jié)點(diǎn)，由于每次用同一算法計(jì)算，所以得出的結(jié)果是相同的，使其查找定位準(zhǔn)確；

3.查找數(shù)據(jù)時(shí)，再次用同一算法計(jì)算鍵，并查找服務(wù)器的數(shù)據(jù)結(jié)點(diǎn)；

4.如果有一個(gè)服務(wù)器宕機(jī)，消除其服務(wù)器結(jié)點(diǎn)，并將數(shù)據(jù)放在下一個(gè)結(jié)點(diǎn)上，由于隨機(jī)節(jié)點(diǎn)位置的隨機(jī)性，所以數(shù)據(jù)被其他服務(wù)器平均負(fù)載，也就降低了宕機(jī)影響。

需要注意的是，這個(gè)環(huán)形空間只是一個(gè)虛擬空間，只是表示了服務(wù)器存儲(chǔ)的范圍和數(shù)據(jù)的落點(diǎn)，在進(jìn)行存儲(chǔ)時(shí)，我們還要通過查找到的落點(diǎn)，將數(shù)據(jù)放入對(duì)應(yīng)的服務(wù)器進(jìn)行查改。

算法實(shí)現(xiàn)

編程語言我們使用PHP來實(shí)現(xiàn)一致性哈希算法：

我們主要用到以下函數(shù)：

intcrc32(string$str)

生成str的32位循環(huán)冗余校驗(yàn)碼多項(xiàng)式。這通常用于檢查傳輸?shù)臄?shù)據(jù)是否完整。

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

通過傳入的格式產(chǎn)生字符串的特定格式形態(tài)。

實(shí)現(xiàn)如下：

classConsistance

protected$num=24;//設(shè)定每一個(gè)服務(wù)器的節(jié)點(diǎn)數(shù)，數(shù)量越多，宕機(jī)時(shí)服務(wù)器負(fù)載就會(huì)分布得越平均，但也增大數(shù)據(jù)查找消耗。

protected$nodes=array();//當(dāng)前服務(wù)器組的結(jié)點(diǎn)列表。

//計(jì)算一個(gè)數(shù)據(jù)的哈希值，用以確定位置

publicfunctionmake_hash($data)

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

//遍歷當(dāng)前服務(wù)器組的節(jié)點(diǎn)列表，確定需要存儲(chǔ)/查找的服務(wù)器

publicfunctionset_loc($data)

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

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

if($loc=$key)

return$val;

//添加一個(gè)服務(wù)器，將其結(jié)點(diǎn)添加到服務(wù)器組的節(jié)點(diǎn)列表內(nèi)。

publicfunctionadd_host($host)

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

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

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

ksort($this-nodes);//對(duì)結(jié)點(diǎn)排序，這樣便于查找。

//刪除一個(gè)服務(wù)器，并將其對(duì)應(yīng)節(jié)點(diǎn)從服務(wù)器組的節(jié)點(diǎn)列表內(nèi)移除。

publicfunctionremove_host($host)

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

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

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

}

我們用以下代碼進(jìn)行測試：

結(jié)果如下：

總結(jié)

算法的實(shí)現(xiàn)到此，我們還可以對(duì)算法進(jìn)行優(yōu)化，如在服務(wù)器數(shù)量和每個(gè)服務(wù)器節(jié)點(diǎn)數(shù)都很多的情況下，對(duì)查找結(jié)點(diǎn)的過程進(jìn)行優(yōu)化，因?yàn)榕判蚝玫?，可以用二分法進(jìn)行查找，加快查詢效率，這些，仁智各見吧。

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