第五周命题作业
发布于: 2020 年 07 月 08 日
用熟悉的编程语言实现一致性Hash算法
测试100万KV 数据、10个服务器节点的情况下,计算KV在服务器上分布数量的标准差,评估算法的存储负载不均衡性
由于之前没有接触过后端的内容,属于小白,现阶只能参照同学的代码进行学习。
计算哈希值 使用CRC32方法
public class ConsistentHash { /** * 哈希环最大位置 */ private static final Integer MAX_HASH_POSTION = Integer.MAX_VALUE; /** * 节点的虚拟节点数量 */ private final int replicasCount; /** * Hash环 */ private final SortedMap<Integer, String> hashCircle = new TreeMap<>(); /** * 构造方法 * * @param replicasCount 虚拟节点数量 * @param nodes 节点 */ public ConsistentHash(int replicasCount, Collection<String> nodes) { this.replicasCount = replicasCount; nodes.stream().forEach(node -> { add(node); }); } /** * 添加节点 * * @param node 节点名称 */ public void add(String node) { for (int i = 0; i < replicasCount; i++) { int nodeHash = hash(node + "#" + i); hashCircle.put(nodeHash, node); } } /** * 定位节点 * * @param key 键值 * @return */ public String get(String key) { if (hashCircle.isEmpty()) { return null; } int hash = hash(key); if (hashCircle.containsKey(hash)) { return hashCircle.get(hash); } SortedMap<Integer, String> tailMap = hashCircle.tailMap(hash); return hashCircle.get(tailMap.isEmpty() ? hashCircle.firstKey() : tailMap.firstKey()); } /** * 使用 CRC32 算法 * * @param key * @return */ public int hash(String key) { CRC32 crc32 = new CRC32(); crc32.update(key.getBytes()); return (int) (crc32.getValue() % MAX_HASH_POSTION); }}
public class ConsistentHashTest { /** * 服务器节点数 */ private static final Integer SERVER_COUNT = 10; /** * 统计server命中情况 */ Map<String, Integer> serverAllocateCount = new HashMap<>(); /** * 虚拟节点个数 */ private static final Integer VIRTURAL_NODES_COUNT = 150; /** * 一致性哈希算法 */ private ConsistentHash consistentHash; private static final String source = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; /** * 初始化一致性哈希算法的hash环 */ @Before public void init() { List<String> nodes = new ArrayList<>(); for (int i = 0; i < SERVER_COUNT; i++) { String server = "testServer-" + i; serverAllocateCount.put(server, 0); nodes.add(server); } consistentHash = new ConsistentHash(VIRTURAL_NODES_COUNT, nodes); } @Test public void testBalance() { // 模拟1000000次KV的请求,请求的key随机 for (int i = 0; i < 1000000; i++) { String server = consistentHash.get(randomString(8)); Integer count = serverAllocateCount.get(server); serverAllocateCount.put(server, ++count); } // 打印落到各个服务器的数量 printServerAllocate(serverAllocateCount); // 标准差 System.out.println("标准差: " + standardDeviation(serverAllocateCount.entrySet().stream().map(entry -> entry.getValue()).collect(Collectors.toList()))); } /** * 生成随机字符串 * * @param length 字符串长度 * @return */ public String randomString(int length) { StringBuffer sb = new StringBuffer(); Random random = new Random(); for (int i = 0; i < length; i++) { int number = random.nextInt(62); sb.append(source.charAt(number)); } return sb.toString(); } /** * 打印分布情况 * * @param serverAllocateCount * @return */ private void printServerAllocate(Map<String, Integer> serverAllocateCount) { System.out.println("服务器分配情况:"); for (Map.Entry<String, Integer> entry : serverAllocateCount.entrySet()) { System.out.println(String.format("服务器 [%s] 分配到的次数:%d", entry.getKey(), entry.getValue())); } } /** * 标准差计算 * σ=sqrt(s^2/n) * * @param input * @return */ private double standardDeviation(List<Integer> input) { int length = input.size(); if (length == 0) { return 0; } // 和 double sum = 0; for (Integer num : input) { sum += num; } // 平均值 double average = sum / length; // 方差 double s = 0; for (Integer num : input) { s += ((num - average) * (num - average)); } return Math.sqrt(s / length); }}
服务器分配情况:服务器[testServer-9]分配到的次数:77199服务器[testServer-8]分配到的次数:65765服务器[testServer-7]分配到的次数:86737服务器[testServer-6]分配到的次数:97315服务器[testServer-5]分配到的次数:127551服务器[testServer-4]分配到的次数:116312服务器[testServer-3]分配到的次数:97729服务器[testServer-2]分配到的次数:104425服务器[testServer-1]分配到的次数:113640服务器[testServer-0]分配到的次数:113327标准差: 18134.422406021098
划线
评论
复制
发布于: 2020 年 07 月 08 日阅读数: 47
冯凯
关注
还未添加个人签名 2020.05.26 加入
还未添加个人简介
评论