- 浏览: 190090 次
- 性别:
- 来自: 杭州
博客专栏
-
Percolator与分布...
浏览量:5551
文章分类
最新评论
-
heglase:
好牛逼 竟然解决了我别的问题
使用jdk工具tools.jar引发的问题 -
wqcva:
在使用这个类的时候workerId应该怎么传
java时间有序id生成 -
沙漠绿树:
增加虚拟节点解决数据均衡的问题。我有个疑问:1.使用虚拟节点后 ...
一致性hash的实现 -
BucketLi:
wangjian95 写道tddl.....?不是
java唯一ID生成 -
wangjian95:
tddl.....?
java唯一ID生成
参照了dennis_zane同学的实现,并且测试了不同虚拟节点和不同hash算法对数据均衡度影响.hash算法实现参考前面的<java几个有用的Hash算法>一文
使用默认KETAMA_HASH,
使用1024个虚拟节点,
前面有一篇<java几个有用的Hash算法>
import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.TreeMap; public class MyConsistHash { // 平均虚拟节点数 int NUM_REPS = 160; HashAlgorithm alg = HashAlgorithm.KETAMA_HASH; public static byte[] computeMD5(final String k) { MessageDigest md5; try { md5 = MessageDigest.getInstance("MD5"); } catch (NoSuchAlgorithmException e) { throw new RuntimeException("MD5 not supported", e); } md5.reset(); md5.update(k.getBytes()); return md5.digest(); } public TreeMap<Long, String> buildMacMap(final List<String> macIps) { final TreeMap<Long/* hash */, String/* macIp */> macMap = new TreeMap<Long, String>(); for (String ip : macIps) { if (this.alg == HashAlgorithm.KETAMA_HASH) { for (int i = 0; i < NUM_REPS / 4; i++) { final byte[] digest = HashAlgorithm.computeMd5(ip + "-" + i); for (int h = 0; h < 4; h++) { final 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; macMap.put(k, ip); } } } else { for (int i = 0; i < NUM_REPS; i++) { final long key = this.alg.hash(ip + "-" + i); macMap.put(key, ip); } } } return macMap; } public String findMacByKey(final TreeMap<Long, String> macMap, final String key) { final Long hash = this.alg.hash(key); Long target = hash; if (!macMap.containsKey(hash)) { target = macMap.ceilingKey(hash); if (target == null && !macMap.isEmpty()) { target = macMap.firstKey(); } } final String targetMac = macMap.get(target); return targetMac; } public static void main(String[] args){ List<String> ips=new ArrayList<String>(); ips.add("10.232.0.2"); ips.add("10.232.0.3"); ips.add("10.232.0.4"); ips.add("10.232.0.5"); ips.add("10.232.0.6"); ips.add("10.232.0.27"); ips.add("10.232.0.28"); ips.add("10.232.0.68"); ips.add("10.232.0.97"); MyConsistHash hash=new MyConsistHash(); // hash.setNUM_REPS(1024); // hash.setAlg(HashAlgorithm.CRC32_HASH); TreeMap<Long,String> macMap=hash.buildMacMap(ips); Map<String,Long> stat=new HashMap<String,Long>(); long start=System.currentTimeMillis(); for(int i=0;i<100000;i++){ String ip=hash.findMacByKey(macMap, "a"+i); Long count=stat.get(ip); if(count==null){ stat.put(ip, new Long(0)); }else{ stat.put(ip, count+1); } } System.out.println(System.currentTimeMillis()-start); for(Map.Entry<String,Long> entry:stat.entrySet()){ System.out.println("mac:"+entry.getKey()+" hits:"+entry.getValue()); } } public void setAlg(HashAlgorithm alg) { this.alg = alg; } public void setNUM_REPS(int nUM_REPS) { NUM_REPS = nUM_REPS; } }
使用默认KETAMA_HASH,
80个虚拟节点:254ms mac:10.232.0.28 hits:10079 mac:10.232.0.68 hits:9699 mac:10.232.0.2 hits:10621 mac:10.232.0.3 hits:9798 mac:10.232.0.4 hits:13422 mac:10.232.0.5 hits:10045 mac:10.232.0.27 hits:10871 mac:10.232.0.6 hits:14791 mac:10.232.0.97 hits:10665 160个虚拟节点:265ms mac:10.232.0.28 hits:12355 mac:10.232.0.68 hits:11182 mac:10.232.0.2 hits:11178 mac:10.232.0.3 hits:9750 mac:10.232.0.4 hits:12429 mac:10.232.0.5 hits:9641 mac:10.232.0.27 hits:10777 mac:10.232.0.6 hits:10610 mac:10.232.0.97 hits:12069 320个虚拟节点:249ms mac:10.232.0.28 hits:11466 mac:10.232.0.68 hits:10064 mac:10.232.0.2 hits:11004 mac:10.232.0.3 hits:10186 mac:10.232.0.4 hits:11570 mac:10.232.0.5 hits:10740 mac:10.232.0.27 hits:11249 mac:10.232.0.6 hits:11324 mac:10.232.0.97 hits:12388 640个虚拟节点:245ms mac:10.232.0.28 hits:10701 mac:10.232.0.68 hits:10978 mac:10.232.0.2 hits:11272 mac:10.232.0.3 hits:10566 mac:10.232.0.4 hits:11700 mac:10.232.0.5 hits:10512 mac:10.232.0.27 hits:11314 mac:10.232.0.6 hits:11541 mac:10.232.0.97 hits:11407 1024个虚拟节点:224 ms mac:10.232.0.28 hits:11196 mac:10.232.0.68 hits:11198 mac:10.232.0.2 hits:11063 mac:10.232.0.3 hits:10930 mac:10.232.0.4 hits:11623 mac:10.232.0.5 hits:10448 mac:10.232.0.27 hits:11289 mac:10.232.0.6 hits:11508 mac:10.232.0.97 hits:10736
使用1024个虚拟节点,
CRC32_HASH:120ms mac:10.232.0.28 hits:10668 mac:10.232.0.68 hits:13738 mac:10.232.0.2 hits:8805 mac:10.232.0.3 hits:10010 mac:10.232.0.4 hits:9525 mac:10.232.0.5 hits:10088 mac:10.232.0.6 hits:12162 mac:10.232.0.27 hits:10855 mac:10.232.0.97 hits:14140 KETAMA_HASH:227ms mac:10.232.0.28 hits:11196 mac:10.232.0.68 hits:11198 mac:10.232.0.2 hits:11063 mac:10.232.0.3 hits:10930 mac:10.232.0.4 hits:11623 mac:10.232.0.5 hits:10448 mac:10.232.0.27 hits:11289 mac:10.232.0.6 hits:11508 mac:10.232.0.97 hits:10736 MYSQL_HASH:82ms mac:10.232.0.28 hits:10119 mac:10.232.0.68 hits:13599 mac:10.232.0.2 hits:15329 mac:10.232.0.3 hits:16799 mac:10.232.0.4 hits:7199 mac:10.232.0.5 hits:10159 mac:10.232.0.27 hits:8519 mac:10.232.0.6 hits:3899 mac:10.232.0.97 hits:14369 ELECTION_HASH:243ms mac:10.232.0.28 hits:11054 mac:10.232.0.68 hits:10554 mac:10.232.0.2 hits:11180 mac:10.232.0.3 hits:11092 mac:10.232.0.4 hits:11137 mac:10.232.0.5 hits:11519 mac:10.232.0.27 hits:10753 mac:10.232.0.6 hits:11412 mac:10.232.0.97 hits:11290 LUA_HASH:113ms mac:10.232.0.28 hits:10950 mac:10.232.0.68 hits:11137 mac:10.232.0.2 hits:10783 mac:10.232.0.3 hits:11370 mac:10.232.0.4 hits:11143 mac:10.232.0.5 hits:10991 mac:10.232.0.27 hits:11645 mac:10.232.0.6 hits:11048 mac:10.232.0.97 hits:10924 NATIVE_HASH:81ms mac:10.232.0.68 hits:89999 mac:10.232.0.2 hits:9999 ...
评论
3 楼
沙漠绿树
2015-01-15
增加虚拟节点解决数据均衡的问题。我有个疑问:
1.使用虚拟节点后,但是当我增加物理节点后,环中的虚拟节点是否要增加,如果把他应用在mysql上,数据迁移是否会很困难?
2.在使用虚拟节点时,比如5个物理节点,每个物理节点虚拟出1024个虚节点,按道理hash环有5120个节点,但是使用kemata哈希虚拟环时,有些节点key的哈希结果相同,导致hash环中少于5120个节点?
1.使用虚拟节点后,但是当我增加物理节点后,环中的虚拟节点是否要增加,如果把他应用在mysql上,数据迁移是否会很困难?
2.在使用虚拟节点时,比如5个物理节点,每个物理节点虚拟出1024个虚节点,按道理hash环有5120个节点,但是使用kemata哈希虚拟环时,有些节点key的哈希结果相同,导致hash环中少于5120个节点?
2 楼
BucketLi
2012-08-23
lyy3323 写道
大概看了一下。如果吧hash的具体算法再抽离出来更好。
前面有一篇<java几个有用的Hash算法>
1 楼
lyy3323
2012-08-06
大概看了一下。如果吧hash的具体算法再抽离出来更好。
发表评论
-
Spring Validator 部分注解说明
2021-01-30 17:13 311@AssertFalse Boole ... -
Mac 安装 OpenJDK
2019-07-17 08:05 782现在 ORACLE 新版本 JDK 越发越快,新版本固然好,但 ... -
git fork 分支合并原分支
2019-06-27 10:35 10391. List the current configured ... -
Cobar内存快速检测tips
2017-11-07 17:20 338很长时间没有使用mat,技巧生疏,趁这次使用Cobar(htt ... -
ORACLE CDC增量同步初始化
2016-09-07 22:29 714// Step 1 Find the source tab ... -
一些文章
2015-09-04 14:38 0http://www.biaodianfu.com/herme ... -
java资源加载
2015-04-22 10:04 557tips下。 this.getClass().getReso ... -
使用jdk工具tools.jar引发的问题
2015-04-22 09:31 1680这里tips下这个问题 之前本地开发机使用jdk7进行开发和 ... -
eclipse for mac快捷键
2015-02-26 13:16 669Command + O:显示大纲 Command + D:删除 ... -
zookeeper client的一些操作
2014-11-07 12:30 6681.登陆 ./zkcli.sh -server 127.0.0 ... -
java获取类版本和检查重复代码
2014-10-13 21:59 1341public final class Version { ... -
java代码细节
2014-10-17 09:29 806看代码过程中一些细节记录,不断补充。质量可靠,开发高效的捷径在 ... -
java程序启动的一些设置
2014-09-19 11:14 01. 开启debug,suspend值设置成y会等待debug ... -
java_web开发tips
2014-07-21 09:44 01.这两天接手一个新的应用,打算在上面开发几个api,因为功能 ... -
信息安全基础
2014-07-21 09:46 711转自某微博,这边tips下,虽然很不完全,但是有一些思路 信 ... -
java 的一些排序方法(转)
2014-07-21 09:48 681一些java排序方法,记录下。 package com.ta ... -
Shift-And和Shift-Or ByteBuffer匹配器
2012-09-07 18:15 1476两个ByteBuffer的匹配算法java实现,原作者 庄大侠 ... -
一个简单的BufferPool
2012-08-31 10:15 924一个简单的buffer分配和收集代码,将一大段buffer分片 ... -
一个典型md5生成工具类
2012-08-23 09:27 1128import java.io.UnsupportedEnc ... -
Java程序员常用工具集(转)
2012-08-31 10:18 989转自庄大侠(killme2008)的博客,我这边收藏下。 原 ...
相关推荐
简单模拟实现一致性Hash,透过虚拟节点映射至实际结点,解决一致性Hash的单调性和平衡性问题。
别人写的一个一致性hash的java实现,分享下
一致性hash应用于负载均衡算法,本实现由C++语言开发。 一致性hash算法提出了在动态变化的Cache环境中,判定哈希算法好坏的四个定义: 1、平衡性(Balance)2、单调性(Monotonicity) 3、分散性(Spread)4、负载(Load)
一致性Hash算法的原理及实现
Ketama算法是一致性hash算法的一个优秀实现。增删节点后数据命中率及均分率都很高。
一致性hash算法简介加C++实现
一致性hash算法实现有两个关键问题需要解决,一个是用于结点存储和查找的数据结构的选择,另一个是结点hash算法的选择。 首先来谈一下一致性hash算法中用于存储结点的数据结构。通过了解一致性hash的原理,我们...
c++实现的一致性hash算法库,可以直接编译成静态库、动态库,包含demo程序。
一致性Hash算法,易于扩容;添加了 单元测试,使用Spring提供的RestTemplate调用RestFul风格的API接口;整合了 quartz 定时任务框架 ,并进行了封装,只需在构建完定时任务Job类后,在 application-quartz....
一致性哈希算法,广泛应用于分布式计算,C版实现,属于分布式服务器管理的核心算法。
主要介绍了PHP实现的一致性Hash算法,结合实例形式详细分析了php一致性Hash算法的概念、原理及相关实现与使用技巧,需要的朋友可以参考下
设计并实现了TNS网络文件存储系统,该系统基于多服务器存储架构,分别由用户服务器、索引服务器、数据服务器、共享服务器、管理服务器和登录服务器组成,为多用户服务,采用一致性Hash实现负载均衡,支持在客户端...
ConsistentHash 一致性hash算法的 java 和 C++ 实现
基于go语言实现的分布式缓存系统源码+项目说明(以键值对的形式存储数据,一致性hash算法选择存储节点,Protobuf通信协议编解码。用户输入查询请求后,会优先在缓存系统查询,查不到则使用回调函数去源数据库查询,...
本文实例讲述了memcache一致性hash的php实现方法。分享给大家供大家参考。具体如下: 最近在看一些分布式方面的文章,所以就用php实现一致性hash来练练手,以前一般用的是最原始的hash取模做 分布式,当生产过程中...
1、解决案:排序+List 2、解决案:遍历+List 1、最好情况是只有个服务器节点的Hash值于带路由结点的Hash值,其 2、最坏情况是所有服务器节点的H
将hash一致性算法使用java实现,原理参考注释。将代码拷贝到ide环境中即可