一致性 Hash 算法实现 - Java

用户头像
羽球
关注
发布于: 2020 年 07 月 08 日
  1. Hash环的实现

面向接口编程,定义环需要的接口

public interface ConsistentHashing {

// 支持虚拟节点
public void addNode(String key, HashNode node) throws UnsupportedEncodingException, NoSuchAlgorithmException;

// 环需要有序
public void sort();

// 取最近的节点
public HashNode getFirstNode(String key) throws UnsupportedEncodingException, NoSuchAlgorithmException;
}

节点类

public class HashNode {

String val;

public HashNode(String val) {
this.val = val;
}

public String getVal() {
return val;
}
}

TreeMap实现环

public class HashTreeMap implements ConsistentHashing{
TreeMap<Long, HashNode> treeMap = new TreeMap<>();
ConsistentHashingAlg hashingAlg;

public HashTreeMap(String alg) {
this.hashingAlg = ConsistentHashingAlgFactory.getSignelStrategy(alg);
}

// 一个主机节点映射出的虚拟节点数量
private static final int VIRTUAL_NODE_SIZE = 10;

@Override
public void addNode(String key, HashNode node) throws UnsupportedEncodingException, NoSuchAlgorithmException {
// 加节点自己
treeMap.put(hashingAlg.hash(key), node);
// 虚拟节点 对应同一个node
for (int i = 0; i < VIRTUAL_NODE_SIZE; i++) {
long hashCode = hashingAlg.hash(key + String.valueOf(i));
treeMap.put(hashCode, node);
}
}

// TreeMap本身有序
@Override
public void sort() { }

@Override
public HashNode getFirstNode(String key) throws UnsupportedEncodingException, NoSuchAlgorithmException {
long hashCode = hashingAlg.hash(key);
// 取大于参数值的子集
SortedMap<Long, HashNode> res = treeMap.tailMap(hashCode);
if (res.isEmpty()) {
return treeMap.firstEntry().getValue();
}
return res.get(res.firstKey());
}


2.Hash算法

有多种实现方式,所以采用策略模式

// 抽象策略
public interface ConsistentHashingAlg {
public long hash(String value) throws NoSuchAlgorithmException, UnsupportedEncodingException;
}



// 具体策略
public class HashingMD5 implements ConsistentHashingAlg{

@Override
public long hash(String value) throws NoSuchAlgorithmException, UnsupportedEncodingException {
MessageDigest md5 = MessageDigest.getInstance("MD5");
md5.reset();
byte[] keyBytes = value.getBytes("UTF-8");
md5.update(keyBytes);
byte[] digest = md5.digest();
// hash code
long md5Code = ((long) (digest[3] & 0xFF) << 24)
| ((long) (digest[2] & 0xFF) << 16)
| ((long) (digest[1] & 0xFF) << 8)
| (digest[0] & 0xFF);
long hashCode = md5Code & 0xFFFFFFFFL;
return hashCode;
}
}



// 策略工厂
public class ConsistentHashingAlgFactory {
private static final HashMap<String, ConsistentHashingAlg> strategys = new HashMap<>();

static {
strategys.put("MD5", new HashingMD5());
}

public static ConsistentHashingAlg getSignelStrategy(String alg) {
return strategys.get(alg);
}
}

3.测试Demo

static String[] ips = {"192.168.2.9", "119.45.56.8", "45.113.8.40", "192.168.10.0", "47.123.8.8",
"36.98.233.54", "142.9.0.98", "119.9.72.90", "69.34.3.87", "123.48.9.9"};

public static void main(String[] args) throws UnsupportedEncodingException, NoSuchAlgorithmException {
getStandardDeviation();
}
// KV 数据在10个服务器上分布数量的标准差
// Standard Deviation =(每个服务器上有多少个映射 - 平均值100万除以10)* 2
private static void getStandardDeviation() throws UnsupportedEncodingException, NoSuchAlgorithmException {
double avgVal = 1000000 / 10;
HashTreeMap hashTreeMapV = new HashTreeMap("MD5");
// 存储node的映射数量
HashMap<String, Integer> nodeMap = new HashMap<>();
// 创建10个服务器
for (int i = 0; i < ips.length; i++) {
hashTreeMapV.addNode(ips[i], new HashNode(ips[i]));
nodeMap.put(ips[i], 0);
}
// 测试 100 万 KV 数据 key = i
for (int i = 0; i < 1000000; i++) {
String ip = hashTreeMapV.getFirstNode(String.valueOf(i)).getVal();
nodeMap.put(ip, nodeMap.get(ip) + 1);
}
nodeMap.forEach((key, value) -> System.out.println(key + " 路由数量:" + value));
// 计算方差
double variance = 0;
for (double x : nodeMap.values()) {
variance += Math.pow((x - avgVal), 2);
}
variance = variance / ips.length;
System.out.println("方差:" + new BigDecimal(variance));
// 计算标准差
double standardDeviation = Math.sqrt(variance);
System.out.println("标准差" + standardDeviation);
}

测试结果

// 10个节点 * 10个虚拟节点

142.9.0.98 路由数量:79771
45.113.8.40 路由数量:83283
36.98.233.54 路由数量:95133
69.34.3.87 路由数量:103912
47.123.8.8 路由数量:128768
119.9.72.90 路由数量:102948
192.168.10.0 路由数量:102002
192.168.2.9 路由数量:150841
123.48.9.9 路由数量:72650
119.45.56.8 路由数量:80692

方差:527358714
标准差22964.292151076635



用户头像

羽球

关注

还未添加个人签名 2017.10.28 加入

还未添加个人简介

评论

发布
暂无评论
一致性Hash算法实现 - Java