一致性 hash 算法 -java

用户头像
jason
关注
发布于: 2020 年 07 月 08 日

1、hash算法采用Murmurs;

2、hash环采用自带有序的树形数据结构:TreeMap;



Murmurs hash算法

import java.math.BigDecimal;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
/**
* Murmurs Hash 算法 高效低碰撞率
*/
public class Murmurs {
/**
* murmur hash算法实现
*/
public static Long hash(byte[] key) {
ByteBuffer buf = ByteBuffer.wrap(key);
int seed = 0x1234ABCD;
ByteOrder byteOrder = buf.order();
buf.order(ByteOrder.LITTLE_ENDIAN);
long m = 0xc6a4a7935bd1e995L;
int r = 47;
long h = seed ^ (buf.remaining() * m);
long k;
while (buf.remaining() >= 8) {
k = buf.getLong();
k *= m;
k ^= k >>> r;
k *= m;
h ^= k;
h *= m;
}
if (buf.remaining() > 0) {
ByteBuffer finish = ByteBuffer.allocate(8).order(
ByteOrder.LITTLE_ENDIAN);
// for big-endian version, do this first:
// finish.position(8-buf.remaining());
finish.put(buf).rewind();
h ^= finish.getLong();
h *= m;
}
h ^= h >>> r;
h *= m;
h ^= h >>> r;
buf.order(byteOrder);
return h;
}
public static Long hash(String key) {
return hash(key.getBytes());
}
/**
* Long转换成无符号长整型(C中数据类型)
*/
public static BigDecimal readUnsignedLong(long value) {
if (value >= 0)
return new BigDecimal(value);
long lowValue = value & 0x7fffffffffffffffL;
return BigDecimal.valueOf(lowValue).add(BigDecimal.valueOf(Long.MAX_VALUE)).add(BigDecimal.valueOf(1));
}
/**
* 返回无符号murmur hash值
*/
public static BigDecimal hashUnsigned(String key) {
return readUnsignedLong(hash(key));
}
public static BigDecimal hashUnsigned(byte[] key) {
return readUnsignedLong(hash(key));
}
}



一致性hash + 负载均衡性测试

import java.util.*;
public class ConsistentHashing {
//真实服务结点
private static List<String> realServerNodes = new LinkedList<String>();
//hash环:使用有序树形数据结构
private static SortedMap<Long, String> hashCircle = new TreeMap<Long, String>();
static {
//先模拟注册10个真实结点列表中
for (int i = 0; i < 10; i++) {
realServerNodes.add("192.1.1." + i);
}
//把真实节点通过hash算法写入到hash环
for (String str : realServerNodes) {
Long hash = Murmurs.hash(str);
hashCircle.put(hash, str);
}
System.out.println();
}
//得到应当路由到的结点
private static String getServer(String key) {
//得到该key的hash值
Long hash = Murmurs.hash(key);
// 得到大于该Hash值的所有Map
SortedMap<Long, String> subMap = hashCircle.tailMap(hash);
String serverNode;
if (subMap.isEmpty()) {
//如果没有比该key的hash值大的,则从第一个node开始
Long i = hashCircle.firstKey();
//返回对应的服务器
serverNode = hashCircle.get(i);
} else {
//第一个Key就是顺时针过去离node最近的那个结点
Long i = subMap.firstKey();
//返回对应的服务器
serverNode = subMap.get(i);
}
return serverNode;
}
public static void main(String[] args) {
HashMap<String, Integer> jsq = new HashMap();
for (int i = 0; i < 1000000; i++) {
String key = new Random(1000) + "fsd323e3" + new Random(1000);
String serverNode = getServer(key);
System.out.println("命中节点:" + serverNode);
if (jsq.get(serverNode) != null) {
jsq.put(serverNode, jsq.get(serverNode) + 1);
} else {
jsq.put(serverNode, 1);
}
}
for (Map.Entry<String, Integer> entry : jsq.entrySet()) {
System.out.println("serverNode: " + entry.getKey() + "; 命中次数: " + entry.getValue());
}
}
}



测试结果:

serverNode: 192.1.1.8; 命中次数: 6626

serverNode: 192.1.1.9; 命中次数: 10162

serverNode: 192.1.1.6; 命中次数: 153780

serverNode: 192.1.1.7; 命中次数: 290582

serverNode: 192.1.1.0; 命中次数: 24298

serverNode: 192.1.1.1; 命中次数: 92808

serverNode: 192.1.1.4; 命中次数: 183800

serverNode: 192.1.1.5; 命中次数: 69769

serverNode: 192.1.1.2; 命中次数: 1641

serverNode: 192.1.1.3; 命中次数: 166534



发布于: 2020 年 07 月 08 日 阅读数: 42
用户头像

jason

关注

还未添加个人签名 2017.10.22 加入

还未添加个人简介

评论

发布
暂无评论
一致性hash算法-java