algorithm - 公平作业处理算法

Question

我有一台机器可以接受用户上传，对其进行一些处理，然后返回结果。处理收到的每个上传通常需要几分钟时间。

问题是，少数用户可以上传很多基本上拒绝其他用户处理很长时间的工作。我想到的只是设置一个硬上限并使用优先级队列，例如一小时内上传 5 次后，所有新上传的处理优先级都较低。我基本上想处理所有作业，但我不希望上传 1000 个作业的用户让大家等待。

我的问题是，是否有更好的方法来做到这一点？

我的目标是尽量减少上传和返回结果之间的时间。如果该算法也能以分布式方式工作，那将是理想的。

谢谢

Answer 1

实现将有很大差异，具体取决于这些作业是什么、它们需要多长时间、处理时间有多大差异，以及在此过程中出现 fatal error 的可能性有多大。

也就是说，在用户之间保持工作均匀分布的一种简单方法是维护所有已提交工作的用户的列表。当您准备好获得一份新工作时，而不是只是从随机队列中取出下一份工作，而是循环浏览用户，每次从每个用户中取出最高的工作。

同样，这可以通过多种方式完成，我会推荐一个从用户到他们各自提交的工作列表的映射。每次准备好新工作时，循环浏览 map 的按键。然后获取您所在键的作业列表，然后执行第一项作业。

这是假设每个作业都是“原子的”，因为一个作业不依赖于在提交它的作业旁边执行。

希望对您有所帮助，当然我可能完全误解了您的要求。