场景

最近要在应用中做一层内存缓存来加快系统的响应。但是由于数据量较大，单台Server无法Load全量数据，所以考虑使用哈希的方式进行分片存储在Server的内存中，接入消息队列进行内存数据的淘汰。

原系统调用关系简化图如下：

系统调用图

无论应用服务一[下面简称服务一]是以何种方式(HTTP/RPC)去请求应用服务二[下面简称服务二].都会经过一层负载均衡.而现在我们要做内存缓存,实际上就是去自己实现一套负载均衡算法来实现应用一对特定的请求key,去访问特定的应用二的机器.

在这里我们忽略跨机房,权重等问题.只考虑选定目标主机的策略,即哈希函数.在分布式缓存中,考量一个哈希函数是否优秀,通常可以用三个指标来确定:

1. 平衡性(Balance)：缓存机器使用率越高越好
2. 单调性(Monotonicity)：上线/下线机器对缓存命中率的影响越小越好
3. 分散性(Spread)：一个缓存key,存在于机器中的数量越少越好.(>=1)

接下来,我们看一下常见的两种哈希函数.在这个场景下的表现.

简单哈希

假定有十台Server,我们给每台Server编号0~9.通过对请求key进行哈希,随后余10,得到对应的数,即为对应Server的编号.抽象成公式:

H = hash(key) % 10

这种方式的哈希函数,在平衡性(十台server全部用上),分散性(每个key对应一台机器)上都很优秀,但是在单调性上,却表现不佳.下面通过一个demo程序,来看一下.

public class Demo {

    public static void main(String[] args) {
        testAfterAddOneServerHitRate();
    }

    public static void testAfterAddOneServerHitRate() {
        List<String> serverList = Lists.newArrayList("192.168.1.1", 
                "192.168.1.2", "192.168.1.3",
                "192.168.1.4", "192.168.1.5", "192.168.1.6", "192.168.1.7",
                "192.168.1.8", "192.168.1.9", "192.168.1.10");
        // serverList多了一台之后.
        serverList.add("192.168.1.11");
        Map<String, Integer> serverHitCount = new HashMap<>(10);
        Map<String, Integer> serverMissCount = new HashMap<>(10);
        //假定哈希空间为0~2^31-1
        for (int i = 0; i < Integer.MAX_VALUE; i++) {
            String targetServerBefore = serverList.get(i % 10);
            String targetServerNow = serverList.get(i % 11);
            if (targetServerNow.equals(targetServerBefore)) {
                plusOneToMapKey(serverHitCount, targetServerNow);
            } else if (!"192.168.1.11".equals(targetServerNow)) {
                plusOneToMapKey(serverMissCount, targetServerNow);
            }
        }

        System.out.println(serverHitCount);
        System.out.println(serverMissCount);
    }

    private static void plusOneToMapKey(Map<String, Integer> map, String key) {
        if (map.containsKey(key)) {
            map.put(key, map.get(key) + 1);
        } else {
            map.put(key, 1);
        }
    }
}

执行结果为:

当新增一台机器后,原server0~server9上的90%的缓存已经不能路由到原来缓存这个数据的机器.所以这种取模的哈希算法,虽然简单,但是在分布式系统中,上线下线机器是在所难免的.在这种情况下缓存的大量失效是无法接收的.

一致性哈希

一致性哈希算法设计思路:

1. 将整个哈希值空间组织成一个虚拟的圆环.假定某哈希函数的值空间为0~2^31-1,Java中int类型的正值范围.整个哈希环如下.

   
   

2. 我们将服务器的列表,通过哈希函数,哈希到圆环上.

   
   

3. 我们将缓存key,也同样映射到缓存空间

   
   

命中规则

缓存key,顺时针移动,找到的第一台服务器,就是该缓存key对应缓存存在的机器.

指标分析

