共计 5774 个字符，预计需要花费 15 分钟才能阅读完成。
前言
当架构师大刘看到实习生小李提交的 记账流水乱序 的问题的时候，他晓得没错了：这一次，大刘又要用一致性哈希这个老伙计来解决这个问题了。
嗯，一致性哈希，分布式架构师必备良药，让咱们一起来尝尝它。
一、满眼都是本人二十年前的样子，让咱们从哈希开始
在 N 年前，互联网的分布式架构方兴未艾。大刘所在的公司因为业务须要，引入了一套由 IBM 团队设计的业务架构。
这套架构采纳了分布式的思维，通过 RabbitMQ 的消息中间件来通信。这套架构，在过后的年代里，算是思维超前，技术少见的黑科技架构了。
然而，因为当年分布式技术落地并不宽泛，有很多尚不成熟的中央。所以，这套架构在经年日久的应用中，一些问题逐步突出。其中，最典型的问题有两个：
- RabbitMQ 是个单点，它一坏掉，整个零碎就会全副瘫痪。
- 收、发消息的业务零碎也是单点。任何一点呈现问题，对应队列的音讯要么无从生产，要么海量音讯沉积。
无论哪种问题，最终是整套分布式系统都无奈应用，后续解决十分麻烦。
对于 RabbitMQ 的单点问题，因为过后 RabbitMQ 的集群性能十分弱，一般模式有 queue 自身的单点问题，所以，最终应用了 Keepalived 配合了两台无关系的 RabbitMQ 搞出了高可用。
而对于业务零碎单点问题，从一开始着手解决的时候就呈现了挫折。一般来说，咱们要解决单点问题，办法就是堆机器，堆利用。收发是单点，咱们间接多部署几个利用就能够了。如果仅仅从技术上看，无非就是多个收发音讯的利用大家一起竞争往 MQ 中放音讯拿音讯而已。
然而，恰好就是在把收发音讯的利用集群化后，零碎呈现了问题。
自身这套零碎架构会被利用到公司的多类业务上，有些业务对音讯的程序有着刻薄的要求。
比方，公司外部的 IM 利用，不论是点对点的聊天还是群聊音讯，都须要对话音讯严格有序。而当咱们把生产音讯和生产音讯的利用集群化后，问题呈现了：
聊天记录呈现了乱序
A 和 B 对话，会呈现某些音讯没有严格依照 A 收回的先后顺序被 B 接管，于是整个聊天程序乱成了一锅粥。
通过排查，发现问题的本源就在于利用集群上。因为没有对利用集群收发音讯做非凡的解决，当 A 收回一条聊天信息给 B 时，发送到 RabbitMQ 中的信息会被在 B 处的生产端所争抢。如果 A 在短时间内收回了几条信息，那么就可能会被集群中的不同利用抢走。
这时候，乱序的问题就呈现了。尽管利用业务逻辑是雷同的，然而这些集群中的利用仍然可能在解决信息速度上呈现差别，最终导致用户看到的聊天信息错乱。
问题找到了，解决办法是什么？
下面咱们说过了，音讯程序错乱是因为集群中不同利用抢音讯而后处理速度不一样导致的。如果咱们能保障 A 和 B 会话，从开始之后到会话完结之前，永远只会被 B 所在的生产音讯集群利用中的同一个利用生产，那么咱们就能保障音讯有序。这样一来，咱们就能够在生产音讯的那个利用中，对抢到的音讯进行排队，而后顺次解决。
那么，这种保障怎么实现呢？
首先，咱们在 RabbitMQ 中会建设有雷同前缀的队列，前面跟着队列编号。而后，集群中的不同利用会别离监听这两个有着不同编号的队列。当在 A 发送信息时，咱们会对信息做一次简略的哈希:
m = hash(id) mod n
这里，id 是用户的标识。n 是集群中 B 所在业务零碎部署的数量。最终的 m 是咱们须要发送到的目标队列编号。
假如，hash(id) 的后果为 2000，n 为 2，通过计算 m = 0。此时，A 就会把他和 B 的对话信息都发送到 chat00 的队列里。B 收到音讯后，就会顺次显示给终端用户。这样，聊天乱序的问题就解决了。
那么，事件到此就完结了吗？这个解决方案是完满的吗？
二、看来，咱们须要减少利用数量了
随着公司的倒退，公司的人数也急剧回升，公司外部的 IM 应用人数也跟着多了起来，新问题又随之呈现了。
最次要的问题是，人们收到聊天信息的速度变慢了。起因也很简略，收取聊天信息的集群机器不够用了。解决办法能够简略间接点，再加台机器就好了。
不过，因为收音讯的集群中新退出了一台机器，这时候，咱们还须要额定多做一些事件：
1. 咱们须要为新退出的这台机器上的利用额定再多减少一个队列 chat02。
2. 咱们还须要批改下咱们的调配音讯的规定，把原来的 hash(id) mod 2 批改为 hash(id) mod 3。
3. 重新启动发送音讯的我的项目，以便批改的规定失效。
4. 把收音讯的利用部署到新机器上。
到这时，所有还都在可控范畴。开发人员只须要在须要的时候，新减少个队列，而后把咱们的调配规定小小的批改下即可。
然而，他们不晓得的是，暴风雨就要来了。
三、新的问题来了，兴许这就是人生吧
因为公司外部很多人在应用这个 IM 工具。有些时候，为了不便，公司的客户还有一些合作方也用起了这个 IM。这让事件变得复杂了起来。起初，开发人员还是像平常一样，每当人们埋怨说收音讯过慢的时候，他们就会加一台机器。
最蹩脚的是，公司的客户也会埋怨，他们发现 IM 有时候彻底不可用。这可不是小事件。公司内部人员的问题还能够外部沟通解决。然而公司客户的问题，粗心不得，因为这关系到公司产品的声誉。
那么，这到底是怎么一回事呢？
原来，根本原因还在于每次批改完配置规定后的重启服务。每次批改完配置规定，就须要布局好一个失当的停机工夫，去从新对我的项目做个上线。
然而，这种办法在公司的客户也应用这个 IM 后就行不通了。因为公司的客户有不少是在国外的。也就是说，不论白天还是深夜，很可能总是有人在应用这个 IM。
这就迫使开发人员们，在减少机器时，还须要去和多方协调沟通出一个上线工夫，而后发布公告，再去上线。这种重复沟通，再上线，再重复沟通，再上线间接把开发人员们折腾了个半死。
往往沟通完，上线工夫间接被放到了半个月当前。而在这半个月里，开发人员还要接受有数外部 IM 应用人的口水。费神极力的沟通，声嘶力竭的解释，缺眠少觉的上线，这所有的所有推动着开发人员们必须对眼前这套技术计划作出扭转了。
四、思路转起来，队列环起来
新的技术计划的需要实质就是：
无论是调配音讯规定变动还是集群机器增加都不能停机停服务
对于这种状况，一个很好的解决方案就是如果咱们对我的项目配置文件进行动静的定时检测，当发现变动时，刷新配置规定即可。
所有看上去很美妙，采纳了动静的定时检测后，每当咱们须要新增集群中的机器时，咱们只须要如下三个步骤了:
- 减少一个队列
- 批改调配音讯的规定
- 部署新的机器
客户毫无感知，开发人员们也不须要和用户们协调沟通出专门的上线安顿。可是，这个计划也存在一些问题：
- 随着咱们的零碎部署越来越多，咱们须要手工批改规定的零碎也越来越多。
- 如果生产机器宕机了，咱们须要删除队列，同时还须要去删除批改调配音讯的规定，等到机器复原了，咱们还要再把调配音讯的规定改回去。
这个调配音讯的规定真厌恶啊，每次有变动，就要去关怀这个调配音讯的规定。有没有什么方法能把这个调配变得更自动化一些呢？
如果咱们假如在 MQ 中有 100 个收发聊天信息的队列（100：这是对咱们的 IM 不可能达到的一个数字），咱们只须要在配置规定中配置成：
m = hash(id) mod 100
而后，咱们的发送音讯的利用启动后，去动静的探测出实在的所有收发聊天信息的队列信息。
当咱们通过哈希算出的编号发现没有实在对应的队列存在时，就依据肯定的规定，去找到一个实在存在的队列，这个队列，就是咱们要发消息的队列。
如果咱们做到这样，那么当前，每次队列有变动，无论增多还是缩小，咱们都不须要再去思考调配规定的事件了，只须要移除有问题的队列或者减少有对应消费者的队列即可。
这个思维，就是一致性哈希的思维。
具体怎么做呢？
第一步，咱们假如有个 100 个收发聊天信息的队列，并且这些队列处于一个环上。
第二步，咱们获取到实在的收发聊天信息的队列数量，假如有 5 个。
第三步，咱们把实在的队列映射到咱们第一步假如的环中。
第四步，咱们通过调配规定 hash(id) mod 100 计算出对应的队列编号。
如果 hash(id) 的后果为 2000，那么算出的队列编号 m = 0。这时候，咱们一查，发现对应编号 0 的 chat00 队列的确存在，那么就间接发送音讯到 chat00 中。
如果咱们的 hash(id) 的后果为 1999，那么算出的队列编号 m = 99。此时，咱们去查队列映射关系，发现 99 编号并没有对应的实在队列。这时候怎么办？很简略，咱们顺时针持续往下找，找到谁了呢？0 对应的 chat00 队列，这是实在存在的，这时候，咱们就将音讯发送到 chat00 队列中。
下面四步就是一个根本的一致性哈希算法了。
那么，这套一致性哈希算法满足咱们不想总是更新音讯调配规定的需要吗？让咱们验证一下：
1.假如咱们须要在生产信息端集群减少一台机器
咱们如果要减少一台机器，那么同时咱们也须要在 MQ 中减少一个队列。这时候，咱们的调配规定是 hash(id) mod 100，减少了队列后，实在的队列数假如为 6。此时，如果 hash(id) mod 100 的后果小于 6，那么调配的规定和没有减少机器的时候规定一样，以前调配到哪个队列，当初还是调配到哪个队列。然而对于后果等于 6 的状况，则产生了变动。信息会被主动调配给 chat05。当调配给 chat05 后，新的消费者就会主动开始进入失常工作了，咱们不须要做任何人工干预，也不须要思考调配规定的变动。
减少机器以前：
减少机器之后：
2.假如生产信息端集群一台机器宕机了
模仿宕机，此时咱们会去缩小一个队列。缩小后的实在队列数量为 5，则正好和减少队列相同，m = 5 时，那么行为不会有任何变动，以前分到哪个队列，还是分到哪个队列。如果 m = 6，因为曾经不存在实在的队列了，就会做顺时针查找，后果找到 chat00，以前会分到 chat05 的就会被分到 chat00。而此时，chat00 因为正好有消费者，所以，零碎的用户是毫无感知的，咱们也分心修复咱们机器即可。当机器复原后，就会和新增机器一样，计算结果为 6 的信息会被重新分配回 chat05。
目前，咱们能够看到，当咱们引入一致性哈希后，咱们不论新增机器还是集群机器宕机，我只须要跟随着机器的状态，做一个操作即可：减少或者缩小 MQ 中的队列。所有简单化了。
那么，这个计划是否仍然还有问题呢？
五、失衡的圆环，压垮骆驼的可能只是一根稻草
假如咱们目前有 5 个队列存在，咱们的调配规定是 m = hash(id) mod 100。那么，此时，问题就进去了。
如果 m 的值大于 5，因为没有对应的实在队列存在，零碎就会顺时针顺着咱们结构进去的哈希环找，最终会找到 chat00 这个队列上。
而后，你会发现，只有是 m 值大于 5 的 id 对应用户发的信息，最终都会落入到 chat00 队列中。
在极其状况下，如果大量的信息涌入到 chat00 队列里，因为对应 chat00 的消费者解决不过去，很可能会导致这个消费者的解体。
而后，去除队列后，依据规定，又会有大量的信息涌入到 chat00 后续的队列 chat01 里，这些信息又会导致 chat01 对应利用的解体，最终引发整个集群的解体，这就是雪崩效应。
咱们须要一种更奇妙的方法来解决这个问题。
六、从实变虚，兴许咱们应该更敢想一些
通过下面的阐述，咱们发现，咱们在调配队列时，之所以失衡，是因为咱们的队列在圆环上的调配失衡。
咱们所有的实在队列都是依照顺时针顺次排布在圆环上的。在下面的场景里，咱们只有 5 个队列。此时，咱们假设会有 100 个队列。那么，m = hash(id) mod 100 这个公式里：
m 大于 5 的概率为 95%
因为咱们的 5 个队列是依照编号程序顺次排列的。那就阐明所有 m 大于 5 的信息就都会映射到一个不存在的队列上，最终，依据规定，顺时针滑到了 0 对应的 chat00 队列中。
如果，咱们能够让实在存在的队列均匀分布到环上，那么，这种重大失衡的景象还会再呈现吗？
从下面的图咱们能够看出，如果咱们能让实在的队列平均的在圆环上散布，那么这种重大失衡的景象就会失去极大的缓解。
那么如何让这些队列能平均的散布在这个圆环中呢？还记得咱们在苦恼调配信息规定的一直批改时，咱们大胆的假如了一个咱们的 IM 零碎永远也不可能达到的队列数字吗？
咱们假如了 MQ 中有 100 个队列，而后，咱们去判断这些队列是否实在存在。不存在，咱们就顺时针滑动始终找到实在存在的队列为止。
如果咱们再大胆一点，偷偷的把咱们的假如进一步优化，把一些原本须要判断为不存在的队列去映射到真正曾经存在的队列上，那么咱们是不是就等于把这些真正存在的队列均匀分布到这个圆环上了？
像上图这种，把曾经存在的大量队列去映射到多个假如队列的办法，就是一致性哈希的虚构节点方法。
而对于怎么让大量的队列映射到多个假如队列，是有多种实现算法存在的。
比方，咱们能够把实在存在的队列名加上一些编号去别离哈希一下, 像 hash(chat00) mod 100，hash(chat00#1) mod 100，而后依据失去的余数，去把 chat00 这个实在队列和对应余数的环中的地位映射上。
如果 hash(chat00) mod 100 = 31，那么 31 号的地位就对应于 chat00，当前所有 m = hash(id) mod 100 中 m = 31 的所对应的音讯就会间接被发送到 chat00 队列。
而 hash(00#1) mod 100 = 56，则 m = 56 对应的音讯同样也会间接发送到 chat00 队列。
这样，咱们就间接的把 MQ 中的实在存在的队列做了平均化散布，从而大大减少了信息失衡的景象。
七、了解算法的思维胜于算法的实现
好了，通过理论场景来对于一致性哈希的思维就临时分析到这里了。
一致性哈希作为一种十分经典的算法思维，被宽泛的用于各大分布式我的项目当中，用于解决各种分片问题，工作散发问题。
然而，在这里，我要纠正一个观点：很多人都在网上说 redis 应用了一致性哈希。这是错的，redis 只是应用了一致性哈希的思维。比方一致性哈希中的环散布，再比方虚构节点对应实在节点的思维。
然而 redis 并没有应用任何哈希算法去计算散布，如果有趣味的读者，能够认真去看下无关内容。从 redis 的例子上来说，咱们能够看到，只有了解了算法的思维，咱们能力更容易更灵便地就地取材的合成、修改、改良算法，让算法能更切合实际的融入到咱们的我的项目之中。
写在最初
欢送大家关注我的公众号【惊涛骇浪如码】，海量 Java 相干文章，学习材料都会在外面更新，整顿的材料也会放在外面。
感觉写的还不错的就点个赞，加个关注呗！点关注，不迷路，继续更新！！！
