摘要：通過虛擬節(jié)點(diǎn)優(yōu)化一致性算法為了提高一致性算法的平衡性，我們首先能夠想到的是，增加節(jié)點(diǎn)數(shù)，但是機(jī)器畢竟是需要經(jīng)費(fèi)啊，不是說增就能隨意增，那就增加虛擬節(jié)點(diǎn)，這樣就沒毛病了。

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

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

（2）解決方案

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

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

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

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

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

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

b、hash算法

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

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

key = hash(imgName) % n

其中：

imgName為圖片名稱，

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

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

當(dāng)請(qǐng)求過來的時(shí)候，比如請(qǐng)求logo1.png這個(gè)圖片，服務(wù)端依據(jù)上述公式計(jì)算出的key，就可以判斷該logo1.png存儲(chǔ)在哪個(gè)服務(wù)器上面。PHP實(shí)現(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;
}
//測(cè)試
var_dump(getImgSrc("logo1.png"));
var_dump(getImgSrc("logo2.png"));
var_dump(getImgSrc("logo3.png"));

輸出：

此時(shí)，我們由存儲(chǔ)映射關(guān)系變?yōu)橛?jì)算服務(wù)器的序號(hào)，確實(shí)極大的簡(jiǎn)化了工作量。

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

C、一致性hash算法

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

其基本思想：

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

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

3、當(dāng)請(qǐng)求過來的時(shí)候，比如請(qǐng)求logo1.png這個(gè)圖片，通過hash計(jì)算后，對(duì)232取余，然后也映射到hash環(huán)上面，如下：

4、然后順時(shí)針轉(zhuǎn)動(dòng)，第一個(gè)到達(dá)的節(jié)點(diǎn)node，就認(rèn)為是存儲(chǔ)logo1.png圖片的服務(wù)器。

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

優(yōu)點(diǎn)：當(dāng)新增機(jī)器的時(shí)候，僅僅標(biāo)志出來的區(qū)域受到影響，如下圖：

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

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

$hostsMap = ["img1.findme.wang", "img2.findme.wang", "img3.findme.wang"];
$hashRing = [];
 
function getImgSrc($imgName){
    global $hostsMap;
    global $hashRing;
    //將節(jié)點(diǎn)映射到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);
    }
 
    //計(jì)算圖片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"));

輸出結(jié)果如下：

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

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

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

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

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

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

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

$hostsMap = ["img1.findme.wang", "img2.findme.wang", "img3.findme.wang"];
$hashRing = [];
 
function getImgSrc($imgName){
    global $hostsMap;
    global $hashRing;
    $virtualNodeLen = 3; //每個(gè)節(jié)點(diǎn)的虛擬節(jié)點(diǎn)個(gè)數(shù)
 
    //將節(jié)點(diǎn)映射到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);
    }
 
    //計(jì)算圖片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é)果如下：

二、備注
1、取模與取余的區(qū)別？

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

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

1、什么是CRC算法？

CRC（Cyclical Redundancy Check）即循環(huán)冗余碼校驗(yàn)，主要用于數(shù)據(jù)校驗(yàn)，常用的有CRC16、CRC32，其中16、32代表多項(xiàng)式最高次冪。