如果你有 n 個(gè)緩存服務(wù)器，一個(gè)常見的負(fù)載均衡方式是使用以下的哈希方法：

服務(wù)器索引 = 哈希(鍵) % N，其中 N 是服務(wù)器池的大小。

讓我們通過一個(gè)例子來說明這是如何工作的。如表5-1所示，我們有4臺(tái)服務(wù)器和8個(gè)字符串鍵及其哈希值。

為了獲取存儲(chǔ)某個(gè)鍵的服務(wù)器，我們執(zhí)行模運(yùn)算 f(鍵) % 4。例如，哈希(鍵0) % 4 = 1 意味著客戶端必須聯(lián)系服務(wù)器1來獲取緩存的數(shù)據(jù)。圖5-1展示了基于表5-1的鍵的分布。

當(dāng)服務(wù)器池的大小固定且數(shù)據(jù)分布均勻時(shí)，這種方法工作得很好。然而，當(dāng)新的服務(wù)器被添加，或者現(xiàn)有的服務(wù)器被移除時(shí)，就會(huì)出現(xiàn)問題。例如，如果服務(wù)器1離線，服務(wù)器池的大小就變成了3。使用相同的哈希函數(shù)，我們得到的鍵的哈希值是相同的。但是應(yīng)用模運(yùn)算會(huì)因?yàn)榉?wù)器數(shù)量減少了1而得到不同的服務(wù)器索引。我們應(yīng)用 哈希 % 3 得到的結(jié)果如表5-2所示：

圖5-2展示了基于表5-2的新鍵分布。

如圖5-2所示，大多數(shù)鍵都被重新分配了，而不僅僅是那些最初存儲(chǔ)在離線服務(wù)器（服務(wù)器1）中的鍵。這意味著，當(dāng)服務(wù)器1離線時(shí)，大多數(shù)緩存客戶端將連接到錯(cuò)誤的服務(wù)器來獲取數(shù)據(jù)。這導(dǎo)致了一場(chǎng)緩存未命中的風(fēng)暴。一致性哈希是一種有效的技術(shù)來緩解這個(gè)問題。

一致性哈希

引用自維基百科："一致性哈希是一種特殊的哈希，使得當(dāng)哈希表大小改變且使用一致性哈希時(shí)，平均只有 k/n 個(gè)鍵需要被重新映射，其中 k 是鍵的數(shù)量，n 是槽位的數(shù)量。相比之下，在大多數(shù)傳統(tǒng)哈希表中，數(shù)組槽位數(shù)量的變化導(dǎo)致幾乎所有的鍵都需要被重新映射[1]”。

哈?？臻g和哈希環(huán)

現(xiàn)在我們理解了一致性哈希的定義，讓我們了解它是如何工作的。假設(shè)使用SHA-1作為哈希函數(shù)f，哈希函數(shù)的輸出范圍是：x0, x1, x2, x3, ..., xn。在密碼學(xué)中，SHA-1的哈?？臻g從0到2^160 - 1。也就是說，x0 對(duì)應(yīng)0，xn 對(duì)應(yīng)2^160 - 1，所有其他的哈希值都落在0和2^160 - 1之間。圖5-3展示了哈?？臻g。

通過連接兩端，我們得到一個(gè)如圖5-4所示的哈希環(huán)：

哈希服務(wù)器

使用相同的哈希函數(shù)f，我們根據(jù)服務(wù)器的IP或名字將服務(wù)器映射到環(huán)上。圖5-5顯示了4臺(tái)服務(wù)器被映射到哈希環(huán)上。

哈希鍵

值得一提的是，這里使用的哈希函數(shù)與“重哈希問題”中的不同，并且沒有模運(yùn)算。如圖5-6所示，4個(gè)緩存鍵（key0，key1，key2和key3）被哈希到哈希環(huán)上。

服務(wù)器查找

為了確定一個(gè)鍵存儲(chǔ)在哪個(gè)服務(wù)器上，我們從環(huán)上的鍵位置順時(shí)針方向進(jìn)行尋找，直到找到一個(gè)服務(wù)器。圖5-7解釋了這個(gè)過程。順時(shí)針方向，key 0 存儲(chǔ)在 server 0上；key1 存儲(chǔ)在 server 1 上；key2 存儲(chǔ)在 server 2 上；key3 存儲(chǔ)在 server 3 上。

