一致性 Hash 算法以及 Java 代码实现

发布于: 6 小时前

Date:  2020/7/7    V1.0

 Author:Jessie

 

目标:

  • 用Java语言实现一致性 hash 算法。

  • 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

 

背景:

在分布式集群环境当中,机器的添加、删除以及产生故障自动脱离集群这是最基本的功能,如果采用hash(o)%n的算法,在机器数量有变动的时候,以前的数据基本是找不到的。比如最开始3台  hash(o)%3=2  如果增加了一台hash(o)%4=?  结果肯定不会为2,如果使用hash取模,在机器数量增减的时候该问题是无法避免的。为了解决这个问题,就产生了一致性hash算法。

 

一致性哈希算法的思路为:先构造出一个长度为232整数环,根据节点名称的hash值(分布为[0,232-1])放到这个环上。现在要存放资源,根据资源的Key的Hash值(也是分布为[0,232-1])值Haaa,在环上顺时针的找到离Haaa最近(第一个大于或等于Haaa)的一个节点,就建立了资源和节点的映射关系。

  • 环的实现:参考文献,用TreeMap使用了红黑树结构存储Hash环。

  • Hash算法:首先们考虑简单的String.HashCode()方法,这个算法的缺点是,资源分布不均。参考采用FNV1_32_HASH算法。

  • 虚拟节点:Hash均衡还有一个关键因素,采用N倍虚拟节点对应实际服务器,将更散列虚拟节点的Hash值存在Hash环上,使得Hash分布更均匀;但虚拟节点数过大,会导致程序效率降低。代码中对虚拟节点数进行调节,实验大致假设虚拟倍数1000时,标准差相对比较小。这里需要实验者不断调整虚拟节点的数量,找到程序效率和标准差的一个相对平衡点。

 

代码实现:

import java.util.*;
public class ConHashSrv2 {
//待添加入Hash环的真实服务器节点列表
private static LinkedList<Node> realNodes = new LinkedList<>();
//虚拟节点列表
private static SortedMap<Integer, Node> sortedMap = new TreeMap<Integer, Node>();
static {
//初始化server 10台。
for (int i = 0; i < 10; i++) {
String nodeName = "server"+i;
Node node = new Node(nodeName);
realNodes.add(node);
}
//引入虚拟节点: 添加1000倍虚拟节点,将10台server对应的虚拟节点放入TreeMap中
for (Node node : realNodes) {
for (int i = 1; i <=1000; i++) {
String nodeName = node.getName() + "-VM" + String.valueOf(i);
int hash = getHash(nodeName);//nodeName.hashCode();
sortedMap.put(hash, node);
System.out.println("虚拟节点hash:" + hash + "【" + nodeName + "】放入");
}
}
}
//使用FNV1_32_HASH算法计算服务器的Hash值
private static int getHash(String str) {
// int hash = str.hashCode();
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < str.length(); i++) {
hash = (hash ^ str.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
// 如果算出来的值为负数则取其绝对值
if (hash < 0) {
hash = Math.abs(hash);
}
return hash;
}
//得到应当路由到的结点
private static Node getServer(String key) {
//得到该key的hash值
int hash = getHash(key);
//得到大于该Hash值的所有Map
Node server;
SortedMap<Integer, Node> subMap = sortedMap.tailMap(hash);
if (subMap.isEmpty()) {
//如果没有比该key的hash值大的,则从第一个node开始
Integer i = sortedMap.firstKey();
//返回对应的服务器
server = sortedMap.get(i);
} else {
//第一个Key就是顺时针过去离node最近的那个结点
Integer i = subMap.firstKey();
//返回对应的服务器
server= subMap.get(i);
}
if(server!=null) {
server.put(key,hash+"");
System.out.println(server.getName());
}
return server;
}
//获取实际服务器上负载平均值
public static double getAverage(LinkedList<Node> arr) {
double sum = 0;
int number = arr.size();
for (int i = 0; i < number; i++) {
Node node =arr.get(i);
sum += node.getCount();
}
return sum / number;
}
//获取实际服务器上负载的标准差
public static double getStandardDevition(LinkedList<Node> arr) {
double sum = 0;
int number = arr.size();
double avgValue = getAverage(arr);//获取平均值
for (int i = 0; i < number; i++) {
Node node =arr.get(i);
sum += Math.pow((node.getCount() - avgValue), 2);
}
return Math.sqrt((sum / (number - 1)));
}
public static void main(String[] args) {
//模拟一百万用户
for (int i = 0; i < 1000000; i++) {
String key = "User:"+i;
System.out.println("[" + key + "]的hash值为" + getHash(key) + ", 被路由到结点[" + getServer(key).getName() + "]");
}
//打印 Node的实际负载
for (int i = 0; i < realNodes.size(); i++) {
Node node = realNodes.get(i);
System.out.println(node.getName()+"-> count:"+node.getCount());
}
System.out.println("标准差:"+getStandardDevition(realNodes)+"");
}
}

import java.util.*;
public class Node {
private String domain;
private String ip;
private int count = 0;
private Map<String, Object> data = new HashMap();
public Node(String domain) {
this.domain= domain;
//this.ip=ip;
}
public <T> void put(String key,String value) {
data.put(key,value);
count++;
}
public void remove(String key){
data.remove(key);
count--;
}
public <T> T get(String key) {
return (T) data.get(key);
}
public int getCount() {
return count;
}
public String getName() {
return domain;
}
}

运行结果:  

100 万 KV 数据,10 台实际服务器节点,模拟了1000倍的虚拟节点。
server0/ count:97803
server1/ count:100733
server2/ count:98947
server3/ count:100521
server4/ count:101165
server5/ count:100262
server6/ count:100055
server7/ count:101418
server8/ count:99019
server9/ count:100077
标准差:1113.1664545590454

参考文献:

https://www.cnblogs.com/markcd/p/8476237.html

https://blog.csdn.net/WANGYAN9110/article/details/70185652

https://blog.csdn.net/ypp91zr/article/details/88993704

发布于: 6 小时前 阅读数: 10
用户头像

还未添加个人签名 2018.08.21 加入

码过代码、做过产品;擅长码字、演讲、认真做事之人。

评论

发布
暂无评论
一致性Hash算法以及Java代码实现