基于murmurhash+List实现一致性Hash

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); } } }

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<BigDecimal, String> inventedNodes(String[] realNodes, int inventedNum, List<BigDecimal> hashList) { //虚拟点和真实节点的对应关系 Map<BigDecimal, String> 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<BigDecimal> hashList = new ArrayList<>(); Map<BigDecimal, String> 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]); } }

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); } } }

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

一致性Hash原理这里不再介绍了，下面是一个简单版的实现方案。

1、MurmurHashUtils

2、HashUtils

3、启动文件

4、结果

相关阅读