Date: 2020/7/7 V1.0
Author：Jessie
目标：
背景：
在分布式集群环境当中，机器的添加、删除以及产生故障自动脱离集群这是最基本的功能，如果采用 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
评论