架构 2 期第 5 周作业



public class ServerTest {
	private static String[] servers = new String[150];
    //key表示服务器的hash值，value表示服务器
    private static SortedMap<Integer, String> sortedMap = new TreeMap<Integer, String>();
    private static Map<String,Integer> result = new HashMap<>();
    //真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
    private static List<String> realNodes = new LinkedList<String>();
    //虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
    //虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应5个虚拟节点
    private static final int VIRTUAL_NODES = 10;
    static{
        //先把原始的服务器添加到真实结点列表中
        for(int i=0; i<servers.length; i++)
            realNodes.add(String.valueOf(i));
        //再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
        for (String str : realNodes){
            result.put(str,0);
            for(int i=0; i<VIRTUAL_NODES; i++){
                String virtualNodeName = str + "&&VN" + String.valueOf(i);
                int hash = getHash(virtualNodeName);
                //System.out.println("虚拟节点[" + virtualNodeName + "]被添加, hash值为" + hash);
                virtualNodes.put(hash, virtualNodeName);
            }
        }
        System.out.println();
    }
    //使用FNV1_32_HASH算法计算服务器的Hash值,这里不使用重写hashCode的方法，最终效果没区别
    private 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;
    }
    //得到应当路由到的结点
    private static String getServer(String key){
        //得到该key的hash值
        int hash = getHash(key);
        // 得到大于该Hash值的所有Map
        SortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);
        String virtualNode;
        if(subMap.isEmpty()){
            //如果没有比该key的hash值大的，则从第一个node开始
            Integer i = virtualNodes.firstKey();
            //返回对应的服务器
            virtualNode = virtualNodes.get(i);
        }else{
            //第一个Key就是顺时针过去离node最近的那个结点
            Integer i = subMap.firstKey();
            //返回对应的服务器
            virtualNode = subMap.get(i);
        }
        //virtualNode虚拟节点名称要截取一下
        if(!"".equals(virtualNode)&&virtualNode!=null){
            return virtualNode.substring(0, virtualNode.indexOf("&&"));
        }
        return null;
    }
    public static void main(String[] args) {
        String m = "";
        for(int i=0; i<10000000; i++){
            m = String.valueOf(i);
            getHash(m);
            putInServce(getServer(m));
        }
        DecimalFormat df = new DecimalFormat("#");
        for(String server:result.keySet()){
            System.out.println("服务器"+server+"命中了"+result.get(server)+"个,占比千分之"+df.format(1000*result.get(server)/10000000));
        }
    }
    static void putInServce(String server){
        if(result.containsKey(server)){
            result.put(server,result.get(server)+1);
        }
    }
}  

模拟150个真实节点 每个真实节点下包括5个虚拟节点 100万个请求 平均分到每个真实节点的命中情况如下：

服务器88命中了62735个,占比千分之6

服务器89命中了75173个,占比千分之7

服务器110命中了45557个,占比千分之4

服务器111命中了49404个,占比千分之4

服务器112命中了33856个,占比千分之3

服务器113命中了54907个,占比千分之5

服务器114命中了75927个,占比千分之7

服务器115命中了54283个,占比千分之5

服务器116命中了65095个,占比千分之6

服务器90命中了58659个,占比千分之5

服务器117命中了63552个,占比千分之6

服务器91命中了73801个,占比千分之7

服务器118命中了95439个,占比千分之9

服务器92命中了33173个,占比千分之3

服务器119命中了105304个,占比千分之10

服务器93命中了32427个,占比千分之3

服务器94命中了71606个,占比千分之7

服务器95命中了87485个,占比千分之8

服务器96命中了43953个,占比千分之4

服务器97命中了60630个,占比千分之6

服务器10命中了72867个,占比千分之7

服务器98命中了66671个,占比千分之6

服务器11命中了86952个,占比千分之8

服务器99命中了70471个,占比千分之7

服务器12命中了46771个,占比千分之4

服务器13命中了70813个,占比千分之7

服务器14命中了76044个,占比千分之7

服务器15命中了85780个,占比千分之8

服务器16命中了61621个,占比千分之6

服务器17命中了82268个,占比千分之8

服务器18命中了64643个,占比千分之6

服务器19命中了52028个,占比千分之5

服务器120命中了83219个,占比千分之8

服务器0命中了66007个,占比千分之6

服务器121命中了84461个,占比千分之8

服务器1命中了69087个,占比千分之6

服务器122命中了76526个,占比千分之7

服务器2命中了44907个,占比千分之4

服务器123命中了62012个,占比千分之6

服务器3命中了72996个,占比千分之7

服务器124命中了56746个,占比千分之5

服务器4命中了86989个,占比千分之8

服务器125命中了80979个,占比千分之8

服务器5命中了54046个,占比千分之5

