建站
咨询
售后
建站咨询
基于murmurhash+List实现一致性Hash
一致性Hash原理这里不再介绍了，下面是一个简单版的实现方案。
1、MurmurHashUtils
package com.jane.pos.sync.utils;
import java.io.UnsupportedEncodingException;
import java.math.BigDecimal;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
/**
* 利用murmurHash实现高性能的低碰撞的纯数字hash值
*/
public class MurmurHashUtils {
private static final String UTF_8 = "UTF-8";
public static long hash74A(byte[] data, int seed) {
return hash74A(ByteBuffer.wrap(data), seed);
}
public static long hash74A(ByteBuffer buf, int seed) {
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(byte[] key) {
return hash74A(key, 0x1234ABCD);
}
public static long hash(String key) {
return hash(encode(key));
}
/**
* 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));
}
private static byte[] encode(String data) {
try {
return data.getBytes(UTF_8);
} catch (UnsupportedEncodingException e) {
throw new IllegalArgumentException(e);
}
}
}
2、HashUtils
package com.jane.pos.sync.utils;
import java.math.BigDecimal;
import java.util.*;
public class HashUtils {
/**
* 真实节点虚拟化,为了节点分布均衡
* @param realNodes 真实节点列表
* @param inventedNum 每个节点虚拟的节点个数
* @param hashList 用数组模拟hash环
* @return
*/
public static Map inventedNodes(String[] realNodes, int inventedNum, List hashList) {
//虚拟点和真实节点的对应关系
Map map = new HashMap<>();
if(realNodes.length > 0) {
for (String node : realNodes) {
for(int i = 1; i <= inventedNum; i++) {
BigDecimal hashCode = MurmurHashUtils.hashUnsigned(node + i);
map.put(hashCode, node);
//组建hash值数组，模拟hash环
hashList.add(hashCode);
}
}
}
return map;
}
/**
* 根据key获取固定的一致性节点
* @param realNodes 真实节点
* @param inventedNum 虚拟的节点数量
* @param key hash的key,这个key对应一个固定的唯一的真实节点
* @return
*/
public static String getFixedOnlyNode(String[] realNodes, int inventedNum, String key) {
List hashList = new ArrayList<>();
Map map = inventedNodes(realNodes, inventedNum, hashList);
//hash数组排序
Collections.sort(hashList);
BigDecimal findHash = MurmurHashUtils.hashUnsigned(key);
for(BigDecimal item : hashList){
//第一个大的节点，即为要的节点
if(item.compareTo(findHash) == 1 ) {
return map.get(item);
}
}
//未命中的key,对节点取余当作下标，获取真实节点
return map.get(findHash.divideAndRemainder(BigDecimal.valueOf(hashList.size()))[1]);
}
}
3、启动文件
public static void main(String[] args) throws InterruptedException {
String storeNo = "store";
String[] nodes = {"tag01","tag02","tag03","tag04","tag05"};
for (int i = 0; i <= 10; i++){
String key = storeNo + i;
for (int j = 0; j <= 10; j++) {
String node = HashUtils.getFixedOnlyNode(nodes, 10, key);
System.out.println(key + "----" + node);
}
}
}4、结果
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store0----tag01
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store1----tag03
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store2----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store3----tag01
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store4----tag02
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store5----tag05
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store6----tag01
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store7----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store8----tag05
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store9----tag02
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03
store10----tag03分享名称：基于murmurhash+List实现一致性Hash
网页URL：http://lswzjz.com/article/jgcgdd.html
