架构师训练营第五周作业

/ 架构师训练营 / 没有评论 / 322浏览

用你熟悉的编程语言实现一致性 hash 算法。 编写测试用例测试这个算法,测试 100 万 KV 数据,10 个服务器节点的情况下,计算这些 KV 数据在服务器上分布数量的标准差,以评估算法的存储负载不均衡性。

Node.java

package com.tale.hash;
public class Node {
    private String ip;
    private String name;
    public Node(String ip, String name) { this.ip = ip; this.name = name; }
    public String getIp() { return ip; }
    public void setIp(String ip) { this.ip = ip; }
    public String getName() { return name; }
    public void setName(String name) { this.name = name; }
}

ConHashTest.java

package com.tale.hash;

import java.math.BigDecimal;
import java.util.*;

public class ConHashTest {
    private static final String IP_PREFIX = "192.168.1.";// 机器节点IP前缀

    // 方差
    public static double Variance(int[] x) {
        int m = x.length;
        double sum = 0;
        //求和
        for (double value : x) sum += value;
        double dAve = sum / m;//求平均值
        double dVar = 0;
        //求方差
        for (double v : x) dVar += (v - dAve) * (v - dAve);
        return dVar / m;
    }
    // 标准差
    public static double StandardDivination(int[] x) {
        return Math.sqrt(Variance(x));
    }

    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();// 每台真实机器节点上保存的记录条数
        HashFunction hashFunction = new HashFunctionImpl();
        LinkedHashMap<Integer, Double> variances = new LinkedHashMap<>();
        
        for (int numberOfReplicas = 100; numberOfReplicas <= 1000; numberOfReplicas += 10) {
            System.out.println("单个机器的虚拟节点: " + numberOfReplicas);
            map.clear();
            //真实物理节点
            List<Node> realNodes = new ArrayList<>();
            for (int i = 1; i <= 10; i++) {
                map.put(IP_PREFIX + i, 0);// 每台真实机器节点上保存的记录条数初始为0
                Node node = new Node(IP_PREFIX + i, "node" + i);
                realNodes.add(node);
            }
            ConsistentHash consistentHash = new ConsistentHash(hashFunction, numberOfReplicas, realNodes);
            // 将1000000条记录尽可能均匀的存储到10台机器节点
            for (int i = 0; i < 1000000; i++) {
                // 产生随机一个字符串当做一条记录,可以是其它更复杂的业务对象,比如随机字符串相当于对象的业务唯一标识
                String data = UUID.randomUUID().toString() + i;
                // 通过记录找到真实机器节点
                Node node = consistentHash.get(data);
                // 每台真实机器节点上保存的记录条数加1
                map.put(node.getIp(), map.get(node.getIp()) + 1);
            }
            // 打印每台真实机器节点保存的记录条数
            int[] numbers = new int[10];
            for (int i = 1; i <= 10; i++) {
                numbers[i - 1] = map.get("192.168.1." + i);
                System.out.println(IP_PREFIX + i + "节点记录条数:" + map.get("192.168.1." + i));
            }
            System.out.println("方差: " + BigDecimal.valueOf(Variance(numbers)));
            System.out.println("标准差: " + BigDecimal.valueOf(StandardDivination(numbers)));
            variances.put(numberOfReplicas, StandardDivination(numbers));
            System.out.println();
            System.out.println();
        }
        System.out.println(variances);
    }
}

ConsistentHash.java

package com.tale.hash;

import java.util.Collection;
import java.util.SortedMap;
import java.util.TreeMap;

public class ConsistentHash {

    private final HashFunction hashFunction;// hash 函数接口
    private final int numberOfReplicas;// 每个机器节点关联的虚拟节点个数
    private final SortedMap<Integer, Node> circle = new TreeMap<>();// 环形虚拟节点

    /**
     * @param hashFunction     hash 函数接口
     * @param numberOfReplicas 每个机器节点关联的虚拟节点个数
     * @param nodes            真实机器节点
     */
    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<Node> nodes) {
        this.hashFunction = hashFunction;
        this.numberOfReplicas = numberOfReplicas;
        nodes.forEach(this::add);
    }

    /**
     * 增加真实机器节点
     */
    public void add(Node node) {
        for (int i = 0; i < this.numberOfReplicas; i++) {
            circle.put(this.hashFunction.hash(node.getIp() + i), node);
        }
    }

    /**
     * 删除真实机器节点
     */
    public void remove(Node node) {
        for (int i = 0; i < this.numberOfReplicas; i++) {
            circle.remove(this.hashFunction.hash(node.getIp() + i));
        }
    }

    /**
     * 取得真实机器节点
     */
    public Node get(String key) {
        if (circle.isEmpty()) return null;
        Integer hash = hashFunction.hash(key);
        if (!circle.containsKey(hash)) {
            SortedMap<Integer, Node> tailMap = circle.tailMap(hash);// 沿环的顺时针找到一个虚拟节点
            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
        }
        return circle.get(hash); // 返回该虚拟节点对应的真实机器节点的信息
    }
}

HashFunction.java

package com.tale.hash;

public interface HashFunction {
    Integer hash(String key);
}

HashFunctionImpl.java

package com.tale.hash;

public class HashFunctionImpl implements HashFunction {
    @Override
    public Integer hash(String key) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) hash = (hash ^ key.charAt(i)) * 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;
    }
}

alt