写点什么

第 5 周作业：一致性 Hash 算法

用户头像
姜 某某
关注
发布于: 2020 年 07 月 07 日

  1. 简单hash负载匀衡算法

1.1 算法原理：简单Hash负载均衡算法时最先出现。主要是对客户端请求Key散列值对服务段机器数取模，模树对应服务器数量，取模结果就是接收该请求的服务器机器。

1.2 缺点。服务器数量发生变化时，按照上面所述的负载匀衡计算方法，对应缓存的key会失效，缓存数据需要重新计算。

  1. 简单一致性HASH算法。

2.1 算法原理：构造一个Hash环，这个Hash环，最大是2的32次方−1，因为hashCode是int型。服务端机器散列分部到HASH环上，客户端请求也散列到HASH环上，按照顺时针或逆时针原则，找到对应的服务器。





2.2 问题点。

  • 服务端机器散列到Hash环上，可能会有分布不均的问题，导致业务请求不能均衡地负载。

  • 如果集群中有一台机器宕机，会导致该机器上的请求分配到临近的下一个机器上，那么该机器有可能导致负载过高而引起系统雪崩。

  • 如果集群中增加一台机器，并不能够均衡原有所有机器的服务压力，只会分担临近机器的压力，所以不能做到新增服务想要达到的目的。

  1. 一致性Hash算法。

一致性Hash算法是在简单一致性Hash算法的基础上，通过引入虚拟节点 的方法，将服务机器更加散列到Hash环上，这种做法并不能够完全均衡地散列服务器，只能够做到相对的均衡。另外一致性Hash算法并不是能够完全解决系统雪崩的问题，而且虚拟节点的数量也不宜过多，否则也会影响到服务的性能。







public interface Cache {
    String get(String key);
    void set(String key, String value);
}
public class CacheImpl implements Cache{
    private ConsistentHashRing ring = new ConsistentHashRing();
    public CacheImpl(List<String>servers, int virtualNumPerNode) {
        ring.addServers(servers, virtualNumPerNode);
    }
    @Override
    public String get(String key) {
        Cache serverKey = ring.getServer(key);
        return serverKey.get(key);
    }
    @Override
    public void set(String key, String val) {
        Cache serverKey = ring.getServer(key);
        serverKey.set(key, val);
    }
    @Override
    public String toString() {
        return ring.toString();
    }
}
public class CacheServer implements Cache {
    //MOCK缓存，存储KV
    private Map<String, String> caches = new HashMap<>();
    private String serverName;
    public CacheServer(String serverName){
        this.serverName = serverName;
    }
    public String getServerName(){
        return this.serverName;
    }
    public Map<String, String> getCaches(){
        return caches;
    }
    @Override
    public String get(String key) {
        return caches.get(key);
    }
    @Override
    public void set(String key, String value) {
        caches.put(key, value);
    }
}
public class ConsistentHashRing {
    TreeMap<Integer, Cache> map = new TreeMap<>();
    List<Cache> servers = new ArrayList<>();
    /**
     * 往环中加入服务器
     */
    public void addServers(List<String> servers, int virtualNum){
        if(CollectionUtils.isNotEmpty(servers)){
            for(String server : servers){
                //先放置服务器
                Cache cacheServer = new CacheServer(server);
                map.put(getHashCode(server), cacheServer);
                //加入虚拟节点
                for(int i=0; i<virtualNum; i++){
                    map.put(getHashCode(server +"?NODE"+i), cacheServer);
                }
                this.servers.add(cacheServer);
            }
        }
    }
    public int getHashCode(String key) {
        final int p = 16777619;
        int ret = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++) {
            ret = (ret ^ key.charAt(i)) * p;
        }
        ret += ret << 13;
        ret ^= ret >> 7;
        ret += ret << 3;
        ret ^= ret >> 17;
        ret += ret << 5;
        return ret < 0 ? -ret : ret;
    }
    /**
     * 根据缓存key，查找环上的对应服务器
     *
     */
    public Cache getServer(String cacheKey) {
        if(MapUtils.isEmpty(map) || StringUtils.isBlank(cacheKey)){
            System.out.println("paras error");
            return null;
        }
        int hash = getHashCode(cacheKey);
        Map.Entry<Integer, Cache> server = map.ceilingEntry(hash);
        if (server == null)
            return map.firstEntry().getValue();
        return server.getValue();
    }
    @Override
    public String toString() {
        int totalNum = 0;
        for (Cache cache : servers) {
            CacheServer cacheServer = (CacheServer) cache;
            totalNum += cacheServer.getCaches().size();
        }
        int avg = totalNum / servers.size();
        StringBuilder sb = new StringBuilder();
        sb.append("总缓存个数：").append(totalNum)
                .append(" 服务器台数：").append(servers.size())
                .append(" 每服务器虚拟节点数：").append(map.size()/servers.size() - 1)
                .append(" 平均值：").append(avg)
                .append("\r\n");
        // 标准差公式： (每个样本 - 平均值)的平方 / (服务器数 - 1)，结果再取平方根
        long diff = 0;
        for (Cache cache : servers) {
            CacheServer cacheServer = (CacheServer) cache;
            int size = cacheServer.getCaches().size();
            sb.append("Server-Name:")
                    .append(cacheServer.getServerName())
                    .append(" Cache-num: ")
                    .append(size)
                    .append("\r\n");
            long tmp = size - avg;
            diff += (tmp * tmp);
        }
        diff /= (servers.size() - 1);
        sb.append("标准差为： ").append(Math.sqrt(diff)).append("\r\n");
        return sb.toString();
    }
}
public class Main {
    static List<String> servers = Arrays.asList(
            "10.0.0.1",
            "10.0.0.2",
            "10.0.0.3",
            "10.0.0.4",
            "10.0.0.5",
            "10.0.0.6",
            "10.0.0.7",
            "10.0.0.8",
            "10.0.0.9",
            "10.0.0.10");
    static int maxCacheNum = 1000000;
    public static void main(String[] args) {
        testCache(0);
        testCache(1);
        testCache(10);
        testCache(100);
        testCache(150);
        testCache(180);
        testCache(200);
        testCache(250);
        testCache(300);
        testCache(400);
        testCache(600);
    }
    static void testCache(int virtualNum) {
        Cache cache = new CacheImpl(servers, virtualNum);
        fillCache(cache, maxCacheNum);
        System.out.println(cache);
    }
    static void fillCache(Cache cache, int cacheNum) {
        for (int i = 0; i < cacheNum; i++) {
            String key = "key" + i;
            String val = "val" + key;
            cache.set(key, val);
        }
    }
}



