Cluster集群可以基于一致性哈希算法么？
作者：程序员马丁
热门项目实战社群，收获国内众多知名公司面试青睐，近千名同学面试成功！助力你在校招或社招上拿个offer。
回答话术
首先，由于数据要分片存储在不同的服务器节点上，因此当用户发起请求时，我们会需要一个哈希算法保证对某个 Key 的请求总是路由到指定的服务器节点。传统的哈希算法基于长度（也就是节点数量）进行取模，因此当扩容和缩容时会需要对大量的数据进行迁移。而一致性哈希算法则用于解决这个问题。
在一致性哈希中，规定了一个固定大小的哈希环，环上均匀分布有 2^32 个节点，服务器节点也分布在环上。当用户发起请求时，将会根据 Key 的哈希值计算出落点，若 Key 的落点没有对应的服务器节点，则顺时针寻找最近的服务器节点。当扩容时，仅需要对新节点与上一节点之间的数据进行迁移，而缩容亦同理。
一致性哈希的优点在于避免了传统哈希算法中扩容和缩容时的大规模数据迁移，但是它也有缺点，那就是当节点在环上分布不均匀就可能导致数据倾斜。因此，当节点掉线或缩容时，可能因为将全部数据压到下一节点而导致服务雪崩。为了解决这个问题，我们需要允许一个节点在环上映射出多个虚拟节点，这样就能尽可能的使请求均匀的打到不同的服务器上。
Redis 集群采用的哈希槽方案同样基于固定数量（2^14）的哈希槽实现，不过相对于一致性哈希，每个节点拥有的哈希槽是可以直接分配的：
- 我们可以直接根据服务器的性能而为它们分配不同数量的哈希槽位，一致性哈希虽然也可以通过改变某个服务器对应虚拟节点的数量做到类似的效果，不过显然没有这么精准。
- 当扩容和缩容的时候，我们可以手动指定将哪些槽位转移到哪些节点，而一致性哈希则做不到类似的效果。
总的来说，哈希槽在使用上比一致性哈希更加灵活，并且实现上也更加简单。
问题详解
1. 为什么需要哈希算法？
在 Redis 集群中，每个分片中的节点存储的数据都是不一样的。因此当客户端进行访问的时候，就需要有一个哈希算法，能保证总是将同一个 Key 路由到一个相同的节点上。
要实现这样的效果，最简单方法就是直接根据节点总数取模，比如我们有三个节点，那么就需要对所有的 Key 哈希值基于三取模（ hash(key) % 3），最终得到的模数即为要访问的节点下标。
不过这个方案有一个致命的缺点，由于节点数量直接影响计算结果，因此当扩容或者缩容的时候，由于 Key 的哈希结果会发生变化，因此可能会引起大规模的数据迁移。
2. 什么是一致性哈希？
2.1. 概述
一致性哈希算法与传统哈希算法一样，也基于长度取模，但是它的长度是一个固定值 2^32。
它假设 2^32 个节点均匀分布在一个哈希环中，然后：
- 确认节点的位置：在开始前，对所有的存储节点进行哈希，确认存储节点落在环中的哪一个位置。
- 确认 Key 的位置：当使用时，对 Key 进行哈希，确认 Key 落在环中的哪一个位置。
- 二次寻址：当 Key 在哈希环上的落点并无直接对应的存储节点时，它再按顺时针寻找最近一个存储节点。
简而言之，这个做法相当于让每个节点都负责哈希环上的一小段区间，它的扩容或者缩容的时候，实际上就是对区间的重新划分。
2.2. 扩容和缩容
基于上面的示例，假如我们在 C 和 A 之间新增一个 D 节点，那么我们仅需要将 C 到 A 之间的数据从原本的 A 迁移到 D 即可：
而缩容则同理，比如现在我们再将节点 A 下线，那么原本的 D 到 A 之间的数据将从原本的 A 迁移到 B：
可见，在这种情况下，扩容和缩容实际上只会影响到一个节点，当进行数据迁移时，最多也只需要迁移一个区间段的数据，相比起传统的哈希算法，它尽可能的降低的迁移的数据量。
2.3. 数据倾斜与虚拟节点
不过，一致性哈希的机制决定了它天生就带有一个缺点：由于哈希算法的随机性，当节点的位置分散的不够均匀时，就会导致部分节点间的间隔过大，此时部分节点将会被迫承担更多的数据，进而造成整个集群的数据倾斜：
比如在上图中，由于节点分布不均匀，就导致 A 节点承担了过多的数据。
糟糕的是，结合它的扩缩容机制，我们不难意识到，当一个节点下线时，实际上上一节点的数据和请求都会直接压到它的下一个节点，如果下一个节点没顶住，就会再压到下下个节点……挂掉的节点越多，下一个节点挂掉的可能性就越大，如此一来，就会造成服务雪崩。
解决这个问题的核心，在于要让节点分布的尽可能的均匀，解决方案也很简单，既然节点数量少会导致区间段划分不均匀，那么我多加几个节点不就行了？
比如，在上文的例子中，我们原本只有 A、B、C 三个真实节点，但是我们可以为每个真实节点都额外创建一个虚拟节点，这样整个哈希环上就有了 6 个节点，A，A'，B，B'，C，C'，其中 A'，B'，C' 都为虚拟节点，当请求到它们的时候，将会从该虚拟节点转发到对应的真实节点上：
当节点 A 下线以后，它所负责的两部分数据，一部分将会迁移到节点 B，而另一部分将会迁移到节点 C：
你部署的节点越多，并且虚拟节点设置的越多，那么节点就会分布的更均匀，数据倾斜的可能性就越小，而当扩缩容进行数据迁移时，服务雪崩的风险也就越小。
在日常中，我们最经常接触到的一致性哈希算法的落地方案，应该是 Dubbo 的一致性哈希负载均衡策略，有兴趣的可以去了解一下。
2.4. 扩缩容引起的数据丢失问题
除了因为节点分布不均匀引起的数据倾斜问题外，当扩容或者缩容时，由于直接改变了节点的分布情况，还可能会引起数据丢失。
比如，假如我们现有 A、B、C 三个节点，此时进行扩容，如果新增的节点 D 落在了 A 与 B 之间。当客户端访问 A 到 B 之间的数据时，原本是应当去节点 B 访问，现在就会改为去 D 节点访问。
然而，此时虽然节点 A 到新节点 D 之间的数据还保留在节点 B 中，但是由于路由的时候总是路由到节点 D ，因此这部分数据已经无法被访问了，站在客户端的角度，相当于此次扩容后这一段数据全部“丢失了”。
我们可以想出一些其他的方案来解决这个问题，核心依然还是 “保证环上节点分布状态不发生调整”。
比如，当扩容的时候，我们挑选基于节点 B 扩容，此时，我们将节点 B 更换为一个虚拟节点，然后让节点 B 和本次扩容新增的节点 D 连接到该虚拟节点。当客户端路由到虚拟节点时，就再哈希一次路由到两个真实节点中。
这个方案虽然可以解决问题，不过使用上明显不够灵活，多次扩容后会导致结 构变得较为复杂，且多次哈希也会影响性能，因此这不是一个很好的解决方案。
或者，我们也可以让他像哈希槽一样，引入一套数据迁移的机制，然后客户端在扩容或者缩容的时候访问到了正在迁移的数据，则返回一个重定向的响应，不过由于一致性哈希节点路由的特殊性，相比起哈希槽，它实现起来会更麻烦一些。
3. 为什么选哈希槽而不选一致性哈希？
在 ✅ 什么是 Redis-Cluster 集群？这篇文章中，我们已经详细的介绍了 Redis-Cluster 集群是如何基于哈希槽方案实现数据分片路由，因此这里就不再赘述，只简单讨论一下如何权衡两个方案。
当搭建集群的时候，哈希槽方案允许我们灵活的为节点分配不同数量的哈希槽，甚至可以做到主动制造数据倾斜而让性能更高的节点承担更多请求。而传统的一致性哈希则做不到类似的效果，它的节点分布难以主动控制，因此会出现非预期的数据倾斜问题，虽然我们可以通过引入虚拟节点机制实现与哈希槽类似的效果，不过灵活性还是不如哈希槽，并且会提高程序的复杂度与集群的管理难度。
相比起传统的哈希算法，两种算法都可以避免扩缩容时的大规模数据迁移。但是，哈希槽由于可以手动分配，因此当扩缩容的时候我们始终可以保证哈希槽在集群节点间均匀分布，避免对某个特定节点造成太大压力。而一致性哈希则 不然，由于其特殊的路由机制，当缩容时，下线节点的全部数据都会压到下一个节点上，操作不当甚至可能引起服务雪崩。同样的，虽然引入虚拟节点机制可以一定程度的避免这个问题，不过这又会带来额外的复杂度。
最后，一致性哈希在扩缩容时，由于节点在环上的分布情况发生了改变，原本已经存放在某个节点的数据，会因此而再也无法被客户端访问到，此时相当于出现了“数据丢失”，虽然也可以通过一些其他的方案解决，不过这些方案相比起哈希槽的解决方案都更为复杂。
说到这里，我们会意识到，哈希槽能做到的事情，一致性哈希通过引入其他的方案进行改进后也能做到，因此选择哪个算法作为集群实现的基础实际上是一个成本取舍问题。哈希槽方案在程序的实现难度与运维管理成本上比一致性哈希方案更低，因此最后 Redis 选择了哈希槽方案而不是一致性哈希方案。