memcached分布测试报告（一致性哈希情况下的散列函数选择）

一、背景资料

    memcached本身是集中式的缓存系统，要搞多节点分布，只能通过客户端实现。memcached的分布算法一般有两种选择：
1、根 据hash(key)的结果，模连接数的余数决定存储到哪个节点，也就是hash(key)% sessions.size()，这个算法简单快速，表现良好。然而这个算法有个缺点，就是在memcached节点增加或者删除的时候，原有的缓存数据 将大规模失效，命中率大受影响，如果节点数多，缓存数据多，重建缓存的代价太高，因此有了第二个算法。
2、Consistent Hashing，一致性哈希算法，他的查找节点过程如下：
    首先求出memcached服务器（节点）的哈希值，并将其配置到0～2³²的圆（continuum）上。然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过2³²仍然找不到服务器，就会保存到第一台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就是java.lang.String.hashCode()方法返回的long取32位的结 果，MYSQL_HASH是xmemcached添加的传说来自于mysql源码中的哈希函数。

	CRC32_HASH	KETAMA_HASH	FNV1_32_HASH	NATIVE_HASH	MYSQL_HASH
命中率	78.5%	83.3%	78.2%	99.89%	86.9%
节点1	319	366	546	3596	271
节点2	399	350	191	1	233
节点3	413	362	491	0	665
节点4	393	364	214	1	42
节点5	464	403	427	1	421
节点6	472	306	299	0	285
节点7	283	347	123	0	635
节点8	382	387	257	2	408
节点9	238	341	297	0	55
节点10	239	375	756	0	586
范围	200~500	300~400	150~750	0~3600	50~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

 

   测试所用文件见附件

评论

4 楼 Stero 2010-01-20  

badqiu 写道

String.hashCode()在应用一致性hash时还有分布不均匀的问题，所以是使用FNV1是比较好的选择
而计算MD5再hash则效率太低！

Memcached的客户端一般运行在前端服务器上，例如Web服务器，一般不存储状态数据，因此可以简单通过简单的负载均衡线性的增加计算能力。而服务器端数据量扩大时，在资源占用和计算效率上都会受影响。因此我认为应在调用者采取尽可能好的算法来提高服务器端的利用率。

3 楼 badqiu 2009-11-10  

String.hashCode()在应用一致性hash时还有分布不均匀的问题，所以是使用FNV1是比较好的选择
而计算MD5再hash则效率太低！

2 楼 ideafrog 2009-04-24  

我只对文中的图比较感兴趣。是用什么画的？主要是那个渐变色的处理

1 楼 hqman 2009-04-24  

最近我也在学 tokyo系列产品，也碰到java 客户端的问题