6

我正在为松散耦合的集群编写一些代码。为了在作业期间实现最佳性能，我让集群在每次孩子进入或退出时重新映射其数据。这最终将成为可选的，但目前它默认执行其数据平衡。我的平衡基本上只是确保每个孩子的文件数量永远不会超过每台机器的平均文件数，再加上一个。如果除法不干净，则加一用于余数。而且由于余数总是小于孩子的数量[除了 0 的情况，但我们可以排除这种情况]，平衡后的孩子最多 avg + 1。

一切似乎都很好，直到我意识到我的算法是 O(n!)。顺着孩子的名单往下看，找出平均数，余数，谁有太多，谁有太少。对于太多列表中的每个孩子，遍历列表，发送给每个太少的孩子。

有没有更好的解决方案？我觉得应该有。

编辑：这里有一些伪代码来展示我是如何导出 O(n!) 的：

foreach ( child in children ) {
    if ( child.dataLoad > avg + 1 ) {
        foreach ( child2 in children ) {
            if ( child != child2 && child2.dataLoad < avg ) {
                sendLoad(child, child2)
            }
        }
    }
}

编辑：O(n^2)。Foreach n, n => n*n => n^2。我想我今天早上没有喝足够的咖啡！;)

将来我想转向更灵活和有弹性的分布方法[权重和启发式]，但现在，数据的统一分布是可行的。

4

4 回答 4

4

@zvrba：您甚至不必对列表进行排序。第二次遍历列表时，只需将所有平均工作量较少的项目移动到列表的末尾（您可以在第一次遍历时保留指向最后一项的指针）。顺序不必是完美的，它只是在最后一步中必须增加或减少迭代器时发生变化。

见上一个答案

最后一步看起来像：

在第二步中，在 child2 中保留一个指向第一个项目的指针，该项目的工作量低于平均工作量（以防止需要有一个双链表）。

for each child in list {
  if child2 == nil then assert("Error in logic");
  while child.workload > avg + 1 {
    sendwork(child, child2, min(avg + 1 - child2.workload, child.workload - (avg + 1)))
    if child2.workload == avg + 1 then child2 = child2.next;
  }
}
于 2008-09-26T14:21:28.367 回答
2

我认为你的分析是不正确的：

  • 遍历列表以找出平均值为 O(n)
  • 制作具有太多或太少数据块的孩子列表也是 O(n)
  • 移动数据与数据量成正比

你是如何到达 O(n!) 的？

您可以对列表 [O(n lg n) in the number of children] 进行排序，这样在前面有工作太多的孩子，最后有工作太少的孩子。然后同时从两端遍历列表：一个迭代器指向一个有多余数据的孩子，另一个指向一个缺乏数据的孩子。传输数据，并向前移动一个迭代器，或向后移动另一个。

于 2008-09-26T13:57:34.210 回答
2

您可能想尝试一种完全不同的方法，例如一致哈希。

有关该主题的相对简单介绍，请参见此处： http ://www8.org/w8-papers/2a-webserver/caching/paper2.html

（也有更深入的论文，从 Karger 等人开始）

我在 Erlang 中创建了一致哈希的工作实现，如果您愿意，可以检查它：

http://distributerl.googlecode.com/svn/trunk/chash.erl

于 2008-09-26T14:42:55.880 回答
1

您发布的代码复杂度为 O(n^2)。尽管如此，正如 malach 观察到的那样，可以在线性时间内完成，其中 n 是子列表中的项目数。

考虑：内部循环有 n 次迭代，最多执行n 次。n*n = n^2。

于 2008-09-26T14:34:56.163 回答