总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：0 平均值：100000
Server-Name:10.0.0.1 Cache-num: 126281
Server-Name:10.0.0.2 Cache-num: 6669
Server-Name:10.0.0.3 Cache-num: 154480
Server-Name:10.0.0.4 Cache-num: 138847
Server-Name:10.0.0.5 Cache-num: 11541
Server-Name:10.0.0.6 Cache-num: 357376
Server-Name:10.0.0.7 Cache-num: 91493
Server-Name:10.0.0.8 Cache-num: 13296
Server-Name:10.0.0.9 Cache-num: 82488
Server-Name:10.0.0.10 Cache-num: 17529
标准差为： 106793.68220545632

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：1 平均值：100000
Server-Name:10.0.0.1 Cache-num: 138804
Server-Name:10.0.0.2 Cache-num: 22060
Server-Name:10.0.0.3 Cache-num: 174995
Server-Name:10.0.0.4 Cache-num: 113543
Server-Name:10.0.0.5 Cache-num: 46784
Server-Name:10.0.0.6 Cache-num: 198967
Server-Name:10.0.0.7 Cache-num: 116060
Server-Name:10.0.0.8 Cache-num: 19315
Server-Name:10.0.0.9 Cache-num: 82488
Server-Name:10.0.0.10 Cache-num: 86984
标准差为： 60789.75229428065

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：10 平均值：100000
Server-Name:10.0.0.1 Cache-num: 104938
Server-Name:10.0.0.2 Cache-num: 79140
Server-Name:10.0.0.3 Cache-num: 72727
Server-Name:10.0.0.4 Cache-num: 112781
Server-Name:10.0.0.5 Cache-num: 140551
Server-Name:10.0.0.6 Cache-num: 101554
Server-Name:10.0.0.7 Cache-num: 79670
Server-Name:10.0.0.8 Cache-num: 85200
Server-Name:10.0.0.9 Cache-num: 130580
Server-Name:10.0.0.10 Cache-num: 92859
标准差为： 22686.196552088673

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：100 平均值：100000
Server-Name:10.0.0.1 Cache-num: 103966
Server-Name:10.0.0.2 Cache-num: 98325
Server-Name:10.0.0.3 Cache-num: 107182
Server-Name:10.0.0.4 Cache-num: 90553
Server-Name:10.0.0.5 Cache-num: 104485
Server-Name:10.0.0.6 Cache-num: 103057
Server-Name:10.0.0.7 Cache-num: 103351
Server-Name:10.0.0.8 Cache-num: 87699
Server-Name:10.0.0.9 Cache-num: 95855
Server-Name:10.0.0.10 Cache-num: 105527
标准差为： 6659.118560290093

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：150 平均值：100000
Server-Name:10.0.0.1 Cache-num: 97799
Server-Name:10.0.0.2 Cache-num: 103811
Server-Name:10.0.0.3 Cache-num: 111376
Server-Name:10.0.0.4 Cache-num: 97195
Server-Name:10.0.0.5 Cache-num: 95083
Server-Name:10.0.0.6 Cache-num: 99680
Server-Name:10.0.0.7 Cache-num: 98785
Server-Name:10.0.0.8 Cache-num: 91618
Server-Name:10.0.0.9 Cache-num: 103900
Server-Name:10.0.0.10 Cache-num: 100753
标准差为： 5461.379221405523

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：180 平均值：100000
Server-Name:10.0.0.1 Cache-num: 95347
Server-Name:10.0.0.2 Cache-num: 101224
Server-Name:10.0.0.3 Cache-num: 104367
Server-Name:10.0.0.4 Cache-num: 99721
Server-Name:10.0.0.5 Cache-num: 103001
Server-Name:10.0.0.6 Cache-num: 95309
Server-Name:10.0.0.7 Cache-num: 106419
Server-Name:10.0.0.8 Cache-num: 96007
Server-Name:10.0.0.9 Cache-num: 100253
Server-Name:10.0.0.10 Cache-num: 98352
标准差为： 3847.598341823117

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：200 平均值：100000
Server-Name:10.0.0.1 Cache-num: 94915
Server-Name:10.0.0.2 Cache-num: 104407
Server-Name:10.0.0.3 Cache-num: 103055
Server-Name:10.0.0.4 Cache-num: 101686
Server-Name:10.0.0.5 Cache-num: 98822
Server-Name:10.0.0.6 Cache-num: 94714
Server-Name:10.0.0.7 Cache-num: 103939
Server-Name:10.0.0.8 Cache-num: 102839
Server-Name:10.0.0.9 Cache-num: 98001
Server-Name:10.0.0.10 Cache-num: 97622
标准差为： 3651.643465619282

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：250 平均值：100000
Server-Name:10.0.0.1 Cache-num: 92358
Server-Name:10.0.0.2 Cache-num: 105479
Server-Name:10.0.0.3 Cache-num: 108135
Server-Name:10.0.0.4 Cache-num: 96552
Server-Name:10.0.0.5 Cache-num: 99564
Server-Name:10.0.0.6 Cache-num: 93253
Server-Name:10.0.0.7 Cache-num: 107010
Server-Name:10.0.0.8 Cache-num: 100038
Server-Name:10.0.0.9 Cache-num: 97353
Server-Name:10.0.0.10 Cache-num: 100258
标准差为： 5461.108495534583

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：300 平均值：100000
Server-Name:10.0.0.1 Cache-num: 98877
Server-Name:10.0.0.2 Cache-num: 104614
Server-Name:10.0.0.3 Cache-num: 109080
Server-Name:10.0.0.4 Cache-num: 97134
Server-Name:10.0.0.5 Cache-num: 92452
Server-Name:10.0.0.6 Cache-num: 96634
Server-Name:10.0.0.7 Cache-num: 104742
Server-Name:10.0.0.8 Cache-num: 99452
Server-Name:10.0.0.9 Cache-num: 95405
Server-Name:10.0.0.10 Cache-num: 101610
标准差为： 5033.286202869851

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：400 平均值：100000
Server-Name:10.0.0.1 Cache-num: 100840
Server-Name:10.0.0.2 Cache-num: 102895
Server-Name:10.0.0.3 Cache-num: 104440
Server-Name:10.0.0.4 Cache-num: 104144
Server-Name:10.0.0.5 Cache-num: 95783
Server-Name:10.0.0.6 Cache-num: 90076
Server-Name:10.0.0.7 Cache-num: 104480
Server-Name:10.0.0.8 Cache-num: 101943
Server-Name:10.0.0.9 Cache-num: 96030
Server-Name:10.0.0.10 Cache-num: 99369
标准差为： 4740.446919858929