服务器126命中了49250个,占比千分之4

服务器6命中了87121个,占比千分之8

服务器127命中了84261个,占比千分之8

服务器7命中了42876个,占比千分之4

服务器128命中了30913个,占比千分之3

服务器8命中了60017个,占比千分之6

服务器129命中了62429个,占比千分之6

服务器9命中了34465个,占比千分之3

服务器20命中了81701个,占比千分之8

服务器21命中了95316个,占比千分之9

服务器22命中了61205个,占比千分之6

服务器23命中了96007个,占比千分之9

服务器24命中了57470个,占比千分之5

服务器25命中了63475个,占比千分之6

服务器26命中了95768个,占比千分之9

服务器27命中了60879个,占比千分之6

服务器28命中了66742个,占比千分之6

服务器29命中了53376个,占比千分之5

服务器130命中了72446个,占比千分之7

服务器131命中了69987个,占比千分之6

服务器132命中了67675个,占比千分之6

服务器133命中了57912个,占比千分之5

服务器134命中了32183个,占比千分之3

服务器135命中了77288个,占比千分之7

服务器136命中了54947个,占比千分之5

服务器137命中了129244个,占比千分之12

服务器138命中了86085个,占比千分之8

服务器139命中了47292个,占比千分之4

服务器30命中了45717个,占比千分之4

服务器31命中了78395个,占比千分之7

服务器32命中了86789个,占比千分之8

服务器33命中了82874个,占比千分之8

服务器34命中了64365个,占比千分之6

服务器35命中了41736个,占比千分之4

服务器36命中了65801个,占比千分之6

服务器37命中了83540个,占比千分之8

服务器38命中了52933个,占比千分之5

服务器39命中了69417个,占比千分之6

服务器140命中了73939个,占比千分之7

服务器141命中了94623个,占比千分之9

服务器142命中了51188个,占比千分之5

服务器143命中了24121个,占比千分之2

服务器144命中了43294个,占比千分之4

服务器145命中了56273个,占比千分之5

服务器146命中了78183个,占比千分之7

服务器147命中了52100个,占比千分之5

服务器148命中了86017个,占比千分之8

服务器149命中了65175个,占比千分之6

服务器40命中了50491个,占比千分之5

服务器41命中了48294个,占比千分之4

服务器42命中了75499个,占比千分之7

服务器43命中了77293个,占比千分之7

服务器44命中了103928个,占比千分之10

服务器45命中了44063个,占比千分之4

服务器46命中了58985个,占比千分之5

服务器47命中了65501个,占比千分之6

服务器48命中了68433个,占比千分之6

服务器49命中了103161个,占比千分之10

服务器50命中了48905个,占比千分之4

服务器51命中了53672个,占比千分之5

服务器52命中了52934个,占比千分之5

服务器53命中了67663个,占比千分之6

服务器54命中了83643个,占比千分之8

服务器55命中了40159个,占比千分之4

服务器56命中了54675个,占比千分之5

服务器57命中了85462个,占比千分之8

服务器58命中了72965个,占比千分之7

服务器59命中了85176个,占比千分之8

服务器60命中了70323个,占比千分之7

服务器61命中了70104个,占比千分之7

服务器62命中了45956个,占比千分之4

服务器63命中了80400个,占比千分之8

服务器64命中了83095个,占比千分之8

服务器65命中了55981个,占比千分之5

服务器66命中了102434个,占比千分之10

服务器67命中了64222个,占比千分之6

服务器68命中了105729个,占比千分之10

服务器69命中了75519个,占比千分之7

服务器70命中了86756个,占比千分之8

服务器71命中了49962个,占比千分之4

服务器72命中了71623个,占比千分之7

服务器73命中了68371个,占比千分之6

服务器74命中了58747个,占比千分之5

服务器75命中了52050个,占比千分之5

服务器76命中了79075个,占比千分之7

服务器77命中了33840个,占比千分之3

服务器78命中了85735个,占比千分之8

服务器79命中了59594个,占比千分之5

服务器100命中了46638个,占比千分之4

服务器101命中了74699个,占比千分之7

服务器102命中了74791个,占比千分之7

服务器103命中了53814个,占比千分之5

服务器104命中了95293个,占比千分之9

服务器105命中了61153个,占比千分之6

服务器106命中了69873个,占比千分之6

服务器80命中了42227个,占比千分之4

服务器107命中了85129个,占比千分之8

服务器81命中了64993个,占比千分之6

服务器108命中了80588个,占比千分之8

服务器82命中了47861个,占比千分之4

服务器109命中了61071个,占比千分之6

服务器83命中了36782个,占比千分之3

服务器84命中了80528个,占比千分之8

服务器85命中了48394个,占比千分之4

服务器86命中了64563个,占比千分之6

服务器87命中了78505个,占比千分之7