Jak*_*old 5 language-agnostic algorithm queue cron scheduled-tasks
想象一下,你正在构建类似监控服务的东西,它有数千个需要在给定时间间隔内执行的任务,彼此独立.这可能是需要检查的单个服务器,或需要验证的备份,或者只是可以安排在给定时间间隔运行的任何内容.
你不能只通过cron安排任务,因为当一个任务运行时,它需要确定它应该在下次运行的时间.例如:
想到一个天真的解决方案是简单地让一个每隔一秒左右运行一次的工作,检查所有挂起的作业并执行需要执行的作业.但是,如果工作岗位数量达到10万,这将如何运作？检查它们可能需要更长的时间,而不是工作人员的滴答间隔,并且任务越多,轮询间隔越高.
有没有更好的方法来设计这样的系统？在实现这个或任何处理这类问题的算法中是否存在任何隐藏的挑战？
使用优先级队列（优先级基于下次执行时间）来保存要执行的任务。当你执行完一个任务后，你会休眠直到队列前面的任务的时间到来。当任务到期时，您删除并执行它，然后（如果它重复出现）计算下一次需要运行的时间，并根据下一次运行时间将其插入优先级队列。
这样您就可以在任何给定时间都有一个活跃的睡眠。插入和删除具有对数复杂度，因此即使您有数百万个任务，它仍然保持高效（例如，在最坏的情况下，插入到具有一百万个任务的优先级队列中应该需要大约 20 次比较）。
有一点可能有点棘手：如果执行线程正在等待直到特定时间才能执行队列头部的项目，并且您插入一个位于队列头部的新项目，位于队列头部之前之前存在的项目，您需要唤醒线程，以便它可以重新调整现在位于队列头部的项目的睡眠时间。