memcached本身是集中式的緩存系統(tǒng)，要搞多節(jié)點分布，只能通過客戶端實現(xiàn)。memcached的分布算法一般有兩種選擇：
1、根據(jù)hash(key)的結(jié)果，模連接數(shù)的余數(shù)決定存儲到哪個節(jié)點，也就是hash(key)% sessions.size()，這個算法簡單快速，表現(xiàn)良好。然而這個算法有個缺點，就是在memcached節(jié)點增加或者刪除的時候，原有的緩存數(shù)據(jù)將大規(guī)模失效，命中率大受影響，如果節(jié)點數(shù)多，緩存數(shù)據(jù)多，重建緩存的代價太高，因此有了第二個算法。
2、Consistent Hashing，一致性哈希算法，他的查找節(jié)點過程如下：
首先求出memcached服務(wù)器（節(jié)點）的哈希值，并將其配置到0～2
32的圓（continuum）上。然后用同樣的方法求出存儲數(shù)據(jù)的鍵的哈希值，并映射到圓上。然后從數(shù)據(jù)映射到的位置開始順時針查找，將數(shù)據(jù)保存到找到的第一個服務(wù)器上。如果超過2
32仍然找不到服務(wù)器，就會保存到第一臺memcached服務(wù)器上。
一致性哈希算法來源于P2P網(wǎng)絡(luò)的路由算法，更多的信息可以讀
這里。
spymemcached和xmemcached都實現(xiàn)了一致性算法（其實我是照抄的），這里要測試下在使用一致性哈希的情況下，增加節(jié)點，看不同
散列函數(shù)下命中率和數(shù)據(jù)分布的變化情況，這個測試結(jié)果對于spymemcached和xmemcached是一樣的，測試場景：
從一篇英文小說（《黃金羅盤》前三章）進行單詞統(tǒng)計，并將最后的統(tǒng)計結(jié)果存儲到memcached，以單詞為key，以次數(shù)為value。單詞個數(shù)為3061，memcached原來節(jié)點數(shù)為10，運行在局域網(wǎng)內(nèi)同一臺服務(wù)器上的不同端口，在存儲統(tǒng)計結(jié)果后，增加兩個memcached節(jié)點（也就是從10個節(jié)點增加到12個節(jié)點），統(tǒng)計此時的緩存命中率并查看數(shù)據(jù)的分布情況。
結(jié)果如下表格，命中率一行表示增加節(jié)點后的命中率情況（增加前為100%），后續(xù)的行表示各個節(jié)點存儲的單詞數(shù),CRC32_HASH表示采用CRC32散列函數(shù)，KETAMA_HASH是基于md5的散列函數(shù)也是默認情況下一致性哈希的推薦算法，F(xiàn)NV1_32_HASH就是FNV 32位散列函數(shù)，NATIVE_HASH就是java.lang.String.hashCode()方法返回的long取32位的結(jié)果，MYSQL_HASH是xmemcached添加的傳說來自于mysql源碼中的哈希函數(shù)。
| |
CRC32_HASH |
KETAMA_HASH |
FNV1_32_HASH |
NATIVE_HASH |
MYSQL_HASH |
命中率
|
78.5% |
83.3% |
78.2% |
99.89% |
86.9% |
| 節(jié)點1 |
319 |
366 |
546 |
3596 |
271 |
| 節(jié)點2 |
399 |
350 |
191 |
1 |
233 |
| 節(jié)點3 |
413 |
362 |
491 |
0 |
665 |
| 節(jié)點4 |
393 |
364 |
214 |
1 |
42 |
| 節(jié)點5 |
464 |
403 |
427 |
1 |
421 |
| 節(jié)點6 |
472 |
306 |
299 |
0 |
285 |
| 節(jié)點7 |
283 |
347 |
123 |
0 |
635 |
| 節(jié)點8 |
382 |
387 |
257 |
2 |
408 |
| 節(jié)點9 |
238 |
341 |
297 |
0 |
55 |
| 節(jié)點10 |
239 |
375 |
756 |
0 |
586 |
| 范圍 |
200~500 |
300~400
|
150~750 |
0~3600 |
50~650 |
結(jié)果分析：
1、命中率最高看起來是NATIVE_HASH，然而NATIVE_HASH情況下數(shù)據(jù)集中存儲在第一個節(jié)點，顯然沒有實際使用價值。為什么會集中存儲在第一個節(jié)點呢？這是由于在查找存儲的節(jié)點的過程中，會比較hash(key)和hash(節(jié)點IP地址)，而在采用了NATIVE_HASH的情況下，所有連接的hash值會呈現(xiàn)一個遞增狀況（因為String.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()會通常小于這些值的第一個，那么查找就經(jīng)常只找到第一個節(jié)點并存儲數(shù)據(jù)，當(dāng)然，這里有測試的局限性，因為memcached都跑在一個臺機器上只是端口不同造成了hash(節(jié)點IP地址)的連續(xù)遞增，將分布不均勻的問題放大了。
2、從結(jié)果上看，KETAMA_HASH維持了一個最佳平衡，在增加兩個節(jié)點后還能訪問到83.3%的單詞，并且數(shù)據(jù)分布在各個節(jié)點上的數(shù)目也相對平均，難怪作為默認散列算法。
3、最后，單純比較下散列函數(shù)的計算效率：
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