架构学习第 5 周作业

package com.hy;

import java.math.BigInteger;
import java.security.NoSuchAlgorithmException;
import java.util.*;
import java.security.MessageDigest;

// key->value server
class Server {
    private HashMap<String, String> hmap;
    private String serverName;

    public Server(String name) {
        serverName = name;
        hmap = new HashMap<String, String>();
    }

    public void set(String key, String val) {
        hmap.put(key, val);
    }

    public String get(String key) {
        return hmap.get(key);
    }

    public int size() {
        return hmap.size();
    }
}

class ConsistentHashService {
    // 服务器哈希->服务器
    private HashMap<String, Server> serverMap;
    // 服务器对应的虚拟节点数量
    private int virtualNums = 3;
    // 服务器哈希值数组
    private ArrayList<String> hashCircle;

    private HashSet<Server> servers;

    public ConsistentHashService(int replic) {
        virtualNums = replic;
        hashCircle = new ArrayList<String>();
        serverMap = new HashMap<String, Server>();
        servers = new HashSet<Server>();
    }

    private void insertHashCircle(String hash) {
        for (int i = 0; i < hashCircle.size(); i++) {
            if (hashCircle.get(i).compareTo(hash) > 0 ) {
                hashCircle.add(i, hash);
                return;
            }
        }

        hashCircle.add(hash);
    }

    private void removeHashCirCle(String hash) {
        int index = hashCircle.indexOf(hash);
        if (index >= 0) {
            hashCircle.remove(index);
        }
    }

    public void addServer(String serverName) {
        Server server = new Server(serverName);
        servers.add(server);
        for (int i = 0; i < virtualNums; i++) {
            String virtualName = serverName + '#' + i;
            String hashName = hashKey(virtualName);
            insertHashCircle(hashName);
            serverMap.put(hashName, server);
        }
    }

    public void removeServer(String serverName) {
        String virtualName = serverName + '#' + 1;
        String hashName = hashKey(virtualName);
        if (serverMap.get(hashName) != null) {
            servers.remove(serverMap.get(hashName));
        }

        for (int i = 0; i < virtualNums; i++) {
            virtualName = serverName + '#' + i;
            hashName = hashKey(virtualName);
            removeHashCirCle(hashName);
            serverMap.remove(serverName);
        }
    }

    public void set(String key, String val) {
        Server server = getServer(key);
        if (server != null) {
            server.set(key, val);
        }
    }

    public String get(String key) {
        Server server = getServer(key);
        if (server != null) {
            return server.get(key);
        }
        return null;
    }

    private String hashKey(String key) {
        byte[] secretBytes = null;
        try {
            secretBytes = MessageDigest.getInstance("md5").digest(
                    key.getBytes());
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException("没有这个md5算法！");
        }
        String md5code = new BigInteger(1, secretBytes).toString(16);
        for (int i = 0; i < 32 - md5code.length(); i++) {
            md5code = "0" + md5code;
        }
        return md5code;
    }

    // 根据哈希值查找下一个离的最近的服务器, 采用二分法
    private Server getNext(String key) {
        if (hashCircle.size() == 0) return null;

        String serverhash = hashCircle.get(0);

        int low = 0;
        int high = hashCircle.size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            String midVal = hashCircle.get(mid);
            int cmp = midVal.compareTo(key);
            if (cmp > 0) {
                serverhash = midVal;
                high = mid - 1;
            } else if (cmp == 0) {
                serverhash = midVal;
                break;
            } else {
                low = mid + 1;
            }
        }

        return serverMap.get(serverhash);
    }

    private Server getServer(String key) {
        String hashKey = hashKey(key);
        return getNext(hashKey);
    }

    public Set<Server> getServers() {
        return servers;
    }

};

public class Main {

    private static double variance(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 dVar / m;
    }

    private static double standardDeviation(long[] x) {
        double var = variance(x);
        return Math.sqrt(var);
    }

    private static void analyze(Set<Server> servers) {
        long[] dataNums = new long[servers.size()];
        int i = 0;
        for (Server server: servers) {
            dataNums[i++] = server.size();
        }

        double stdVar = standardDeviation(dataNums);
        long min = dataNums[0];
        long max = 0;
        double avg = 0;
        long sum = 0;
        for (i = 0; i < servers.size(); i++) {
            sum += dataNums[i];
            if (dataNums[i] < min) min = dataNums[i];
            if (dataNums[i] > max) max = dataNums[i];
        }
        avg = sum / servers.size();


        System.out.println(String.format("平均值：%.2f", avg));
        System.out.println(String.format("最大值：%d,（%.2f%%）", max, 100.0 * max / avg));
        System.out.println(String.format("最小值：%d,（%.2f%%）", min, 100.0 * min / avg));
        System.out.println(String.format("标准差：%.2f,（%.2f%%）", stdVar, 100.0 * stdVar));
    }

    public static void main(String[] args) {
	// write your code here
        ConsistentHashService service = new ConsistentHashService(150);

        for (int i = 1; i <= 10; i++) {
            service.addServer("10.0.0." + i);
        }

        HashMap<String, String> testData = new HashMap<String, String>();
        for (int i = 1; i <= 1000000; i++) {
            testData.put("key11" + i, "value33" + i);
        }

        for (Map.Entry<String, String> entry : testData.entrySet()) {
            String key = entry.getKey();
            String Val = entry.getValue();
            service.set(key, Val);
        }

        for (Map.Entry<String, String> entry : testData.entrySet()) {
            String key = entry.getKey();
            String Val = entry.getValue();
            if (!service.get(key).equals(Val)) {
                System.out.printf("key %s valid error\r\n", key);
            }
        }

        analyze(service.getServers());

        System.out.println("add one server");
        service.addServer("10.0.0.20");
        // service.removeServer("10.0.0.1");

        int count = 0;
        for (Map.Entry<String, String> entry : testData.entrySet()) {
            String key = entry.getKey();
            String Val = entry.getValue();
            String keyVal = service.get(key);
            if (keyVal == null) {
                count++;
                continue;
            }

            if (!keyVal.equals(Val)) {
                System.out.printf("key %s valid error\r\n", key);
            }
        }
        System.out.printf("miss key count %d\r\n", count);
        analyze(service.getServers());

        System.out.println("all test ok");
    }
}