用你熟悉的編程語(yǔ)言實(shí)現(xiàn)一致性 hash 算法揪荣。

編寫(xiě)測(cè)試用例測(cè)試這個(gè)算法迁霎，測(cè)試 100 萬(wàn) KV 數(shù)據(jù)懈息，10 個(gè)服務(wù)器節(jié)點(diǎn)的情況下抵屿，計(jì)算這些 KV 數(shù)據(jù)在服務(wù)器上分布數(shù)量的標(biāo)準(zhǔn)差聚唐，以評(píng)估算法的存儲(chǔ)負(fù)載不均衡性

先看結(jié)果

image.png

其實(shí)不是很均勻丐重，主要是Hash函數(shù)還不夠優(yōu)化。

/*Dht*/
import java.util.Map;
import java.util.Objects;
import java.util.TreeMap;

public class Dht {
    private int numOfServers;
    private int numOfVirtualNodesPerServer;
    private TreeMap<Integer, Node> nodes;

    public Dht(int numOfServers, int numOfVirtualNodesPerServer) {
//        this.data = data;
        this.numOfServers = numOfServers;
        this.numOfVirtualNodesPerServer = numOfVirtualNodesPerServer;
        nodes = new TreeMap<>();
        initServer();
    }

    private void initServer() {
        for (int i = 0; i < numOfServers; i++) {
            for (int j = 0; j < numOfVirtualNodesPerServer; j++) {
                Node node = new Node(i, j);
                nodes.put(node.getNodeHashKey(), node);
            }
        }
    }

    public int[] getDistribution() {
        int[] distribution = new int[numOfServers];
        for (Map.Entry<Integer, Node> node : nodes.entrySet()) {
            distribution[node.getValue().getServerNo()] += node.getValue().getCount();
        }
        return distribution;
    }

    public void distribute(int[] data) {
        for (int i = 0; i < data.length; i++) {
            int hashCode = Hash.getHash(data[i] + "");
            Map.Entry<Integer, Node> entry = (entry = nodes.ceilingEntry(hashCode)) != null ? entry : nodes.firstEntry();
            entry.getValue().cache(i, data[i]);
        }
    }
}

/*Node*/
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Node {
    private int nodeNo;

    private int serverNo;

    private int nodeHashKey;

    private Map<Integer, Integer> values = new HashMap<>(1000);

    public int getServerNo() {
        return serverNo;
    }

    public int getNodeHashKey() {
        return nodeHashKey;
    }

    public Node(int serverNo, int nodeNo) {
        this.serverNo = serverNo;
        this.nodeNo = nodeNo;
        this.nodeHashKey = Hash.getHash("server" + this.serverNo + "#" + String.format("%3d", this.nodeNo));
    }

    public void cache(int key, int value) {
        values.put(key, value);
    }

    public int getCount() {
        return values.size();
    }
}

/*Hash*/
public class Hash {
    public static int getHash(String str) {
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < str.length(); i++)
            hash = (hash ^ str.charAt(i)) * p;
        hash += hash << 13;
        hash ^= hash >> 7;
        hash += hash << 3;
        hash ^= hash >> 17;
        hash += hash << 5;

        hash = Math.abs(hash);
        return hash;
    }
}