什么是一致性哈希？一致性哈希是如何工作的？如何設計一致性哈希？
如果你有 n 個緩存服務器，一個常見的負載均衡方式是使用以下的哈希方法：
服務器索引 = 哈希(鍵) % N，其中 N 是服務器池的大小。
讓我們通過一個例子來說明這是如何工作的。如表5-1所示，我們有4臺服務器和8個字符串鍵及其哈希值。
為了獲取存儲某個鍵的服務器，我們執行模運算 f(鍵) % 4。例如，哈希(鍵0) % 4 = 1 意味著客戶端必須聯系服務器1來獲取緩存的數據。圖5-1展示了基于表5-1的鍵的分布。
當服務器池的大小固定且數據分布均勻時，這種方法工作得很好。然而，當新的服務器被添加，或者現有的服務器被移除時，就會出現問題。例如，如果服務器1離線，服務器池的大小就變成了3。使用相同的哈希函數，我們得到的鍵的哈希值是相同的。但是應用模運算會因為服務器數量減少了1而得到不同的服務器索引。我們應用 哈希 % 3 得到的結果如表5-2所示：
圖5-2展示了基于表5-2的新鍵分布。
如圖5-2所示，大多數鍵都被重新分配了，而不僅僅是那些最初存儲在離線服務器（服務器1）中的鍵。這意味著，當服務器1離線時，大多數緩存客戶端將連接到錯誤的服務器來獲取數據。這導致了一場緩存未命中的風暴。一致性哈希是一種有效的技術來緩解這個問題。
一致性哈希
引用自維基百科："一致性哈希是一種特殊的哈希，使得當哈希表大小改變且使用一致性哈希時，平均只有 k/n 個鍵需要被重新映射，其中 k 是鍵的數量，n 是槽位的數量。相比之下，在大多數傳統哈希表中，數組槽位數量的變化導致幾乎所有的鍵都需要被重新映射[1]”。
哈?？臻g和哈希環
現在我們理解了一致性哈希的定義，讓我們了解它是如何工作的。假設使用SHA-1作為哈希函數f，哈希函數的輸出范圍是：x0, x1, x2, x3, ..., xn。在密碼學中，SHA-1的哈?？臻g從0到2^160 - 1。也就是說，x0 對應0，xn 對應2^160 - 1，所有其他的哈希值都落在0和2^160 - 1之間。圖5-3展示了哈?？臻g。
通過連接兩端，我們得到一個如圖5-4所示的哈希環：
哈希服務器
使用相同的哈希函數f，我們根據服務器的IP或名字將服務器映射到環上。圖5-5顯示了4臺服務器被映射到哈希環上。
哈希鍵
值得一提的是，這里使用的哈希函數與“重哈希問題”中的不同，并且沒有模運算。如圖5-6所示，4個緩存鍵（key0，key1，key2和key3）被哈希到哈希環上。
服務器查找
為了確定一個鍵存儲在哪個服務器上，我們從環上的鍵位置順時針方向進行尋找，直到找到一個服務器。圖5-7解釋了這個過程。順時針方向，key 0 存儲在 server 0上；key1 存儲在 server 1 上；key2 存儲在 server 2 上；key3 存儲在 server 3 上。
添加服務器
使用上述邏輯，添加新服務器只需要重新分配一部分鍵。
在圖5-8中，新增 server 4 后，只有 key0 需要被重新分配。k1, k2, 和 k3 仍然在相同的服務器上。讓我們仔細看看這個邏輯。在 server 4 添加之前，key0 存儲在 server 0 上?，F在，key0 將存儲在 server 4 上，因為 server 4 是它從環上的 key0 位置順時針方向遇到的第一個服務器。其他的鍵根據一致性哈希算法不需要重新分配。
移除服務器
當服務器被移除時，只有少部分的鍵需要通過一致性哈希進行重新分配。在圖5-9中，當 server 1 被移除時，只有 key1 必須被映射到 server 2。其余的鍵不受影響。
基本方法中的兩個問題
一致性哈希算法是由MIT的Karger等人提出的[1]?；静襟E如下：
- 使用均勻分布的哈希函數將服務器和鍵映射到環上。
- 要找出鍵映射到哪個服務器，從鍵位置開始順時針方向找到環上的第一個服務器。
這種方法存在兩個問題。首先，考慮到服務器可能會被添加或移除，不可能在環上為所有服務器保持相同大小的分區。分區是相鄰服務器之間的哈?？臻g。每個服務器被分配到的環上的分區大小可能非常小或者相當大。在圖5-10中，如果s1被移除，s2的分區（雙向箭頭高亮表示）就是s0和s3分區的兩倍大。
第二，環上的鍵分布可能非均勻。例如，如果服務器映射到圖5-11中列出的位置，大部分的鍵都存儲在server 2上。然而，server 1 和 server 3 沒有任何數據。
一種被稱為虛擬節點或副本的技術被用來解決這些問題。
虛擬節點
虛擬節點是指實際節點，每個服務器在環上都由多個虛擬節點表示。在圖5-12中，server 0 和 server 1 都有3個虛擬節點。這個3是隨意選擇的；在實際系統中，虛擬節點的數量要多得多。我們不再使用 s0，而是使用 s0_0, s0_1 和 s0_2 來在環上表示 server 0。同樣，s1_0, s1_1 和 s1_2 在環上表示 server 1。有了虛擬節點，每個服務器就負責多個分區。標簽為 s0 的分區（邊）由 server 0 管理。另一方面，標簽為 s1 的分區由 server 1 管理。
要找出一個鍵存儲在哪個服務器上，我們從鍵的位置順時針方向去找環上遇到的第一個虛擬節點。在圖5-13中，要找出k0存儲在哪個服務器上，我們從k0的位置順時針方向找到虛擬節點s1_1，它指向server 1。
隨著虛擬節點數量的增加，鍵的分布變得更加均衡。這是因為隨著虛擬節點數量的增加，標準差變得更小，導致數據分布均衡。標準差衡量了數據的分散程度。在線研究的一項實驗結果[2]表明，當有一百或兩百個虛擬節點時，標準差在均值的5%（200個虛擬節點）到10%（100個虛擬節點）之間。當我們增加虛擬節點數量時，標準差會變小。然而，我們需要更多的空間來存儲虛擬節點的數據。這是一個權衡，我們可以調整虛擬節點的數量以適應我們的系統需求。
找到受影響的鍵
當添加或移除一個服務器時，部分數據需要被重新分布。我們如何找到受影響的范圍以重新分配鍵呢？
在圖5-14中，server 4被添加到環中。受影響的范圍從s4（新添加的節點）開始，逆時針移動到找到一個服務器（s3）。因此，位于s3和s4之間的鍵需要被重新分配給s4。
當一個服務器（s1）如圖5-15所示被移除時，受影響的范圍從s1（被移除的節點）開始，逆時針繞環移動到找到一個服務器（s0）。因此，位于s0和s1之間的鍵必須被重新分配給s2。
總結
在這一章，我們深入討論了一致性哈希，包括為什么需要它以及它是如何工作的。一致性哈希的好處包括：
- 當服務器被添加或移除時，最小化鍵的重新分布。
- 因為數據更均勻地分布，所以易于橫向擴展。
- 緩解熱點鍵問題。過度訪問特定的分片可能導致服務器過載。想象一下，Katy Perry、Justin Bieber和Lady Gaga的數據全部都在同一個分片上。一致性哈希通過更均勻地分布數據來緩解這個問題。
一致性哈希在現實世界的系統中被廣泛應用，包括一些著名的系統：
- Amazon的Dynamo數據庫的分區組件 [3]
- Apache Cassandra中跨集群的數據分區 [4]
- Discord聊天應用 [5]
- Akamai內容分發網絡 [6]
- Maglev網絡負載均衡器 [7]
恭喜你走到這一步！現在給自己一個贊。干得好！
參考資料
[1] 一致性哈希：https://en.wikipedia.org/wiki/Consistent_hashing
[2] 一致性哈希：
https://tom-e-white.com/2007/11/consistent-hashing.html
[3] Dynamo：亞馬遜的高可用鍵值存儲：
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
[4] Cassandra - 一個去中心化的結構化存儲系統：
http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF
[5] 如何將Discord Elixir擴展到500萬并發用戶：
https://blog.discord.com/scaling-elixir-f9b8e1e7c29b
[6] CS168：現代算法工具箱第一課：簡介和一致性哈希：http://theory.stanford.edu/~tim/s16/l/l1.pdf
[7] Maglev：一個快速可靠的軟件網絡負載均衡器：
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf
