一致性 hash 算法的实现

需求

编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性



从需求中我们抽离出几个对象，单个数据对象data，数据池对象dataPool,服务器server，以及虚拟节点VirturalNode。



定义数据对象data

public class Data {
    private String key;
    private String value;
    public Data(String key, String value) {
        this.key = key;
        this.value = value;
    }
    public String getKey() {
        return key;
    }
    public String getValue() {
        return value;
    }
}



定义数据池DataPool

public class DataPool {
    private ArrayBlockingQueue<Data> dataQueue;
    private int allocatedCnt;
    public DataPool(int size) {
        this.dataQueue = new ArrayBlockingQueue<>(size);
        allocatedCnt = 0;
    }
    public void addData(String key, String value) {
        dataQueue.add(new Data(key, value));
        allocatedCnt++;
    }
    public Data getData() {
        Data poll = dataQueue.poll();
        allocatedCnt--;
        return poll;
    }
    public int getAllocatedCnt() {
        return allocatedCnt;
    }
}



服务器对象server

public class Server {
    //服务器ip地址
    private String ip;
    //服务器数据量
    private int dataCnt;
//    private List<Data> dataList = new ArrayList<>();
    public Server(String ip) {
        this.ip = ip;
        this.dataCnt = 0;
    }
    public Server addData(Data data) {
//        dataList.add(data);
        dataCnt++;
        return this;
    }
    public int getDataCnt() {
        return dataCnt;
    }
    public String getIp() {
        return ip;
    }
}



最后定义虚拟节点VirturalNode

public class VirturalNode {
    private Server realServer;
    private int hashCode;
    public VirturalNode(int  hashCode, Server realServer) {
        this.hashCode = hashCode;
        this.realServer = realServer;
    }
    public int getHashCode() {
        return hashCode;
    }
    public VirturalNode setHashCode(int hashCode) {
        this.hashCode = hashCode;
        return this;
    }
    public Server getRealServer() {
        return realServer;
    }
    public  void addData(Data data){
        realServer.addData(data);
    }
}



最后我们盯一下我们的主类

public class HashTask {
    private static final String PREFIX = "###"; 
    
    public static void main(String[] args) {
        for (int i = 1; i < 100; i++) {
            run(10, 50*i, 1000000);
        }
    }
    private static void run(int serverSize, int verturalNodeSize, int dataSizeA) {
        //创建测试数据
        DataPool dataPool = getData(dataSizeA);
        //创建待测试的服务器
        List<Server> servers = getServer(serverSize);
        //创建hash环
        TreeMap<Integer, VirturalNode> hashRing = createVirtualNode(verturalNodeSize, servers);
        Map<String, Server> ipAndServerMap = new HashMap<>(serverSize);
        servers.forEach(s -> {
            ipAndServerMap.put(s.getIp(), s);
        });
        while (true) {
            Data data = dataPool.getData();
            if (data == null) {
                break;
            }
            VirturalNode rightNode = getRightNode(hashRing, data.getKey());
            Server server = ipAndServerMap.get(rightNode.getRealServer().getIp()).addData(data);
            ipAndServerMap.put(rightNode.getRealServer().getIp(), server);
        }
        double[] dataSize = new double[serverSize];
        for (int i = 0; i < serverSize; i++) {
            String ip = servers.get(i).getIp();
            int dataCnt = ipAndServerMap.get(ip).getDataCnt();
            dataSize[i] = dataCnt;
        }
        //计算方差
        double variance = MathUtils.POP_Variance(dataSize);
        double standardDeviation = MathUtils.POP_STD_dev(dataSize); 
        System.out.println("数据量: " + dataSizeA + " 单台虚拟节点数: " + verturalNodeSize + " 方差: " + variance + " 标准差: " + standardDeviation);
    }
    private static VirturalNode getRightNode(TreeMap<Integer, VirturalNode> hashRing, String value) {
        int hashValue = hash(value);
        Map.Entry<Integer, VirturalNode> integerVirturalNodeEntry = hashRing.ceilingEntry(hashValue);
        if (integerVirturalNodeEntry == null) {
            integerVirturalNodeEntry = hashRing.firstEntry();
        }
        return integerVirturalNodeEntry.getValue();
    }
    private static TreeMap<Integer, VirturalNode> createVirtualNode(int nodeSize, List<Server> servers) {
        TreeMap<Integer, VirturalNode> virturalNodes = new TreeMap<>();
        for (int i = 0, serverSize = servers.size(); i < serverSize; i++) {
            Server server = servers.get(i);
            for (int j = 0; j < nodeSize; j++) {
                VirturalNode virturalNode = new VirturalNode(hash(server.getIp() + PREFIX + j), server);
                virturalNodes.put(virturalNode.getHashCode(), virturalNode);
            }
        }
        return virturalNodes;
    }
    private static int hash(String key) {
        MurmurHash3Strategy hash3Strategy = new MurmurHash3Strategy();
        return hash3Strategy.getHashCode(key);
    }
    private static DataPool getData(int size) {
        DataPool dataPool = new DataPool(size);
        for (int i = 0; i < size; i++) {
            dataPool.addData(i + "", i + "");
        } 
        
        return dataPool;
    }
    private static List<Server> getServer(int size) {
        List<Server> servers = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            servers.add(new Server("192.168.0." + i));
        }
        return servers;
    }
}



