架构师训练营 - 第 5 周作业

// 算法的主要实现类
package architect;
import org.apache.commons.math3.stat.descriptive.moment.StandardDeviation;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.*;
public class ConsistentHashWithVirtualNode {
    /**
     * 服务器节点个数
     */
    private Integer serverNodeCount;
    /**
     * 每个服务器的虚拟节点的个数
     */
    private Integer virtualNodeCount;
    /**
     * 服务器节点名称
     */
    private String serverNodeName;
    /**
     * 虚拟节点名称
     */
    private String virtualNodeName;
    public ConsistentHashWithVirtualNode(Integer serverNodeCount, Integer virtualNodeCount, String serverNodeName, String virtualName) {
        this.serverNodeCount = serverNodeCount;
        this.virtualNodeCount = virtualNodeCount;
        this.serverNodeName = serverNodeName;
        this.virtualNodeName = virtualName;
    }
    public SortedMap<Integer, String> initNodes(){
        SortedMap<Integer, String> result = new TreeMap<>();
        for (int i = 0; i < serverNodeCount; i++) {
            for (int j = 0; j < virtualNodeCount; j++) {
                String node = serverNodeName + i + virtualNodeName + j;
                int hash = HashUtils.getHash(node);
                result.put(hash, node);
            }
        }
        return result;
    }
    public BigDecimal calculateStandardDeviation(Collection<Integer> dataList) {
        SortedMap<Integer, String> serverNodes = this.initNodes();
        Map<String,Integer> countMap = new HashMap<>();
        for(Integer data : dataList){
            String hitServerName = HitServerUtils.hitServer(data, serverNodes, virtualNodeName);
            HitServerUtils.countHit(hitServerName,countMap);
        }
        return calculateServerNodeStandardDeviation(countMap);
    }
    private BigDecimal calculateServerNodeStandardDeviation(Map<String,Integer> map) {
        double[] values = new double[serverNodeCount+1];
        int i = 0;
        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            values[i++] = entry.getValue();
            System.out.println(String.format("虚拟节点数量为 %s,服务器 %s 的命中次数为" + entry.getValue() , virtualNodeCount, entry.getKey()));
        }
        StandardDeviation standardDeviation = new StandardDeviation();
        return new BigDecimal(standardDeviation.evaluate(values)).setScale(0, RoundingMode.HALF_UP);
    }
}

package architect;
// HashCode计算类
public class HashUtils {
    /**
     * 使用FNV1_32_HASH算法计算服务器的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;
        // 如果算出来的值为负数则取其绝对值
        if (hash < 0)
            hash = Math.abs(hash);
        return hash;
    }
}

// 计算服务器的命中
package architect;
import java.util.Map;
import java.util.SortedMap;
public class HitServerUtils {
    public static String hitServer(Integer node, SortedMap<Integer, String> nodeMap, String virtualNodeName){
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap =
                nodeMap.tailMap(node);
        // 第一个Key就是顺时针过去离node最近的那个结点
        if(subMap.size()>0){
            Integer i = subMap.firstKey();
            // 返回对应的虚拟节点名称，这里字符串稍微截取一下
            String virtualNode = subMap.get(i);
            return virtualNode.substring(0, virtualNode.indexOf(virtualNodeName));
        }
        return nodeMap.get(nodeMap.firstKey()).substring(0, nodeMap.get(nodeMap.firstKey()).indexOf(virtualNodeName));
    }
    public static void countHit(String node, Map<String, Integer> map){
        if(map.containsKey(node)){
            map.put(node,map.get(node)+1);
            return;
        }
        map.put(node,1);
    }
}

// 单元测试类
package architect;

import junit.framework.TestCase;
import org.junit.Test;

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

public class ConsistentHashWithVirtualCodeTest extends TestCase {
    /**
     * 基于虚拟节点的一致性hash算法
     */
    private ConsistentHashWithVirtualNode consistentHashWithVirtualNode;
    /**
     * 服务器节点个数
     */
    private int serverNodeCount = 10;
    /**
     * 待查找命中缓存数据个数
     */
    private int keyNumber = 1000000;
    /**
     * 待查找命中缓存数据hashCode清单
     */
    private Collection<Integer> dataList;
    /**
     * 服务器节点名称
     */
    private String serverNodeName = "serverNode";
    /**
     * 虚拟节点名称
     */
    private String virtualNodeName = "&&virtual";
    /**
     * 待测试每个服务器的虚拟节点的个数清单
     */
    private List<Integer> virtualNodeNumbers = Arrays.asList(1, 5, 100, 120, 140, 150, 180, 200, 250, 300, 400, 500, 1000, 1500, 2000, 2500);
    @Override
    public void setUp() {
        this.dataList = this.initDataToHit();
        System.out.println("总数据个数为 " + this.dataList.size());
    }
    /**
     * 服务器节点在设置不同虚拟节点个数下缓存命中的次数的标准差测试
     */
    @Test
    public void testServerNodeTitTimesStandardDeviationByVirtualNode() {
        SortedMap<Integer, BigDecimal> standardDeviations = new TreeMap<>();
        virtualNodeNumbers.forEach(virtualNodeNumber -> {
            consistentHashWithVirtualNode = new ConsistentHashWithVirtualNode(serverNodeCount, virtualNodeNumber, serverNodeName, virtualNodeName);
            BigDecimal standardDeviation = consistentHashWithVirtualNode.calculateStandardDeviation(dataList);
            standardDeviations.put(virtualNodeNumber, standardDeviation);
        });
        standardDeviations.entrySet().forEach(standardDeviation -> {
            System.out.println(String.format("虚拟节点数量为 %s,标准差为：%s", standardDeviation.getKey(), standardDeviation.getValue()));
        });
    }
    /**
     * 初始化待缓存查找命中数据hashCode集合
     *
     * @return hashCode集合
     */
    private Collection<Integer> initDataToHit() {
        Collection<Integer> result = new ArrayList<>();
        for (int i = 0; i < keyNumber; i++) {
            int value = HashCodeUtils.getHash(UUID.randomUUID().toString());
            result.add(value);
        }
        return result;
    }
}



