架构师第五周作业

关注
发布于: 2020 年 07 月 08 日
一致性哈希算法首先求出memcached服务器（节点）的哈希值，并将其配置到0～232的圆（continuum）上。
然后采用同样的方法求出存储数据的键的哈希值，并映射到相同的圆上。
然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器，就会保存到第一台memcached服务器上。
﻿
﻿
从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化而影响缓存的命中率，但Consistent Hashing中，只有在园（continuum）上增加服务器的地点逆时针方向的第一台服务器上的键会受到影响，如下图所示：
﻿
﻿
基于虚拟节点的一致性hash算法解决一致性hash算法 增加节点以后负载不均衡的问题
增加新节点以后，数据哈希更均匀，同时每个节点都会有一部分数据失效，但是由于数据量小，影响不大
﻿
```
package com.suke.hystrix;
﻿
import java.util.*;
﻿
/**
 * 带虚拟节点的一致性Hash算法
 */
public class ConsistentHashingWithoutVirtualNode {
    static String str="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    static int KEY_LENGTH = 10;
    static int KEY_COUNT = 1000000;
    //待添加入Hash环的服务器列表
    private static String[] servers = {
            "192.168.0.0:111",
            "192.168.0.1:111",
            "192.168.0.2:111",
            "192.168.0.3:111",
            "192.168.0.4:111",
            "192.168.0.5:111",
            "192.168.0.6:111",
            "192.168.0.7:111",
            "192.168.0.8:111",
            "192.168.0.9:111"};
﻿
    //真实结点列表,考虑到服务器上线、下线的场景，即添加、删除的场景会比较频繁，这里使用LinkedList会更好
    private static List<String> realNodes = new LinkedList<String>();
﻿
    //虚拟节点，key表示虚拟节点的hash值，value表示虚拟节点的名称
    private static SortedMap<Integer, String> virtualNodes = new TreeMap<Integer, String>();
﻿
    //虚拟节点的数目，这里写死，为了演示需要，一个真实结点对应10个虚拟节点
    private static final int VIRTUAL_NODES = 10;
﻿
    static{
        //先把原始的服务器添加到真实结点列表中
        for(int i=0; i<servers.length; i++)
            realNodes.add(servers[i]);
﻿
        //再添加虚拟节点，遍历LinkedList使用foreach循环效率会比较高
        for (String str : realNodes){
            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(virtualNode != null && !"".equals(virtualNode)){
            return virtualNode.substring(0, virtualNode.indexOf("&&"));
        }
        return null;
    }
﻿
    public static void main(String[] args){
        Map<String,Integer> db = new HashMap<>();
        for(int i = 0;i < KEY_COUNT;i ++){
            String key = getRandomString(KEY_LENGTH);
            String server = getServer(key);
            Integer count = db.getOrDefault(server,0);
            db.put(server,count+1);
        }
        double[] valArr = db.values().stream().mapToDouble(value -> value.doubleValue()).toArray();
        System.out.println("节点hash分布:");
        db.forEach((key,val)->{
            System.out.println(" server: " + key+" 数据量:"+val);
        });
﻿
        System.out.println("数据分布标准差:" + StandardDiviation(KEY_COUNT,valArr));
    }
    public static double StandardDiviation(double sum ,double[] x) {
        int m=x.length;
﻿
        double dAve=sum/m;//求平均值
        double dVar=0;
        for(int i=0;i<m;i++){//求方差
            dVar+=(x[i]-dAve)*(x[i]-dAve);
        }
        //reture Math.sqrt(dVar/(m-1));
        return Math.sqrt(dVar/m);
    }
    public static String getRandomString(int length){
        Random random=new Random();
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<length;i++){
            int number=random.nextInt(62);
            sb.append(str.charAt(number));
        }
        return sb.toString();
    }
}
﻿
```
﻿