第五周作业
发布于: 2020 年 10 月 25 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
package week5;import cn.hutool.core.util.HashUtil;import cn.hutool.core.util.StrUtil;import java.util.LinkedList;import java.util.List;import java.util.SortedMap;import java.util.TreeMap;/** * @program: GeekTest * @description: 一致性hash实现 * @author: Meow_Young * @created: 2020/10/24 23:17 */public class ConsistentHash { /** * 服务器列表 */ public static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:111", "192.168.0.4:111", "192.168.0.5:111", "192.168.0.6:111", "192.168.0.7:111", "192.168.0.8:111", "192.168.0.9:111"}; private static List<String> realNodes = new LinkedList<String>(); /** *虚拟节点,key表示虚拟节点的hash值,value表示虚拟节点的名称 */ private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>(); /** * 一个真实结点对应的虚拟节点 */ private static final int VIRTUAL_NODES = 100; static{ //先把原始的服务器添加到真实结点列表中 for(int i=0; i<servers.length; i++) { realNodes.add(servers[i]); } //再添加虚拟节点,遍历LinkedList使用foreach循环效率会比较高 for (String str : realNodes){ for(int i=0; i<VIRTUAL_NODES; i++){ String virtualNodeName = str + "&&VN" + String.valueOf(i); int hash = getHash(virtualNodeName); System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash); virtualNodes.put(hash, virtualNodeName); } } System.out.println(); } /** * 使用FNV1_32_HASH算法计算服务器的Hash值 */ public static int getHash(String str){ return HashUtil.fnvHash(str); } /** * 得到应当路由到的结点 */ public static String getServer(String key){ //得到该key的hash值 int hash = getHash(key); // 得到大于该Hash值的所有Map SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash); String virtualNode; if(subMap.isEmpty()){ //如果没有比该key的hash值大的,则从第一个node开始 Integer i = virtualNodes.firstKey(); //返回对应的服务器 virtualNode = virtualNodes.get(i); }else{ //第一个Key就是顺时针过去离node最近的那个结点 Integer i = subMap.firstKey(); //返回对应的服务器 virtualNode = subMap.get(i); } //virtualNode虚拟节点名称要截取一下 if(StrUtil.isNotBlank(virtualNode)){ return virtualNode.substring(0, virtualNode.indexOf("&&")); } return null; } public static void main(String[] args){ String[] keys = {"1024", "程序员节", "加班","赶作业"}; for (String key : keys) { System.out.println("[" + key + "]的hash值为" + getHash(key) + ", 被路由到结点[" + getServer(key) + "]"); } }}
package week5;import java.util.Arrays;import java.util.Map;import java.util.TreeMap;/** * @program: GeekTest * @description: 测试 100 万 KV 数据,10 个服务器节点的情况下, * 计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。 * @author: Meow_Young * @created: 2020/10/24 23:53 */public class Test { /** * 计算标准方差 * * @param array * @return */ public static double calcStd(Integer[] array) { double avg = Arrays.stream(array).mapToInt(Integer::intValue).average().orElse(0d); double avgStd = Arrays.stream(array).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average() .orElse(0d); return Math.sqrt(avgStd); } public static void main(String[] args) { int keyNum = 10000; Map<String, Integer> serverCount = new TreeMap<>(); for (String server : ConsistentHash.servers) { serverCount.put(server, 0); } String serverName = ""; String key = ""; for (int i = 0; i < keyNum; i++) { key = "key" + System.currentTimeMillis(); serverName = ConsistentHash.getServer(key); serverCount.put(serverName, serverCount.get(serverName) + 1); } Integer[] array = new Integer[serverCount.size()]; double rs = calcStd(serverCount.values().toArray(array)); System.out.println("rs = " + rs); }}
划线
评论
复制
发布于: 2020 年 10 月 25 日 阅读数: 4
Meow
关注
还未添加个人签名 2018.05.09 加入
还未添加个人简介
评论