1. 平衡性: 由于在一个环上,所有的机器都会存储一定量的缓存数据
2. 单调性: 当有Server02下线的时候,只有Server01和Server02中间的缓存数据会迁移到Server03,而其他缓存数据并不会没任何移动.单调性良好.
3. 分散性: 每个缓存key都会存储在一台机器中.

存在问题

当我们的服务器较少的时候,可能会这种情况:

可能大量的缓存,会命中到Server02.因为Server01~02之间的空隙很大.这样实际上三台机器的负载就会很不均匀.至于有多不均匀,我们可以运行一段Demo程序来看看结果.

全部采用实节点的Demo

public class Demo {

    public static void main(String[] args) {
        pureServerList();
    }

    public static void pureServerList(){
        Hash hash = new MurmurHash();
        List<String> serverList = Lists.newArrayList("192.168.1.1", "192.168.1.2", "102.168.1.3");
        TreeMap<Integer, String> hashCircle = new TreeMap<>();
        serverList.forEach(item -> hashCircle.put(hash.hash(item) & 0x7fffffff, item));
        Map<String, Integer> counter = Maps.newHashMap();
        for (int i = 0; i < Integer.MAX_VALUE ; i++) {
            Integer serverHash = hashCircle.ceilingKey(i);
            if (serverHash == null) {
                serverHash = hashCircle.firstKey();
            }
            String server = (hashCircle.get(serverHash));
            if (counter.containsKey(server)) {
                counter.put(server, counter.get(server) + 1);
            } else {
                counter.put(server, 1);
            }
        }
        System.out.println(counter);
    }
}

代码说明:

1. 由于要找到比指定哈希值大的第一个key,则使用TreeMap(红黑树)这种结构,实现简单,并且效率良好.
2. 对哈希值进行了 & 0x7fffffff 操作,是因为哈希值可能为负.而我们的哈希空间,设定为大于等于0

程序运行结果:

由结果我们可以看到三台机器,实际上有一台能映射到的机会非常少.为了解决这个问题,我们可以通过引入虚拟节点来进行解决。

虚拟节点的引入

虚拟节点.故名思议.我们可以为我们的每个服务器模拟多个节点,使得更多的机器可以落在哈希环上.通过这种方式来让我们的key,可以落的均匀.最简单的办法.就是在ip后面添加#00,#01这种方式.如下图.

下面我们再写一段程序,看看引入虚拟节点后的key的分布情况.

public class Demo {

    public static void main(String[] args) {
        virtualServerList();
    }

    public static void virtualServerList(){
        Hash hash = new MurmurHash();
        List<String> serverList = Lists.newArrayList("192.168.1.1", "192.168.1.2", "102.168.1.3");
        List<String> vServerList = Lists.newArrayList();
        for (String str : serverList) {
            for (int i = 0; i < 1024; i++) {
                vServerList.add(((str + "#" + i)));
            }
        }
        TreeMap<Integer, String> hashCircle = new TreeMap<>();
        vServerList.forEach(item -> hashCircle.put(hash.hash(item) & 0x7fffffff, item));
        Map<String, Integer> counter = Maps.newHashMap();
        for (int i = 0; i < Integer.MAX_VALUE ; i++) {
            Integer serverHash = hashCircle.ceilingKey(i);
            if (serverHash == null) {
                serverHash = hashCircle.firstKey();
            }
            String server = (hashCircle.get(serverHash)).split("#")[0];
            if (counter.containsKey(server)) {
                counter.put(server, counter.get(server) + 1);
            } else {
                counter.put(server, 1);
            }
        }
        System.out.println(counter);
    }
}

代码说明:

1. 每个节点,分成1024个虚拟节点

程序运行结果:

通过使用虚拟节点这种方式,我们的key已经可以均匀的落在各台机器上了.

总结

目前一致性哈希基本成为了分布式系统组件的标准配置，例如Memcached的各种客户端都提供内置的一致性哈希支持,值得我们学习与使用.

参考资料

《Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web》
《一致性哈希算法及其在分布式系统中的应用》
《每天进步一点点——五分钟理解一致性哈希算法(consistent hashing)》