通過PHP實現一致性哈希算法

tulayang 發布于2019-07-01 12:32 / 2132人閱讀

摘要：通過虛擬節點優化一致性算法為了提高一致性算法的平衡性，我們首先能夠想到的是，增加節點數，但是機器畢竟是需要經費啊，不是說增就能隨意增，那就增加虛擬節點，這樣就沒毛病了。

一、案例分析
（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 < $hostKey) {
            return "http://" . $h . "/" . $imgName;
        }
    }
    return "http://" . current($hashRing) . "/" . $imgName;
}
 
var_dump(getImgSrc("logo1.png"));
var_dump(getImgSrc("logo2.png"));
var_dump(getImgSrc("logo3.png"));

輸出結果如下：

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

d、通過虛擬節點優化一致性hash算法

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

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

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

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

PHP實現如下：

$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 < $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"));

執行結果如下：

二、備注
1、取模與取余的區別？

取余，遵循盡可能讓商向0靠近的原則

取模，遵循盡可能讓商向負無窮靠近的原則

1、什么是CRC算法？

CRC（Cyclical Redundancy Check）即循環冗余碼校驗，主要用于數據校驗，常用的有CRC16、CRC32，其中16、32代表多項式最高次冪。

GPU云服務器云服務器一致性哈希算法哈希一致性一致性哈希 golang 一致性哈希

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/30928.html

[PHP內核探索]PHP中的哈希表

摘要：的介紹哈希表是實現字典操作的一種有效數據結構。因此，實現一個好的哈希表的關鍵就是一個好的哈希函數和處理哈希沖突的方法。取而代之的是通過應用哈希表的，然后只取哈希表的低位。由上面可以看到，的哈希表實現相當復雜。在PHP內核中，其中一個很重要的數據結構就是HashTable。我們常用的數組，在內核中就是用HashTable來實現。那么，PHP的HashTable是怎么實現的呢？最近在看H...

Yuanf 2019-06-27 14:00 評論0 收藏0
memcached分布式原理與實現

摘要：哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。平衡性平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。 memcached分布式原理與實現標簽（空格分隔）： nosql 0x01 概況 1.1 什么是memcached memcached是一個分布式，開源的數據存儲引擎。memcach...

Ververica 2019-08-06 12:27 評論0 收藏0
memcached分布式原理與實現

摘要：哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。平衡性平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。 memcached分布式原理與實現標簽（空格分隔）： nosql 0x01 概況 1.1 什么是memcached memcached是一個分布式，開源的數據存儲引擎。memcach...

LiuRhoRamen 2019-06-24 18:07 評論0 收藏0
什么是一致性Hash算法？

摘要：五一致性算法的容錯性和可擴展性現假設不幸宕機，可以看到此時對象不會受到影響，只有對象被重定位到。綜上所述，一致性算法對于節點的增減都只需重定位環空間中的一小部分數據，具有較好的容錯性和可擴展性。最近有小伙伴跑過來問什么是Hash一致性算法，說面試的時候被問到了，因為不了解，所以就沒有回答上，問我有沒有相應的學習資料推薦，當時上班，沒時間回復，晚上回去了就忘了這件事，今天突然看到這個，...

feng409 2019-07-01 12:32 評論0 收藏0
如何對用戶密碼進行加密

摘要：結論對用戶密碼進行加密時需要做到防止用戶密碼明文被竊聽交給，明文傳輸。為什么鹽可以明文存儲攻擊者很難有足夠的計算資源和存儲空間建立海量的哈希值密碼數據庫，針對單條用戶記錄，建立哈希值密碼數據庫進行攻擊的成本過高。摘要密碼驗證是很常見的需求，如何在實現功能之余，防止用戶密碼泄露，已經有了很成熟的方案。這篇文章把自己的思考和結論做一下記錄。結論對用戶密碼進行加密時需要做到：防止用...

張率功 2019-06-28 14:31 評論0 收藏0