PHP實作一致性雜湊演算法的詳細介紹（程式碼範例）

這篇文章帶給大家的內容是關於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中文網其他相關文章！