memcached分布测试报告（一致性哈希情况下的散列函数选择）
一致性哈希算法来源于P2P网络的路由算法，更多的信息可以读这里。
二、测试报告
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就是?CRC32_HASHKETAMA_HASHFNV1_32_HASHNATIVE_HASHMYSQL_HASH命中率78.5%83.3%78.2%99.89%86.9%节点13193665463596271节点23993501911233节点34133624910665节点4393364214142节点54644034271421节点64723062990285节点72833471230635节点83823872572408节点9238341297055节点102393757560586范围200~500300~400150~7500~360050~650
结果分析：
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
?
String.hashCode()在应用一致性hash时还有分布不均匀的问题，所以是使用FNV1是比较好的选择
而计算MD5再hash则效率太低！
?
badqiu 写道String.hashCode()在应用一致性hash时还有分布不均匀的问题，所以是使用FNV1是比较好的选择Memcached的客户端一般运行在前端服务器上，例如Web服务器，一般不存储状态数据，因此可以简单通过简单的负载均衡线性的增加计算能 力。而服务器端数据量扩大时，在资源占用和计算效率上都会受影响。因此我认为应在调用者采取尽可能好的算法来提高服务器端的利用率。?
