算法题: Minimum Shard Movement

Question

我在分布式系统中遇到分片移动问题。

【问题】
最初每个分区负责任意数量的分片。 (这个数字可以是任意的，因为系统支持将分片从一个分区移动到另一个分区)

然后一个新的分区来了，系统需要重新分片。目标是使分片分配尽可能统一，即任意两个分区之间的最大分片数差最多为1，并尽量减少移动分片数。

例如，假设最初有三个分区，P1、P2 和 P3。 P1 处理 5 个分片，P2 处理 3 个分片，P3 处理 1 个分片。然后一个新的分区 P4 进来所以系统重新分片。重新分片的结果是一个分区处理 3 个分片，三个分区每个处理 2 个分片。现在问题变成了哪个分区应该处理 3 个分片。对于这种特定情况，P1 应该处理 3 个分片，否则分片移动不是最小的。

【我的粗略】
现在我有一个大概的想法，如果分区 Pi 有第 i 个最多的分片，那么 Pi 的新分片数也应该是第 i 个最大的数新的分片编号。例如，如果分区 P1、P2、P3 中的原始分片编号分别为 10、2、1，那么分区 P1 现在应该处理 4 个分片，分区 P2、P3、P4(新分区)各处理 3 个分片。

【我的问题】
我尝试了一些例子，这个算法有效。但我不确定它是否正确。这是对的吗？如何证明？谢谢!

Answer 1

从你的问题我可以理解，你需要的是 Consistent Hashing .你可以找到关于它的多篇文章。每当添加新分片时，它都会从其他节点中获取公平份额的对象。