机群作业调度算法

Question

我正在寻找适合以下问题的算法：

1. 类似Hadoop的公平调度程序。这里的问题是：当集群大小未知时，我可以在哪里获得最小的共享？
2. 将一些惩罚与每个用户相关联。当用户的作业被安排时，增量惩罚。使用将作业调度给用户的概率为1-（规范化惩罚）。这类似于步幅调度，但我找不到任何好的解释。

Answer 1

当我实现一个非常相似的作业运行器（用于生产系统）时，我不再让每个服务器随机选择作业类型。这是我的理由--

>

来自一个用户的作业过多不应影响其他用户运行作业的机会（用户-用户公平性）

一个作业类型的过剩不应该影响其他作业类型运行的机会（用户-作业和作业-作业公平性）

调度器知道等待作业、作业类型和用户元数据，但不知道作业数据（即用户名、作业名和计数，但不知道有效载荷）

我还希望每个服务器都是独立的，可以自主地安排自己的工作，而不必了解其他服务器

我确定的解决方案是通过{user,jobtype}属性元组跟踪等待作业，并让每个调度步骤随机选择5个元组，从每个元组中最多选择10个作业接下来运行。选定的作业将由下一个可用的运行者运行。只要有足够的容量来运行更多的作业（可能是因为作业已经完成，或者是因为次要限制它们无法运行），就运行另一个调度步骤来获取更多的工作。

一个特定工作类型的大量工作需要很长时间才能全部完成，但情况总是如此。通过从多个用户中挑选作业类型，作业处理的响应性不会受到不利影响。

可以添加许多次要限制（例如，每秒对linkedin的调用不超过5次），但以上是系统的核心。