架构师训练营 - 第五周 - 作业一

关注
发布于: 2020 年 10 月 24 日
题目用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
解答一致性hash算法相比传统的hash取模算法，一致性hash算法在应对节点数变更时更加平滑，避免节点变动导致缓存大范围失效。
import cn.hutool.core.util.RandomUtil;
import lombok.Builder;
import lombok.Data;
import lombok.experimental.Accessors;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
/**
 * 一致性hash算法
 *
 * @author
 */
public class Hash1Test {
    public static void main(String[] args) {
        // init node
        List<Node1> nodes = new ArrayList<>();
        int nodeNumber = 10;
        for (int i = 0; i < nodeNumber; i++) {
            nodes.add(Node1.builder().name("node" + i).hash(RandomUtil.randomInt(Integer.MAX_VALUE)).keyCount(0).build());
        }
        nodes.sort(Comparator.comparingInt(Node1::getHash));
        // init data
        int dataNumber = 1000000;
        for (int i = 0; i < dataNumber; i++) {
            int dataHash = RandomUtil.randomInt(Integer.MAX_VALUE);
            for (int j = 0; j < nodes.size(); j++) {
                Node1 n = nodes.get(j);
                if (n.getHash() > dataHash) {
                    n.setKeyCount(n.getKeyCount() + 1);
                    break;
                }
                if (j == nodes.size() - 1) {
                    n = nodes.get(0);
                    n.setKeyCount(n.getKeyCount() + 1);
                }
            }
        }
        // show data
        for (Node1 node : nodes) {
            System.out.println(node);
        }
        // 计算标准差
        System.out.println(standardDeviation(nodes.stream().map(x -> x.getKeyCount().longValue()).collect(Collectors.toList()).toArray(new Long[nodes.size()])));
    }
    @Data
    @Accessors(chain = true)
    @Builder
    static class Node1 {
        private String name;
        private Integer hash;
        private Integer keyCount;
    }
    private static double standardDeviation(Long[] 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);
    }
}
使用10个节点，100万数据标准差在10万左右，数据分布并不均匀。
虚拟节点一致性hash算法相比一致性hash算法，虚拟节点一致性hash算法通过给单个节点虚拟出多个节点，让数据分布更加均匀。
import cn.hutool.core.util.RandomUtil;
import lombok.Builder;
import lombok.Data;
import lombok.experimental.Accessors;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
/**
 * 虚拟节点一致性hash算法
 *
 * @author
 */
public class Hash2Test {
    public static void main(String[] args) {
        // init node
        List<Node1> nodes = new ArrayList<>();
        int nodeNumber = 10;
        int virtualNodeNumber = 200;
        for (int i = 0; i < nodeNumber; i++) {
            for (int j = 0; j < virtualNodeNumber; j++) {
                nodes.add(Node1.builder().name("node" + i).hash(RandomUtil.randomInt(Integer.MAX_VALUE)).keyCount(0).virtualNumber(j).build());
            }
        }
        nodes.sort(Comparator.comparingInt(Node1::getHash));
        // init data
        int dataNumber = 1000000;
        for (int i = 0; i < dataNumber; i++) {
            int dataHash = RandomUtil.randomInt(Integer.MAX_VALUE);
            for (int j = 0; j < nodes.size(); j++) {
                Node1 n = nodes.get(j);
                if (n.getHash() > dataHash) {
                    n.setKeyCount(n.getKeyCount() + 1);
                    break;
                }
                if (j == nodes.size() - 1) {
                    n = nodes.get(0);
                    n.setKeyCount(n.getKeyCount() + 1);
                }
            }
        }
        // show data
        for (Node1 node : nodes) {
            System.out.println(node);
        }
        // 计算标准差
        System.out.println(standardDeviation(nodes.stream().collect(Collectors.groupingBy(Node1::getName)).values()
                .stream().map(x -> x.stream().mapToLong(z -> z.getKeyCount()).sum()).collect(Collectors.toList())
                .toArray(new Long[nodeNumber])));
    }
    @Data
    @Accessors(chain = true)
    @Builder
    static class Node1 {
        private String name;
        private Integer hash;
        private Integer keyCount;
        private Integer virtualNumber;
    }
    private static double standardDeviation(Long[] 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);
    }
}
使用10个节点，每个节点对应200个虚拟节点，100万数据标准差在5000左右，数据分布相比一致性hash算法均匀很多。
发布于: 2020 年 10 月 24 日阅读数: 30
行者

关注
还未添加个人签名 2018.03.09 加入
还未添加个人简介
发布
暂无评论
创作场景

架构师训练营 - 第五周 - 作业一

题目

解答

一致性hash算法

虚拟节点一致性hash算法

行者

评论