说明：这里采取的hash算法是MurmurHash3，这个算法运行速度快，碰撞小，在很多谷歌的开源项目中被广泛使用。



运行上面的代码最后得到的结果：



数据量: 1000000 单台虚拟节点数: 50 方差: 1.706545908E8 标准差: 13063.483103674916

数据量: 1000000 单台虚拟节点数: 100 方差: 3.76567056E7 标准差: 6136.505976530944

数据量: 1000000 单台虚拟节点数: 150 方差: 5.4312789E7 标准差: 7369.721093772817

数据量: 1000000 单台虚拟节点数: 200 方差: 4.31049338E7 标准差: 6565.434776159153

数据量: 1000000 单台虚拟节点数: 250 方差: 3.10201366E7 标准差: 5569.57238933116

数据量: 1000000 单台虚拟节点数: 300 方差: 3.3156246E7 标准差: 5758.146055806504

数据量: 1000000 单台虚拟节点数: 350 方差: 2.2634808E7 标准差: 4757.605279970166

数据量: 1000000 单台虚拟节点数: 400 方差: 2.44370196E7 标准差: 4943.381393337965

数据量: 1000000 单台虚拟节点数: 450 方差: 2.41342986E7 标准差: 4912.667157461413

数据量: 1000000 单台虚拟节点数: 500 方差: 2.33506756E7 标准差: 4832.253677115886

数据量: 1000000 单台虚拟节点数: 550 方差: 1.78698452E7 标准差: 4227.273967937257

数据量: 1000000 单台虚拟节点数: 600 方差: 1.04300166E7 标准差: 3229.553622406663

数据量: 1000000 单台虚拟节点数: 650 方差: 8410917.2 标准差: 2900.158133619613

数据量: 1000000 单台虚拟节点数: 700 方差: 1.0544343E7 标准差: 3247.205413890535

数据量: 1000000 单台虚拟节点数: 750 方差: 8951915.6 标准差: 2991.975200431982

数据量: 1000000 单台虚拟节点数: 800 方差: 9799121.4 标准差: 3130.354836116826

数据量: 1000000 单台虚拟节点数: 850 方差: 7019127.6 标准差: 2649.363621702389

数据量: 1000000 单台虚拟节点数: 900 方差: 6523755.4 标准差: 2554.164325175653

数据量: 1000000 单台虚拟节点数: 950 方差: 6159186.2 标准差: 2481.770779101084

数据量: 1000000 单台虚拟节点数: 1000 方差: 8089933.4 标准差: 2844.2808229849597

数据量: 1000000 单台虚拟节点数: 1050 方差: 8683926.2 标准差: 2946.8502167568677

数据量: 1000000 单台虚拟节点数: 1100 方差: 1.03834998E7 标准差: 3222.343836402317

数据量: 1000000 单台虚拟节点数: 1150 方差: 8816671.4 标准差: 2969.2880291409924

数据量: 1000000 单台虚拟节点数: 1200 方差: 8637710.0 标准差: 2938.9981286145794

数据量: 1000000 单台虚拟节点数: 1250 方差: 5843301.4 标准差: 2417.292162730852

数据量: 1000000 单台虚拟节点数: 1300 方差: 3996625.0 标准差: 1999.15607194636

数据量: 1000000 单台虚拟节点数: 1350 方差: 2572026.0 标准差: 1603.7537217415895

