架构师训练营第 1 期 -week5

package com.geektime;
import java.util.Arrays;
/** * 数学相关计算工具类 */public class MathUtil {
    /**     * 传入一个数列x计算平均值     *     * @param x 要计算的数列     * @return 平均值     */    public static double average(double[] x) {        return Arrays.stream(x).average().orElse(0);    }
    /**     * 传入一个数列x计算方差     * <p>     * 方差s^2=[（x1-x）^2+（x2-x）^2+......（xn-x）^2]/（n）（x为平均数）     *     * @param x 要计算的数列     * @return 方差     */    public static double variance(double[] x) {        double avg = average(x);        return Arrays.stream(x).map(i -> Math.pow(i - avg, 2)).average().orElse(0);    }
    /**     * 传入一个数列x计算标准差     * 标准差σ=sqrt(s^2)，即标准差=方差的平方根     *     * @param x 要计算的数列     * @return 标准差     */    public static double standardDeviation(double[] x) {        return Math.sqrt(variance(x));    }}

package com.geektime;
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;    }
    /**     * 使用IP当做hash的Key     *     * @return String     */    @Override    public String toString() {        return ip;    }}

private static int hash(Object key) {        return MurmurHash.hash32(key.toString());    }

package com.geektime;
import java.util.Collection;import java.util.SortedMap;import java.util.TreeMap;
public class ConsistentHash<T> {
    /**     * 每个节点的虚拟节点的个数     */    private final int numberOfReplicas;
    /**     * 哈希环     */
    private final SortedMap<Long, T> circle = new TreeMap<>();
    /**     * 初始化     *     * @param numberOfReplicas 虚拟节点数量     * @param nodes 物理节点列表     */    public ConsistentHash(int numberOfReplicas, Collection<T> nodes) {        this.numberOfReplicas = numberOfReplicas;        // 初始化节点        for (T node : nodes) {            add(node);        }    }
    /**     * 添加节点     *     * @param node 物理节点     */    public void add(T node) {        for (int i = 0; i < numberOfReplicas; i++) {            String key = node.toString() + i;            long hash = hash(key);            circle.put(hash, node);        }    }
    public T get(String key) {        if (circle.isEmpty()) {            return null;        }
        long hash = hash(key);
        // 沿环的顺时针找到一个虚拟节点        if (!circle.containsKey(hash)) {            SortedMap<Long, T> tailMap = circle.tailMap(hash);            hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();        }        return circle.get(hash);    }

    private static int hash(Object key) {        return MurmurHash.hash32(key.toString());    }
    static final class MurmurHash {
        // all methods static; private constructor.        private MurmurHash() {        }
        /**         * Generates 32 bit hash from byte array of the given length and         * seed.         *         * @param data   byte array to hash         * @param length length of the array to hash         * @param seed   initial seed value         * @return 32 bit hash of the given array         */        public static int hash32(final byte[] data, int length, int seed) {            // 'm' and 'r' are mixing constants generated offline.            // They're not really 'magic', they just happen to work well.            final int m = 0x5bd1e995;            final int r = 24;
            // Initialize the hash to a random value            int h = seed ^ length;            int length4 = length / 4;
            for (int i = 0; i < length4; i++) {                final int i4 = i * 4;                int k = (data[i4 + 0] & 0xff) + ((data[i4 + 1] & 0xff) << 8)                        + ((data[i4 + 2] & 0xff) << 16) + ((data[i4 + 3] & 0xff) << 24);                k *= m;                k ^= k >>> r;                k *= m;                h *= m;                h ^= k;            }
            // Handle the last few bytes of the input array            switch (length % 4) {                case 3:                    h ^= (data[(length & ~3) + 2] & 0xff) << 16;                case 2:                    h ^= (data[(length & ~3) + 1] & 0xff) << 8;                case 1:                    h ^= (data[length & ~3] & 0xff);                    h *= m;            }
            h ^= h >>> 13;            h *= m;            h ^= h >>> 15;
            return h;        }
        /**         * Generates 32 bit hash from byte array with default seed value.         *         * @param data   byte array to hash         * @param length length of the array to hash         * @return 32 bit hash of the given array         */        public static int hash32(final byte[] data, int length) {            return hash32(data, length, 0x9747b28c);        }
        /**         * Generates 32 bit hash from a string.         *         * @param text string to hash         * @return 32 bit hash of the given string         */        public static int hash32(final String text) {            final byte[] bytes = text.getBytes();            return hash32(bytes, bytes.length);        }
        /**         * Generates 32 bit hash from a substring.         *         * @param text   string to hash         * @param from   starting index         * @param length length of the substring to hash         * @return 32 bit hash of the given string         */        public static int hash32(final String text, int from, int length) {            return hash32(text.substring(from, from + length));        }
        /**         * Generates 64 bit hash from byte array of the given length and seed.         *         * @param data   byte array to hash         * @param length length of the array to hash         * @param seed   initial seed value         * @return 64 bit hash of the given array         */        public static long hash64(final byte[] data, int length, int seed) {            final long m = 0xc6a4a7935bd1e995L;            final int r = 47;
            long h = (seed & 0xffffffffL) ^ (length * m);
            int length8 = length / 8;
            for (int i = 0; i < length8; i++) {                final int i8 = i * 8;                long k = ((long) data[i8 + 0] & 0xff) + (((long) data[i8 + 1] & 0xff) << 8)                        + (((long) data[i8 + 2] & 0xff) << 16) + (((long) data[i8 + 3] & 0xff) << 24)                        + (((long) data[i8 + 4] & 0xff) << 32) + (((long) data[i8 + 5] & 0xff) << 40)                        + (((long) data[i8 + 6] & 0xff) << 48) + (((long) data[i8 + 7] & 0xff) << 56);
                k *= m;                k ^= k >>> r;                k *= m;
                h ^= k;                h *= m;            }
            switch (length % 8) {                case 7:                    h ^= (long) (data[(length & ~7) + 6] & 0xff) << 48;                case 6:                    h ^= (long) (data[(length & ~7) + 5] & 0xff) << 40;                case 5:                    h ^= (long) (data[(length & ~7) + 4] & 0xff) << 32;                case 4:                    h ^= (long) (data[(length & ~7) + 3] & 0xff) << 24;                case 3:                    h ^= (long) (data[(length & ~7) + 2] & 0xff) << 16;                case 2:                    h ^= (long) (data[(length & ~7) + 1] & 0xff) << 8;                case 1:                    h ^= (long) (data[length & ~7] & 0xff);                    h *= m;            }
            h ^= h >>> r;            h *= m;            h ^= h >>> r;
            return h;        }
        /**         * Generates 64 bit hash from byte array with default seed value.         *         * @param data   byte array to hash         * @param length length of the array to hash         * @return 64 bit hash of the given string         */        public static long hash64(final byte[] data, int length) {            return hash64(data, length, 0xe17a1465);        }
        /**         * Generates 64 bit hash from a string.         *         * @param text string to hash         * @return 64 bit hash of the given string         */        public static long hash64(final String text) {            final byte[] bytes = text.getBytes();            return hash64(bytes, bytes.length);        }
        /**         * Generates 64 bit hash from a substring.         *         * @param text   string to hash         * @param from   starting index         * @param length length of the substring to hash         * @return 64 bit hash of the given array         */        public static long hash64(final String text, int from, int length) {            return hash64(text.substring(from, from + length));        }    }}

package com.geektime;
import java.util.ArrayList;import java.util.Arrays;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.UUID;
public class Main {
    /**     * 机器节点IP前缀     */    private static final String IP_PREFIX = "192.168.0.";
    public static void main(String[] args) {        //节点列表        int numOfNodes = 10;        //虚拟节点        int replicas = 150;        // KV数据        int sampleCnt = 1000000;        // 每台真实机器节点上保存的记录条数        Map<String, Integer> counter = new HashMap<>();
        List<Node> nodeList = new ArrayList<>(numOfNodes);        for (int i = 1; i <= numOfNodes; i++) {            counter.put(IP_PREFIX + i, 0);            Node node = new Node(IP_PREFIX + i, "node" + i);            nodeList.add(node);        }        System.out.println("节点数：" + numOfNodes + ",虚拟节点数：" + replicas);
        //一致性哈希初始化        ConsistentHash<Node> consistentHash = new ConsistentHash<>(replicas, nodeList);

        for (int i = 0; i < sampleCnt; i++) {            // 产生随机一个字符串当做一条记录            String data = UUID.randomUUID().toString() + i;            Node node = consistentHash.get(data);            String ip = node.getIp();            counter.put(ip, counter.containsKey(ip) ? counter.get(ip) + 1 : 1);        }        //计算标准差        for (Map.Entry<String, Integer> entry : counter.entrySet()) {            System.out.println("节点:" + entry.getKey() + ",数目：" + entry.getValue());        }
        double[] doubles = Arrays.stream(counter.values().toArray(new Integer[0]))                .mapToDouble(Integer::doubleValue)                .toArray();        double standardDeviation = MathUtil.standardDeviation(doubles);
        System.out.println("标准差为：" + standardDeviation);    }}