用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
一致性 Hash 算法实现
原理：
一致性 Hash 算法通过构建环状的 Hash 空间替线性 Hash 空间的方法解决了这个问题，整个 Hash 空间被构建成一个首位相接的环。
其具体的构造过程为：
先构造一个长度为 2^32 的一致性 Hash 环
计算每个缓存服务器的 Hash 值，并记录，这就是它们在 Hash 环上的位置
为了解决新增节点带来的数据倾斜即分配不均的问题可以采用虚拟节点。
虚拟节点
以将每台物理服务器虚拟为一组虚拟服务器，使得 Hash 环在空间上的分割更加均匀。
这样只是将虚拟节点的 Hash 值放置在 Hash 环上，在查找时，首先根据 Key 值找到环上的虚拟节点，然后再根据虚拟节点找到真实服务器。虚拟节点的数目足够多，就会使得节点在 Hash 环上的分布更加随机化，也就是增加或者删除一台服务器时，都会较为均匀的影响原来集群中已经存在的服务器。
接下来说下这种算法的优缺点：
优点：相比余数 Hash 一致性 Hash 能更加均匀的分配服务器资源（在负载均衡服务器应用场景中）
缺点：
1、Hash 环上节点数过多的情况下会导致查询效率过低。
2、整个 Hash 环需要一个服务器来做负载均衡，存在单点故障的风险。
构造虚拟节点需要考虑两个问题：
1、一个真实的节点如何对应多个虚拟节点。
2、虚拟节点找到后如何还原成真实的节点。
代码实现
接口：
package jianxink.hash;
import java.util.HashMap;
/** * 负载均衡服务器接口。 * * @author jianxink * */public interface LoadBalancer { /** * 新增服务节点。 * * @param serverNodeName */ public void addNewServerNode(String serverNodeName);
/** * 删除服务节点。 * @param serverNodeName * @return */ public HashMap<String, String> delServerNode(String serverNodeName);
/** * 选择服务节点。 * @param requestURL * @return */ public String selectServerNode(String requestURL);
}
复制代码
虚拟节点实现
package jianxink.hash;
import java.util.HashMap;import java.util.Map;import java.util.TreeMap;
public class HashWithVirtualNode implements LoadBalancer { private TreeMap<Integer, String> treeMapHash;
@Override public void addNewServerNode(String serverNodeName) { int hash = HashUtil.getHashCodeWithFNVI_32_HASH(serverNodeName); treeMapHash.put(hash, serverNodeName); }
@Override public HashMap<String, String> delServerNode(String serverNodeName) { int hash = HashUtil.getHashCodeWithFNVI_32_HASH(serverNodeName); treeMapHash.remove(hash); return treeMapHash; }
@Override public String selectServerNode(String requestURL) { int hash = HashUtil.getHashCodeWithFNVI_32_HASH(requestURL); // 向右寻找第一个 key Map.Entry<Integer, String> subEntry = treeMapHash.ceilingEntry(hash); // 设置成一个环，如果超过尾部，则取第一个点 subEntry = subEntry == null ? treeMapHash.firstEntry() : subEntry; String VNNode = subEntry.getValue(); return VNNode.substring(0, VNNode.indexOf("&&")); } // 构建 Hash 环 public SortedMap<Integer, String> buildHash(TreeMap<Integer, String> treeMap) { this.treeMapHash = treeMap; return treeMapHash; }
}
复制代码
使用标准差分析代码
package jianxink.hash;
import java.util.Collection;import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.concurrent.ConcurrentHashMap;
/** * hash node analysis * * @author jianxink * */public class HashNodeAnalysis { public double analysis(HashMap<String, String> map) { Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator(); // 计数 map <Server, Count> ConcurrentHashMap<String, Integer> countMap = new ConcurrentHashMap<>(); while (iterator.hasNext()) { Map.Entry<String, String> entry = iterator.next(); String server = entry.getValue(); if (countMap.containsKey(server)) { countMap.put(server, countMap.get(server) + 1); } else { countMap.put(server, 1); } } Collection<Integer> values = countMap.values(); Iterator<Integer> val = values.iterator(); int count = 0; int[] res = new int[values.size()]; while (val.hasNext()) { res[count] = val.next(); } return standardDiviation(res); }
// 标准差 public static double standardDiviation(int[] x) { int m=x.length; double sum=0; for(int i=0;i<m;i++){//求和 sum+=x[i]; } double dAve=sum/m;//求平均值 double dVar=0; for(int i=0;i<m;i++){//求方差 dVar+=(x[i]-dAve)*(x[i]-dAve); } return Math.sqrt(dVar/m); }
}
复制代码
测试结果发现 虚拟节点数 1000 时的标准差是 1.26 10000 时的标准差是 7.36
理论上虚拟节点数越多 越离散
评论