数据量: 1000000 单台虚拟节点数: 1400 方差: 3700361.8 标准差: 1923.6324493000216

数据量: 1000000 单台虚拟节点数: 1450 方差: 4287100.6 标准差: 2070.5314776646114

数据量: 1000000 单台虚拟节点数: 1500 方差: 4276065.6 标准差: 2067.8649859214697

数据量: 1000000 单台虚拟节点数: 1550 方差: 3110307.2 标准差: 1763.6063052733737

数据量: 1000000 单台虚拟节点数: 1600 方差: 4565242.6 标准差: 2136.642833980448

数据量: 1000000 单台虚拟节点数: 1650 方差: 5561280.6 标准差: 2358.236756561987

数据量: 1000000 单台虚拟节点数: 1700 方差: 6278742.6 标准差: 2505.741926057031

数据量: 1000000 单台虚拟节点数: 1750 方差: 6315780.6 标准差: 2513.121684280329

数据量: 1000000 单台虚拟节点数: 1800 方差: 5991123.6 标准差: 2447.6771845976746

数据量: 1000000 单台虚拟节点数: 1850 方差: 7151666.4 标准差: 2674.259972403581

数据量: 1000000 单台虚拟节点数: 1900 方差: 7458201.2 标准差: 2730.970743160754

数据量: 1000000 单台虚拟节点数: 1950 方差: 7816993.0 标准差: 2795.888588624375

数据量: 1000000 单台虚拟节点数: 2000 方差: 5771499.2 标准差: 2402.3944721881126

数据量: 1000000 单台虚拟节点数: 2050 方差: 4890070.4 标准差: 2211.3503566825407

数据量: 1000000 单台虚拟节点数: 2100 方差: 3863642.4 标准差: 1965.6150182576444

数据量: 1000000 单台虚拟节点数: 2150 方差: 3029066.0 标准差: 1740.4212133848519

数据量: 1000000 单台虚拟节点数: 2200 方差: 3749603.2 标准差: 1936.3892170738816

数据量: 1000000 单台虚拟节点数: 2250 方差: 2527633.2 标准差: 1589.853200770436

数据量: 1000000 单台虚拟节点数: 2300 方差: 2719744.0 标准差: 1649.1646370208161

数据量: 1000000 单台虚拟节点数: 2350 方差: 2676983.4 标准差: 1636.1489540992286

数据量: 1000000 单台虚拟节点数: 2400 方差: 2756331.0 标准差: 1660.2201661225538

数据量: 1000000 单台虚拟节点数: 2450 方差: 2627468.4 标准差: 1620.9467603841897

数据量: 1000000 单台虚拟节点数: 2500 方差: 2420497.8 标准差: 1555.7949093630561

数据量: 1000000 单台虚拟节点数: 2550 方差: 2216648.2 标准差: 1488.841227263673

数据量: 1000000 单台虚拟节点数: 2600 方差: 2243186.0 标准差: 1497.726944406089

数据量: 1000000 单台虚拟节点数: 2650 方差: 2858885.4 标准差: 1690.8238820172844

数据量: 1000000 单台虚拟节点数: 2700 方差: 3198598.0 标准差: 1788.4624681552589

数据量: 1000000 单台虚拟节点数: 2750 方差: 3381132.8 标准差: 1838.7856862614522

数据量: 1000000 单台虚拟节点数: 2800 方差: 3658703.8 标准差: 1912.773849674864

数据量: 1000000 单台虚拟节点数: 2850 方差: 3778010.8 标准差: 1943.7105751628765

数据量: 1000000 单台虚拟节点数: 2900 方差: 3691919.0 标准差: 1921.4367020539605

数据量: 1000000 单台虚拟节点数: 2950 方差: 3491018.0 标准差: 1868.4266108145646

数据量: 1000000 单台虚拟节点数: 3000 方差: 3717657.2 标准差: 1928.1227139370565

数据量: 1000000 单台虚拟节点数: 3050 方差: 2800397.4 标准差: 1673.4387948174262

数据量: 1000000 单台虚拟节点数: 3100 方差: 2530996.0 标准差: 1590.9104311682665

数据量: 1000000 单台虚拟节点数: 3150 方差: 2297384.6 标准差: 1515.71257169689

数据量: 1000000 单台虚拟节点数: 3200 方差: 1990126.0 标准差: 1410.7182567756045

