這是系統(tǒng)面試準備系列的第一篇博客转捕。我的目標是設(shè)計出KISS(keep it simple stupid)系統(tǒng)刃跛，可以在實際系統(tǒng)設(shè)計面試中花費45-60分鐘進行討論策橘。
介紹
任務(wù)調(diào)度是一個常見的系統(tǒng)設(shè)計面試問題锚扎，下面的一些領(lǐng)域坎拐，可能會需要設(shè)計一個任務(wù)調(diào)度系統(tǒng)：
- 設(shè)計一個對賬處理的系統(tǒng)（每月/周/日 進行對賬處理）
- 設(shè)計一個代碼部署的系統(tǒng)（定期進行代碼流水線處理）
這篇文章的目的是設(shè)計一個簡單且可擴容的任務(wù)調(diào)度系統(tǒng)
問題陳述
設(shè)計一個在指定時間間隔運行的任務(wù)調(diào)度系統(tǒng)
功能性需求
- 用戶能夠調(diào)度或者查看任務(wù)
- 用戶能夠列出所有已提交的任務(wù)担忧，并顯式當前任務(wù)的狀態(tài)
- 任務(wù)能夠運行一次或者重復運行芹缔。任務(wù)需要在定義的調(diào)度時間之后，再給定的X閾值時間內(nèi)運行（假設(shè)X = 15分鐘）
- 單個任務(wù)的執(zhí)行時間不能超過X分鐘（假設(shè)X = 5分鐘）
- 任務(wù)也會有優(yōu)先級瓶盛，高優(yōu)先級的任務(wù)需要比低優(yōu)先級的任務(wù)先執(zhí)行
- 任務(wù)的最終輸出需要被存儲至文件系統(tǒng)中
非功能性需求
- 高可用 - 對于用戶而言最欠，系統(tǒng)可以一直添加/查看任務(wù)
- 可擴展性 - 系統(tǒng)可以擴展支持數(shù)百萬的任務(wù)調(diào)度
- 可靠性 - 系統(tǒng)必須最少一次執(zhí)行一個任務(wù)示罗，并且相同的任務(wù)不能在同一時間
被不同的進程調(diào)度 - 持久性 - 在任何失敗場景下，系統(tǒng)都不應(yīng)該丟失任務(wù)的信息
- 延遲 - 系統(tǒng)應(yīng)在作業(yè)被接受后立即回饋用戶芝硬。 用戶不必等到工作完成蚜点。
流量和存儲估算
假設(shè)任務(wù)調(diào)度系統(tǒng)的QPS設(shè)計目標：1000QPS；假設(shè)單個調(diào)度任務(wù)最多可以運行 5 分鐘吵取，因此該系統(tǒng)是高度受到CPU的制約的
CPU限制（CPU Bound）
一個現(xiàn)代的CPU可以有16核禽额，單核擁有2個線程，單個調(diào)度任務(wù)最多可以運行 5 分鐘皮官。 那么單機器CPU執(zhí)行任務(wù)的公式：
16核 * 2線程 / 5min / 60s = 0.1 任務(wù)/秒 (8000 任務(wù)/天)
內(nèi)存限制（Memory Bound）
假設(shè)每一個任務(wù)會占用5M的內(nèi)存脯倒，對應(yīng)的內(nèi)存分配了16G， 那么單機器內(nèi)存執(zhí)行任務(wù)的公式：
16G * 1024 / 5M / 5min / 60s = 10 任務(wù)/秒
如果需要達到1000QPS捺氢， 那么需要的機器數(shù)量 1000 / 10 = 100
上述結(jié)果給了我們一個提示藻丢，即用于處理任務(wù)調(diào)度的單機設(shè)計既不高可用也不可擴展。 所以我們需要分布式系統(tǒng)來設(shè)計解決方案
系統(tǒng)接口
有如下三個接口需要暴露給用戶
- 任務(wù)提交： submitJob(api_key, user_id, job_schedule_time, job_type, priority, result_location)
job_type值可以是ONCE 或者 RECURRING摄乒，API可以返回HTTP Code 202代表接收到了任務(wù) - 單個任務(wù)查看： viewJob(api_key, user_id, job_id)
響應(yīng)的任務(wù)狀態(tài)包括NOT_STARTED STARTED COMPLETED - 任務(wù)列表查看： listJobs(api_key, user_id, pagination_token)
高層級設(shè)計
用戶的請求流程：
(1 & 2) 用戶通過load balancer(或API 網(wǎng)關(guān))提交/獲取任務(wù)
(3) 請求會被持久化到DB中悠反，并且返回ack告知用戶已處理
(4 & 5)Job Scheduler Service會持續(xù)的從DB中拉取快到期執(zhí)行的任務(wù)，并將其塞入隊列中
(6 & 7)Job Executor Service會執(zhí)行實際的業(yè)務(wù)邏輯調(diào)度任務(wù)馍佑，更新最終結(jié)果進文件系統(tǒng)并將任務(wù)調(diào)度狀態(tài)置為COMPLETED
DB 設(shè)計
由于我們對事務(wù)支持或任何其他 ACID 屬性沒有嚴格要求斋否，只需牢記峰值的QPS（2 * 1000 = 2000），所以我們可以同時使用SQL或者NoSQL數(shù)據(jù)庫拭荤，考慮到 NoSql 在規(guī)模茵臭、維護和成本方面的明顯優(yōu)勢，我會選擇使用 DynamoDb 的 NoSql 解決方案
用戶查詢模式
給定UsedId舅世，新增任務(wù)
給定UserId旦委，獲取所有jobIdsDB Schema
Table: JOB
+------------------------------+--------+
| Attribute | Type |
+------------------------------+--------+
| user_id (partition key) | uuid |
| job_id (sort key) | uuid |
| actual_job_execution_time | date |
| job_status | string |
| job_type | string |
| job_interval | int |
| result_location | string |
| current_retries | int |
| max_retries | int |
| scheduled_job_execution_time | date |
| execution_status | string |
job_status：用戶查看的任務(wù)狀態(tài)，包含NOT_STARTED, STARTED, COMPLETED三種狀態(tài)
execution_status：當前服務(wù)維護的實際執(zhí)行狀態(tài)雏亚，包含NOT_STARTED, CLAIMED, PROCESSING, SUCCESS, RETRIABLE_FAILURE, FATAL_FAILURE
除了用戶之外缨硝，我們的作業(yè)調(diào)度服務(wù)將輪詢數(shù)據(jù)庫以獲取到期的任務(wù)，可以通過不同的方式來實現(xiàn)這一目標：
- 基于X分鐘大小的桶窗口分區(qū)
我們可以創(chuàng)建名為 scheduleJob 的索引來檢索最后 X 分鐘到期的作業(yè)罢低，將其拉出之后使用延時隊列特性塞入MQ中
Index: ScheduledJob
+----------------------------------------------+------+
| Attribute | Type |
+----------------------------------------------+------+
| scheduled_job_execution_time (partition key) | time |
| job_id (sort key) | uuid |
+----------------------------------------------+------+
Query (SQL equivalent):
SELECT * FROM ScheduledJob WHERE scheduled_job_execution_time == now() - X
- 基于X分鐘大小的桶窗口+ share id 的分區(qū)
很有可能查辩，在一個特定的時間窗口內(nèi)，很多任務(wù)會被接收到（假設(shè)有10萬個）网持。在這種場景下宜肉，上述查詢語句的性能會非常的慢，我們可以根據(jù)隨機的Share Id(假設(shè)在1到N之間)進一步對DB進行分區(qū)
Index: ScheduledJob
+----------------------------------------------+------+
| Attribute | Type |
+----------------------------------------------+------+
| scheduled_job_execution_time (partition key) | uuid |
| shard_id (partition key) | int |
| job_id (sort key) | uuid |
+----------------------------------------------+------+
Query (SQL equivalent):
SELECT * FROM ScheduledJob WHERE scheduled_job_execution_time == now() - X and shard_id == Y
深入底層設(shè)計
- 任務(wù)調(diào)度器（Job Scheduler）如何工作
任務(wù)調(diào)度流程：
- 每 X 分鐘翎碑，Master節(jié)點創(chuàng)建一個權(quán)威的 UNIX 時間戳谬返，并為每個 worker 分配一個 shard_id 和 schedule_job_execution_time。
- Worker 節(jié)點將執(zhí)行以下查詢日杈，并將任務(wù)推送到 Kafka 隊列中執(zhí)行遣铝。
worker 1:
SELECT * FROM ScheduledJob WHERE scheduled_job_execution_time == now() - X and shard_id = 1
worker 2:
SELECT * FROM ScheduledJob WHERE scheduled_job_execution_time == now() - X and shard_id = 2
容錯設(shè)計
- Master 監(jiān)控Worker的健康狀況并知曉哪個Worker死亡以及如何將查詢重新分配給新Worker佑刷。
- 如果Master節(jié)點死亡，我們可以分配其他worker節(jié)點作為master
- 此外酿炸，如果worker成功查詢db瘫絮，我們還可以引入本地數(shù)據(jù)庫來跟蹤狀態(tài)并將待執(zhí)行任務(wù)放入隊列中
- 任務(wù)執(zhí)行器（Job Executor）如何工作
Job Executor存在多個Consumer從隊列中拉取待消費的任務(wù)，Consumer 機器也存在Master進程與Worker進程填硕。Master進程與Worker進程都基于Pull模型上運行麦萤。Master進程 將從隊列中輪詢調(diào)度任務(wù)，Worker進程將通過執(zhí)行以下代碼不斷從 master 輪詢調(diào)度任務(wù)
while True:
w = get_next_work()
do_work(w)
任務(wù)執(zhí)行流程與容錯設(shè)計
- 當從隊列中取出調(diào)度任務(wù)時扁眯，消費者的 master 更新db中JOB的屬性 execution_status=CLAIMED壮莹。
- 當Worker進程接手工作時，它會更新 execution_status=PROCESSING 并不斷向本地 DB 發(fā)送健康檢查姻檀。
- 調(diào)度任務(wù)完成后命满，Worker進程會將結(jié)果推送到 AWS s3 中，更新db中JOB的 execution_status=COMPLETED 或 FATAL_FAILED绣版，并使用狀態(tài)更新本地 db
- Worker進程和Master進程都將更新本地數(shù)據(jù)庫中的健康檢查胶台。
健康檢查服務(wù)
健康檢查服務(wù)定期運行（比如每 x 秒），并掃描上次從Worker進程接收到的健康檢查小于定義閾值的數(shù)據(jù)庫杂抽。 在這種情況下诈唬，它認為調(diào)度任務(wù)未能處理并將其推送回隊列。
結(jié)論
系統(tǒng)設(shè)計是一個廣泛的話題缩麸，一小時的面試很難涵蓋到系統(tǒng)設(shè)計的方方面面铸磅。在上述的設(shè)計中，我們已經(jīng)達到了面試官可以進一步深究的大部分區(qū)域匙睹。
引用
