一致性Hash算法的缩容扩容分析

标签: 算法

保留所有版权，请引用而不是转载本文（原文地址 https://yeecode.top/blog/18/ ）。

背景

之前的文章我们已经分析过，一致性Hash算法能够在Hash输出空间发生变化时，引起最小的变动。

以上篇文章的例子来讲，增加或者移除一台服务器时，对原有的服务器和用户之间的映射关系产生的影响最小。

本文我们讨论使用了一致性Hash算法后，扩容和缩容具体会产生怎样的影响，以及在扩容缩容时应该如何做来减少影响。

如果扩容增加一台服务器X，如下图：

我们发现，该扩容对对象A、B、D无影响，只有对象C会被重定位到新的Node X。

因此，在扩容时，仅仅影响扩容服务器所在的位置的后面一台服务器，原本分配到它身上的请求被分流了，使得它的请求减少。

而对于新增加的服务器，接入了其后面一台服务器的部分流量。

在实际生产中，使用了一致性Hash算法后，如果需要增加一台服务器X，只需要将其插入位置后面的服务器C的内容拷贝到服务器X上一份即可。

更精细化的操作可以将服务器C的数据按照新的Hash输出结果分摊到服务器C和服务器X这两台服务器上，这样可以避免数据冗余，但操作相对繁杂一些。

假如服务器C被缩容摘除，则对数据对象A、B、D不会产生任何影响。只有C对象被重定位到服务器D上。

而事实上，C对象对应的Node C不存在了，因此无论如何C都会受到影响。同时，会对服务器D产生影响，因为原本分配到服务器C上的流量会被转到它的身上，使其压力增大。

在具体生产操作中，如果需要缩容服务器C，则需要将该服务器C的内容拷贝到其后面的服务器D上。这样，由服务器C转接过来的流量还可以访问到对应的数据。

可以访问个人知乎阅读更多文章：易哥（https://www.zhihu.com/people/yeecode），欢迎关注。