一致性hash的实现 -

BucketLi

浏览: 195814 次
性别:
来自: 杭州

最近访客更多访客>>

涓滴之水

cuker919

yang198876

java8988

博主相关

博客

微博

相册

留言

关于我

博客专栏

: Percolator与分布...
浏览量：5686

文章分类

社区版块

存档分类

一致性hash的实现

博客分类：

java基础

参照了dennis_zane同学的实现,并且测试了不同虚拟节点和不同hash算法对数据均衡度影响.hash算法实现参考前面的<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

...

分享到：

Spring ioc容器简要分析 | Linux远程命令执行

2011-12-31 17:49
浏览 3601
评论(3)
分类:互联网
查看更多

3 楼沙漠绿树 2015-01-15

增加虚拟节点解决数据均衡的问题。我有个疑问：
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的具体算法再抽离出来更好。

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

博客专栏

文章分类

社区版块

存档分类

最新评论

一致性hash的实现

评论

发表评论

相关推荐

最近访客 更多访客>>

博主相关

博客专栏

文章分类

社区版块

存档分类

最新评论

一致性hash的实现

评论

发表评论

相关推荐

Spring Validator 部分注解说明

Mac 安装 OpenJDK

git fork 分支合并原分支

Cobar内存快速检测tips

ORACLE CDC增量同步初始化

一些文章

java资源加载

使用jdk工具tools.jar引发的问题

eclipse for mac快捷键

zookeeper client的一些操作

java获取类版本和检查重复代码

java代码细节

java程序启动的一些设置

java_web开发tips

信息安全基础

java 的一些排序方法(转)

Shift-And和Shift-Or ByteBuffer匹配器

一个简单的BufferPool

一个典型md5生成工具类

Java程序员常用工具集(转)

最近访客更多访客>>