一致雜湊

一致雜湊 是一種特殊的雜湊演算法。在使用一致雜湊演算法後，雜湊表槽位數（大小）的改變平均只需要對 $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]