负载均衡/重分布相关算法名称

Question

给定一个数组x1，x2，x3，...，xk，其中xi是框i中的项数，我如何重新分配这些项，以使框中包含的项不超过N项。N接近sum(xi)/k --也就是说，N接近每个具有相同项数的框。中间包装盒不应该用来装载物品--如果x1有剩余而x2和x3有赤字，x1应该将一些物品发送到x2和x3，但不应该将其所有物品发送到x2，然后让x2解决剩余问题。

实际问题是:每个计算节点都有一组样本，在重采样步骤之后，一些计算机节点可能有剩余，而另一些计算机节点则有不足，因此我希望在最小化通信的同时重新分配样本。

我想这类问题是有名字的。

Answer 1

我不相信你的问题(如上所述)复杂到足以吸引独立研究。如果机器计数(称之为C)以千计，而您的样本计数甚至是数万亿，那么将样本 counts 发送到协调主节点是微不足道的。

然后，主节点可以简单地(O(C))计算N，识别违反该界限的节点，以及违反多少。请注意，超出界限的超量总和恰好是所需的最小通信量。通过在计算N时插入松弛参数(即接受不平衡)，您可以控制此数量。

使用排序，可以在O(C log C)中按照样本计数对节点进行排序。移动两个光标，一个从两端朝中间移动。在每个步骤中，计划从大节点到小节点的传输，大小为大节点中剩余剩余的最小值，或小节点中剩余的闲置大小。前移最后一句中具有活动约束的任何节点的指针，并重复，直到新的大节点没有多余为止。(我相信这就是@Noxville的贪婪算法。)

假设N大于每个节点样本的平均计数，这是理想的w.r.t。最低限度的交流。

如果您的机器网络有任何约束，无论是缺少链接，还是跨边的最大流或可变成本，那么您需要分解图流内容。然而，您没有提到任何类似的内容，并且同一数据中心内的计算机集群通常没有。

Answer 2

听起来您想要使用一致的散列

http://en.wikipedia.org/wiki/Consistent_hashing

基本上，使用一个好的随机哈希函数将允许您为您的样本获得唯一的ids，从而提供均匀的分布。然后，很容易将样本一致地分布在一组节点上。

看见

http://www.lexemetech.com/2007/11/consistent-hashing.html http://www.tomkleinpeter.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

了解更多信息。

Answer 3

我认为这个问题应该这样澄清：

对于M剩余节点和K亏损节点，我们应该将节点之间的样本重新分配到具有0个剩余节点和(可能)一些亏损节点的状态。样品应该以包的形式交换，并且这些包的数量应该最小化。

或者，在数学上，我们有M*K矩阵，它的每个单元表示从节点M传递到节点K的样本数，每行中给定的元素和以及每列中给定的最大元素和。目标是最小化非零单元格的数量。

这是一种"Constraint satisfaction problems"。它是NP完全的。我发现了两个与这个问题类似的经典问题：“集合打包”和“广义精确覆盖”。

为了将问题减少到"Set packing"，我们需要(临时)添加几个具有N+1样本的剩余节点，以便在重新分配之后没有剩余节点。然后，对于每个节点，我们需要为剩余元素和“赤字”元素生成所有可能的分区。然后对剩余和赤字分区的Cartesian product应用“优化”版本中的“集合打包”，即找到最小数量的子集。

为了将问题减少到"Generalized exact cover"，对于每个节点，我们需要为剩余元素和“赤字”元素生成所有可能的分区。然后我们应该添加M，M+1，...优化节点以最小化封面中的子集数量。然后对盈余和赤字分区和优化节点的笛卡尔乘积应用“广义精确覆盖”。对于较少的优化节点，该算法将失败，对于较大的节点，该算法将找到最小数量的子集。

“广义精确覆盖”可以用"Knuth's Algorithm X"来解决。我不知道任何“集合打包”的算法。

所有这些解决方案都给出了准确的答案，但它们具有巨大的计算复杂性，因此不太可能有人在真正的调度程序中使用它们。实用的方法是使用一些启发式和贪婪算法。只需对剩余节点和赤字节点进行排序，并应用“最佳拟合”策略。