第五周作业 (作业一)
发布于: 2020 年 10 月 25 日
用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。
/** /** * @author zhuhuiming * @date 2020/10/25 3:51 下午 * @description: * 整个组成部分: * 1、服务器ip集 * 2、单个服务器ip对应的虚拟节点数 * 3、虚拟节点和服务器ip映射关系集 */public class ConsistencyOperator { //单个服务器ip对应的虚拟节点数 private static int virtual_num = 10; //虚拟节点和服务器ip映射关系集(其中key为hash值,value为对应的服务器ip) private final static TreeMap<Long,String> virtual_server_map = new TreeMap<>(); private Set<String> server_ip = null; // 32位的 Fowler-Noll-Vo 哈希算法 // https://en.wikipedia.org/wiki/Fowler–Noll–Vo_hash_function private static Long FNVHash(String key) { final int p = 16777619; Long hash = 2166136261L; for (int idx = 0, num = key.length(); idx < num; ++idx) { hash = (hash ^ key.charAt(idx)) * 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; } //一个服务器ip对应虚拟节点个数 public ConsistencyOperator(int virtual_num,Set<String> server_ip){ if(virtual_num > 0) this.virtual_num = virtual_num; this.server_ip = server_ip; initVirtualServerNodes(); } //生成虚拟节点 private boolean initVirtualServerNodes(){ Long hashcode = null; int size = server_ip.size(); for(String ip:server_ip){ for(int i = 0; i < virtual_num; i++){ hashcode = FNVHash(ip+"#"+i); virtual_server_map.put(hashcode,ip); } } return true; } //加入服务节点 public boolean addServerNode(String serverip){ if(StringUtils.isBlank(serverip)) return false; server_ip.add(serverip); Long hashcode = null; for(int i = 0; i < virtual_num; i++){ hashcode = FNVHash(serverip+"#"+i); virtual_server_map.put(hashcode,serverip); } return true; } //删除服务节点 public boolean removeServerNode(String serverip){ if(StringUtils.isBlank(serverip)) return false; server_ip.remove(serverip); Long hashcode = null; for(int i = 0; i < virtual_num; i++){ hashcode = FNVHash(serverip+"#"+i); virtual_server_map.remove(hashcode); } return true; } // 查找对象映射的节点 public String getObjectNode(String object) { long hash = FNVHash(object); SortedMap<Long, String> tailMap = virtual_server_map.tailMap(hash); // 所有大于 hash 的节点 Long key = tailMap.isEmpty() ? virtual_server_map.firstKey() : tailMap.firstKey(); return virtual_server_map.get(key); } // 统计对象与节点的映射关系 public void dumpObjectNodeMap(String label, int objectMin, int objectMax) { // 统计 Map<String, Integer> objectNodeMap = new TreeMap<>(); // IP => COUNT for (int object = objectMin; object <= objectMax; ++object) { String nodeIp = getObjectNode(Integer.toString(object)); Integer count = objectNodeMap.get(nodeIp); objectNodeMap.put(nodeIp, (count == null ? 0 : count + 1)); } // 打印 double totalCount = objectMax - objectMin + 1; System.out.println("======== " + label + " ========"); for (Map.Entry<String, Integer> entry : objectNodeMap.entrySet()) { long percent = (int) (100 * entry.getValue() / totalCount); System.out.println("IP=" + entry.getKey() + ": RATE=" + percent + "%"); } } public static void main(String[] args) { Set<String> server_ip = new TreeSet<String>(); //服务器ip地址集 for(int i = 0; i < 10; i++){ //写入10个server的ip server_ip.add("192.168.3."+i); } ConsistencyOperator ch = new ConsistencyOperator(100,server_ip); // 初始情况 ch.dumpObjectNodeMap("初始情况", 0, 1000000); }}
以上代码参考过https://blog.csdn.net/kefengwang/article/details/81628977
划线
评论
复制
发布于: 2020 年 10 月 25 日 阅读数: 8
版权声明: 本文为 InfoQ 作者【Geek_83908e】的原创文章。
原文链接:【http://xie.infoq.cn/article/d896f3cc24fba1221ac113797】。文章转载请联系作者。
Geek_83908e
关注
还未添加个人签名 2019.04.28 加入
还未添加个人简介
评论