- 浏览: 250474 次
- 性别:
- 来自: 苏州
文章分类
- 全部博客 (289)
- java (72)
- oracle (3)
- mysql (5)
- spring (28)
- hibernate (2)
- osgi (0)
- linux (2)
- ExtJs (1)
- jvm (0)
- mybatis (7)
- 分布式 (11)
- MINA (6)
- apache+tomcat (13)
- js+htm (7)
- android (44)
- http (1)
- hbase+hdoop (0)
- memcache (13)
- search (27)
- 部署及性能 (12)
- mongoDB (2)
- 多线程 (12)
- 安全管理验证 (9)
- struts (1)
- webservice (0)
- easyUI (1)
- spring security (16)
- pattern (6)
- 算法 (2)
最新评论
-
lzh8189146:
CommonsHttpSolrServer这个类,现在是不是没 ...
CommonsHttpSolrServer -
xiaochanzi:
我按照你的方法试了下,tomcat6可以发布,但是访问任何网页 ...
基于内嵌Tomcat的应用开发 -
phoneeye:
麻烦你,如果是抄来的文章,请给出来源。谢谢
ant 两则技巧 -
neverforget:
转载不注明出处
Spring Security3.1登陆验证 替换 usernamepasswordfilter -
liang1022:
若不使用eclipse ,如何在命令行下 运行服务端程序 ?
WebService CXF学习(入门篇2):HelloWorld
原文地址:http://www.iteye.com/topic/684087
一致性哈希算法(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的介绍
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分配在相同节点上的比例(命中率)。
多次测试后发现,命中率与结点数目和增减的节点数量有关。同样增删结点数目情况下,结点多时命中率高。同样节点数目,增删结点越少,命中率越高。这些都与实际情况相符。
发表评论
-
Java keytool 安全证书学习笔记
2012-08-02 14:16 761http://linliangyi2007.iteye.com ... -
java国际化
2012-07-16 14:08 381http://lavasoft.blog.51cto.com/ ... -
Java版远程控制V1.0
2012-06-17 21:37 713http://www.cnblogs.com/syxchina ... -
浅析Java中CountDownLatch用法
2012-05-16 20:57 767CountDownLatch如其所写,是一个 ... -
SMTP发送邮件
2012-04-18 09:41 729SMTP发送邮件 openkk 2011-06-0 ... -
smtp 返回代码 信息
2012-04-18 08:52 1417SMTP Server Response Cod ... -
JavaMail详解
2012-04-18 02:24 0JavaMail详解 博客分类: JAV ... -
安装Eclipse反编译插件
2012-04-17 09:34 779安装Eclipse反编译插件 博客分类: ... -
Java编程中“为了性能”尽量要做到的一些地方
2012-04-13 08:30 641最近的机器内存又爆满了,除了新增机器内存外,还应该好好r ... -
Dijkstra算法
2012-04-11 08:00 831Dijkstra算法 博客分类: 算 ... -
java 播放音乐
2012-04-11 08:00 974java 播放音乐 博客分类: J2 ... -
Java中的native,transient,volatile和strictfp关键字
2012-04-06 08:49 707Java中的native,transient,v ... -
用ReentrantLock模拟宴会的热闹情景
2012-04-05 08:32 876用ReentrantLock模拟宴会的热闹情景 ... -
Hashmap 分析
2012-04-05 08:32 702Hashmap 博客分类: 算法 ... -
ExecutorService线程池
2012-04-05 08:32 732ExecutorService线程池 (2010 ... -
Java并发:juc Executor框架详解
2012-04-05 08:32 739Java并发:juc Executor ... -
java并发包,多线程,工具类,笔记
2012-04-11 08:00 864JDK 线程池 Executors.newCachedT ... -
利用 Spring 和 EHCache 做方法缓存处理〔转〕
2012-04-09 09:49 801利用 Spring 和 EHCache 做方法缓存处理〔 ... -
EhCache使用详细介绍
2012-04-09 09:49 1324EhCache使用详细介绍 Ehcache中不仅可 ... -
HashMap 分析
2012-04-01 08:21 1865http://www.blogjava.net ...
相关推荐
Hash函数是提供数据完整性保障的一个...本次实验,我们希望通过上机操作,使 同学们对安全Hash算法SHA-1的基本原理有一个全面的理解。通过本次实验,使学生掌握对 Hash函数的应用,为后面数字签名方案的学习打下基础。
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
Hash函数是提供数据完整性保障的一个...本次实验,我们希望通过上机操作,使同学们对安全Hash算法SHA-1的基本原理有一个全面的理解。通过本次实验,使学生掌握对Hash函数的应用,为后面数字签名方案的学习打下基础。
如果没有找到,则取整个环的第个节点。测试结果测试代码是整理的,主体法没有变分布平均性测试:测试随机成的众多key是否会平均分布到各个结点上测试结果如下:最上是参
最快的排序算法 最快的内容查找算法-----暴雪的Hash算法,排序算法数据结构
python_geohash-0.8.5-cp39-cp39-win_amd64
python_geohash-0.8.5-cp37-cp37m-win_amd64
Hash算法的介绍,属于课件形式,图文并茂介绍Hash的原理和应用。
各种hash算法,可用于编写自己需要的hash值应用代码
python_geohash-0.8.5-cp36-cp36m-win32
MurmurHash算法由Austin Appleby创建于2008年,现已应用到Hadoop、libstdc 、nginx、libmemcached,Redis,Memcached,Cassandra,HBase,Lucene等开源系统。2011年Appleby被Google雇佣,随后Google推出其变种的...
赠送jar包:shiro-crypto-hash-1.4.0.jar; 赠送原API文档:shiro-crypto-hash-1.4.0-javadoc.jar; 赠送源代码:shiro-crypto-hash-1.4.0-sources.jar; 赠送Maven依赖信息文件:shiro-crypto-hash-1.4.0.pom; ...
python_geohash-0.8.5-cp35-cp35m-win_amd64
最快的排序算法 计算机最快的算法-史上14个最快速算法:孩子的计算能力爆表!大脑堪比计算机!...,排序算法数据结构
An implementation of the hash functions SHA-256, 384 and 512 is presented, obtaining a high clock rate through a re- duction of the critical path length, both in the Expander and in the Compressor of ...
2013-12-4最新亲测可用好友hash算法
赠送jar包:shiro-crypto-hash-1.4.0.jar; 赠送原API文档:shiro-crypto-hash-1.4.0-javadoc.jar; 赠送源代码:shiro-crypto-hash-1.4.0-sources.jar; 赠送Maven依赖信息文件:shiro-crypto-hash-1.4.0.pom; ...
Hash函数集合,包含主流的hash函数: nginx_hash算法,OpenSSL_hash算法,RSHash,JSHash,PJWHash,ELFHash,BKDRHash,DJBHash,DEKHash,APHash等等!
Hash-Hash-Hash
python_geohash-0.8.5-cp37-cp37m-win32