本文转载自微信公众号《指南针氪金入口》，作者指南针氪金入口。转载本文请联系罗盘氪金入口公众号。1.写在前面周末就像太阳，总会来，总会走。此时此刻，没错，就是星期六！还是周末啊！昨晚在B站看了几个长视频，所以一直到2点多才睡，早上10点就醒了。在这里温馨提醒各位朋友，虽然我们都是年轻人，但还是要规律作息，早睡早起。废话不多说，开始今天的话题：什么是一致性哈希算法。2.圆的字面意思。第一次听到这个词的时候，一头雾水，请问这到底是什么意思呢？一致性，我们了解hash算法，我们也了解一致性+hash算法？虽然我脑子比较空，但是我不相信所有的网友都知道这个词，于是在知乎上找了个问题还以为是我写的：好像真的有大白这样的年轻人，虽然不聪明但是充满好奇！所以我决定继续上路，Doit！3.分布式系统和一致性哈希要理解一致性哈希算法，需要了解分布式系统的一些特性。年轻人，你们一定会问：为什么？因为一致性哈希算法是为了解决分布式系统中的一些关键问题。3.1分布式系统概述随着高并发、海量数据处理等场景越来越多，服务应用实现高可用、易扩展、短延时成为必然。在这种情况下，分布式系统应运而生。互联网场景无非就是存储和计算，所以分布式系统可以简单的分为：分布式存储和分布式计算可以简单的认为是一组物理上不相邻的计算机组合起来对外提供服务。对于用户来说，到底有多少台电脑完成了请求，是完全不知道的。分布式系统中的计算机越多，计算和存储资源等越多，可以处理的并发访问量就越大，响应速度也就越快。简单的整体架构如图所示：3.2分布式与集群集群是从原来的单机发展而来的。如果单机无法支撑，则增加机器，直到满足业务负载、稳定性、时延等指标。在集群中的N台机器上部署同一个程序，就像复制了一台机器的多个副本。这种形式就是聚类。分布式就是将一个完整的系统按照业务功能拆分成独立的子系统。使用更高效的通信协议如RPC来完成这些服务之间的调度。每个子服务就像一台机器。能同时实现业务解耦和提升并发能力，确实不错。大型分布式系统可以理解为拆分后的子服务集群化，子服务之间使用类似RPC的协议串联起来，形成一个庞大的存储和计算网络。图中给出了一个简单的分布式系统结构：3.3集群中遇到的问题我们以分布式存储系统为例来说明一致性哈希算法的使用。对于集群来说，如果机器太多的话，会很难管理。难免会出现物理机故障，业务扩张收缩也很正常。机器调整必然导致数据迁移。如果存储集群有5台机器，此时如果有读写请求，需要考虑从哪台机器操作数据。一般有以下几种方法：随机访问轮询策略加权轮询策略Hash取模策略一致性哈希每种策略方法各有优缺点：随机访问可能造成服务器负载压力不均衡；轮询策略要求均匀分配，但当服务器有性能差异时，不能按性能分配；权重需要静态配置，不能自动调整；哈希取模如果机器动态变化，路由会发生变化，会迁移大量数据。在实践中，对于小型系统，散列取模策略被广泛使用。下面重点介绍哈希取模和一致性哈希的区别和联系。4、Hash取模的原理和优缺点Hash取模策略是一种常用的方法，可以保证同一个请求由同一台机器处理。这是一种并行转串行的方法，在工程中很常见。如果数据相对独立，避免了线程间的通信和同步，实现了无锁处理，所以还是很有用的。index=hash_fun(key)%N从上面的通用哈希取模公式可以看出，如果N保持不变或者可以自己主动控制，就可以实现数据负载均衡和无锁处理，但是一旦N发生变化没有被封锁的控制，那么就会有问题。让我们看一下哈希取模策略是如何处理缩放问题的。注意，为了简化问题模型，以下示例不考虑实例的主从配置。目前有N=4台机器S1-S4，通过哈希函数%N请求拼接密钥，得到指定的机器序列号，将请求转发给机器。磁盘故障请求支持S3机器因磁盘故障而停机。此时代理层收到故障告警，调整N=3。这时，问题出现了。如果用作缓存，S3机器上的所有key都会有CacheMiss。S1中原来存储的key=abc使用了新的N，调整到S4中，所以abc也有CacheMiss，因为在S4上找不到abc的数据。这种场面牵动全身。在缓存场景下，会造成缓存崩溃。如果量很大，会造成缓存雪崩。救援来了，因为S3宕机了，所以管理员加了一台机器S5，代理层再次调整N=4。这时又会出现类似stage2的数据迁移，仍然会出现CacheMiss。5.Consistenthashingalgorithm我们看一下维基百科的英文定义：在计算机科学中，consistenthashing是一种特殊的哈希算法，当哈希表调整大小时，平均只需要重新映射K/n个键，其中K是键的数量，n是槽的数量。简单翻译一下：一致性哈希是一种特殊的哈希算法。使用一致性哈希算法后，哈希表槽数（size）的变化平均只需要重新映射K/n个关键字，其中K为关键字数，n为槽数。在传统的哈希表中，添加或删除一个插槽需要重新映射几乎所有的键。由定义可知，一致性哈希是一种特殊的哈希算法，它不同于哈希取模。这种特殊的哈希算法实现了少量数据的迁移，避免了几乎所有数据的移动，从而解决了普通哈希取模动态调整带来的全量数据变化。这个有点厉害，看看是怎么实现的。5.1ConsistentHash算法的思考先不看算法的具体实现，先想一下commonhash取模问题的根源是什么？这是正确的！根本原因在于N的变化和数据归属地的问题。如果N改变了，如果N固定了呢？如果把N做大，那么每次移动的key个数就是K_all/Slot_n，也就是slots的概念，或者说是smallshards的概念，直白点就是鸡蛋放在很多很多固定数量的baskets:Key_all存储所有key的个数Slot_n，槽或分片的总数Min_Change是最小移动次数Min_change=Key_all/Slot_nMin_change也是数据的最小分片Shardsmallshards还有一个归属问题需要解决.N固定并设置为较大的值后，数据分片shard变得很小。这时候就出现了分片所有权的问题。即比如N=100w，此时有10个集群，理论上每台机器平均有10w。当然也可以根据机器的性能进行差异化的属性配置。更多的分片分配给性能好的，较少的分片分配给性能差的。分一些碎片。至此，问题基本清楚了，但是我们再来看看1997年MIT发明的一致性哈希算法的原理。5.2Karger的ConsistentHashAlgorithmConsistentHashAlgorithm是由Karger等人提出的。MIT于1997年解决了分布式缓存。设计目标是解决互联网中的热点问题。与鲤鱼非常相似。一致性哈希纠正了CARP使用的简单哈希算法带来的问题，使DHT真正应用于P2P环境。下面我们就来看看Karger一致性哈希算法的基本原理以及如何处理缩放问题。哈希环分片我们之前想到的，Karger的一致性哈希算法将N设为2^32，形成一个0~(2^32-1)的哈希环，相当于取模时间N=2^32。对数据key进行哈希计算时，落在0~(2^32-1的哈希环上。如果key的总数为Sum，则单个哈希环的最小单元上的key个数为：Unit_keys=Sum/2^32由于N很大，hash环最小单元的数据量unit_keys要小得多，服务节点和hashringshard将server节点作为key分发给hashring：con_hash(ip_key)%2^32一致性哈希算法采用顺时针的方式实现节点归属到哈希环分片，但是由于服务器节点数量远少于2^32，所以非常稀疏，就像宇宙一样你以为有天体很多，但相对于浩瀚的宇宙来说还是空洞的。一致性哈希的非平衡实体服务器节点相对于哈希环分片数据来说是小的。这个特性决定了哈希的一致性。由于服务数量少节点，服务节点分布不均，res导致机器负载不平衡。如图所示，服务器1的负载远大于其他机器：虚拟节点的引入意味着所谓的服务器节点不够用，所以服务器的磁盘、内存、CPU都占用up空间，现实生活中也是这样：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这个是由于引入了虚拟节点，所以虚拟节点的分片实际上一定属于真实的服务节点，所以实际中涉及到虚拟节点和物理节点的映射.添加新的服务器节点当管理员添加服务器4时，分布在服务器3和服务器1之间的哈希环单元上的部分数据会迁移到服务器4，当然由于虚拟节点的引入，这部分数据迁移会不要大。服务器4和服务器1之间并不是所有的数据都必须顺时针迁移，所以在添加机器的时候，只能迁移少量的数据。删除服务器节点当服务器节点2关闭时，需要将其删除以进行故障转移。原S2及其虚拟节点上的数据会顺时针迁移到下一个物理节点或虚拟节点。6.Redis的一致性哈希实现Redis集群有固定的16384个slot，slot是虚拟的，分配给各个master，当key映射到负责slot的master时，相应的master会为key提供服务。每个Master节点维护一个16384/8字节的比特序列bitmap，即Master利用bitmap的原理来表示slot的下标，Master节点用bit来标识自己拥有哪些slot，例如对于slot编号为1的Slot，Master只需要判断序列的第二位是否为1。这样就建立了分片和服务节点的归属关系，所以整个过程也是基于两个原则，符合上面一致性哈希的思想。hash_slot_index=CRC16(key)mod163847。思考与总结通过前面的比较和理解，我们有必要思考一下一致性哈希算法的本质。7.1一致性哈希算法的两个关键点一致性哈希算法是一种特殊的哈希算法，它的特殊之处在于普通哈希的模N是固定的，从而保证相同的key必须在相同的位置，从而避免了影响哈希的问题整体，这是理解一致性哈希的关键。consistenthashing算法的另一个关键点是，当N固定并设置为一个大的值后，实际上是在进行数据分片，而分发的小片??必须与实际的机器相关，即哪台机器负责哪台机器小件件。但是一致性哈希算法并没有完全解决服务器数据动态调整带来的数据迁移问题，而是将原来普通的哈希取模带来的几乎所有迁移都减少到一小部分数据移动，这是一个很大的挑战优化。在我看来，一致性哈希算法有两个关键点：大量固定数量的小数据块分片和小分片服务器归属问题7.2该算法的其他工程版本如Redis没有使用2^的哈希环32，但是使用16384个固定slot来实现，然后每个serverMaster使用bitmap来确定自己的管辖slot。管理员可以根据机器配置和负载情况动态调整槽位，基本解决了前几种负载均衡策略的不足。所以如果让你设计一个一致性哈希算法，你只需要掌握两个原则即可。它不仅仅是MITKarger的一个哈希算法，它只是提供了一个思路和方向。7.3一致性哈希算法的命名回到最初的问题：为什么要用“一致性哈希算法”这个名字。英文原文是Consistenthashing，其中Consistent译为“一致的，连贯的”。我认为coherent更合适，认为这种特殊的哈希算法实现了普通哈希模算法的平滑和连贯版本，称为coherent永久哈希算法似乎更合适。个人愚见，水平有限，看看就好。8.总结指南针的资深读者，应该看到这是一篇老文章了，确实，真的很抱歉。【小编推荐】开源Go项目推荐：汉字转拼音甚至可以有声调。GoGC是如何标记内存的？颜色是什么意思？图形化三色标注用Delve代替Println调试Go程序云原生时代，Java还是Go？蚂蚁王一：Go+可以有效补足Python的短板
