轉： http://blog.csdn.net/shagoo/archive/2010/10/29/5974643.aspx

一致性哈希算法來源于 P2P 網絡的路由算法，目前主流的 P2P 軟件就是利用我們所熟知的 DHT (Distributed Hash Table，分布式哈希表) 來定位整個分布式網絡的信息，另外此算法在目前火熱的云計算領域也將占有極其重要的位置。可以說散列函數在當代計算機和網絡系統中所起的重要作用大家應該都有目共睹了，特別是在目前這個分布式應用爆炸的時代，這個方面的知識只會越來越引起人們的重視，本文重在從 Memcached 這個流行的分布式應用的場景中來對一致性哈希散列的幾個主流算法做一些比較和分析。

[背景信息]

對于 Memcached 來說，本身是集中式的緩存系統，要搞多節點分布，只能通過客戶端實現。Memcached 的分布算法一般有兩種選擇：

1、根據 hash(key) 的結果，模連接數的余數決定存儲到哪個節點，也就是 hash(key) % sessions.size()，這個算法簡單快速，表現良好。然而這個算法有個缺點，就是在memcached節點增加或者刪除的時候，原有的緩存數據將大規模失效，命中率大受影響，如果節點數多，緩存數據多，重建緩存的代價太高，因此有了第二個算法。

2、Consistent Hashing，一致性哈希算法，他的查找節點過程如下：首先求出 Memcached 服務器（節點）的哈希值，并將其配置到 0～232 的圓（continuum）上。然后用同樣的方法求出存儲數據的鍵的哈希值，并映射到圓上。然后從數據映射到的位置開始順時針查找，將數據保存到找到的第一個服務器上。如果超過 232 仍然找不到服務器，就會保存到第一臺 Memcached 服務器上。

下圖就是一致性哈希算法算法的示意圖，比如我們現在有 4 臺服務器，我們把他們的 hash 值當作 node 節點按照某種平均分布算法被分配到這個環上面，我們 按順時針方向 ?把 Key 的哈希值與 node 節點的 hash 值比較，總是把 Key 節點保存到找到的 第一個 ?hash 值大于 Key 節點的那個 node 節點服務器上：

現在假如我們有一臺新的服務器加入進來（減少一個服務器同理），那么按照此前的算法，受影響的 Key 值只有下圖黃色那部分的數據，從某種意義上甚至這樣可以說， 加入的服務器 node 節點越多，受影響的數據就越少 ?，從而使這個動態的分布式系統中的數據穩定性達到最大，而這就是一致性哈希算法的精髓所在了：

Spymemcached 和 Xmemcached 都實現了一致性算法，這里要測試下在使用一致性哈希的情況下，增加節點，看不同散列函數下命中率和數據分布的變化情況，這個測試結果對于 Spymemcached 和 Xmemcached 是一樣的，測試場景：

從一篇英文小說（《黃金羅盤》前三章）進行單詞統計，并將最后的統計結果存儲到 Memcached，以單詞為 Key，以次數為 Value。單詞個數為 3061，Memcached 原來節點數為10，運行在局域網內同一臺服務器上的不同端口，在存儲統計結果后，增加兩個 Memcached 節點（也就是從 10個節點增加到12個節點），統計此時的緩存命中率并查看數據的分布情況。

結果如下表格，命中率一行表示增加節點后的命中率情況（增加前為100%），后續的行表示各個節點存儲的單詞數,CRC32_HASH 表示采用 CRC32 散列函數，KETAMA_HASH 是基于 md5 的散列函數也是默認情況下一致性哈希的推薦算法，FNV1_32_HASH 就是 FNV 32 位散列函數，NATIVE_HASH 就是 java.lang.String.hashCode() 方法返回的 long 取 32 位的結果，MYSQL_HASH 是 Xmemcached 添加的傳說來自于 mysql 源碼中的哈希函數。

[結果分析]

1、命中率最高看起來是NATIVE_HASH，然而NATIVE_HASH情況下數據集中存儲在第一個節點，顯然沒有實際使用價值。為什么會集中存儲在第一個節點呢？這是由于在查找存儲的節點的過程中，會比較hash(key)和hash(節點IP地址)，而在采用了NATIVE_HASH的情況下，所有連接的hash值會呈現一個遞增狀況（因為String.hashCode是乘法散列函數），如：

192.168.0.100:12000 736402923
192.168.0.100:12001 736402924
192.168.0.100:12002 736402925
192.168.0.100:12003 736402926

如果這些值很大的會，那么單詞的hashCode()會通常小于這些值的第一個，那么查找就經常只找到第一個節點并存儲數據，當然，這里有測試的局限性，因為memcached都跑在一個臺機器上只是端口不同造成了hash(節點IP地址)的連續遞增，將分布不均勻的問題放大了。

2、從結果上看，KETAMA_HASH 維持了一個最佳平衡，在增加兩個節點后還能訪問到83.3%的單詞，并且數據分布在各個節點上的數目也相對平均，難怪作為默認散列算法。

3、最后，單純比較下散列函數的計算效率：

CRC32_HASH:3266
KETAMA_HASH:7500
FNV1_32_HASH:375
NATIVE_HASH:187
MYSQL_HASH:500

簡單看以上算法的效率排序如下：

NATIVE_HASH > FNV1_32_HASH > MYSQL_HASH > CRC32_HASH > KETAMA_HASH

綜上所述，大家可以比較清楚的看出哪種 hash 算法適合你所在的場景，對于分布式應用，本人比較推薦在 CRC32_HASH、FNV1_32_HASH、KETAMA_HASH 這三種算法中選擇，至于你是注重算法效率還是命中率，這就需要根據具體的場景來選擇了。另外，對于 PHP 客戶端可以通過 Memcache 擴展如下配置（在 php.ini 中）來選擇：

memcache.hash_function={crc32(default),fnv}

memcache.hash_strategy={consistent(default),standard}

然后通過 Memcache::addServer 函數即可添加服務器節點了，相當方便哦~

[zt] 從 Memcached 分布式應用看一致性哈希散列函數的選擇