实现一致性 hash 算法

用户头像
不在调上
关注
发布于: 2020 年 07 月 05 日



package com.architecture.consistenthash;

import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Collection;
import java.util.Iterator;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHashRouter {
private final SortedMap<Long, VirtualNode> ring = new TreeMap<>();
private HashFunction hashFunction;
public ConsistentHashRouter(Collection<String> pNodes, int vNodeCount) {
this(pNodes,vNodeCount, new MD5Hash());
}

public static interface HashFunction {
public long hash(String key);
}

public ConsistentHashRouter(Collection<String> pNodes, int vNodeCount, HashFunction hashFunction) {
if (hashFunction == null) {
throw new NullPointerException("Hash Function is null");
}
this.hashFunction = hashFunction;
if (pNodes != null) {
for (String pNode : pNodes) {
addNode(pNode, vNodeCount);
}
}
}

public void addNode(String pNode, int vNodeCount) {
if (vNodeCount < 0) throw new IllegalArgumentException("illegal virtual node counts :" + vNodeCount);
int existingReplicas = getExistingReplicas(pNode);
for (int i = 0; i < vNodeCount; i++) {
VirtualNode vNode = new VirtualNode(pNode, i + existingReplicas);
ring.put(hashFunction.hash(vNode.getKey()), vNode);
}
}

public void removeNode(String pNode) {
Iterator<Long> it = ring.keySet().iterator();
while (it.hasNext()) {
Long key = it.next();
VirtualNode virtualNode = ring.get(key);
if (virtualNode.isVirtualNodeOf(pNode)) {
it.remove();
}
}
}

public String routeNode(String objectKey) {
if (ring.isEmpty()) {
return null;
}
Long hashVal = hashFunction.hash(objectKey);
SortedMap<Long,VirtualNode> tailMap = ring.tailMap(hashVal);
Long nodeHashVal = !tailMap.isEmpty() ? tailMap.firstKey() : ring.firstKey();
return ring.get(nodeHashVal).physicalNode;
}



public int getExistingReplicas(String pNode) {
int replicas = 0;
for (VirtualNode vNode : ring.values()) {
if (vNode.isVirtualNodeOf(pNode)) {
replicas++;
}
}
return replicas;
}

private static class MD5Hash implements HashFunction {
MessageDigest instance;

public MD5Hash() {
try {
instance = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException e) {
}
}

@Override
public long hash(String key) {
instance.reset();
instance.update(key.getBytes());
byte[] digest = instance.digest();

long h = 0;
for (int i = 0; i < 4; i++) {
h <<= 8;
h |= ((int) digest[i]) & 0xFF;
}
return h;
}
}

public static void main(String[] args) {
}
}




上面是一致性hash 算法,现在发现谢谢算法也挺好的, 不要光想,写出来的才是王道,我是想的太多,做的太少了,



1

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

不在调上

关注

还未添加个人签名 2018.04.28 加入

还未添加个人简介

评论

发布
暂无评论
实现一致性 hash 算法