一致性 Hash 算法——架构师训练营第 5 周

 关注
发布于: 2020 年 07 月 04 日
一致性Hash算法在很多集群方案中都有大规模应用，在面试中也经常出现，作为一个应用广泛的实用型算法，正好借着参加架构师训练营的机会，在开始作业内容之前，我还是决定将一致性hash算法做一个总结与说明。
一致性Hash算法，是为了解决分布式缓存在服务器扩容时数据访问不一致问题的算法，防止在服务器扩容时大量的缓存击穿引发缓存雪崩。
0. 架构师训练营第5周作业内容用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
1. Hash算法1.1 简单Hash负载均衡算法简单Hash负载均衡算法时最先出现的，算法逻辑与实现也非常简单，主要是对客户端请求Key的散列值对服务段机器数量取模，模数对应的服务端机器就是需要接收处理该请求的机器。
﻿
简单Hash算法的问题
服务器数量发生变化时，数据需要重新散列，成本代价比较大；
服务器数量发生变化时，对于缓存的key会失效，大量请求会缓存击穿，严重时会引发缓存雪崩，造成系统灾难。
1.2 简单一致性Hash负载均衡算法先说一下一致性Hash算法，主要特点如下：
构造一个Hash环，这个环有一个范围，例如：[0,3),[300,Integer.MAX_VALUE)
这个Hash环，最大是232−1，因为hashCode是int型，最大就是232−1
服务端机器负载散列到Hash环上
客户端请求也散列到Hash环上，按照顺时针（也可以用逆时针）找到最近的服务器负载
简单一致性Hash负载均衡算法的问题
服务端机器散列到Hash环上，可能会有分布不均的问题，导致业务请求不能均衡地负载
﻿
如果集群中有一台机器宕机，会导致该机器上的请求分配到临近的下一个机器上，那么该机器有可能导致负载过高而引起系统雪崩
如果集群中增加一台机器，并不能够均衡原有所有机器的服务压力，只会分担临近机器的压力，所以不能做到新增服务想要达到的目的，例如：下图增加了机器5，只会缓解机器0的压力，机器2，3，1的压力并未因增加了机器5而得到缓解
1.3 一致性Hash算法一致性Hash算法是在简单一致性Hash算法的基础上，通过引入虚拟节点 的方法，将服务机器更加散列到Hash环上，这种做法并不能够完全均衡地散列服务器，只能够做到相对的均衡。另外一致性Hash算法并不是能够完全解决系统雪崩的问题，而且虚拟节点的数量也不宜过多，否则也会影响到服务的性能。
2. 一致性Hash负载均衡算法实现（Java版本）2.1 代码实现、测试、总结这个版本并未考虑线程安全的问题
该版本测试以10个服务器节点，从1个虚节点到999个虚节点做了测试，计算相应的访问请求接入标准差，并进行了统计分析，发现以下特点：
虚节点个数少的时候，请求分布不均衡；
随着节点个数的增加，分布会相对地越来越均衡，但是性能会有所降低，耗时会增长；
随着节点个数增加到233（总虚节点233∗10=2330）时，标准差在3300左右，耗时在1600ms左右，请求均衡分布随着节点个数的增长就不会有太大的提升空间了；
虚节点增加到500（总虚节点500∗10=5000）时，性能随着节点数的增加趋于稳定；
虚节点在662（总虚节点662∗10=6620）时，标准差最小在2800左右，耗时在1300ms左右
2.2 一致性Hash负载均衡算法Java实现
public class ConsistentHash {
    // 服务器列表
    private List<String> servers = null;
    // 服务器虚拟节点
    private TreeMap<Integer, String> virtualNodes = new TreeMap<>();
    // 服务器访问统计
    private TreeMap<String, Integer> serverVisit = new TreeMap<>();
    // 虚拟节点个数
    private int virtualFactor = 180;
    public ConsistentHash(List<String> servers, int virtualFactor) {
        this.servers = servers;
        this.virtualFactor = virtualFactor;
        this.servers.forEach(server -> this.addServer(server));
    }
    /**
     * 获取字符串的hash值
     *
     * @param str
     * @return
     */
    public 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;
        return hash;
    }
    /**
     * 添加server节点
     *
     * @param server
     */
    public void addServer(String server) {
        if (!serverVisit.containsKey(server)) {
            serverVisit.put(server, 0);
            for (int i = 0; i < virtualFactor; i++) {
                virtualNodes.put(getHash(server + "?VNODE=" + i), server);
            }
        }
    }
    /**
     * 移除server节点
     *
     * @param server
     */
    public void removeServer(String server) {
        if (serverVisit.containsKey(server)) {
            serverVisit.remove(server);
            for (int i = 0; i < virtualFactor; i++) {
                Object o = virtualNodes.remove(getHash(server + "?VNODE=" + i));
            }
        }
    }
    /**
     * 模拟请求获取服务地址
     *
     * @param reqKey
     * @return
     */
    public String request(String reqKey) {
        String server = null;
        int reqHash = getHash(reqKey);
        SortedMap<Integer, String> greaterMap = virtualNodes.tailMap(reqHash, true);
        if (greaterMap.isEmpty()) {
            // 如果没有比reqHash大的值，则返回第一个虚拟服务器节点
            server = virtualNodes.get(virtualNodes.firstKey());
        } else {
            // greaterMap第一个值就是顺时针下离reqHash最近的虚拟服务器节点
            server = greaterMap.get(greaterMap.firstKey());
        }
        // 记录访问次数
        serverVisit.put(server, serverVisit.get(server) + 1);
        return server;
    }
    /**
     * 计算请求分布的标准差
     *
     * @return
     */
    public double calcStd() {
        Integer[] visitData = new Integer[serverVisit.size()];
        serverVisit.values().toArray(visitData);
        double avg = Arrays.stream(visitData).mapToInt(Integer::intValue).average().orElse(0d);
        double avgStd = Arrays.stream(visitData).map(count -> Math.pow(count - avg, 2)).mapToDouble(Double::doubleValue).average().orElse(0d);
        double std = Math.sqrt(avgStd);
        return std;
    }
}
2.3 一致性Hash负载均衡算法测试统计
    public static void main(String[] args) {
        // 模拟请求次数
        for (int j = 1; j < 1000; j++) {
            int times = 1000000;
            List<String> servers = Arrays.asList("192.168.1.1:8080", "192.168.1.2:8080", "192.168.1.3:8080");
            ConsistentHash consistentHash = new ConsistentHash(servers, j);
            long s = System.currentTimeMillis();
        /*for (int i = 0; i < times; i++) {
            consistentHash.request(UUID.randomUUID().toString());
        }
        System.out.println("耗时：" + (System.currentTimeMillis() - s) + " 标准差："+consistentHash.calcStd());
        // 打印模拟请求分布情况
        consistentHash.serverVisit.forEach((k, v) -> {
            System.out.println(k + " - [ " + v + " - " + times / consistentHash.serverVisit.size() + " = " + (v - times / consistentHash.serverVisit.size()) + " ]");
        });
        System.out.println("=======================================================");
        // 清除模拟请求分布数据
        consistentHash.serverVisit.forEach((k, v) -> {
            consistentHash.serverVisit.put(k, 0);
        });
        // 模拟移除一台服务器
        consistentHash.removeServer("192.168.1.1:8080");
        s = System.currentTimeMillis();
        for (int i = 0; i < times; i++) {
            consistentHash.request(UUID.randomUUID().toString());
        }
        System.out.println("耗时：" + (System.currentTimeMillis() - s) + " 标准差："+consistentHash.calcStd());
        consistentHash.serverVisit.forEach((k, v) -> {
            System.out.println(k + " - [ " + v + " - " + times / consistentHash.serverVisit.size() + " = " + (v - times / consistentHash.serverVisit.size()) + " ]");
        });
        System.out.println("=======================================================");
        // 清除模拟请求分布数据
        consistentHash.serverVisit.forEach((k, v) -> {
            consistentHash.serverVisit.put(k, 0);
        });
        // 模拟添加几台服务器
        consistentHash.addServer("192.168.1.1:8080");*/
            consistentHash.addServer("192.168.1.4:8080");
            consistentHash.addServer("192.168.1.5:8080");
            consistentHash.addServer("192.168.1.6:8080");
            consistentHash.addServer("192.168.1.7:8080");
            consistentHash.addServer("192.168.1.8:8080");
            consistentHash.addServer("192.168.1.9:8080");
            consistentHash.addServer("192.168.1.10:8080");
            s = System.currentTimeMillis();
            for (int i = 0; i < times; i++) {
                consistentHash.request(UUID.randomUUID().toString());
            }
            System.out.println(consistentHash.virtualFactor + "\t" + (System.currentTimeMillis() - s) + "\t" + consistentHash.calcStd());
        }
    }
﻿
发布于: 2020 年 07 月 04 日阅读数: 323
王友

 关注
懒是一种艺术 2018.03.26 加入
间歇性自律，持续性懒散，真的很懒！
发布
暂无评论