"一致性 hash 的设计初衷是解决分布式缓存问题, 它不仅能起到 hash 作用, 还可以在服务器宕机时, 尽量少地迁移数据. 因此被广泛用于状态服务的路由功能"
01 分布式系统的路由算法
假设有一个消息推送系统, 其简易架构如下
设备接入层不仅要接收设备的登录, 下线等状态命令, 还要把开发者的消息推送给设备. 这个时候设备接入层就需要维护设备的状态信息(当然可以专门拆一个状态服务去维护这些信息, 要求这部分必须少有代码更新, 具体原因自己去想哦 =_=). 这个时候设备接入层的每台 server 都保留一批设备的状态信息 cache, 设备应该连接哪台 server 去获取数据, 同时中间层的消息又该发往哪个 server 去推送呢? 这就用到了一致性 hash 算法.
02 什么是一致性 hash 算法
一致性 hash 由对象, 资源, 算法和机器组成. 它要做的是: 对象通过算法判断连哪台机器. 在如上系统中: 设备 id(userID)为对象; 其对应的状态数据 (cache) 为资源; 服务器为机器.
一致性 hash
在一致性 hash 算法中, 这些资源围成了一个闭环, 每台机器又保存着一个资源段, 每个资源段对应一批对象 / 设备; 这样如果某台机器挂了, 那它对应的资源转移到离它较近的机器 x, 这台 dead server 对应的设备连接到机器 x 就行.
现在假设这四个资源段对应的设备, 活跃情况相差较大. 比如说资源段 1,2 对应的设备特别活跃, 而资源段 3 和 4 几乎没活动. 这样机器 1-2 需要保存大量的状态数据, 而 3-4 则有大量的空置, 显然是不合理的. 改进版的一致性 hash 算法是这样操作的: 它不再是每台机器去保存一个连续的资源段, 而是让每台机器都保存多个区域的部分资源段. 如机器 1 保存每个资源段的 1/4, 机器 2 保存每个资源段的 1/4, 机器 3,4 同样如此. 这样即使个别号段有热点, 也会均摊到不同的机器.
一致性 hash 改进版
03 一致性 hash 在系统中的应用
如上介绍了一致性 hash 的概念和改进, 在系统实践中, 我们用户量非常大, 往往不只一个集群. 我们是如此使用一致性 hash:
首先根据不同号段选择对应的集群, 这部分是可配置的
确定集群后, 根据一致性 hash 把设备匹配到 server 的某个 instance 上(每台 server 部署多个设备接入层实例(1. 每个 instance 保存的状态信息更分散; 2. 服务的 gc 问题会有缓解)
建立机器虚拟节点: 把 user 逆序(打乱之前连续 userId), 组成新的资源段; 相当于建立了 server 虚拟节点
记录每台 server 锁服务的设备数, 如果机器 A 挂了, 挑选服务设备数最少的机器去承接 kicked-device
04 不是所有情况都适合一致性 hash
以上介绍了一致性 Hash 的原理和实践, 但不是所有的服务都适合用一致性 hash 来路由. 比如 01 节中的消息推送系统, 中间层是无状态的, 开发者接入层请求 cluter-A 的哪台机器都行, 它只要做完基本校验后, 把消息异步发给 MQ 即可, 无需等待结果直接返回; 而设备接入层是有状态的, 且对较高时延无法忍受, 更适合一致性 Hash 选择好 server-instance, 然后通过 TCP/UDP 来通信.
在此我向大家推荐一个架构学习交流圈. 点击加入交流圈 里面资深架构师会分享一些整理好的录制视频录像和 BATJ 面试题: 有 Spring,MyBatis,Netty 源码分析, 高并发, 高性能, 分布式, 微服务架构的原理, JVM 性能优化, 分布式架构等这些成为架构师必备的知识体系. 还能领取免费的学习资源, 目前受益良多.
注:
来源: http://www.jianshu.com/p/e2c8e927e799