一、背景资料
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
测试所用文件见附件
分享到:
相关推荐
一致性哈希是一种以提供或删除一个插槽不会显着改变键到插槽的映射的方式提供哈希表功能的方案。 可以在博客文章中阅读有关hash_ring的更多信息(该文章更详细地解释了该想法): 一致的散列仅在python中实现 这些...
5. **负载均衡策略**:在多节点环境中,平衡哈希还可以结合负载均衡策略,如一致性哈希(Consistent Hashing)、虚拟节点等,进一步优化节点的负载分布。 6. **动态调整**:当系统中节点数量发生变化时,平衡哈希...
- `memcache.hash_function`:散列函数的选择,“crc32”使用CRC32算法,“fnv”使用FNV-1a算法,后者虽然速度略慢但散列效果更优。 #### 五、Memcache的使用示例 以下是一个基本的Memcache使用代码示例: ```php...
- 一致性哈希特别适合于分布式缓存系统,如Memcached和Redis集群。 **一致性哈希的工作原理:** 1. **哈希环**: - 一致性哈希将所有的节点映射到一个0到2^32-1的环形空间上。 - 每个节点都对应环上的一个位置。...