PHP實現(xiàn)一致性哈希算法的詳細介紹（代碼示例）

2020-03-22 17:49:18

字體：大中小

供稿：網(wǎng)友

本篇文章給大家?guī)淼膬?nèi)容是關(guān)于PHP實現(xiàn)一致性哈希算法的詳細介紹（代碼示例），有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。

一、案例分析
（1）問題概述

假設(shè)我們的圖片數(shù)據(jù)均勻的分配在三臺服務(wù)（分別標注為服務(wù)器A，服務(wù)器B、服務(wù)器C）上面，現(xiàn)在我們要從里面取圖片，服務(wù)端在拿到這個請求后，怎么會指定，這張圖片是存在服務(wù)器A、服務(wù)器B，還是服務(wù)器C上面呢？若是去遍歷，兩三臺還好說，但那也太out了，當服務(wù)器的數(shù)量達到成百上千臺的時候，還敢說去遍歷嗎？

（2）解決方案

a、通過存儲映射關(guān)系

首先我們可能會想到，可以搞一個中間層來記錄圖片存儲在哪個服務(wù)器上面，如下：

logo1.png =====》服務(wù)A

ogo2.png =====》服務(wù)B

logo3.png =====》服務(wù)C

這樣，每當請求過來的時候，我們先去請求圖片與服務(wù)器的映射關(guān)系，找到圖片存儲的服務(wù)器，在向指定的服務(wù)器發(fā)出請求。從實現(xiàn)的角度來說，這是可行的，但是在存儲圖片的時候，我們也必須存儲圖片與服務(wù)器的映射關(guān)系，這明顯加大了工作量，其維護也是一個問題，一旦存儲的圖片和服務(wù)器映射關(guān)系出現(xiàn)了問題，整個系統(tǒng)就掛了。

b、hash算法

既然我們要排除存儲映射關(guān)系，這個時候，人們想到了hash算法。如

圖片在存儲的時候，依據(jù)圖片名稱（logo1.png），通過hash算法求出散列值val，通過對val進行取模，得出的值，就可以判斷圖片應(yīng)該存儲在哪個服務(wù)器上面。如下：

key = hash(imgName) % n

其中：

imgName為圖片名稱，

n為服務(wù)器的個數(shù)，

key代表圖片應(yīng)該存儲在第幾個服務(wù)器上面。

當請求過來的時候，比如請求logo1.png這個圖片，服務(wù)端依據(jù)上述公式計算出的key，就可以判斷該logo1.png存儲在哪個服務(wù)器上面。PHP實現(xiàn)如下：

$hostsMap = [ img1.findme.wang , img2.findme.wang , img3.findme.wang function getImgSrc($imgName) { global $hostsMap; $key = crc32($imgName) % count($hostsMap); return http:// . $hostsMap[abs($key)] . / . $imgName;var_dump(getImgSrc( logo1.png ));var_dump(getImgSrc( logo2.png ));var_dump(getImgSrc( logo3.png ));

輸出：

此時，我們由存儲映射關(guān)系變?yōu)橛嬎惴?wù)器的序號，確實極大的簡化了工作量。

但是一旦新增機器，就非常麻煩了，因為n變了，幾乎所有的序列號key也變了，于是需要大量的數(shù)據(jù)遷移工作。

C、一致性hash算法

一致性hash算法，是一種特殊的hash算法，旨在解決當node數(shù)（如存儲圖片的服務(wù)器數(shù)量）變化時候，盡量少數(shù)據(jù)的遷移。

其基本思想：

1、首先把0~2的32次方個點，均勻的分布到一個圓環(huán)上面，如下：

2、然后將所有的節(jié)點node（存儲圖片的服務(wù)器）通過hash計算后，對232取余，然后也映射到hash環(huán)上面，如下：

3、當請求過來的時候，比如請求logo1.png這個圖片，通過hash計算后，對232取余，然后也映射到hash環(huán)上面，如下：

4、然后順時針轉(zhuǎn)動，第一個到達的節(jié)點node，就認為是存儲logo1.png圖片的服務(wù)器。

