通过本文将了解到以下内容:
分布式系统的概念和作用
分布式系统常用负责均衡策略
普通哈希取模策略优缺点
一致性哈希算法的定义和思想
一致性哈希的基本过程
Redis 集群中一致性哈希的实现
1. 分布式系统的基本概念
分布式系统与高并发高可用
当今 高并发和海量数据处理等场景越来越多 , 实现服务应用的 高可用, 易扩展, 短延时 等成为必然. 在此情况下 分布式系统应运而生, 互联网的场景无外乎存储和计算 , 因此分布式系统可以简单地分为:
分布式存储
分布式计算
所谓分布式系统就是一批计算机组合起来共同对外提供服务, 对于用户来说具体有多少规模的计算机完成了这次请求, 完全是无感知的.
分布式系统中的计算机越多, 意味着计算和存储资源等也就越多 , 能够处理的 并发访问量也就越大 , 响应速度也越快 .
如图为简单整体架构图:
大前端主要实现了服务应用对应的所有流量的接入, 比如 aaa.com 域名下可能有 N 个子服务, 这一层涉及很多网络流量的处理, 也很有挑战, 像百度的 BFE(百度统一前端)接入了百度的大部分流量, 每日转发 1 万亿次, 峰值 QPS1000w.
中间层完成了各个服务的调度和分发, 粒度相比大前端接入层更细致一些, 这一层实现了用户的无感知体验, 可以简单理解为反向代理层.
业务层完成了数据存储, 数据计算, 数据缓存等, 各个业务环节高度解耦, 并且基于集群化来实现.
集群和分布式的区别与联系
集群是从原来的 单机演变来的 , 单台机器扛不住就加机器, 直到服务负载, 稳定性, 延时等指标都满足, 集群中的 N 台机器上部署一样的程序, 就像一台机器被复制多份一样, 这种形式就是集群化 .
分布式是将一个完整的系统, 按照业务功能拆分成一个个独立的子系统 , 这些服务之间使用更高效的通信协议比如 RPC 来完成调度, 各个子服务就像在一台机器上一样, 实现了业务解耦, 同时提高了并发能力确实不赖.
一个大的分布式系统可以理解拆分之后的子服务使用集群化, 一个个子服务之间使用类似于 RPC 的协议串联, 组成一个庞大的存储和计算网络.
如图为 简单的分布式系统结构 :
注: 图片来自网络 详见参考 1
2. 分布式系统的分发
常用负载均衡策略
以分布式系统中的存储和缓存为例, 如果存储集群中有 5 台机器, 如果这时有请求, 就需要考虑从哪台机器获取数据, 一般有几种方法:
随机访问
轮询策略
权重轮询策略
Hash 取模策略
一致性哈希策略
各种方法都有各自的优缺点:
随机访问可能造成服务器负载压力不均衡;
轮询策略请求均匀分配, 但当服务器有性能差异, 无法按性能分发;
权值需要静态配置, 无法自动调节;
哈希取模如果机器动态变化会导致路由产生变化, 数据产生大量迁移.
Hash 取模策略
Hash 取模策略是其中常用的一种做法 , 它可以保证相同请求相同机器处理, 这是一种 并行转串行 的方法, 工程中非常常见.
笔者在刚毕业做流量分析时就是按照报文的五元组信息做 key 来决定服务内的业务线程 id, 这样确保相同的 TCP/HTTP 连接被相同的线程处理, 避免了线程间的通信和同步, 实现了无锁化处理 , 所以还是很有用的.
index = hash_fun(key) % N
从上面的普通 hash 取模公式可以看到, 如果 N 不变或者可以自己主动控制, 就可以实现数据的负载均衡和无锁化处理, 但是一旦 N 的变化不被控制, 那么就会出现问题.
Hash 取模的弊端
阶段一:
目前有 N=4 台机器 S1-S4, 请求拼接 key 通过 hash 函数 %N, 获取指定的机器序号, 并将请求转发至该机器 .
阶段二:
S3 机器因为磁盘故障而宕机 , 这时代理层获得故障报警调整 N=3, 这时就出现了问题, 如果作为缓存使用, S3 机器上的所有 key 都将出现 CacheMiss , 原来存放在 S1 的 key=abc 使用新的 N, 被调整到 S4 , 这样 abc 也出现 CacheMiss , 因为在 S4 上找不到 abc 的数据, 这种场景就是 牵一发而动全身, 在缓存场景中会造成缓存击穿, 如果量很大会造成缓存雪崩 .
阶段三:
由于 S3 宕机了, 因此管理员 增加了一台机器 S5 , 代理层再次调整 N=4, 此时又将 出现类似于阶段二的数据迁移 , 仍然会出现 CacheMiss 的情况.
3. 一致性哈希算法
一致性哈希的定义
In computer science, consistent hashing is a special kind of hashing such that when a hash table is resized, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots.
维基百科 - Consistent hashing
翻译一下:
一致哈希 是一种特殊的哈希算法.
在使用一致哈希算法后, 哈希表槽位数 (大小) 的改变平均只需要对 K/n 个关键字重新映射, 其中 K 是关键字的数量, n 是槽位数量.
在传统的哈希表中, 添加或删除一个槽位的几乎需要对所有关键字进行重新映射.
维基百科 - 一致性哈希
从定义可以知道, 一致性哈希是一种特殊的哈希算法 , 区别于哈希取模, 这种 特殊的哈希算法实现了少量数据的迁移, 避免了几乎全部数据的移动 , 这样就解决了普通 hash 取模的动态调整带来的全量数据变动.
解决思路是什么
先不看 算法的具体实现, 先想想普通 hash 取模的问题根源是什么?
N 的变动
没错! 根源就在于 N 的变动, 那么如果 N 被固定住呢 ? 并且让 N 很大 , 那么每次被移动的 key 数就是 K_all/Slot_n, 也就是有槽位的概念, 或者说是小分片的概念, 直白一点就是鸡蛋放到了很多很多的固定数量的篮子里 :
Key_all 存储的全部 key 的数量
Slot_n 总的槽位或者分片数
Min_Change 为最小移动数量
Min_change = Key_all/Slot_n
Min_change 也是数据的最小分片 Shard
小分片的归属
这里还有一个问题要解决, 将 N 固定且设置很大之后, 数据分片 shard 变得非常小了, 这时就有 shard 的所属问题 , 也就是比如 N=100w, 此时集群有 10 台, 那么每台机器上理论上平均有 10w, 当然可以根据机器的性能来做差异化的归属配置, 性能强的多分一些 shard, 性能差的少分一些 shard.
问题到这里, 基本上已经守得云开见月明了, 不过还是来看看 1997 年麻省理工发明的一致性哈希算法原理吧.
Karger 的一致性哈希算法
一致性哈希算法在 1997 年由麻省理工学院的 Karger 等人在解决分布式 Cache 中提出的, 设计目标是为了解决因特网中的热点 (Hot spot) 问题, 初衷和 CARP 十分类似. 一致性哈希修正了 CARP 使用的简单哈希算法带来的问题, 使得 DHT 可以在 P2P 环境中真正得到应用.
一致性哈希算法
数据在哈希环上的分片
正如我们前面的思考, Karger 的一致性哈希算法将 N 设置为 2^32, 形成了一个 0~(2^32-1)的哈希环, 也就是相当于普通 Hash 取模时 N=2^32 .
注: 图片来自网络 详见参考 2
在将数据 key 进行 hash 计算时就落在了 0~(2^32-1 的哈希环上, 如果总的 key 数量为 Sum, 那么单个哈希环的最小单位上的 key 数就是:
Unit_keys = Sum/2^32
由于 N 非常大所以哈希环最小单位的数据量 unit_keys 小了很多.
服务器节点和哈希环分片的分配
注: 图片来自网络 详见参考 2
将服务器结点也作为一种 key 分发到哈希环上:
con_hash(ip_key)%2^32
一致性哈希算法使用顺时针方法实现结点对哈希环 shard 的归属 , 但是 由于服务器结点的数量相比 2^32 会少非常多, 因此很稀疏, 就像宇宙空间中的天体, 你以为天体很多, 但是相比浩渺的宇宙还是空空如也.
一致性哈希的不均衡
实体服务器结点少量相比哈希环分片数据很少, 这种特性决定了一致性哈希的数据倾斜, 由于数量少导致服务节点分布不均, 造成机器负载失衡, 如图所示, 服务器 1 的负载远大于其他机器:
注: 图片来自网络 详见参考 2
虚拟节点的引入:
这个说白了服务器结点不够, 就让服务器的磁盘, 内存, CPU 全去占位置, 现实生活中也这样: 12306 出来之前, 火车站连夜排队买票, 这时什么书包, 水杯, 眼镜都代表了张三, 李四, 王二麻子 .
同样的道理, 将服务器结点根据某种规则来虚拟出更多结点, 但是这些虚拟节点就相当于服务器的分身 .
比如采用如下规则在 ip 后缀增加 #index, 来实现虚拟节点的定位:
- vnode_A_index = con_hash(ip_key_#A)%2^32
- vnode_B_index = con_hash(ip_key_#B)%2^32
- ...
- vnode_k_index = con_hash(ip_key_#k)%2^32
注: 图片来自网络 详见参考 2
这是由于引入了虚拟节点, 因此虚拟节点的分片都要实际归属到真实的服务节点上, 因此在实际中涉及到虚拟节点和实体结点的映射问题.
新增服务器结点
注: 图片来自网络 详见参考 2
当管理员新增了服务器 4 时, 原来在服务器 3 和服务器 1 之间分布的哈希环单元上的数据, 将有一部分迁移到服务器 4, 当然由于虚拟节点的引入, 这部分数据迁移不会很大, 并不是服务器 4 和服务器 1 之间的数据都要顺时针迁移, 因此这样就实现了增加机器时, 只移动少量数据即可.
删除服务器结点
注: 图片来自网络 详见参考 2
当服务器结点 2 发生宕机, 此时需要被摘除进行故障转移, 原来 S2 以及其虚拟节点上的数据都将进行顺时针迁移到下一个实体结点或者虚拟结点.
4.Redis 的一致性哈希实现
Redis cluster 拥有固定的 16384 个 slot ,slot 是虚拟的且被分布到各个 master 中, 当 key 映射到某个 master 负责 slot 时, 就由对应的 master 为 key 提供服务.
每个 Master 节点都维护着一个位序列 bitmap 为 16384/8 字节 , 也就是 Master 使用 bitmap 的原理来表征 slot 的下标, Master 节点通过 bit 来标识哪些槽自己是否拥有, 比如对于编号为 1 的槽, Master 只要判断序列的第二位是不是为 1 即可.
这样就建立了分片和服务结点的所属关系, 所以整个过程也是两个原则, 符合上文的一致性哈希的思想.
hash_slot_index =CRC16(key) mod 16384
注: 图片来自网络 详见参考 4
5. 总结和思考
一致性哈希算法的两个关键点
一致性哈希算法是一种特殊的哈希算法 , 特殊之处在于 将普通哈希取模的 N 进行固定, 从而确保了相同的 key 必然是相同的位置, 从而避免了牵一发而动全身的问题, 这是理解一致性哈希的关键.
一致性哈希算法的另外一个要点就是将 N 固定且设置很大之后, 实际上就是进行数据分片 Sharding, 分布的小片就要和实际的机器产生关联关系, 也就是哪台机器负责哪些小分片 .
但是一致性哈希算法 并不是从彻底解决了由于动态调整服务器数据产生的数据迁移问题, 而是将原来普通哈希取模造成的几乎全部迁移, 降低为小部分数据的移动 , 是 一种非常大的优化 , 在工程上基本上可以满足要求.
一致性哈希算法的关键有两点:
大量固定数量的小数据块的分片
小分片的服务器归属问题
一致性哈希算法的其他工程版本
像 Redis 并没有使用 2^32 这种哈希环, 而是采用了 16384 个固定 slot 来实现的 , 然后每个 服务器 Master 使用 bitmap 来确定自己的管辖 slot , 管理员可以根据机器的配置和负载情况进行 slot 的动态调整 , 基本上解决了最开始的几种负载均衡策略的不足.
所以假如让 你设计一个一致性哈希算法, 只要把握两个原则即可, 并不是只有麻省理工 Karger 的一种哈希算法, 它只是提供了一种思想和方向 .
天马行空
一直有个疑问问 什么要用 "一致性哈希算法" 这个名字 , 让我总 和分布式系统中的一致性协议 (eg 最终一致性) 混淆.
英文原文是 Consistent hashing, 其中 Consistent 译为 "一致的, 连贯的" , 我觉得连贯的更贴切一些, 以为这种特殊的哈希算法实现了普通哈希取模算法的 平滑连贯版本 , 称为连贯性哈希算法, 好像更合适, 一点愚见, 水平有限, 看看就完事了.
5. 参考资料
- https://waylau.com/talk-about-distributed-system/
- https://juejin.im/post/5ce4a666e51d4558936a9fdd
- https://www.oschina.net/news/111425/bfe-opensouced
- https://www.jianshu.com/p/b398250d661a
来源: http://www.tuicool.com/articles/aURr6jR