一、背景资料
memcached本身是集中式的缓存系统，要搞多节点分布，只能通过客户端实现。memcached的分布算法一般有两种选择：
1、根
据hash(key)的结果，模连接数的余数决定存储到哪个节点，也就是hash(key)%
sessions.size()，这个算法简单快速，表现良好。然而这个算法有个缺点，就是在memcached节点增加或者删除的时候，原有的缓存数据
将大规模失效，命中率大受影响，如果节点数多，缓存数据多，重建缓存的代价太高，因此有了第二个算法。
2、consistent hashing，一致性哈希算法，他的查找节点过程如下：
首先求出memcached服务器（节点）的哈希值，并将其配置到0～232的圆（continuum）上。然后用同样的方法求出存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台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
测试所用文件见附件
- 2009-03-10 16:30
- 浏览 8380
- 评论(4)
- 论坛回复 / 浏览 (4 / 17598)
- 分类:企业架构
相关推荐
ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
全面的memcached测试案列和详细讲解
记忆快取 memcached 一致哈希 memcached： : 请参阅文档：memcached全面剖析（ ） 一致的散列 看到java代码： :
一致性哈希是一种提供哈希表功能的方案，该方式使得添加或删除服务器节点不会显着更改密钥到服务器节点的映射。 用于一致性哈希的算法与libketama相同。 例如，有多种处理错误的方法，例如，当服务器不可用时，您...
c# memcached客户端源码 测试例子
实现一致的哈希，当服务器节点的数量可以增加或减少时（例如在memcached中），可以使用该哈希。 哈希环是使用与libketama相同的算法构建的。 一致性哈希是一种以提供或删除一个插槽不会显着改变键到插槽的映射的方式...
memcached测试的工具类
memcached存储机制 测试 memcached存储机制 测试 memcached存储机制 测试
memcached，redis性能测试，内存缓存系统的性能测试；
session memcached memcached配置需要下载以下jar包并放在tomcat的lib目录下 如果tomcat过多不建议session同步，server间相互同步session很耗资源，高并发环境容易引起session风暴。请根据自己应用情况合理采纳...
null 博文链接：https://geeklee.iteye.com/blog/1607632
在终端（也即cmd命令界面）下输入 ‘c:\memcached\memcached.exe -d install’ 安装 3. 再输入： ‘c:\memcached\memcached.exe -d start’ 启动。note: 以后memcached将作为windows的一个服务每次开机时自动启动...
和memcached类似，它支持存储的value类型相对更多，包括string(字符串)、 list(链表)、set(集合)、zset(sorted set –有序集合)和hash（哈希类型）。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更...
对于 memcached 来说，本身是集中式的缓存系统，要搞多节点分布，只能通过客户端实现。memcached 的分布算法一般有两种选择：
memcached安装包及测试
nginx的session一致性，使用memcached解决所需要的jar包
一个完整的memcached使用实例，memcached安装在windows上，使用java代码测试memcached是否安装部署成功，包括编译好的exe 及 jar文件，使用请看readme.txt文件
memcache redis tair 性能测试报告，精心准备的常用缓存工具的性能测试报告，非常详细
memcached, libevent, memcachedclient
memcached 64位 window memcached 64位 window memcached 64位 window