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

所以說到分布式，肯定會提到客戶端。看下圖：

簡單來說，這里的客戶端做了一個路由功能，負責將不同的請求轉(zhuǎn)發(fā)到對應的機器（實例）。

那么客戶端如何確定將特定請求轉(zhuǎn)發(fā)到哪臺機器？

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

而且，在存儲數(shù)據(jù)和獲取數(shù)據(jù)時，同一臺機器定位。它會滿足我們的需求嗎？

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

因為在實際生產(chǎn)環(huán)境中肯定會出現(xiàn)一些意外情況。比如上面三臺機器中的一臺突然宕機了，或者我想加一臺，會不會出現(xiàn)這個問題？起來了？

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

有沒有更好的方法可以在機器宕機的情況下進行平滑升級并盡可能保持正常運行？

這個當然有，就是我們接下來要講的一致性哈希算法。

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

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

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

以下是其實現(xiàn)原理的細目分類，網(wǎng)上已經(jīng)有詳細說明。

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

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

hash() = key1;

…………

hash() = key4;

基本思路

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

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

hash(A) = 鍵 A;

…………

hash(C) = 鍵 C;

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

既然對象和對象都通過相同的哈希算法映射到哈希值空間，接下來要考慮的是如何將對象映射到它。

在這個環(huán)形空間中，如果從對象的key值開始順時針方向，直到遇到一個，那么就將對象存儲在this上，因為對象的hash值和hash值是固定的，所以這個必須是唯一的和確定的。你沒有找到對象的映射方法嗎？ ！

繼續(xù)上面的例子（見圖3），那么按照上面的方法，對象就會被存儲在A上；并對應于 C；對應B;

前面說過，先hash再計算余數(shù)的方法帶來的最大問題是不能滿足單調(diào)性。當有變化時，就會失敗，這會對后端服務(wù)器造成巨大的影響?，F(xiàn)在讓我們來分析和分析算法。 .

刪除

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

所以這里我們只需要改變對象，重新映射到C；見下圖

添加

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

所以這里我們只需要改變對象，重新映射到D即可；見下圖

另一個考慮Hash算法的指標是()一致性hash算法php開源，定義如下：

平衡

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

哈希算法不保證絕對平衡。如果對象較少，則無法均勻映射對象。例如，在上面的例子中，當只部署了A和C時，4個對象中，A只存儲，C存儲，和；分布很不均勻。

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

“虛擬節(jié)點”（node）是哈?？臻g中一個實際節(jié)點的副本（），一個實際節(jié)點對應幾個“虛擬節(jié)點”，這個對應的數(shù)字也變成了“副本數(shù)”，“虛擬節(jié)點” “ ”在哈希空間中按哈希值排列。

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

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

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

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

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

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

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

Hash("202.168.14.241");

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

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

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

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

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

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

C 語言版本

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