白话分布式系统中的一致性哈希算法

后端技术指南针后端研究所

通过本文将了解到以下内容：

分布式系统的概念和作用
分布式系统常用负责均衡策略
普通哈希取模策略优缺点
一致性哈希算法的定义和思想
一致性哈希的基本过程
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_nMin_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^32vnode_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

7.关于本公众号

开号不久作者力争持续输出原创干货，如果文章有帮助到你，希望朋友们多多转发和分享，作者会更加有动力推出更好的文章，共同进步。

继续滑动看下一个