從上面可以得知，其實一致性hash的亮點，首先在于對節(jié)點node（存儲圖片的服務(wù)器）和對象（圖片）都進行了hash計算和映射，其次是閉環(huán)的設(shè)計。

優(yōu)點：當新增機器的時候，僅僅標志出來的區(qū)域受到影響，如下圖：

缺點：當節(jié)點node比較少的時候，往往缺少平衡性，因為經(jīng)過hash計算后，映射到hash環(huán)上面的節(jié)點node，并不是均勻分布的，導(dǎo)致了有的機器負載很高，有的機器很空閑。

PHP實現(xiàn)如下：

$hostsMap = [ img1.findme.wang , img2.findme.wang , img3.findme.wang $hashRing = [];function getImgSrc($imgName){ global $hostsMap; global $hashRing; //將節(jié)點映射到hash環(huán)上面 if (empty($hashRing)) { foreach($hostsMap as $h) { $hostKey = fmod(crc32($h) , pow(2,32)); $hostKey = abs($hostKey); $hashRing[$hostKey] = $h; //從小到大排序，便于查找 ksort($hashRing); //計算圖片hash $imgKey = fmod(crc32($imgName) , pow(2,32)); $imgKey = abs($imgKey); foreach($hashRing as $hostKey = $h) { if ($imgKey $hostKey) { return http:// . $h . / . $imgName; return http:// . html' target='_blank'>current($hashRing) . / . $imgName;var_dump(getImgSrc( logo1.png ));var_dump(getImgSrc( logo2.png ));var_dump(getImgSrc( logo3.png ));

輸出結(jié)果如下：

至于為什么使用fmod函數(shù)不適用求余運算符%，主要是因為pow(2,32)在32位操作系統(tǒng)上面，超高了PHP_INT_MAX，具體可以參考上一篇文章“PHP中對大數(shù)求余報錯Uncaught pisionByZeroError: Modulo by zero”。

d、通過虛擬節(jié)點優(yōu)化一致性hash算法

為了提高一致性hash算法的平衡性，我們首先能夠想到的是，增加節(jié)點數(shù)，但是機器畢竟是需要經(jīng)費啊，不是說增就能隨意增，那就增加虛擬節(jié)點，這樣就沒毛病了。思路如下：

1、假設(shè)host1、host2、host3，都分別有3個虛擬節(jié)點，如host1的虛擬節(jié)點為host1_1、host1_2、host1_3

2、然后將所有的虛擬節(jié)點node（存儲圖片的服務(wù)器）通過hash計算后，對232取余，然后也映射到hash環(huán)上面，如下：

然后，接下來步驟同一致性hash算法一致，只是最后需要將虛擬節(jié)點，轉(zhuǎn)為真實的節(jié)點。

PHP實現(xiàn)如下：

$hostsMap = [ img1.findme.wang , img2.findme.wang , img3.findme.wang $hashRing = [];function getImgSrc($imgName){ global $hostsMap; global $hashRing; $virtualNodeLen = 3; //每個節(jié)點的虛擬節(jié)點個數(shù) //將節(jié)點映射到hash環(huán)上面 if (empty($hashRing)) { foreach($hostsMap as $h) { $i = 0; while($i $virtualNodeLen){ $hostKey = fmod(crc32($h. _ .$i) , pow(2,32)); $hostKey = abs($hostKey); $hashRing[$hostKey] = $h; $i++; //從小到大排序，便于查找 ksort($hashRing); //計算圖片hash $imgKey = fmod(crc32($imgName) , pow(2,32)); $imgKey = abs($imgKey); foreach($hashRing as $hostKey = $h) { if ($imgKey $hostKey) { return http:// . $h . / . $imgName; return http:// . current($hashRing) . / . $imgName;var_dump(getImgSrc( login1.png ));var_dump(getImgSrc( login2.png ));var_dump(getImgSrc( login3.png ));

執(zhí)行結(jié)果如下：