架构师训练营 一致性 Hash 算法 Java 实现
发布于: 2020 年 07 月 06 日
hash 环的大小使用 int 的最大值 2147483647
每个真实节点的虚拟节点数量为 200
hash 算法使用 FNV32
算出 hash 值和 hash 环的值按位与得到的
算法主类：
public class ConsistenceHash {
private static final long FNV_32_INIT = 2166136261L;
private static final long FNV_32_PRIME = 16777619;
// 虚拟节点树 private TreeMap<Long, Node> treeMap = new TreeMap<>();
// 实际节点列表 private List<String> realNodes;
private int virtual;
public ConsistenceHash(List<String> realNodes) { this(realNodes, 200); }
public ConsistenceHash(List<String> realNodes, int virtual) { this.realNodes = realNodes; this.virtual = virtual; init(); }
private String findNode(String key) { long point = hash(key); Map.Entry<Long, Node> entry = treeMap.ceilingEntry(point); if (Objects.isNull(entry)) { entry = treeMap.firstEntry(); } return entry.getValue().realNode; }
// 初始化虚拟节点 private void init() { String virtualNode; long point; for (int i = 0; i < virtual; i++) { for (String realNode : realNodes) { virtualNode = realNode + "_" + UUIDHexGenerator.generate(); point = hash(virtualNode); treeMap.put(point, new Node(realNode, virtualNode, point)); } } }
// hash值与上环 private long hash(String key) { long hashRing = Integer.MAX_VALUE; return fnv32(key) & hashRing; }
// hash算法 private long fnv32(String key) { long rv = 0; rv = FNV_32_INIT; int len = key.length(); for (int i = 0; i < len; i++) { rv *= FNV_32_PRIME; rv ^= key.charAt(i); } return rv; }
private static class Node implements Comparable<Node> {
//真实节点 private String realNode;
private String virtualNode;
// 该节点对应hash环上的值 private long endPoint;
private Node(String realNode, String virtualNode, long endPoint) { this.realNode = realNode; this.virtualNode = virtualNode; this.endPoint = endPoint; }
@Override public int compareTo(Node o) { return Long.compare(this.endPoint, o.endPoint); } }
public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("192.168.0.10"); list.add("192.168.0.11"); list.add("192.168.0.12"); list.add("192.168.0.13"); list.add("192.168.0.14"); list.add("192.168.0.15"); list.add("192.168.0.16"); list.add("192.168.0.17"); list.add("192.168.0.18"); list.add("192.168.0.19"); ConsistenceHash hash = new ConsistenceHash(list); System.out.println("===============2 树================="); test(s -> hash.findNode(UUIDHexGenerator.generate()));
}
private static void test(Function<String, String> function) { int i = 1000000; Map<String, Integer> countMap = new HashMap<>(); long start = System.currentTimeMillis(); for (int j = 0; j < i; j++) { String node = function.apply(UUIDHexGenerator.generate()); countMap.put(node, countMap.getOrDefault(node, 0) + 1); } long end = System.currentTimeMillis(); System.out.println("cost: " + (end - start)); countMap.forEach((k, v) -> System.out.println(k + " , " + v + " , " + percent(v, i))); double stddev = stdDev(countMap); System.out.println(stddev); }
//计算标准差（抽样标准差） private static double stdDev(Map<String, Integer> countMap) { IntSummaryStatistics summary = countMap.values().stream().collect(Collectors.summarizingInt(o -> o)); double avg = summary.getAverage(); double sum = countMap.values().stream().map(o -> Math.pow(o - avg, 2)).mapToDouble(o -> o).sum(); return Math.sqrt(sum / (double)(summary.getCount() - 1)); }
// 计算占比 private static String percent(int count, int total) { return BigDecimal.valueOf(count) .divide(BigDecimal.valueOf(total), 3, BigDecimal.ROUND_HALF_UP) .multiply(BigDecimal.valueOf(100)) .setScale(2, BigDecimal.ROUND_HALF_UP) .toString() + "%";
}}复制代码
UUID 类：
public class UUIDHexGenerator {
private static final int JVM = (int) (System.currentTimeMillis() >>> 8);
private static String sep = "";
private static int IP;
private static String formatedIP = "";
private static String formatedJVM = "";
private static short counter = (short) 0;
static { int ipadd; try { ipadd = toInt(InetAddress.getLocalHost().getAddress()); } catch (Exception e) { ipadd = 0; } IP = ipadd; formatedIP = format(getIP()); formatedJVM = format(getJVM()); }
public static String generate() { return formatedIP + sep + formatedJVM + sep + format(getHiTime()) + sep + format(getLoTime()) + sep + format(getCount()); }
private static String format(int intValue) { String formatted = Integer.toHexString(intValue); StringBuilder buf = new StringBuilder("00000000"); buf.replace(8 - formatted.length(), 8, formatted); return buf.toString(); }
private static String format(short shortValue) { String formatted = Integer.toHexString(shortValue); StringBuilder buf = new StringBuilder("0000"); buf.replace(4 - formatted.length(), 4, formatted); return buf.toString(); }
private static int getJVM() { return JVM; }
protected static short getCount() { synchronized (UUIDHexGenerator.class) { if (counter < 0) { counter = 0; } return counter++; } }
private static int getIP() { return IP; }
private static short getHiTime() { return (short) (System.currentTimeMillis() >>> 32); }
private static int getLoTime() { return (int) System.currentTimeMillis(); }
private static int toInt(byte[] bytes) { int result = 0; for (int i = 0; i < 4; i++) { result = ((result << 8) - Byte.MIN_VALUE) + bytes[i]; } return result; }}复制代码
输出：
测试用例为 10 个节点，100 万的 uuid 值
标准差（抽样标准差）在 9427 也就是平均误差率在 9.4%左右
根据打印出的占比也可以看出，大部分占比都在 8%到 12%之间，总体来说还是比较均衡的
多次计算，标准差在 8000 到 14000 的范围之内浮动
===============2 树=================cost: 947192.168.0.10 , 85938 , 8.60%192.168.0.11 , 93434 , 9.30%192.168.0.12 , 112281 , 11.20%192.168.0.13 , 96923 , 9.70%192.168.0.14 , 98986 , 9.90%192.168.0.15 , 113675 , 11.40%192.168.0.16 , 98415 , 9.80%192.168.0.17 , 88833 , 8.90%192.168.0.18 , 108689 , 10.90%192.168.0.19 , 102826 , 10.30%9427.359840143768复制代码
划线
评论
复制
发布于: 2020 年 07 月 06 日阅读数: 106
版权声明: 本文为 InfoQ 作者【Cloud.】的原创文章。
原文链接:【http://xie.infoq.cn/article/5cffc400ed98331611a4856db】。未经作者许可，禁止转载。
Cloud.
关注
还未添加个人签名 2020.05.14 加入
还未添加个人简介
评论