背景设计一个分布式任务调度系统类似于AWS EventBridge SchedulerKubernetes CronJobGoogle Cloud SchedulerMetas internal distributed scheduler系统需要支持数亿100M定时任务系统需求功能需求1. 创建jobCreateJob( jobId, cron expression, callbackURL, payload )2. 修改job3. 删除Job4. Trigger Job5. 至少一次执行 At-least-once6. 支持Retry7. 用户可以查历史非功能需求1. Scale100 million jobs, peak is 2 million/minute2. availability: 99.99%3. durability: 即使整个machine挂掉job不能丢4. latency scheduled time /- 1 secondAPI设计1. Create JobPOST /job BODY: { cron: ****, url: /job/1234, payload: hello, world }2. Update JobPUT /job/{jobId} BODY: { cron: ****, url: /job/1234, payload: hello, world }3. Get JobGET /job/{jobId}4. Delete JobDELETE /job/{jobId}5. Trigger JobPOST /job/{jobId}/runs架构设计本系统的架构设计如下1. client通过API GW向后端发送job的CRUD请求。我们在后端设置scheduler service处理这种请求更新job的meda data DB。2. 在scheduler service初次创建一个job的时候将job的首个scheduling信息写到scheduling index DB里。Scheduling index DB使用AWS Dynamo DB。使用minute做parition key使用second做sort key。对于每个primary key维护一个job list。3. 启动scheduling workers通过shard lease获取对某些shard的记录的访问权限。scheduling workers会读取自己负责的shard的job ID将该job dispatch到queue中。在dispatch完成后scheduling workers重新计算该job的下一次fire time更更新scheduling index DB。4. Execution workers会从dispatch queue读出dispatched job然后执行。并且将执行的结果写入到execution history DB里。5. 如果是trigger job我们只需要将该job ID存入到当前即将执行的scheduling index DB的primary key中即可。讨论本系统设计的核心在于对于非常多需要调度的任务怎样快速查找到当前需要调度的任务。这里的思路是通过DDB的schema设计由minutepartition key和secondsort key保存每秒需要调度的任务ID。下面我们讨论以下问题1. 如果某个时刻比如零点需要调度的任务非常多应该如何处理?分为两种情况。第一种job的execution时间不是非常严格。这种情况下我们可以考虑给每秒的可以execute的job设置一个上限。超过上限则放到下一个bucket里。这样可以平滑job运行的峰值。第二种job的execution时间是严格的。我们可以认为scheduling workers是可以一直scale out的我们唯一需要处理的问题是DDB的hot partition的问题。我们可以考虑将大的bucket的primary key加上suffix进一步划分为多个bucket。比如分钟_1, 分钟_2, ...。