架构师 0 期 | 一致性 Hash 算法

 关注
发布于: 2020 年 07 月 08 日
架构师训练营第五周作业用你熟悉的编程语言实现一致性 hash 算法。
编写测试用例测试这个算法，测试 100 万 KV 数据，10 个服务器节点的情况下，计算这些 KV 数据在服务器上分布数量的标准差，以评估算法的存储负载不均衡性。
﻿
为啥会有一致性Hash算法?在分布式系统中，为了平均分配服务器资源，最简单的思路就是随机分配。
对服务器总数进行取模运算，得到的余数就是目标服务器编号。
﻿
但是这个算法有个致命的问题，当业务高速发展时，增加服务器时，服务器总数增加，导致取模得到的值全都发生了变化，之前的数据就都错了。对分布式缓存来说，同一时刻，大量缓存失效，会出现缓存雪崩。后果都是灾难性的。
﻿
要解决这个问题就需要一个方案，当服务器数据有变化时，尽可能的小的影响现有的这种映射关系。
所以就诞生了一致性Hash算法。
﻿
一致性Hash算法原理一致性哈希算法通过一个叫作一致性哈希环的数据结构实现。
这个环的起点是 0，终点是 2^32 - 1，并且起点与终点连接，故这个环的整数分布范围是 [0, 2^32-1]
﻿
hash-ring.jpg
这次不再对服务器总数进行取模运算，而是对 2^32进行取模运算，这样得到的值就在这个哈希环上。
将服务器节点放在这个环上。
同样的道理，对缓存的对象进行同样的取模运算。得到的值也在此环上。顺时针寻找下去，将它放在离它最近的服务器里。
即对象k3、k1放在服务器t1上、 k4放在t3上、k2放在t2上。
﻿
hash-ring-hash-servers.jpg
﻿
这样当服务器数据有变化时，受影响的节点就只有离它最近的服务器。当服务器越多时，受到的影响越小。
﻿
hash-ring-add-server.jpg
﻿
虚拟节点以上方案还有个问题是，虽然增减服务器不会影响到太多已有服务。但是提升性能不太明显，只会分担节点顺时针后面的那台服务器，其他的没起到分担负载的作用。
解决方案是，增加虚拟节点。每台服务器虚拟成200个节点，平均散落在哈希环上。
﻿
判断Hash算法的好坏平衡性
哈希的结果能够尽可能分布到所有的集群机器上。
单调性
已经有一部分数据通过哈希算法分配到了相应机器上，又有新的机器加入到集群系统中。哈希的结果应该能够保证原有已分配的数据可以被映射到原有的或者新的机器上，而不是被映射到旧的集群中的其他机器。
分散性
在分布式环境中，终端看不到集群中所有的机器，而是只能看到其中的一部分。当终端希望通过哈希算法将数据映射到机器上时，由于不同终端所见的机器范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的数据被不同的终端映射到不同的机器上。这种情况显然是应该避免的，这极大地降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。 
负载
既然不同的终端可能将相同的数据映射到不同的机器上，那么对于一个特定的机器而言，也可能被不同的用户映射为不同的数据。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低机器的负荷。
﻿
代码实现代码目录结构
﻿
测试方法，模拟10台服务器，100万个KV数据，分别计算虚拟节点在1个、10个、100个、200个、500个、1000个的时候，标准差是多少。
﻿
public class Main {
    //10台服务器
    static String[] servers = new String[]{
            "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",
    };
    //测试100万个KV数据
    static int maxCacheNum = 1000000;
    public static void main(String[] args) {
        //测试从0个节点到1000个节点的标准差
        testCache(0);
        testCache(1);
        testCache(10);
        testCache(100);
        testCache(200);
        testCache(500);
        testCache(1000);
    }
    //测试方法，模拟每台服务多少虚拟节点
    static void testCache(int virtualNumPerNode) {
        Cache cache = new CacheImplement(servers, virtualNumPerNode);
        fillCache(cache, maxCacheNum);
        System.out.println(cache);
    }
    //把虚拟节点放到hash环上
    static void fillCache(Cache cache, int cacheNum) {
        for (int i = 0; i < cacheNum; i++) {
            String key = "key" + i;
            //System.out.println(String.valueOf(i) + ":" + (ConsistentHashRing.getHashCode(key)));
            String val = "val" + key;
            cache.set(key, val);
        }
    }
}
﻿
定义缓存接口类Cache，方便更换实现类。面向接口编程。
接口类中只暴露2个方法，一个get，一个set
﻿
public interface Cache {
    /**
     * 根据key读取缓存数据
     * @param key key
     * @return 缓存
     */
    String get(String key);
    /**
     * 设置缓存
     * @param key 缓存key
     * @param val 缓存值
     */
    void set(String key, String val);
}
﻿
实现缓存接口类CacheImplement
重新接口定义方法get、set、toString
构造方法，接收服务器列表和每台服务器虚拟节点数。
将虚拟节点遍历加到hash环上。
﻿
public class CacheImplement implements Cache {
    private ConsistentHashing hash = new ConsistentHashing();
    private String[] servers;
    //构造方法，添加服务器数组，及每台服务器虚拟节点个数
    public CacheImplement(String[] servers, int virtualNumPerNode) {
        hash.addServers(servers, virtualNumPerNode);
    }
    @Override
    public String get(String key) {
        Cache cache = hash.getServer(key);
        return cache.get(key);
    }
    @Override
    public void set(String key, String val) {
        Cache cache = hash.getServer(key);
        cache.set(key, val);
    }
    @Override
    public String toString() {
        return hash.toString();
    }
}
﻿
具体缓存实现类CacheServer
﻿
import java.util.HashMap;
import java.util.Map;
public class CacheServer implements Cache {
    //
    private Map<String, String> caches = new HashMap<>();
    //服务器名字
    private String serverName;
    public CacheServer(String serverName) {
        this.serverName = serverName;
    }
    public Map<String, String> getCaches() {
        return caches;
    }
    public String getServerName() {
        return serverName;
    }
    @Override
    public String get(String key) {
        return caches.get(key);
    }
    @Override
    public void set(String key, String val) {
        caches.put(key, val);
    }
}
﻿
一致性Hash类
提供向Hash环添加服务器方法
提供通过key，查找对应服务器方法
提供计算HashCode方法
提供打印结果及计算标准差
﻿
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
public class ConsistentHashing {
    //
    TreeMap<Integer, Cache> map = new TreeMap<>();
    //服务器列表
    List<Cache> servers = new ArrayList<>();
    /**
     * 往环中加入服务器
     *
     * @param servers           要加入的服务器列表
     * @param virtualNumPerNode 每台服务器增加多少个虚拟节点，0表示不增加虚拟节点
     */
    public void addServers(String[] servers, int virtualNumPerNode) {
        if (servers != null) {
            for (String server : servers) {
                Cache cacheServer = new CacheServer(server);
                map.put(getHashCode(server), cacheServer);
                // 加虚拟节点
                for (int i = 1; i <= virtualNumPerNode; i++) {
                    map.put(getVirutalHashCode(server, i), cacheServer);
                }
                this.servers.add(cacheServer);
            }
        }
    }
    /**
     * 根据指定的缓存key，查找环上的对应服务器返回
     *
     * @param cacheKey 缓存key
     * @return 服务器
     */
    public Cache getServer(String cacheKey) {
        if (map.size() <= 0)
            throw new IllegalArgumentException("you must add server before call this method.");
        if (cacheKey == null || cacheKey.isEmpty())
            throw new IllegalArgumentException("cacheKey can't be empty");
        int hash = getHashCode(cacheKey);
        Map.Entry<Integer, Cache> server = map.ceilingEntry(hash);
        if (server == null)
            return map.firstEntry().getValue();
        return server.getValue();
    }
    /**
     * 返回第i个虚拟结点的hash值，注意不能用随机值，以免重启导致变化。
     *
     * @param key 服务器值
     * @param i   第几个虚拟节点
     * @return hash code
     */
    private int getVirutalHashCode(String key, int i) {
        key = key + "&&Virtual" + i;
        return getHashCode(key);
    }
    public static int getHashCode(String key) {
        // 这里不使用hashCode的方法，最终效果没区别.
        // 结果太聚集，不使用
        // int ret = key.hashCode();
        //使用FNV1_32_HASH算法计算服务器的Hash值
        final int p = 16777619;
        int hash = (int) 2166136261L;
        for (int i = 0; i < key.length(); i++)
            hash = (hash ^ key.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;
    }
    @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("\n服务器台数：").append(servers.size())
                .append("\n每台服务器虚拟节点数：").append(map.size()/servers.size() - 1)
                .append("\n每台服务器虚拟节点平均值：").append(avg)
                .append("\r\n");
        // 标准差公式： (每个样本 - 平均值)的平方 / (服务器数 - 1)，结果再取平方根
        long diff = 0;
        for (Cache cache : servers) {
            CacheServer cacheServer = (CacheServer) cache;
            int size = cacheServer.getCaches().size();
            sb.append("服务器地址:").append(cacheServer.getServerName())
                    .append("  缓存个数: ").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();
    }
}
﻿
计算测试结果如下：
不使用虚拟节点的话，偏差很大，最少的是6千多个，最多的是35万多个，很不均衡。
﻿
当虚拟节点达到200个时，最少的是9万4千多个，最多的是11万多，差距已经不是很多。
﻿
当虚拟节点是1000个时，最小是9万5，最大是10万4，增加300个虚拟节点，收益并不大了。
﻿
以下为详细数据
总缓存个数：1000000
服务器台数：10
每台服务器虚拟节点数：0
每台服务器虚拟节点平均值：100000
服务器地址:10.0.0.1  缓存个数: 126281
服务器地址:10.0.0.2  缓存个数: 6669
服务器地址:10.0.0.3  缓存个数: 154480
服务器地址:10.0.0.4  缓存个数: 138847
服务器地址:10.0.0.5  缓存个数: 11541
服务器地址:10.0.0.6  缓存个数: 357376
服务器地址:10.0.0.7  缓存个数: 91493
服务器地址:10.0.0.8  缓存个数: 13296
服务器地址:10.0.0.9  缓存个数: 82488
服务器地址:10.0.0.10  缓存个数: 17529
标准差为： 106793.68220545632
总缓存个数：1000000
服务器台数：10
每台服务器虚拟节点数：1
每台服务器虚拟节点平均值：100000
服务器地址:10.0.0.1  缓存个数: 106183
服务器地址:10.0.0.2  缓存个数: 96674
服务器地址:10.0.0.3  缓存个数: 50094
服务器地址:10.0.0.4  缓存个数: 168298
服务器地址:10.0.0.5  缓存个数: 101609
服务器地址:10.0.0.6  缓存个数: 209265
服务器地址:10.0.0.7  缓存个数: 91493
服务器地址:10.0.0.8  缓存个数: 25798
服务器地址:10.0.0.9  缓存个数: 69784
服务器地址:10.0.0.10  缓存个数: 80802
标准差为： 53754.40262899403
总缓存个数：1000000
服务器台数：10
每台服务器虚拟节点数：10
每台服务器虚拟节点平均值：100000
服务器地址:10.0.0.1  缓存个数: 115236
服务器地址:10.0.0.2  缓存个数: 86865
服务器地址:10.0.0.3  缓存个数: 103043
服务器地址:10.0.0.4  缓存个数: 114599
服务器地址:10.0.0.5  缓存个数: 130974
服务器地址:10.0.0.6  缓存个数: 77227
服务器地址:10.0.0.7  缓存个数: 121106
服务器地址:10.0.0.8  缓存个数: 84139
服务器地址:10.0.0.9  缓存个数: 63553
服务器地址:10.0.0.10  缓存个数: 103258
标准差为： 21450.422699797782
总缓存个数：1000000
服务器台数：10
每台服务器虚拟节点数：100
每台服务器虚拟节点平均值：100000
服务器地址:10.0.0.1  缓存个数: 119498
服务器地址:10.0.0.2  缓存个数: 91413
服务器地址:10.0.0.3  缓存个数: 107542
服务器地址:10.0.0.4  缓存个数: 90998
服务器地址:10.0.0.5  缓存个数: 107033
服务器地址:10.0.0.6  缓存个数: 96690
服务器地址:10.0.0.7  缓存个数: 101308
服务器地址:10.0.0.8  缓存个数: 89079
服务器地址:10.0.0.9  缓存个数: 90149
服务器地址:10.0.0.10  缓存个数: 106290
标准差为： 10054.467962055476
总缓存个数：1000000
服务器台数：10
每台服务器虚拟节点数：200
每台服务器虚拟节点平均值：100000
服务器地址:10.0.0.1  缓存个数: 106077
服务器地址:10.0.0.2  缓存个数: 110631
服务器地址:10.0.0.3  缓存个数: 96678
服务器地址:10.0.0.4  缓存个数: 94859
服务器地址:10.0.0.5  缓存个数: 103557
服务器地址:10.0.0.6  缓存个数: 98031
服务器地址:10.0.0.7  缓存个数: 94187
服务器地址:10.0.0.8  缓存个数: 98124
服务器地址:10.0.0.9  缓存个数: 99672
服务器地址:10.0.0.10  缓存个数: 98184
标准差为： 5213.855962720872
总缓存个数：1000000
服务器台数：10
每台服务器虚拟节点数：500
每台服务器虚拟节点平均值：100000
服务器地址:10.0.0.1  缓存个数: 98448
服务器地址:10.0.0.2  缓存个数: 106866
服务器地址:10.0.0.3  缓存个数: 95085
服务器地址:10.0.0.4  缓存个数: 103181
服务器地址:10.0.0.5  缓存个数: 96207
服务器地址:10.0.0.6  缓存个数: 95953
服务器地址:10.0.0.7  缓存个数: 101765
服务器地址:10.0.0.8  缓存个数: 104403
服务器地址:10.0.0.9  缓存个数: 98083
服务器地址:10.0.0.10  缓存个数: 100009
标准差为： 3954.8606802262957
总缓存个数：1000000
服务器台数：10
每台服务器虚拟节点数：1000
每台服务器虚拟节点平均值：100000
服务器地址:10.0.0.1  缓存个数: 98062
服务器地址:10.0.0.2  缓存个数: 104081
服务器地址:10.0.0.3  缓存个数: 103674
服务器地址:10.0.0.4  缓存个数: 96718
服务器地址:10.0.0.5  缓存个数: 101704
服务器地址:10.0.0.6  缓存个数: 102176
服务器地址:10.0.0.7  缓存个数: 99261
服务器地址:10.0.0.8  缓存个数: 100983
服务器地址:10.0.0.9  缓存个数: 98101
服务器地址:10.0.0.10  缓存个数: 95240
标准差为： 2983.193758373733
Process finished with exit code 0
﻿