是一個(gè)集中式單點(diǎn)緩存系統(tǒng)，不具備集群功能。此操作主要由客戶(hù)端完成。

所以說(shuō)到分布式，肯定會(huì)提到客戶(hù)端?？聪聢D：

簡(jiǎn)單來(lái)說(shuō)，這里的客戶(hù)端做了一個(gè)路由功能，負(fù)責(zé)將不同的請(qǐng)求轉(zhuǎn)發(fā)到對(duì)應(yīng)的機(jī)器（實(shí)例）。

那么客戶(hù)端如何確定將特定請(qǐng)求轉(zhuǎn)發(fā)到哪臺(tái)機(jī)器？

在上面的場(chǎng)景中，我們可以在每次訪問(wèn)數(shù)據(jù)時(shí)根據(jù)緩存key計(jì)算出hash值一致性hash算法php開(kāi)源，然后根據(jù)實(shí)際的機(jī)器數(shù)量來(lái)定位我們想要的機(jī)器（這里只是舉例，實(shí)際環(huán)境往往更復(fù)雜），

而且，在存儲(chǔ)數(shù)據(jù)和獲取數(shù)據(jù)時(shí)，同一臺(tái)機(jī)器定位。它會(huì)滿(mǎn)足我們的需求嗎？

是的，正常情況下可以滿(mǎn)足我們的需求，為什么是正常的？

因?yàn)樵趯?shí)際生產(chǎn)環(huán)境中肯定會(huì)出現(xiàn)一些意外情況。比如上面三臺(tái)機(jī)器中的一臺(tái)突然宕機(jī)了，或者我想加一臺(tái)，會(huì)不會(huì)出現(xiàn)這個(gè)問(wèn)題？起來(lái)了？

由于機(jī)器數(shù)量的變化，所有原來(lái)的緩存無(wú)法正確定位，無(wú)法再使用。這在一些高并發(fā)系統(tǒng)中往往是致命的。

有沒(méi)有更好的方法可以在機(jī)器宕機(jī)的情況下進(jìn)行平滑升級(jí)并盡可能保持正常運(yùn)行？

這個(gè)當(dāng)然有，就是我們接下來(lái)要講的一致性哈希算法。

當(dāng)我第一次看到一致性哈希算法這個(gè)詞時(shí)，我腦海中的第一反應(yīng)就是上面的實(shí)現(xiàn)。事實(shí)上，事實(shí)并非如此。更準(zhǔn)確地說(shuō)，一致性哈希算法是一個(gè)全局概念模型，是集群部署中的一個(gè)很好的解決方案。

一致性哈希算法()早在1997年就已經(jīng)提出，目前在很多服務(wù)器中被廣泛使用，目前比較流行。

它的最終目標(biāo)是在移除或添加機(jī)器時(shí)最小化對(duì)現(xiàn)有鍵映射關(guān)系的影響。

以下是其實(shí)現(xiàn)原理的細(xì)目分類(lèi)，網(wǎng)上已經(jīng)有詳細(xì)說(shuō)明。

考慮到通常的hash算法是映射到一個(gè)32位的key值，也就是0~2^32-1次冪的數(shù)值空間；我們可以把這個(gè)空間看作是第一個(gè)（0）尾（2^32-1）個(gè)連接環(huán)，如下圖1所示。

接下來(lái)考慮4個(gè)對(duì)象~，hash函數(shù)計(jì)算出的hash值key在環(huán)上的分布如圖2所示。

hash() = key1;

…………

hash() = key4;

基本思路

是將對(duì)象映射到相同的哈希值空間，并使用相同的哈希算法。

假設(shè)當(dāng)前有3個(gè)單元A、B、C，則映射結(jié)果如圖3所示，將它們排列在對(duì)應(yīng)的hash值的hash空間中。

hash(A) = 鍵 A;

…………

hash(C) = 鍵 C;

說(shuō)到這里，順便提一下哈希計(jì)算。一般的方法可以使用機(jī)器的IP地址或機(jī)器名作為hash輸入。

既然對(duì)象和對(duì)象都通過(guò)相同的哈希算法映射到哈希值空間，接下來(lái)要考慮的是如何將對(duì)象映射到它。

在這個(gè)環(huán)形空間中，如果從對(duì)象的key值開(kāi)始順時(shí)針?lè)较?，直到遇到一個(gè)，那么就將對(duì)象存儲(chǔ)在this上，因?yàn)閷?duì)象的hash值和hash值是固定的，所以這個(gè)必須是唯一的和確定的。你沒(méi)有找到對(duì)象的映射方法嗎？ ！