总缓存个数：1000000 服务器台数：10 每服务器虚拟节点数：600 平均值：100000
Server-Name:10.0.0.1 Cache-num: 103417
Server-Name:10.0.0.2 Cache-num: 102469
Server-Name:10.0.0.3 Cache-num: 100347
Server-Name:10.0.0.4 Cache-num: 95392
Server-Name:10.0.0.5 Cache-num: 101912
Server-Name:10.0.0.6 Cache-num: 90973
Server-Name:10.0.0.7 Cache-num: 104451
Server-Name:10.0.0.8 Cache-num: 101727
Server-Name:10.0.0.9 Cache-num: 100812
Server-Name:10.0.0.10 Cache-num: 98500
标准差为： 4082.0972550883694



实验数据：

  1. 虚拟节点位于1-150时 标准方差逐步缩小。

  2. 虚拟节点个数 180时 标准方差 3847

虚拟节点个数 200时 标准方差 3651

  1. 虚拟节点个数250-600时 标准方差 又逐步变大。



结论：

虚拟节点 180-200 数量较好。

参考：

https://xie.infoq.cn/article/8651e7b5ef05177005b474dfc

https://xie.infoq.cn/article/0c660a8f26689cb4ac94e8b17



划线
评论
复制
发布于: 2020 年 07 月 07 日阅读数: 53
用户头像

姜 某某

关注

还未添加个人签名 2019.05.09 加入

还未添加个人简介

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
第 5 周作业：一致性 Hash 算法