轉(zhuǎn)： http://blog.csdn.net/shagoo/archive/2010/10/29/5974643.aspx

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

[背景信息]

對于 Memcached 來說，本身是集中式的緩存系統(tǒng)，要搞多節(jié)點(diǎn)分布，只能通過客戶端實(shí)現(xiàn)。Memcached 的分布算法一般有兩種選擇：

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

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

下圖就是一致性哈希算法算法的示意圖，比如我們現(xiàn)在有 4 臺服務(wù)器，我們把他們的 hash 值當(dāng)作 node 節(jié)點(diǎn)按照某種平均分布算法被分配到這個(gè)環(huán)上面，我們 按順時(shí)針方向 ?把 Key 的哈希值與 node 節(jié)點(diǎn)的 hash 值比較，總是把 Key 節(jié)點(diǎn)保存到找到的 第一個(gè) ?hash 值大于 Key 節(jié)點(diǎn)的那個(gè) node 節(jié)點(diǎn)服務(wù)器上：

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

Spymemcached 和 Xmemcached 都實(shí)現(xiàn)了一致性算法，這里要測試下在使用一致性哈希的情況下，增加節(jié)點(diǎn)，看不同散列函數(shù)下命中率和數(shù)據(jù)分布的變化情況，這個(gè)測試結(jié)果對于 Spymemcached 和 Xmemcached 是一樣的，測試場景：

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

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

[結(jié)果分析]

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

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()會通常小于這些值的第一個(gè)，那么查找就經(jīng)常只找到第一個(gè)節(jié)點(diǎn)并存儲數(shù)據(jù)，當(dāng)然，這里有測試的局限性，因?yàn)閙emcached都跑在一個(gè)臺機(jī)器上只是端口不同造成了hash(節(jié)點(diǎn)IP地址)的連續(xù)遞增，將分布不均勻的問題放大了。

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

3、最后，單純比較下散列函數(shù)的計(jì)算效率：

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 算法適合你所在的場景，對于分布式應(yīng)用，本人比較推薦在 CRC32_HASH、FNV1_32_HASH、KETAMA_HASH 這三種算法中選擇，至于你是注重算法效率還是命中率，這就需要根據(jù)具體的場景來選擇了。另外，對于 PHP 客戶端可以通過 Memcache 擴(kuò)展如下配置（在 php.ini 中）來選擇：

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

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

然后通過 Memcache::addServer 函數(shù)即可添加服務(wù)器節(jié)點(diǎn)了，相當(dāng)方便哦~

[zt] 從 Memcached 分布式應(yīng)用看一致性哈希散列函數(shù)的選擇