繼續(xù)上面的例子（見(jiàn)圖3），那么按照上面的方法，對(duì)象就會(huì)被存儲(chǔ)在A上；并對(duì)應(yīng)于 C；對(duì)應(yīng)B;

前面說(shuō)過(guò)，先hash再計(jì)算余數(shù)的方法帶來(lái)的最大問(wèn)題是不能滿(mǎn)足單調(diào)性。當(dāng)有變化時(shí)，就會(huì)失敗，這會(huì)對(duì)后端服務(wù)器造成巨大的影響?，F(xiàn)在讓我們來(lái)分析和分析算法。 .

刪除

考慮假設(shè) B 掛斷了電話。根據(jù)上面提到的映射方法，只有那些沿著 B 逆時(shí)針遍歷直到下一個(gè)（C）的對(duì)象才會(huì)受到影響，這些對(duì)象原本是映射到 B 上的那些對(duì)象。

所以這里我們只需要改變對(duì)象，重新映射到C；見(jiàn)下圖

添加

考慮添加一個(gè)新的D，假設(shè)在這個(gè)循環(huán)的hash空間中，D在對(duì)象和之間進(jìn)行映射。此時(shí)，唯一受影響的將是那些沿 D 逆時(shí)針遍歷直到下一個(gè) (B) 的對(duì)象（它們是最初映射到 C 的對(duì)象的一部分）。將這些對(duì)象重新映射到 D。

所以這里我們只需要改變對(duì)象，重新映射到D即可；見(jiàn)下圖

另一個(gè)考慮Hash算法的指標(biāo)是()一致性hash算法php開(kāi)源，定義如下：

平衡

平衡意味著可以將哈希結(jié)果盡可能分配到所有的緩沖區(qū)，從而可以使用所有的緩沖區(qū)空間。

哈希算法不保證絕對(duì)平衡。如果對(duì)象較少，則無(wú)法均勻映射對(duì)象。例如，在上面的例子中，當(dāng)只部署了A和C時(shí)，4個(gè)對(duì)象中，A只存儲(chǔ)，C存儲(chǔ)，和；分布很不均勻。

為了解決這種情況，引入了“虛擬節(jié)點(diǎn)”的概念，可以定義如下：

“虛擬節(jié)點(diǎn)”（node）是哈?？臻g中一個(gè)實(shí)際節(jié)點(diǎn)的副本（），一個(gè)實(shí)際節(jié)點(diǎn)對(duì)應(yīng)幾個(gè)“虛擬節(jié)點(diǎn)”，這個(gè)對(duì)應(yīng)的數(shù)字也變成了“副本數(shù)”，“虛擬節(jié)點(diǎn)” “ ”在哈?？臻g中按哈希值排列。

仍然以?xún)H部署A和C的情況為例，如圖4所示，分布并不均勻?，F(xiàn)在我們引入虛擬節(jié)點(diǎn)，將“復(fù)制次數(shù)”設(shè)置為2，即總共會(huì)有4個(gè)“虛擬節(jié)點(diǎn)”，A1、A2代表A； C1、C2代表C；假設(shè)一個(gè)更理想的情況，見(jiàn)下圖

此時(shí)對(duì)象與“虛擬節(jié)點(diǎn)”的映射關(guān)系為：

-> A2; -> A1; -> C1; -> C2;

所以對(duì)象和被映射到A，和被映射到C；平衡得到了很大的改善。

引入“虛擬節(jié)點(diǎn)”后，映射關(guān)系從{ -> node}轉(zhuǎn)化為{ -> node}。查詢(xún)對(duì)象時(shí)的映射關(guān)系如圖所示。

“虛擬節(jié)點(diǎn)”的hash計(jì)算可以采用在對(duì)應(yīng)節(jié)點(diǎn)的IP地址加上數(shù)字后綴的方法。例如，假設(shè)A的IP地址為202.168.14.241。

在引入“虛擬節(jié)點(diǎn)”之前，計(jì)算A的hash值：

Hash("202.168.14.241");

引入“虛擬節(jié)點(diǎn)”后，計(jì)算“虛擬節(jié)點(diǎn)”點(diǎn)A1和A2的hash值：

Hash("202.168.14.241#1"); // A1

Hash("202.168.14.241#2"); // A2

基本原則是這些。具體分布的理論分析應(yīng)該很復(fù)雜，但一般不使用。

上面有java版本的例子，可以參考。

轉(zhuǎn)載了一個(gè)PHP版本的實(shí)現(xiàn)代碼。

C 語(yǔ)言版本

查看本文的一致性哈希算法：