数据量: 1000000 单台虚拟节点数: 3250 方差: 3146721.6 标准差: 1773.9001099272755

数据量: 1000000 单台虚拟节点数: 3300 方差: 2997088.2 标准差: 1731.210039250004

数据量: 1000000 单台虚拟节点数: 3350 方差: 2255072.2 标准差: 1501.6897815461089

数据量: 1000000 单台虚拟节点数: 3400 方差: 2479367.8 标准差: 1574.6008383079186

数据量: 1000000 单台虚拟节点数: 3450 方差: 2681772.8 标准差: 1637.6119198393737

数据量: 1000000 单台虚拟节点数: 3500 方差: 2409157.6 标准差: 1552.1461271413848

数据量: 1000000 单台虚拟节点数: 3550 方差: 2555181.2 标准差: 1598.4934156886602

数据量: 1000000 单台虚拟节点数: 3600 方差: 2695792.2 标准差: 1641.886780505891

数据量: 1000000 单台虚拟节点数: 3650 方差: 2424443.6 标准差: 1557.0624907176975

数据量: 1000000 单台虚拟节点数: 3700 方差: 2122435.2 标准差: 1456.8579889611754

数据量: 1000000 单台虚拟节点数: 3750 方差: 2480783.6 标准差: 1575.0503484015996

数据量: 1000000 单台虚拟节点数: 3800 方差: 2059351.6 标准差: 1435.044110820291

数据量: 1000000 单台虚拟节点数: 3850 方差: 1772841.2 标准差: 1331.4808297530985

数据量: 1000000 单台虚拟节点数: 3900 方差: 1775497.6 标准差: 1332.477992313569

数据量: 1000000 单台虚拟节点数: 3950 方差: 1677087.4 标准差: 1295.0240924399823

数据量: 1000000 单台虚拟节点数: 4000 方差: 1549187.6 标准差: 1244.6636493446733

数据量: 1000000 单台虚拟节点数: 4050 方差: 1477244.0 标准差: 1215.4192692235877

数据量: 1000000 单台虚拟节点数: 4100 方差: 1354489.4 标准差: 1163.8253305371902

数据量: 1000000 单台虚拟节点数: 4150 方差: 874452.0 标准差: 935.1213824953421

数据量: 1000000 单台虚拟节点数: 4200 方差: 973179.6 标准差: 986.4986568667998

数据量: 1000000 单台虚拟节点数: 4250 方差: 1033476.2 标准差: 1016.6003147746906

数据量: 1000000 单台虚拟节点数: 4300 方差: 1100983.4 标准差: 1049.2775609913708

数据量: 1000000 单台虚拟节点数: 4350 方差: 778354.2 标准差: 882.2438438436394

数据量: 1000000 单台虚拟节点数: 4400 方差: 970530.8 标准差: 985.1552161969199

数据量: 1000000 单台虚拟节点数: 4450 方差: 1131403.0 标准差: 1063.6742922530375

数据量: 1000000 单台虚拟节点数: 4500 方差: 826229.4 标准差: 908.971616718586

数据量: 1000000 单台虚拟节点数: 4550 方差: 1123161.2 标准差: 1059.7929986558695

数据量: 1000000 单台虚拟节点数: 4600 方差: 1020618.6 标准差: 1010.2567000520214

数据量: 1000000 单台虚拟节点数: 4650 方差: 872741.8 标准差: 934.2065082196763

数据量: 1000000 单台虚拟节点数: 4700 方差: 877893.8 标准差: 936.9598710723956

数据量: 1000000 单台虚拟节点数: 4750 方差: 1058893.6 标准差: 1029.0255584775337

数据量: 1000000 单台虚拟节点数: 4800 方差: 1143261.0 标准差: 1069.2338378483914

数据量: 1000000 单台虚拟节点数: 4850 方差: 1374332.2 标准差: 1172.3191544967608

数据量: 1000000 单台虚拟节点数: 4900 方差: 1265730.0 标准差: 1125.0466656988056

数据量: 1000000 单台虚拟节点数: 4950 方差: 1131698.6 标准差: 1063.81323548826



说明：该代码只是为了快速的实现一致性hash算法，并没有进一步去完善代码。上面的测试说明在一定范围内单台的虚拟节点越多效果越好数据越均匀，物理节点的新增和失效导致的数据移动代价会更小。