总数据个数为 1000000
虚拟节点数量为 1,服务器 serverNode9 的命中次数为97187
虚拟节点数量为 1,服务器 serverNode8 的命中次数为78086
虚拟节点数量为 1,服务器 serverNode7 的命中次数为85674
虚拟节点数量为 1,服务器 serverNode6 的命中次数为29623
虚拟节点数量为 1,服务器 serverNode5 的命中次数为89130
虚拟节点数量为 1,服务器 serverNode4 的命中次数为182166
虚拟节点数量为 1,服务器 serverNode3 的命中次数为9496
虚拟节点数量为 1,服务器 serverNode2 的命中次数为131325
虚拟节点数量为 1,服务器 serverNode1 的命中次数为255595
虚拟节点数量为 1,服务器 serverNode0 的命中次数为41718
虚拟节点数量为 5,服务器 serverNode9 的命中次数为73578
虚拟节点数量为 5,服务器 serverNode8 的命中次数为180238
虚拟节点数量为 5,服务器 serverNode7 的命中次数为41220
虚拟节点数量为 5,服务器 serverNode6 的命中次数为128081
虚拟节点数量为 5,服务器 serverNode5 的命中次数为86920
虚拟节点数量为 5,服务器 serverNode4 的命中次数为74617
虚拟节点数量为 5,服务器 serverNode3 的命中次数为68683
虚拟节点数量为 5,服务器 serverNode2 的命中次数为141864
虚拟节点数量为 5,服务器 serverNode1 的命中次数为112912
虚拟节点数量为 5,服务器 serverNode0 的命中次数为91887
虚拟节点数量为 100,服务器 serverNode9 的命中次数为106150
虚拟节点数量为 100,服务器 serverNode8 的命中次数为91360
虚拟节点数量为 100,服务器 serverNode7 的命中次数为101192
虚拟节点数量为 100,服务器 serverNode6 的命中次数为99490
虚拟节点数量为 100,服务器 serverNode5 的命中次数为111914
虚拟节点数量为 100,服务器 serverNode4 的命中次数为90069
虚拟节点数量为 100,服务器 serverNode3 的命中次数为98016
虚拟节点数量为 100,服务器 serverNode2 的命中次数为101417
虚拟节点数量为 100,服务器 serverNode1 的命中次数为95026
虚拟节点数量为 100,服务器 serverNode0 的命中次数为105366
虚拟节点数量为 120,服务器 serverNode9 的命中次数为102905
虚拟节点数量为 120,服务器 serverNode8 的命中次数为91757
虚拟节点数量为 120,服务器 serverNode7 的命中次数为107976
虚拟节点数量为 120,服务器 serverNode6 的命中次数为109105
虚拟节点数量为 120,服务器 serverNode5 的命中次数为111018
虚拟节点数量为 120,服务器 serverNode4 的命中次数为93980
虚拟节点数量为 120,服务器 serverNode3 的命中次数为94215
虚拟节点数量为 120,服务器 serverNode2 的命中次数为92237
虚拟节点数量为 120,服务器 serverNode1 的命中次数为92362
虚拟节点数量为 120,服务器 serverNode0 的命中次数为104445
虚拟节点数量为 140,服务器 serverNode9 的命中次数为109771
虚拟节点数量为 140,服务器 serverNode8 的命中次数为96680
虚拟节点数量为 140,服务器 serverNode7 的命中次数为104084
虚拟节点数量为 140,服务器 serverNode6 的命中次数为104986
虚拟节点数量为 140,服务器 serverNode5 的命中次数为112695
虚拟节点数量为 140,服务器 serverNode4 的命中次数为91172
虚拟节点数量为 140,服务器 serverNode3 的命中次数为91529
虚拟节点数量为 140,服务器 serverNode2 的命中次数为91174
虚拟节点数量为 140,服务器 serverNode1 的命中次数为96932
虚拟节点数量为 140,服务器 serverNode0 的命中次数为100977
虚拟节点数量为 150,服务器 serverNode9 的命中次数为102331
虚拟节点数量为 150,服务器 serverNode8 的命中次数为95192
虚拟节点数量为 150,服务器 serverNode7 的命中次数为106368
虚拟节点数量为 150,服务器 serverNode6 的命中次数为104536
虚拟节点数量为 150,服务器 serverNode5 的命中次数为108816
虚拟节点数量为 150,服务器 serverNode4 的命中次数为93751
虚拟节点数量为 150,服务器 serverNode3 的命中次数为98255
虚拟节点数量为 150,服务器 serverNode2 的命中次数为91523
虚拟节点数量为 150,服务器 serverNode1 的命中次数为92389
虚拟节点数量为 150,服务器 serverNode0 的命中次数为106839
虚拟节点数量为 180,服务器 serverNode9 的命中次数为95511
虚拟节点数量为 180,服务器 serverNode8 的命中次数为97311
虚拟节点数量为 180,服务器 serverNode7 的命中次数为105246
虚拟节点数量为 180,服务器 serverNode6 的命中次数为103885
虚拟节点数量为 180,服务器 serverNode5 的命中次数为101063
虚拟节点数量为 180,服务器 serverNode4 的命中次数为99486
虚拟节点数量为 180,服务器 serverNode3 的命中次数为105489
虚拟节点数量为 180,服务器 serverNode2 的命中次数为99242
虚拟节点数量为 180,服务器 serverNode1 的命中次数为89041
虚拟节点数量为 180,服务器 serverNode0 的命中次数为103726
虚拟节点数量为 200,服务器 serverNode9 的命中次数为100093
虚拟节点数量为 200,服务器 serverNode8 的命中次数为97431
虚拟节点数量为 200,服务器 serverNode7 的命中次数为103665
虚拟节点数量为 200,服务器 serverNode6 的命中次数为109936
虚拟节点数量为 200,服务器 serverNode5 的命中次数为103993
虚拟节点数量为 200,服务器 serverNode4 的命中次数为94820
虚拟节点数量为 200,服务器 serverNode3 的命中次数为101720
虚拟节点数量为 200,服务器 serverNode2 的命中次数为92533
虚拟节点数量为 200,服务器 serverNode1 的命中次数为96410
虚拟节点数量为 200,服务器 serverNode0 的命中次数为99399
虚拟节点数量为 250,服务器 serverNode9 的命中次数为100820
虚拟节点数量为 250,服务器 serverNode8 的命中次数为97893
虚拟节点数量为 250,服务器 serverNode7 的命中次数为101562
虚拟节点数量为 250,服务器 serverNode6 的命中次数为106167
虚拟节点数量为 250,服务器 serverNode5 的命中次数为95834
虚拟节点数量为 250,服务器 serverNode4 的命中次数为104858
虚拟节点数量为 250,服务器 serverNode3 的命中次数为98374
虚拟节点数量为 250,服务器 serverNode2 的命中次数为97810
虚拟节点数量为 250,服务器 serverNode1 的命中次数为98218
虚拟节点数量为 250,服务器 serverNode0 的命中次数为98464
虚拟节点数量为 300,服务器 serverNode9 的命中次数为91489
虚拟节点数量为 300,服务器 serverNode8 的命中次数为102993
虚拟节点数量为 300,服务器 serverNode7 的命中次数为101695
虚拟节点数量为 300,服务器 serverNode6 的命中次数为101534
虚拟节点数量为 300,服务器 serverNode5 的命中次数为95657
虚拟节点数量为 300,服务器 serverNode4 的命中次数为109415
虚拟节点数量为 300,服务器 serverNode3 的命中次数为94634
虚拟节点数量为 300,服务器 serverNode2 的命中次数为101595
虚拟节点数量为 300,服务器 serverNode1 的命中次数为102359
虚拟节点数量为 300,服务器 serverNode0 的命中次数为98629
虚拟节点数量为 400,服务器 serverNode9 的命中次数为93989
虚拟节点数量为 400,服务器 serverNode8 的命中次数为98911
虚拟节点数量为 400,服务器 serverNode7 的命中次数为117310
虚拟节点数量为 400,服务器 serverNode6 的命中次数为102818
虚拟节点数量为 400,服务器 serverNode5 的命中次数为98519
虚拟节点数量为 400,服务器 serverNode4 的命中次数为96831
虚拟节点数量为 400,服务器 serverNode3 的命中次数为95536
虚拟节点数量为 400,服务器 serverNode2 的命中次数为98536
虚拟节点数量为 400,服务器 serverNode1 的命中次数为97318
虚拟节点数量为 400,服务器 serverNode0 的命中次数为100232
虚拟节点数量为 500,服务器 serverNode9 的命中次数为91246
虚拟节点数量为 500,服务器 serverNode8 的命中次数为101325
虚拟节点数量为 500,服务器 serverNode7 的命中次数为110125
虚拟节点数量为 500,服务器 serverNode6 的命中次数为104245
虚拟节点数量为 500,服务器 serverNode5 的命中次数为101343
虚拟节点数量为 500,服务器 serverNode4 的命中次数为101815
虚拟节点数量为 500,服务器 serverNode3 的命中次数为94576
虚拟节点数量为 500,服务器 serverNode2 的命中次数为100973
虚拟节点数量为 500,服务器 serverNode1 的命中次数为96725
虚拟节点数量为 500,服务器 serverNode0 的命中次数为97627
虚拟节点数量为 1000,服务器 serverNode9 的命中次数为97321
虚拟节点数量为 1000,服务器 serverNode8 的命中次数为100783
虚拟节点数量为 1000,服务器 serverNode7 的命中次数为104555
虚拟节点数量为 1000,服务器 serverNode6 的命中次数为96789
虚拟节点数量为 1000,服务器 serverNode5 的命中次数为96124
虚拟节点数量为 1000,服务器 serverNode4 的命中次数为99348
虚拟节点数量为 1000,服务器 serverNode3 的命中次数为102450
虚拟节点数量为 1000,服务器 serverNode2 的命中次数为100374
虚拟节点数量为 1000,服务器 serverNode1 的命中次数为99537
虚拟节点数量为 1000,服务器 serverNode0 的命中次数为102719
虚拟节点数量为 1,标准差为：74008
虚拟节点数量为 5,标准差为：41044
虚拟节点数量为 100,标准差为：6784
虚拟节点数量为 120,标准差为：7834
虚拟节点数量为 140,标准差为：7797
虚拟节点数量为 150,标准差为：6549
虚拟节点数量为 180,标准差为：5122
虚拟节点数量为 200,标准差为：5094
虚拟节点数量为 250,标准差为：3325
虚拟节点数量为 300,标准差为：5087
虚拟节点数量为 400,标准差为：6553
虚拟节点数量为 500,标准差为：5278
虚拟节点数量为 1000,标准差为：2750