系统设计面试指南之分布式任务调度

1 简介

任务是需要资源(CPU 时间、内存、存储、网络带宽等)在指定时间内完成的一段计算工作。

通过智能地将资源分配给任务以满足任务级和系统级目标的系统称为任务调度程序。

任务调度程序：

及时决定和分配资源给任务的过程称为任务调度。

当我们在 Facebook 发表评论时。我们不会让评论发布者等待直到那条评论被交付给所有关注者。交付被委托给一个异步任务调度程序离线完成。

在分布式系统中，许多任务是在用户的单个请求的背景下运行。考虑Facebook、WhatsApp 或 Instagram 这样的热门系统有数亿用户。这些系统需要一个任务调度程序来处理数十亿个任务。Facebook 使用 Async 根据其用户的数十亿个并行异步请求来调度其所有任务。

Async 是 Facebook 自己的分布式任务调度程序，调度其所有任务。一些任务时间敏感，如应该运行的通知用户某项活动开始直播的任务。如果用户在直播结束后才收到通知就没意义了。某些任务可延迟，如向用户提出好友建议的任务。Async 根据适当的优先级调度任务。

2 需求

• 可用性：系统应高可用以调度和执行任务
• 持久性：系统收到的任务应持久化，不应丢失
• 可扩展性：系统应能每天调度和执行越来越多的任务
• 有限的等待时间：这是任务在开始执行之前需要等待的时间。我们不能在预期时间之后执行任务。用户不应该无限期地等待。如果用户的等待时间超过一定阈值，他们应该收到通知

3 组件设计

3.1 任务调度程序架构设计

① Task Submitter（任务提交者）

接受任务。没有单一的任务提交者。相反，我们有一组接收越来越多任务的节点。

② Database（数据库）

任务提交者接收的所有任务都存储在分布式数据库。使用关系数据库来存储：

• task IDs
• user IDs
• 所需资源
• 执行上限
• 客户端尝试总次数
• 延迟容忍度
• ...

使用有向无环图（DAG）存储依赖任务的数据的图数据结构的非关系数据库。

③ Batching and prioritization（批处理和优先级）

将任务存储在 RDB 后，将任务分批。优先级基于任务的属性，如：

• 延迟容忍度
• 或执行时间短的任务等。

将最高 K 优先级的任务推送到分布式队列，K限制可以推送到队列的元素数量。K值取决许多因素，如：

• 当前可用资源
• 客户端
• 或任务优先级
• 订阅级别

④ Queue manager（队列管理器）

队列管理器在队列中添加、更新或删除任务。它跟踪我们使用的队列的类型。它还负责保持任务在队列中直到成功执行。如果任务执行失败，该任务将再次出现在队列。队列管理器知道在高峰时段、非高峰时段应该运行什么队列。

⑤ Res