架构师训练营 一致性 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: 947
192.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 日 阅读数: 50
用户头像

Cloud.

关注

还未添加个人签名 2020.05.14 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 一致性Hash算法Java实现