一致哈希

一致哈希 是一種特殊的哈希算法。在使用一致哈希算法後，哈希表槽位數（大小）的改變平均只需要對 $K/n$ 個關鍵字重新映射，其中 $K$ 是關鍵字的數量， $n$ 是槽位數量。然而在傳統的哈希表中，添加或刪除一個槽位的幾乎需要對所有關鍵字進行重新映射。

歷史

一致哈希由MIT的Karger及其合作者提出，現在這一思想已經擴展到其它領域。在這篇1997年發表的學術論文中介紹了「一致哈希」如何應用於用戶易變的分布式Web服務中。哈希表中的每一個代表分布式系統中一個節點，在系統添加或刪除節點只需要移動 $K/n$ 項。^[1]

一致哈希也可用於實現健壯緩存來減少大型Web應用中系統部分失效帶來的負面影響。^[2]

一致哈希的概念還被應用於分布式散列表（DHT）的設計。DHT使用一致哈希來劃分分布式系統的節點。所有關鍵字都可以通過一個連接所有節點的覆蓋網絡高效地定位到某個節點。

需求

在使用n台緩存服務器時，一種常用的負載均衡方式是，對資源o的請求使用 ${\mbox{hash}}(o)=o\mod n$ 來映射到某一台緩存服務器。當增加或減少一台緩存服務器時這種方式可能會改變所有資源對應的hash值，也就是所有的緩存都失效了，這會使得緩存服務器大量集中地向原始內容服務器更新緩存。因此需要一致哈希算法來避免這樣的問題。一致哈希儘可能使同一個資源映射到同一台緩存服務器。這種方式要求增加一台緩存服務器時，新的服務器儘量分擔存儲其他所有服務器的緩存資源。減少一台緩存服務器時，其他所有服務器也可以儘量分擔存儲它的緩存資源。一致哈希算法的主要思想是將每個緩存服務器與一個或多個哈希值域區間關聯起來，其中區間邊界通過計算緩存服務器對應的哈希值來決定。（定義區間的哈希函數不一定和計算緩存服務器哈希值的函數相同，但是兩個函數的返回值的範圍需要匹配。）如果一個緩存服務器被移除，則它所對應的區間會被併入到鄰近的區間，其他的緩存服務器不需要任何改變。

實現

最簡單的一種實現是哈希環法：將每個對象映射到圓環邊上的一個點，系統再將可用的節點機器映射到圓環的不同位置。查找某個對象對應的機器時，需要用一致哈希算法計算得到對象對應圓環邊上位置，沿着圓環邊上查找直到遇到某個節點機器，這台機器即為對象應該保存的位置。當刪除一台節點機器時，這台機器上保存的所有對象都要移動到下一台機器。添加一台機器到圓環邊上某個點時，這個點的下一台機器需要將這個節點前對應的對象移動到新機器上。更改對象在節點機器上的分布可以通過調整節點機器的位置來實現。

這裡是哈希環法的可視化演示，可以觀察整個操作的過程。

特性

David Karger及其合作者列出了使得一致哈希在互聯網分布式緩存中非常有用的幾個特性： ^[1]

冗餘少
負載均衡
過渡平滑
存儲均衡
關鍵詞單調

應用實例

在亞馬遜的雲存儲系統Dynamo的數據劃分功能模塊中使用一致哈希。^[3]

參考資料

^ ^1.0 ^1.1 Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA: 654–663. 1997. doi:10.1145/258533.258660.
^ Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. Web Caching with Consistent Hashing. Computer Networks. 1999, 31 (11): 1203–1213 [2012年3月19日]. doi:10.1016/S1389-1286(99)00055-9. （原始內容存檔於2008年7月21日）.
^ DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A,; Sivasubramanian, S.; Vosshall, P. ;Vogels, W. Dynamo: Amazon's Highly Available Key-Value Store. Proceedings of the 21st ACM Symposium on Operating Systems Principles. 2007.

外部連結

[KargerEtAl1997-1] 1.0 ^1.1 Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA: 654–663. 1997. doi:10.1145/258533.258660.

[KargerEtAl1999-2] Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. Web Caching with Consistent Hashing. Computer Networks. 1999, 31 (11): 1203–1213 [2012年3月19日]. doi:10.1016/S1389-1286(99)00055-9. （原始內容存檔於2008年7月21日）.

[Amazon2007-3] DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A,; Sivasubramanian, S.; Vosshall, P. ;Vogels, W. Dynamo: Amazon's Highly Available Key-Value Store. Proceedings of the 21st ACM Symposium on Operating Systems Principles. 2007.

[1]

[2]

[3]