添加服務(wù)器

使用上述邏輯，添加新服務(wù)器只需要重新分配一部分鍵。

在圖5-8中，新增 server 4 后，只有 key0 需要被重新分配。k1, k2, 和 k3 仍然在相同的服務(wù)器上。讓我們仔細(xì)看看這個(gè)邏輯。在 server 4 添加之前，key0 存儲(chǔ)在 server 0 上。現(xiàn)在，key0 將存儲(chǔ)在 server 4 上，因?yàn)?server 4 是它從環(huán)上的 key0 位置順時(shí)針方向遇到的第一個(gè)服務(wù)器。其他的鍵根據(jù)一致性哈希算法不需要重新分配。

移除服務(wù)器

當(dāng)服務(wù)器被移除時(shí)，只有少部分的鍵需要通過一致性哈希進(jìn)行重新分配。在圖5-9中，當(dāng) server 1 被移除時(shí)，只有 key1 必須被映射到 server 2。其余的鍵不受影響。

基本方法中的兩個(gè)問題

一致性哈希算法是由MIT的Karger等人提出的[1]?；静襟E如下：

• 使用均勻分布的哈希函數(shù)將服務(wù)器和鍵映射到環(huán)上。
• 要找出鍵映射到哪個(gè)服務(wù)器，從鍵位置開始順時(shí)針方向找到環(huán)上的第一個(gè)服務(wù)器。

這種方法存在兩個(gè)問題。首先，考慮到服務(wù)器可能會(huì)被添加或移除，不可能在環(huán)上為所有服務(wù)器保持相同大小的分區(qū)。分區(qū)是相鄰服務(wù)器之間的哈?？臻g。每個(gè)服務(wù)器被分配到的環(huán)上的分區(qū)大小可能非常小或者相當(dāng)大。在圖5-10中，如果s1被移除，s2的分區(qū)（雙向箭頭高亮表示）就是s0和s3分區(qū)的兩倍大。

第二，環(huán)上的鍵分布可能非均勻。例如，如果服務(wù)器映射到圖5-11中列出的位置，大部分的鍵都存儲(chǔ)在server 2上。然而，server 1 和 server 3 沒有任何數(shù)據(jù)。

一種被稱為虛擬節(jié)點(diǎn)或副本的技術(shù)被用來解決這些問題。

虛擬節(jié)點(diǎn)

虛擬節(jié)點(diǎn)是指實(shí)際節(jié)點(diǎn)，每個(gè)服務(wù)器在環(huán)上都由多個(gè)虛擬節(jié)點(diǎn)表示。在圖5-12中，server 0 和 server 1 都有3個(gè)虛擬節(jié)點(diǎn)。這個(gè)3是隨意選擇的；在實(shí)際系統(tǒng)中，虛擬節(jié)點(diǎn)的數(shù)量要多得多。我們不再使用 s0，而是使用 s0_0, s0_1 和 s0_2 來在環(huán)上表示 server 0。同樣，s1_0, s1_1 和 s1_2 在環(huán)上表示 server 1。有了虛擬節(jié)點(diǎn)，每個(gè)服務(wù)器就負(fù)責(zé)多個(gè)分區(qū)。標(biāo)簽為 s0 的分區(qū)（邊）由 server 0 管理。另一方面，標(biāo)簽為 s1 的分區(qū)由 server 1 管理。

要找出一個(gè)鍵存儲(chǔ)在哪個(gè)服務(wù)器上，我們從鍵的位置順時(shí)針方向去找環(huán)上遇到的第一個(gè)虛擬節(jié)點(diǎn)。在圖5-13中，要找出k0存儲(chǔ)在哪個(gè)服務(wù)器上，我們從k0的位置順時(shí)針方向找到虛擬節(jié)點(diǎn)s1_1，它指向server 1。

隨著虛擬節(jié)點(diǎn)數(shù)量的增加，鍵的分布變得更加均衡。這是因?yàn)殡S著虛擬節(jié)點(diǎn)數(shù)量的增加，標(biāo)準(zhǔn)差變得更小，導(dǎo)致數(shù)據(jù)分布均衡。標(biāo)準(zhǔn)差衡量了數(shù)據(jù)的分散程度。在線研究的一項(xiàng)實(shí)驗(yàn)結(jié)果[2]表明，當(dāng)有一百或兩百個(gè)虛擬節(jié)點(diǎn)時(shí)，標(biāo)準(zhǔn)差在均值的5%（200個(gè)虛擬節(jié)點(diǎn)）到10%（100個(gè)虛擬節(jié)點(diǎn)）之間。當(dāng)我們?cè)黾犹摂M節(jié)點(diǎn)數(shù)量時(shí)，標(biāo)準(zhǔn)差會(huì)變小。然而，我們需要更多的空間來存儲(chǔ)虛擬節(jié)點(diǎn)的數(shù)據(jù)。這是一個(gè)權(quán)衡，我們可以調(diào)整虛擬節(jié)點(diǎn)的數(shù)量以適應(yīng)我們的系統(tǒng)需求。

找到受影響的鍵

當(dāng)添加或移除一個(gè)服務(wù)器時(shí)，部分?jǐn)?shù)據(jù)需要被重新分布。我們?nèi)绾握业绞苡绊懙姆秶灾匦路峙滏I呢？

在圖5-14中，server 4被添加到環(huán)中。受影響的范圍從s4（新添加的節(jié)點(diǎn)）開始，逆時(shí)針移動(dòng)到找到一個(gè)服務(wù)器（s3）。因此，位于s3和s4之間的鍵需要被重新分配給s4。

當(dāng)一個(gè)服務(wù)器（s1）如圖5-15所示被移除時(shí)，受影響的范圍從s1（被移除的節(jié)點(diǎn)）開始，逆時(shí)針繞環(huán)移動(dòng)到找到一個(gè)服務(wù)器（s0）。因此，位于s0和s1之間的鍵必須被重新分配給s2。

總結(jié)

在這一章，我們深入討論了一致性哈希，包括為什么需要它以及它是如何工作的。一致性哈希的好處包括：

• 當(dāng)服務(wù)器被添加或移除時(shí)，最小化鍵的重新分布。
• 因?yàn)閿?shù)據(jù)更均勻地分布，所以易于橫向擴(kuò)展。
• 緩解熱點(diǎn)鍵問題。過度訪問特定的分片可能導(dǎo)致服務(wù)器過載。想象一下，Katy Perry、Justin Bieber和Lady Gaga的數(shù)據(jù)全部都在同一個(gè)分片上。一致性哈希通過更均勻地分布數(shù)據(jù)來緩解這個(gè)問題。

一致性哈希在現(xiàn)實(shí)世界的系統(tǒng)中被廣泛應(yīng)用，包括一些著名的系統(tǒng)：

• Amazon的Dynamo數(shù)據(jù)庫(kù)的分區(qū)組件 [3]
• Apache Cassandra中跨集群的數(shù)據(jù)分區(qū) [4]
• Discord聊天應(yīng)用 [5]
• Akamai內(nèi)容分發(fā)網(wǎng)絡(luò) [6]
• Maglev網(wǎng)絡(luò)負(fù)載均衡器 [7]

恭喜你走到這一步！現(xiàn)在給自己一個(gè)贊。干得好！

參考資料

[1] 一致性哈希：https://en.wikipedia.org/wiki/Consistent_hashing

[2] 一致性哈希：

https://tom-e-white.com/2007/11/consistent-hashing.html

[3] Dynamo：亞馬遜的高可用鍵值存儲(chǔ)：
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

[4] Cassandra - 一個(gè)去中心化的結(jié)構(gòu)化存儲(chǔ)系統(tǒng)：

http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF

[5] 如何將Discord Elixir擴(kuò)展到500萬并發(fā)用戶：
https://blog.discord.com/scaling-elixir-f9b8e1e7c29b

[6] CS168：現(xiàn)代算法工具箱第一課：簡(jiǎn)介和一致性哈希：http://theory.stanford.edu/~tim/s16/l/l1.pdf

[7] Maglev：一個(gè)快速可靠的軟件網(wǎng)絡(luò)負(fù)載均衡器：
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf文章來源地址http://www.zghlxwxcb.cn/news/detail-459051.html

到了這里，關(guān)于什么是一致性哈希？一致性哈希是如何工作的？如何設(shè)計(jì)一致性哈希？的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！