0

我想问一下是否有人对以下场景的最佳（最快）算法有一个想法：

  • X 进程生成一个非常大的文件列表。每个进程一次生成一个文件
  • Y 进程被通知文件已准备好。每个 Y 进程都有自己的队列来收集通知
  • 在给定时间，1 X 进程将通过具有 Round Rubin 算法的负载均衡器通知 1 Y 进程
  • 每个文件都有大小，自然，更大的文件会让 X 和 Y 更忙

限制

  • 一旦文件进入 Y 进程，将其删除并将其移动到另一个 Y 进程是不切实际的。

目前我想不出其他限制。

这种方法的缺点

  • 有时 X 落后（文件不再被推送）。它并没有真正受到排队系统的影响，无论我是否改变它，它仍然会有缓慢/美好的时光。
  • 有时 Y 落后（很多文件聚集在队列中）。再一次，和以前一样。
  • 1 Y 进程正忙于处理一个非常大的文件。它的队列中还有几个小文件可以被其他 Y 进程处理。
  • 通知本身是通过 HTTP 进行的，有时似乎不可靠。通知失败，调试没有显示任何内容。

还有一些细节有助于更清楚地看到图片。

  • Y 进程是数据库线程/作业
  • X 进程是 Web 应用程序
  • 一旦文件到达 X 进程，这些也会通过查询从 DB 端消耗资源。对生产部分有影响

现在我考虑了以下方法：

  • X 将像以前一样生成文件，但不会通知 Y。它将保存一个缓冲区（表）来填充文件列表
  • Y 将不断在缓冲区中搜索文件并自行检索它们并将它们存储在自己的队列中。

现在这种改变是否可行？就像我说的，每个 Y 进程都有自己的队列，保留它似乎不再有效。如果是这样，那么我仍然不确定下一点：

如何决定要获取哪些文件

我已经通读了背包问题，我认为如果我从一开始就拥有整个文件列表，而我没有。实际上，我确实有每个文件的列表和大小，但我不知道每个文件什么时候准备好接收。

我已经解决了生产者-消费者问题，但它以固定缓冲区为中心并对其进行了优化，但在这种情况下，缓冲区是无限的，我真的不在乎它是大还是小。

下一个最佳选择是贪婪方法，其中每个 Y 进程锁定最小的文件并获取它。起初，它似乎确实是最快的方法，我目前正在构建一个模拟来验证这一点，但第二种意见会很棒。

更新 为了确保每个人都能了解大局，我在这里链接了一个快速完成的图表。

  • 作业独立于流程。它们将以一定速度运行并处理可能的文件数量。
  • 当 Job 完成一个文件时，它将向 LB 发送一个 HTTP 请求
  • 每个进程对来自 LB 的请求（文件）进行排队
  • LB 采用循环规则

图表

4

1 回答 1

0

现在的LB思路不好

您所描述的负载均衡器是一个坏主意，因为预测未来是不必要的，您说这是不可能的。此外，当作业的长度不同时，循环是一种糟糕的调度策略。

只需让消费者在空闲时通知 LB。当一个新的工作从生产者那里到达时，它会选择第一个空闲的消费者并将工作发送到那里。当没有空闲消费者时，生产者的作业在LB中排队等待空闲消费者出现。

这样，消费者将始终处于最佳忙碌状态。

你说“让一个队列来服务 100 个应用程序（例如）将是低效的。” 这是直觉的巨大飞跃，可能是错误的。仅处理文件名的工作队列可能很快。您只需要比平均“超大文件”处理操作快 100 倍（因为您推断有 100 个消费者）。文件处理通常是 10 秒或秒。例如，基于 Apache mod 或 Redis 的队列处理程序有两个随机选择，每秒可以很容易地处理 10,000 个请求。这与成为瓶颈的距离相差 10 倍。

如果您基于 FIFO 从空闲消费者中进行选择，则当所有作业长度相等时，行为将是循环的。

如果 LB 绝对不能排队工作

然后让 Ty(t) 为在当前时期 t 完成消费者 y 队列中的工作所需的未来总时间。LB 的目标是使所有 y 和 t 的 Ty(t) 值相等。这是理想。

为了尽可能接近理想值，它需要一个内部模型来计算这些 Ty(t) 值。当一个新的工作在时期 t 从生产者到达时，它找到具有最小 Ty(t) 值的消费者 y，将工作分配给这个 y，并相应地调整模型。这是“最少剩余时间”调度策略的一种变体，最适合这种情况。

该模型不可避免地是一个近似值。近似的质量将决定其有用性。

一种标准方法（例如，来自操作系统调度），将是为每个消费者 y 维护一对 [t, T]_y。T 是在过去的时期 t 计算的 Ty(t) 的估计值。因此，在稍后的 t+d 时期，我们可以将 Ty(t+d) 估计为 max(Tt,0)。max是因为d>t，估计的job时间已经过期，所以consumer应该是完整的。

LB 使用它可以获得的任何信息来更新模型。示例是估计工作所需的时间（根据您的描述可能基于文件大小和其他特征），消费者实际完成工作的通知（LB 将 T 减去已完成工作的估计持续时间并更新 t），分配新工作的估计时间（LB 增加新工作的估计持续时间并更新 t），以及在长时间工作期间消费者剩余估计时间的中间进度更新。

如果 LB 可用的信息很详细，您将希望将 [t, T]_y 对中的总时间 T 替换为在 y 处排队的更完整的工作模型：例如，估计的工作持续时间列表，其中列表的头部是当前正在执行的。

LB 模型越准确，消费者在有工作时挨饿的可能性就越小，这是您要避免的。

于 2013-03-23T20:22:59.973 回答