分布式应用与一致性哈希

场景

最近要在应用中做一层内存缓存来加快系统的响应。但是由于数据量较大,单台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);
        }
    }
}

执行结果为:

server hit miss rate
192.168.1.1 19522579 175703208 0.1
192.168.1.2 19522579 175703207 0.1
192.168.1.3 19522579 175703207 0.1
192.168.1.4 19522579 175703207 0.1
192.168.1.5 19522579 175703207 0.1
192.168.1.6 19522579 175703207 0.1
192.168.1.7 19522579 175703207 0.1
192.168.1.8 19522579 175703207 0.1
192.168.1.9 19522579 175703207 0.1
192.168.1.10 19522579 175703207 0.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

程序运行结果:

server count
192.168.1.1 26553108
102.168.1.3 1057185279
192.168.1.2 1063745260

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

虚拟节点的引入

虚拟节点.故名思议.我们可以为我们的每个服务器模拟多个节点,使得更多的机器可以落在哈希环上.通过这种方式来让我们的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个虚拟节点

程序运行结果:

server count
192.168.1.1 735336735
102.168.1.3 708566329
192.168.1.2 703580583

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

总结

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

参考资料

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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,324评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,303评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,192评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,555评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,569评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,566评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,927评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,583评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,827评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,590评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,669评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,365评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,941评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,928评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,159评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,880评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,399评论 2 342

推荐阅读更多精彩内容