- 浏览: 883150 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
u013146595:
楼主你人呢,搬家了吗。还想看你的文章
读代码的“深度优先”与“广度优先”问题 -
zjut_ywf:
写的不错,比书上还具体,受益匪浅
MapReduce:详解Shuffle过程 -
sxzheng96:
<div class="quote_title ...
MapReduce:详解Shuffle过程 -
sxzheng96:
<div class="quote_title ...
MapReduce:详解Shuffle过程 -
jinsedeme0881:
<div class="quote_title ...
MapReduce:详解Shuffle过程
一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法,常用于负载均衡。Memcached client也选择这种算法,解决将key-value均匀分配到众多Memcached server上的问题。它可以取代传统的取模操作,解决了取模操作无法应对增删Memcached Server的问题(增删server会导致同一个key,在get操作时分配不到数据真正存储的server,命中率会急剧下降),详细的介绍在这篇帖子中http://www.iteye.com/topic/611976(后文指代这篇文章的地方均称为引文)。
[下面以Memcached的分布式问题为讨论点,但将Memcached server抽象为节点(Node)]
引文中描述的一致性Hash算法有个潜在的问题是:
将节点hash后会不均匀地分布在环上,这样大量key在寻找节点时,会存在key命中各个节点的概率差别较大,无法实现有效的负载均衡。
如有三个节点Node1,Node2,Node3,分布在环上时三个节点挨的很近,落在环上的key寻找节点时,大量key顺时针总是分配给Node2,而其它两个节点被找到的概率都会很小。
这种问题的解决方案可以有:
改善Hash算法,均匀分配各节点到环上;[引文]使用虚拟节点的思想,为每个物理节点(服务器)在圆上分配100~200个点。这样就能抑制分布不均匀,最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上,就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。
在查看Spy Memcached client时,发现它采用一种称为Ketama的Hash算法,以虚拟节点的思想,解决Memcached的分布式问题。
对Ketama的介绍
下面以Spy Memcached中的代码为例来说明这种算法的使用
该client采用TreeMap存储所有节点,模拟一个环形的逻辑关系。在这个环中,节点之前是存在顺序关系的,所以TreeMap的key必须实现Comparator接口。
那节点是怎样放入这个环中的呢?
上面的流程大概可以这样归纳:四个虚拟结点为一组,以getKeyForNode方法得到这组虚拟节点的name,Md5编码后,每个虚拟结点对应Md5码16个字节中的4个,组成一个long型数值,做为这个虚拟结点在环中的惟一key。第12行k为什么是Long型的呢?呵呵,就是因为Long型实现了Comparator接口。
处理完正式结点在环上的分布后,可以开始key在环上寻找节点的游戏了。
对于每个key还是得完成上面的步骤:计算出Md5,根据Md5的字节数组,通过Kemata Hash算法得到key在这个环中的位置。
引文中已详细描述过这种取节点逻辑:在环上顺时针查找,如果找到某个节点,就返回那个节点;如果没有找到,则取整个环的第一个节点。
测试结果
测试代码是自己整理的,主体方法没有变
分布平均性测试:测试随机生成的众多key是否会平均分布到各个结点上
测试结果如下:
最上面一行是参数说明,节点数目,总共有多少key,每个节点应该分配key的比例是多少。下面是每个结点分配到key的数目和比例。
多次测试后发现,这个Hash算法的节点分布还是不错的,都在标准比例左右徘徊,是个合适的负载均衡算法。
节点增删测试:在环上插入N个结点,每个节点nCopies个虚拟结点。随机生成众多key,在增删节点时,测试同一个key选择相同节点的概率
测试如果如下:
上面三行分别是正常情况,节点增加,节点删除情况下的节点数目。下面两行表示在节点增加和删除情况下,同一个key分配在相同节点上的比例(命中率)。
多次测试后发现,命中率与结点数目和增减的节点数量有关。同样增删结点数目情况下,结点多时命中率高。同样节点数目,增删结点越少,命中率越高。这些都与实际情况相符。
附件为Ketama算法的Java代码及测试代码
如何理解key的哈希冲突?
1、不同的key经过hash运算之后得到同一个hash值?
2、应用中某一个或某几个key非常热?
对于第一种情况输入hash算法问题,hash算法有一个特性是均衡性。均衡性很难保证的hash算法是不合格的。
对于第二种情况,可以在原有hash基础上再次做一次hash,通过二次hash来重建均衡性。ConcurrentHashMap中选择segment就采用了二次hash。
以上是个人理解。
楼主,“均衡性很难保证的hash算法是不合格的。” 这句话怎么理解....
如何理解key的哈希冲突?
1、不同的key经过hash运算之后得到同一个hash值?
2、应用中某一个或某几个key非常热?
对于第一种情况输入hash算法问题,hash算法有一个特性是均衡性。均衡性很难保证的hash算法是不合格的。
对于第二种情况,可以在原有hash基础上再次做一次hash,通过二次hash来重建均衡性。ConcurrentHashMap中选择segment就采用了二次hash。
以上是个人理解。
在代码的注释中我解释过,只是为了适应MD5的16字节
你也看到了,hash函数及虚拟节点的引入都是为了解决尽量让负载在节点间平衡。如果出现不平衡的问题,一定得先查出是什么原因导致。可以从数据的特点来分析,是不是某些数据与其它数据不一样,让hash函数不是那么平均?
如果真的出现这种问题,我们需要更平均地分摊负载。可能的作法有:加节点;增加虚拟节点数量;使用更平均的hash函数。我能想到的就是这几点。你的看法呢?
嗯。我暂时没有好的想法,只是有这么个疑虑
你也看到了,hash函数及虚拟节点的引入都是为了解决尽量让负载在节点间平衡。如果出现不平衡的问题,一定得先查出是什么原因导致。可以从数据的特点来分析,是不是某些数据与其它数据不一样,让hash函数不是那么平均?
如果真的出现这种问题,我们需要更平均地分摊负载。可能的作法有:加节点;增加虚拟节点数量;使用更平均的hash函数。我能想到的就是这几点。你的看法呢?
一台压力比较大的原因是什么?正常情况下不应该的
正常情况下不应该,但是如果出现这种情况,怎么解决呢?
一台压力比较大的原因是什么?正常情况下不应该的
引入虚拟节点的概念是解决物理节点分布不均的问题。所以理论上说,虚拟节点设置的越多,往集群中放数据时选择节点的概率越平等,分布在每台节点的数据也就越均匀。所以这个值的设置由你把握。
Ketama 算法是产生众多虚拟节点的过程,以便key在选择时可以更随机。而key的目的单纯,只是为了选择某个虚拟节点,除了hash就不需要更多的处理。不知道这样解释可能解决你的疑惑?
[下面以Memcached的分布式问题为讨论点,但将Memcached server抽象为节点(Node)]
引文中描述的一致性Hash算法有个潜在的问题是:
将节点hash后会不均匀地分布在环上,这样大量key在寻找节点时,会存在key命中各个节点的概率差别较大,无法实现有效的负载均衡。
如有三个节点Node1,Node2,Node3,分布在环上时三个节点挨的很近,落在环上的key寻找节点时,大量key顺时针总是分配给Node2,而其它两个节点被找到的概率都会很小。
这种问题的解决方案可以有:
改善Hash算法,均匀分配各节点到环上;[引文]使用虚拟节点的思想,为每个物理节点(服务器)在圆上分配100~200个点。这样就能抑制分布不均匀,最大限度地减小服务器增减时的缓存重新分布。用户数据映射在虚拟节点上,就表示用户数据真正存储位置是在该虚拟节点代表的实际物理服务器上。
在查看Spy Memcached client时,发现它采用一种称为Ketama的Hash算法,以虚拟节点的思想,解决Memcached的分布式问题。
对Ketama的介绍
引用
Ketama is an implementation of a consistent hashing algorithm, meaning you can add or remove servers from the memcached pool without causing a complete remap of all keys.
Here’s how it works:
* Take your list of servers (eg: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
* Hash each server string to several (100-200) unsigned ints
* Conceptually, these numbers are placed on a circle called the continuum. (imagine a clock face that goes from 0 to 2^32)
* Each number links to the server it was hashed from, so servers appear at several points on the continuum, by each of the numbers they hashed to.
* To map a key->server, hash your key to a single unsigned int, and find the next biggest number on the continuum. The server linked to that number is the correct server for that key.
* If you hash your key to a value near 2^32 and there are no points on the continuum greater than your hash, return the first server in the continuum.
If you then add or remove a server from the list, only a small proportion of keys end up mapping to different servers.
Here’s how it works:
* Take your list of servers (eg: 1.2.3.4:11211, 5.6.7.8:11211, 9.8.7.6:11211)
* Hash each server string to several (100-200) unsigned ints
* Conceptually, these numbers are placed on a circle called the continuum. (imagine a clock face that goes from 0 to 2^32)
* Each number links to the server it was hashed from, so servers appear at several points on the continuum, by each of the numbers they hashed to.
* To map a key->server, hash your key to a single unsigned int, and find the next biggest number on the continuum. The server linked to that number is the correct server for that key.
* If you hash your key to a value near 2^32 and there are no points on the continuum greater than your hash, return the first server in the continuum.
If you then add or remove a server from the list, only a small proportion of keys end up mapping to different servers.
下面以Spy Memcached中的代码为例来说明这种算法的使用
该client采用TreeMap存储所有节点,模拟一个环形的逻辑关系。在这个环中,节点之前是存在顺序关系的,所以TreeMap的key必须实现Comparator接口。
那节点是怎样放入这个环中的呢?
//对所有节点,生成nCopies个虚拟结点 for(Node node : nodes) { //每四个虚拟结点为一组,为什么这样?下面会说到 for(int i=0; i<nCopies / 4; i++) { //getKeyForNode方法为这组虚拟结点得到惟一名称 byte[] digest=HashAlgorithm.computeMd5(getKeyForNode(node, i)); /** Md5是一个16字节长度的数组,将16字节的数组每四个字节一组, 分别对应一个虚拟结点,这就是为什么上面把虚拟结点四个划分一组的原因*/ for(int h=0;h<4;h++) { //对于每四个字节,组成一个long值数值,做为这个虚拟节点的在环中的惟一key Long k = ((long)(digest[3+h*4]&0xFF) << 24) | ((long)(digest[2+h*4]&0xFF) << 16) | ((long)(digest[1+h*4]&0xFF) << 8) | (digest[h*4]&0xFF); allNodes.put(k, node); } } }
上面的流程大概可以这样归纳:四个虚拟结点为一组,以getKeyForNode方法得到这组虚拟节点的name,Md5编码后,每个虚拟结点对应Md5码16个字节中的4个,组成一个long型数值,做为这个虚拟结点在环中的惟一key。第12行k为什么是Long型的呢?呵呵,就是因为Long型实现了Comparator接口。
处理完正式结点在环上的分布后,可以开始key在环上寻找节点的游戏了。
对于每个key还是得完成上面的步骤:计算出Md5,根据Md5的字节数组,通过Kemata Hash算法得到key在这个环中的位置。
final Node rv; byte[] digest = hashAlg.computeMd5(keyValue); Long key = hashAlg.hash(digest, 0); //如果找到这个节点,直接取节点,返回 if(!ketamaNodes.containsKey(key)) { //得到大于当前key的那个子Map,然后从中取出第一个key,就是大于且离它最近的那个key SortedMap<Long, Node> tailMap=ketamaNodes.tailMap(key); if(tailMap.isEmpty()) { key=ketamaNodes.firstKey(); } else { key=tailMap.firstKey(); } //在JDK1.6中,ceilingKey方法可以返回大于且离它最近的那个key //For JDK1.6 version // key = ketamaNodes.ceilingKey(key); // if (key == null) { // key = ketamaNodes.firstKey(); // } } rv=allNodes.get(key);
引文中已详细描述过这种取节点逻辑:在环上顺时针查找,如果找到某个节点,就返回那个节点;如果没有找到,则取整个环的第一个节点。
测试结果
测试代码是自己整理的,主体方法没有变
分布平均性测试:测试随机生成的众多key是否会平均分布到各个结点上
测试结果如下:
Nodes count : 5, Keys count : 100000, Normal percent : 20.0% -------------------- boundary ---------------------- Node name :node1 - Times : 20821 - Percent : 20.821001% Node name :node3 - Times : 19018 - Percent : 19.018% Node name :node5 - Times : 19726 - Percent : 19.726% Node name :node2 - Times : 19919 - Percent : 19.919% Node name :node4 - Times : 20516 - Percent : 20.516%
最上面一行是参数说明,节点数目,总共有多少key,每个节点应该分配key的比例是多少。下面是每个结点分配到key的数目和比例。
多次测试后发现,这个Hash算法的节点分布还是不错的,都在标准比例左右徘徊,是个合适的负载均衡算法。
节点增删测试:在环上插入N个结点,每个节点nCopies个虚拟结点。随机生成众多key,在增删节点时,测试同一个key选择相同节点的概率
测试如果如下:
Normal case : nodes count : 50 Added case : nodes count : 51 Reduced case : nodes count : 49 ------------ boundary ------------- Same percent in added case : 93.765% Same percent in reduced case : 93.845%
上面三行分别是正常情况,节点增加,节点删除情况下的节点数目。下面两行表示在节点增加和删除情况下,同一个key分配在相同节点上的比例(命中率)。
多次测试后发现,命中率与结点数目和增减的节点数量有关。同样增删结点数目情况下,结点多时命中率高。同样节点数目,增删结点越少,命中率越高。这些都与实际情况相符。
附件为Ketama算法的Java代码及测试代码
- Ketama_Hashing_Algorithm.rar (3.6 KB)
- 下载次数: 3566
评论
34 楼
jasonGe
2016-07-20
Normal case : nodes count : 50
Added case : nodes count : 58
Reduced case : nodes count : 40
81582 --- 75086
Same percent in added case : 81.582%
Same percent in reduced case : 75.086%
楼主你好,这是我运行的结果,平衡性差异挺大啊。第二个58,第三个40 。
能帮忙解释下么?
Added case : nodes count : 58
Reduced case : nodes count : 40
81582 --- 75086
Same percent in added case : 81.582%
Same percent in reduced case : 75.086%
楼主你好,这是我运行的结果,平衡性差异挺大啊。第二个58,第三个40 。
能帮忙解释下么?
33 楼
guliangliang
2016-07-13
tdttyl.cwm 写道
runjia1987 写道
我想知道,如果key的哈希冲突了,乍办?
如何理解key的哈希冲突?
1、不同的key经过hash运算之后得到同一个hash值?
2、应用中某一个或某几个key非常热?
对于第一种情况输入hash算法问题,hash算法有一个特性是均衡性。均衡性很难保证的hash算法是不合格的。
对于第二种情况,可以在原有hash基础上再次做一次hash,通过二次hash来重建均衡性。ConcurrentHashMap中选择segment就采用了二次hash。
以上是个人理解。
楼主,“均衡性很难保证的hash算法是不合格的。” 这句话怎么理解....
32 楼
tdttyl.cwm
2016-02-28
runjia1987 写道
我想知道,如果key的哈希冲突了,乍办?
如何理解key的哈希冲突?
1、不同的key经过hash运算之后得到同一个hash值?
2、应用中某一个或某几个key非常热?
对于第一种情况输入hash算法问题,hash算法有一个特性是均衡性。均衡性很难保证的hash算法是不合格的。
对于第二种情况,可以在原有hash基础上再次做一次hash,通过二次hash来重建均衡性。ConcurrentHashMap中选择segment就采用了二次hash。
以上是个人理解。
31 楼
chenchunji
2015-03-17
哥们,冒昧的问一下。这个代码你们在JAVA项目中应用了吗?
30 楼
runjia1987
2014-09-03
我想知道,如果key的哈希冲突了,乍办?
29 楼
langyu
2012-11-26
kevins.xf 写道
请问为什么要四个虚拟结点为一组呢,没看出来有什么好处
在代码的注释中我解释过,只是为了适应MD5的16字节
28 楼
kevins.xf
2012-11-23
请问为什么要四个虚拟结点为一组呢,没看出来有什么好处
27 楼
grzrt
2012-05-17
langyu 写道
grzrt 写道
正常情况下不应该,但是如果出现这种情况,怎么解决呢?
你也看到了,hash函数及虚拟节点的引入都是为了解决尽量让负载在节点间平衡。如果出现不平衡的问题,一定得先查出是什么原因导致。可以从数据的特点来分析,是不是某些数据与其它数据不一样,让hash函数不是那么平均?
如果真的出现这种问题,我们需要更平均地分摊负载。可能的作法有:加节点;增加虚拟节点数量;使用更平均的hash函数。我能想到的就是这几点。你的看法呢?
嗯。我暂时没有好的想法,只是有这么个疑虑
26 楼
langyu
2012-05-17
grzrt 写道
正常情况下不应该,但是如果出现这种情况,怎么解决呢?
你也看到了,hash函数及虚拟节点的引入都是为了解决尽量让负载在节点间平衡。如果出现不平衡的问题,一定得先查出是什么原因导致。可以从数据的特点来分析,是不是某些数据与其它数据不一样,让hash函数不是那么平均?
如果真的出现这种问题,我们需要更平均地分摊负载。可能的作法有:加节点;增加虚拟节点数量;使用更平均的hash函数。我能想到的就是这几点。你的看法呢?
25 楼
grzrt
2012-05-17
langyu 写道
grzrt 写道
请问增么控制新增加的节点的位置?如果发现原来的其中一台的压力比较大,要减压扩容怎么做呢?
一台压力比较大的原因是什么?正常情况下不应该的
正常情况下不应该,但是如果出现这种情况,怎么解决呢?
24 楼
langyu
2012-05-17
grzrt 写道
请问增么控制新增加的节点的位置?如果发现原来的其中一台的压力比较大,要减压扩容怎么做呢?
一台压力比较大的原因是什么?正常情况下不应该的
23 楼
grzrt
2012-05-17
请问增么控制新增加的节点的位置?如果发现原来的其中一台的压力比较大,要减压扩容怎么做呢?
22 楼
grzrt
2012-05-17
楼主 给力
21 楼
manecocomph
2011-07-19
学习了, 写的真不错
20 楼
langyu
2011-04-20
veenter 写道
我有一个问题: 虚拟节点的多少应该如何设置呢!或者说和物理节点的多少有什么倍数关系吗
引入虚拟节点的概念是解决物理节点分布不均的问题。所以理论上说,虚拟节点设置的越多,往集群中放数据时选择节点的概率越平等,分布在每台节点的数据也就越均匀。所以这个值的设置由你把握。
19 楼
veenter
2011-04-20
我有一个问题: 虚拟节点的多少应该如何设置呢!或者说和物理节点的多少有什么倍数关系吗
18 楼
langyu
2011-04-20
wanrue 写道
楼主,为什么测试用的key不用ketama hash算法处理呢?
Ketama 算法是产生众多虚拟节点的过程,以便key在选择时可以更随机。而key的目的单纯,只是为了选择某个虚拟节点,除了hash就不需要更多的处理。不知道这样解释可能解决你的疑惑?
17 楼
wanrue
2011-04-19
楼主,为什么测试用的key不用ketama hash算法处理呢?
16 楼
wanrue
2011-04-19
楼主 给力
可以参考下了 真需要
可以参考下了 真需要
15 楼
gigi_112
2010-12-22
前提是我用在了数据库中,有个问题想问下,如果由于机房拆迁,你的node更换了IP地址,此时所有隐射都会改变,除了在隐射一次新地址和老地址之外,还有别的方法么
发表评论
-
文件中行级偏移量的一种获取方式
2012-04-11 18:48 16106下面所描述的内容是根据实际需要对BufferedReade ... -
给新人的一些题目
2012-04-05 11:48 12803/* * @Author: dennyy99@gmail.c ... -
新人召集贴,我来出题你来做
2012-04-05 09:26 5/* * @Author: dennyy99@gmail.c ... -
[Java拾遗]初次尝试BCEL:修改类实现的例子
2011-09-15 17:17 6113项目中有个需求 ... -
[Java拾遗]Java对象大小探究
2011-09-07 14:22 8387平时我们不会关心生成的对象到底在JVM中占据多少内存 ... -
闲谈程序中如何打印log
2011-08-13 12:11 17482程序中记录日志一般有两个目的:Troubleshooting ... -
[Java拾遗]迭代list过程中删除元素
2011-07-20 23:21 6621今天在翻看H ... -
某些并发环境下Double-check模型的改进
2010-11-01 14:26 2586简单场景: 多线程环境,每个线程携带惟一的k ... -
详解 Too many open files
2010-09-14 18:01 92570运行在Linux系统上的Java程序可能会出 ... -
Avro总结(RPC/序列化)
2010-07-08 18:13 59432Avro(读音类似于[ævrə])是Hadoop的一 ... -
Memcached CAS 协议
2010-05-31 16:33 41797什么是CAS协议 Memcached于1.2.4版本新增CA ... -
java动态代理学习笔记
2009-06-17 16:30 50885没事的时候翻看lang.refle ... -
如何实现key, value有序的HashMap?
2009-05-22 18:33 13685想要写个key, value有序的HashMap,出现性能问题 ... -
java主要集合类的数据结构学习
2009-04-03 13:57 14492在程序中,集合类每天都在使用,以致于某些代码充斥着List和M ...
相关推荐
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
对已有的负载平衡的改进算法,通过一致性哈希算法,负载平衡更加的有效。
C#一致性hash算法,性能绝对最优。结算结果和Java版本结果完全相同。
smart eredis 是基于ketama算法和eredis项目的redis erlang驱动,主要以一致性hash的方式存储数据,做到key的分布式存储
Ketama Hashing Algorithm java代码完全可以运行,已经添加了Node类,和一些注释。
h uhashring在纯Python中实现一致的哈希。... 面向实例的用法,因此您可以在代码中直接使用一致的哈希环对象(请参阅高级用法)。 原生pypy支持,因为这是一个纯python库。 实施,密钥分发和ketama兼容
ketama:C库,用于一致的哈希和langauge绑定
go-memcache-ketama-选择器 用于Go-memcache的Ketama选择器
记录阅读过的开源代码程序和注释ConsistentHashing一致性哈希的java实现(Ketama),加了注释,可参考。NetworkProgramming网络编程相关的程序源码(包括某些开源软件)及其注释AND一些经过自己修改的可重用的功能...
功能列表数据结构优先队列堆rbtree(red_black_tree) 地图/多地图集/多集位图布隆过滤器hamt(hash_array_mapped_trie) 克塔玛跳过列表算法排序(快速排序) 稳定排序(合并排序) binary_search 下界upper_bound ...
C片段:我的C片段-buf,cfg,datetime,dict,event,heap,ketama,list,log,map,queue,skiplist,stack,strings
-k use ketama key allocation algorithm -f file, unix socket path to listen on. default is off -i number, set max keep alive connections for one memcached server, default is 20 -v verbose 修正问题...
-k use ketama key allocation algorithm -f file, unix socket path to listen on. default is off -i number, set max keep alive connections for one memcached server, default is 20 -v verbose 修正问题...
名称 Cache :: Memcached :: AnyEvent-AnyEvent兼容的Memcached客户端 概要 use Cache::Memcached::AnyEvent; my $memd = Cache::Memcached::AnyEvent->...# use ketama algorithm instead of the traditional one m