算法问题:最小碎片运动

Question

在分布式系统中，我有一个碎片移动问题。

[问题]

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

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

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

[我的粗略解决方案]

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

[我的问题]

我试了几个例子，这个算法奏效了。但我不确定这是否正确。这是正确的吗？如何证明？谢谢!

Answer 1

根据我从你的问题中所能理解的，你需要的是一致散列。你可以找到关于它的多篇文章。每当添加新的碎片时，它都会从其他节点获取公平的对象份额。