想象一下,你正在构建类似监控服务的东西,它有数千个需要在给定时间间隔内执行的任务,彼此独立 . 这可能是需要检查的单个服务器,或需要验证的备份,或者只是可以安排在给定时间间隔运行的任何内容 .
你不能只通过cron安排任务,因为当一个任务运行时,它需要确定它应该在下次运行的时间 . 例如:
-
计划服务器正常运行时间每1分钟检查一次
-
第一次检查服务器已关闭,安排下次检查5秒钟
-
5秒后服务器再次可用,请在5秒后再次检查
-
5秒后服务器仍然可用,继续以1分钟的间隔进行检查
想到一个天真的解决方案是简单地让一个每隔一秒左右运行一次的工作,检查所有挂起的作业并执行需要执行的作业 . 但是,如果工作岗位数量达到10万,这将如何运作?检查它们可能需要更长的时间,而不是工作人员的滴答间隔,并且任务越多,轮询间隔越高 .
有没有更好的方法来设计这样的系统?在实现这个或任何处理这类问题的算法中是否存在任何隐藏的挑战?
2 回答
使用优先级队列(优先级基于下一个执行时间)来保存要执行的任务 . 完成任务后,您将一直睡到队列前面的任务时间 . 当任务到期时,您删除并执行它,然后(如果它的重复)计算下次需要运行的时间,并根据其下一个运行时间将其重新插入优先级队列 .
这样,您可以在任何给定时间激活一个睡眠 . 插入和删除具有对数复杂性,因此即使您有数百万个任务,它仍然有效(例如,插入具有一百万个任务的优先级队列在最坏的情况下应该进行大约20次比较) .
我们在设计Revalee时遇到了同样的问题,这是一个用于调度触发回调的开源项目 . 最后,我们最终编写了自己的优先级队列类(我们称之为
ScheduledDictionary
)来处理您在问题中概述的用例 . 作为一个免费的开源项目,完整的源代码(在本例中为C#)可在GitHub上找到 . 我建议你看看 .