這篇文章帶給大家的內容是關於PHP實作一致性雜湊演算法的詳細介紹（程式碼範例），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。
一、案例分析
（1）問題概述
假設我們的圖片資料均勻的分配在三台服務（分別標註為伺服器A，伺服器B、伺服器C）上面，現在我們要從裡面拿圖片，服務端拿到這個請求後，怎麼會指定，這張圖片是存在伺服器A、伺服器B，還是伺服器C上面呢？若是去遍歷，兩三台還好說，但那也太out了，當伺服器的數量達到成百上千台的時候，還敢說去遍歷嗎？
（2）解決方案
a、透過儲存映射關係
首先我們可能會想到，可以搞一個中間層來記錄圖片存儲在哪個伺服器上面，如下：
logo1.png =====》 服務A
ogo2.png =====》服務 B
logo3.png == ===》 服務C
這樣，每當請求過來的時候，我們先去請求圖片與伺服器的映射關係，找到圖片儲存的伺服器，在向指定的伺服器發出請求。從實現的角度來說，這是可行的，但是在儲存圖片的時候，我們也必須儲存圖片與伺服器的映射關係，這明顯加大了工作量，其維護也是一個問題，一旦儲存的圖片和伺服器映射關係出現了問題，整個系統掛了。
b、hash演算法
既然我們要排除儲存映射關係，這個時候，人們想到了hash演算法。如
圖片在儲存的時候，依據圖片名稱（logo1.png），透過hash演算法求出雜湊值val，透過對val進行取模，得出的值，就可以判斷圖片應該儲存在哪個伺服器上面。如下：
key = hash(imgName) % n
其中：
imgName為圖片名稱，
n為伺服器的個數，
key代表圖片應該儲存在第幾個伺服器上面。
當請求過來的時候，例如請求logo1.png這個圖片，服務端依據上述公式計算出的key，就可以判斷該logo1.png儲存在哪個伺服器上面。 PHP實作如下：
$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"));輸出：
此時，我們由儲存對應關係變成運算伺服器的序號，確實極大的簡化了工作量。
但一旦新增機器，就非常麻煩了，因為n變了，幾乎所有的序號key也變了，於是需要大量的資料遷移工作。
C、一致性hash演算法
一致性hash演算法，是一種特殊的hash演算法，旨在解決當node數（如儲存圖片的伺服器數量）變化時候，盡量少資料的遷移。
其基本思想：
1、先把0~2的32次方個點，均勻的分佈到一個圓環上面，如下：
2、然後將所有的節點node（儲存圖片的伺服器）經過hash計算後，對232取餘，然後也映射到hash環上面，如下：
3、當請求過來的時候，例如請求logo1.png這個圖片，透過hash計算後，對232取餘，然後也映射到hash環上面，如下：
4、然後順時針轉動，第一個到達的節點node，就認為是儲存logo1.png圖片的伺服器。
從上面可以得知，其實一致性hash的亮點，首先在於對節點node（儲存圖片的伺服器）和物件（圖片）都進行了hash計算和映射，其次是閉環的設計。
優點：當新增機器的時候，僅僅標誌出來的區域受到影響，如下圖：
#缺點：當節點node比較少的時候，往往缺乏平衡性，因為經過hash計算後，映射到hash環上面的節點node，並不是均勻分佈的，導致了有的機器負載很高，有的機器很空閒。
PHP實作如下：
$hostsMap = ['img1.findme.wang', 'img2.findme.wang', 'img3.findme.wang'];
$hashRing = [];
function getImgSrc($imgName){
global $hostsMap;
global $hashRing;
//将节点映射到hash环上面
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 <p>輸出結果如下：</p><p><img src="https://img.php.cn/upload/image/534/248/963/1551677736513489.png" title="1551677736513489.png" alt="PHP實作一致性雜湊演算法的詳細介紹（程式碼範例）"></p><p>至于为什么使用fmod函数不适用求余运算符%，主要是因为pow(2,32)在32位操作系统上面，超高了PHP_INT_MAX，具体可以参考上一篇文章“PHP中对大数求余报错Uncaught pisionByZeroError: Modulo by zero”。</p><p>d、通过虚拟节点优化一致性hash算法</p><p>为了提高一致性hash算法的平衡性，我们首先能够想到的是，增加节点数，但是机器毕竟是需要经费啊，不是说增就能随意增，那就增加虚拟节点，这样就没毛病了。思路如下：</p><p>1、假设host1、host2、host3，都分别有3个虚拟节点，如host1的虚拟节点为host1_1、host1_2、host1_3</p><p>2、然后将所有的虚拟节点node（存储图片的服务器）通过hash计算后，对232取余，然后也映射到hash环上面，如下：</p><p><img src="https://img.php.cn/upload/image/891/291/577/1551677752319649.png" title="1551677752319649.png" alt="PHP實作一致性雜湊演算法的詳細介紹（程式碼範例）"></p><p>然后，接下来步骤同一致性hash算法一致，只是最后需要将虚拟节点，转为真实的节点。</p><p>PHP实现如下：</p><pre class="brush:php;toolbar:false">$hostsMap = ['img1.findme.wang', 'img2.findme.wang', 'img3.findme.wang'];
$hashRing = [];
function getImgSrc($imgName){
global $hostsMap;
global $hashRing;
$virtualNodeLen = 3; //每个节点的虚拟节点个数
//将节点映射到hash环上面
if (empty($hashRing)) {
foreach($hostsMap as $h) {
$i = 0;
while($i $h) {
if ($imgKey <p>执行结果如下：</p><p><img src="https://img.php.cn/upload/image/947/947/423/1551677769758146.png" title="1551677769758146.png" alt="PHP實作一致性雜湊演算法的詳細介紹（程式碼範例）"></p><p><strong>二、备注</strong><br>1、取模与取余的区别？</p><p>取余，遵循尽可能让商向0靠近的原则</p><p>取模，遵循尽可能让商向负无穷靠近的原则</p><p>1、什么是CRC算法？</p><p>CRC（Cyclical Redundancy Check）即循环冗余码校验，主要用于数据校验，常用的有CRC16、CRC32，其中16、32代表多项式最高次幂。</p><p></p>以上是PHP實作一致性雜湊演算法的詳細介紹（程式碼範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！
