1

当我正在实施一个简单的负载平衡服务时，我认为 Big-O 是其未来性能和可扩展性的关键因素。但是我找不到关于两种算法（WRR和RR）的大 O 的参考。

我试着计算它们。
（警告我的计算可能是错误的，但我会在得到正确答案后立即编辑帖子）

n-> 服务节点的数量（和权重）
z-> 等待/未完成任务的数量
对于 WRR：O(n n z)
对于 RR：O(z^2)

For WRR: O(1)
For RR: O(1)

所以真正的问题是，如果我的计算是正确的，但最重要的是，在持续负载平衡（到每个运行节点）每秒数千个提交任务的情况下，哪种算法执行速度最快。

一些有用的参考资料：

  • 一个非常好的 RR实现
  • 关于 WRR的 stackoverflow问题

干杯!

4

1 回答 1

0

那么你到底需要测量什么？由于大 O 是针对算法性能的，因此衡量每个调度决策的时间复杂度似乎是合理的，即需要多少操作才能将一项任务与一个节点匹配。

循环赛

就绪节点列表和等待任务列表都可以实现为队列，对队列的操作可以实现恒定摊销时间。因此，除了需要为队列分配新内存所需的时间外，您在 O(1) 中进行操作。

加权循环

如果您的权重是固定的且可通约的，那么您也可以在这里实现相同的复杂性：只需将每个节点多次放入循环队列中，与其权重成正比。可以制定一种算法以将它们均匀地分布在队列中。对于大多数实际应用，一些适度的量化将导致权重可以表示为（即缩放到）相当小的整数。

其他注意事项

您是否收到任何关于您的节点是忙还是闲的反馈？如果你这样做了，那么 RR 应该足够好，因为你没有说明任何公平要求。如果您没有空闲反馈，那么 WRR 可能有意义。但在这种情况下，z您的公式中的数字显得有些混乱，因为如果您不知道节点是否准备好接受它们，任务怎么会等待呢？如果他们正在等待是因为平衡器无法足够快地处理它们，那么这对您的考虑仍然无关紧要，因为您可以像调度算法之前一样想象任务队列：该队列的长度对什么没有影响发生在调度程序中。再次假设所有任务对您来说都是相同的，没有优先级、QoS 保证或类似的元信息。

于 2013-02-07T22:07:20.663 回答