memcached分布测试报告(一致性哈希情况下的散列函数选择) -买球官网平台

`

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

    博客分类:
  • java

一、背景资料

    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

 

   测试所用文件见附件

  • (40.7 kb)
  • 下载次数: 857
分享到:
评论
4 楼 2010-01-20  
badqiu 写道
string.hashcode()在应用一致性hash时还有分布不均匀的问题,所以是使用fnv1是比较好的选择
而计算md5再hash则效率太低!


memcached的客户端一般运行在前端服务器上,例如web服务器,一般不存储状态数据,因此可以简单通过简单的负载均衡线性的增加计算能力。而服务器端数据量扩大时,在资源占用和计算效率上都会受影响。因此我认为应在调用者采取尽可能好的算法来提高服务器端的利用率。
3 楼 2009-11-10  
string.hashcode()在应用一致性hash时还有分布不均匀的问题,所以是使用fnv1是比较好的选择
而计算md5再hash则效率太低!
2 楼 2009-04-24  
我只对文中的图比较感兴趣。是用什么画的?主要是那个渐变色的处理
1 楼 2009-04-24  
最近我也在学 tokyo系列产品,也碰到java 客户端的问题

相关推荐

    全面的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的一个服务每次开机时自动启动...

    在windows下安装memcached时,下了很多资源,很多都不能用或者不确定当前版本是否与本地php版本相对应。于是就整了份完整资料,给有需要的人。本地php是5.3版本的,所以压缩包里放了memcached 2.2.6版的...

    和memcached类似,它支持存储的value类型相对更多,包括string(字符串)、 list(链表)、set(集合)、zset(sorted set –有序集合)和hash(哈希类型)。这些数据类型都支持push/pop、add/remove及取交集并集和差集及更...

    对于 memcached 来说,本身是集中式的缓存系统,要搞多节点分布,只能通过客户端实现。memcached 的分布算法一般有两种选择:

    memcached安装包及测试

    一个完整的memcached使用实例,memcached安装在windows上,使用java代码测试memcached是否安装部署成功,包括编译好的exe 及 jar文件,使用请看readme.txt文件

    memcache redis tair 性能测试报告,精心准备的常用缓存工具的性能测试报告,非常详细

    memcached 64位 window memcached 64位 window memcached 64位 window

    memcached, libevent, memcachedclient

    监测memcached运行情况的几种方法

global site tag (gtag.js) - google analytics