從零打造一個任務排程器

下面是一個任務排程器在工作。60 個任務，有些要等別的任務做完才能開始，交給 4 個 worker 同時做。按「開始」。

排程器本身沒什麼好挑剔的：沒有一個 worker 在有事可做的時候閒著，也沒有一個任務搶在它等的東西之前開始。有問題的是下面那三條進度條。時間過了一半，數件數的那一條說 67%；時間過到 76%，它跨過 90%，然後在那上面待到結束。整份工作有將近四分之一的時間，它都在告訴你「快好了」。

這篇文章做兩件事：先把這個排程器從零寫出來，它只有四條規則，包括任務失敗之後怎麼重新排進去；然後回答任何排程器都會被問的那個問題：還要多久？ 第二件比第一件難得多，而且最好的答案，是把排程器自己再叫一次。

整個排程器加上後面的四條進度條，一共 215 行 TypeScript，沒有用任何函式庫；下面每一張圖都是你的瀏覽器現場跑出來的。它是看得完的大小：任務會失敗、會被重新排進去，但沒有優先順序，也沒有人跟你搶機器。少掉的那些東西，文章最後會一項一項說。

排程器只有四條規則

一份工作是一張圖：每個任務記著「我在等誰」。排程器反覆做四件事：

1. 誰可以開始？ 還沒做完、現在沒人在做、而且它等的任務全都做完了的，就是可以開始的。
2. 有空的 worker 就拿一個可以開始的任務去做。
3. 把時間快轉到下一次嘗試結束的那一刻，把那個 worker 放回來。
4. 那一次如果失敗了，任務不算做完：它回到「可以開始」的那一堆，等下一個有空的 worker 再試一次；等它的任務繼續等。然後回到第 1 步。

沒有時鐘在滴答走。時間只在「有一次嘗試結束」的時候往前跳，所以一份要跑兩個多小時的工作，排一次只要大約 8 微秒（我的機器上量的）。核心是兩個函式和一個迴圈（sim/job.ts 裡的 Scheduler，這裡只省略了記錄用的幾行）：

assign() {                                                     // 規則 1 和 2
  for (const t of this.tasks) {
    if (!this.freeWorkers.length) break;
    const ready = !this.finished[t.id] && !this.busy[t.id] && t.deps.every((d) => this.finished[d]);
    if (ready) this.begin(t.id, this.now);                     // 記下開始時間、拿走一個 worker
  }
}
 
advance() {                                                    // 規則 3 和 4
  const id = earliest(this.running, this.ends);
  const ok = this.tried[id] === this.attempts[id].length - 1;
  this.now = this.ends[id]; this.busy[id] = 0; this.freeWorkers.push(this.worker[id]);
  if (ok) { this.finished[id] = 1; this.left--; }
  else this.tried[id]++;                                       // 沒做完，所以規則 1 會再看到它
}
 
while (s.left > 0) { s.assign(); s.advance(); }                // 整個排程器

規則 4 只有一行，因為失敗的任務不需要特別的「重試佇列」：它只是沒有被標成做完，所以下一輪的規則 1 自然會再看到它。

下面是同一個排程器，換成一份小到可以整張看完的工作：14 個任務、3 個 worker。箭頭從被等的任務指向等它的任務。一直按「下一步」，看規則 2 和規則 3 輪流發生；然後按「重來」，在某個任務跑到一半的時候點它，讓它當場失敗，看規則 4 怎麼把它排回去。

最後一件事：attempts（每個任務每一次嘗試要多久）是從外面傳進來的。傳「實際發生的」，得到的是真正的時間軸；傳「我以為每個任務一次就成功、要這麼久」，得到的就是一個預測。這件事後面會用到。

任務失敗了怎麼辦

剛才是你親手弄壞任務。現在讓它們自己壞：下面是開場那一份工作，同樣的任務、同樣的先後順序，只是每一次嘗試都有機率做到一半失敗。粉紅色的空框是失敗的那一次；往右找，同一個任務會再出現一次。

我離線量的（200 份工作、預估準確）：每次嘗試有 20% 會失敗的時候，一份工作平均多出 15 次失敗的嘗試，worker 有 13% 的時間花在最後沒有成果的事情上，整份工作從 38 分鐘變成 44 分鐘。

時間只多了 15%，比「20% 會失敗」聽起來少，有兩個原因：失敗的那一次通常沒有做完整段就死了；而且這個排程器重試得很乾脆，失敗的任務馬上回到可以開始的那一堆，剛好空出來的那個 worker 通常立刻把它接回去。

失敗還帶來一個後果，和下一節有關：沒有人知道哪一次會失敗，所以任何預測都會偏樂觀。

還要多久：三個不同的量

從這裡開始的三張圖都先把失敗關掉，一次只看一件事。

進度條可以回答三個問題：

• 完成了幾件？ 最好算，數就好。
• 做完了多少工？ 要先對每個任務有個預估，然後加起來。
• 過了多少時間？ 這才是等的人想知道的，而它要等整份工作跑完才有答案。

前兩個是手上有的，第三個是人家要的。進度條說謊，就是拿前兩個去冒充第三個。

冒充得像不像，要看任務的大小有多懸殊。下面這張圖不是一份工作，是 150 份工作的平均，每移一次滑桿，你的瀏覽器就在背景重跑一次。

滑桿上的數字是任務大小取對數之後的標準差：0.2 是都差不多，1.2（預設）是最大的一成任務佔四成多的工作量。任務都差不多大的時候，兩條線都貼著對角線，數件數完全夠用。往右拉，數件數的那一條鼓起來：我用 200 份工作離線量過，預設的懸殊程度下它平均差 10 點，有 24% 的時間待在 90% 以上（誠實的話是 10%）。照工作量加權的那一條好一半，平均差 6 點。

預設的 1.2 是不是太誇張？我拿這個專案自己的測試來對（在我的機器上各跑一次）：168 個端對端測試的執行時間，這個數字是 1.0；237 個單元測試是 2.8，最大的一成測試佔了 98% 的時間。把滑桿拉到 2.8：數件數的那一條平均差 28 點，有 45% 的時間待在 90% 以上。真的工作比我的預設更懸殊，不是更平均。

照工作量的那一條也不貼著對角線，而這一次不能怪預估，因為這裡的預估是準的。

worker 越多，進度條越不誠實

「做完了多少工」不等於「過了多少時間」，因為同時在做事的 worker 數量一直在變。開頭有一堆任務可以同時做，四個 worker 全開，工作量掉得很快；到了尾巴，只剩一兩個任務在等前面的結果，其他 worker 沒事做，時間照樣在走。

把滑桿從 1 拉到 32。有兩件事同時發生。

第一，整份工作先是變快，然後撞到一條水平線就不再變快（上面那張圖）。我量的平均是：1 個 worker 122 分鐘，2 個 63，4 個 38，8 個 31.4，之後不管加到幾個都是 31.0。那個 31 分鐘是工作裡最長的一條「你等我、我等他」的鏈子，再多人手也只能等。

第二，數件數的進度條越來越不誠實：4 個 worker 時平均差 10 點，16 個時差 17 點，有三分之一的時間待在 90% 以上。人手越多，開頭衝得越快，尾巴還是一樣長。

第三條線幾乎貼著對角線（平均差不到 1 點）。它就是前面說的那件事：把排程器再叫一次。它不問「做了多少」，而是把還沒做完的任務、用預估的時間、在同樣這幾個 worker 上排一遍，看排出來還要多久。排程器被用了兩次：一次是真的在跑，一次是拿來預測自己。要回答時間的問題，就得把工作圖和 worker 數量都算進去，而這兩樣東西排程器本來就有。

它有一個盲點，就是前面說的失敗：預測的時候，它假設剩下的任務都一次成功。把「任務失敗了怎麼辦」那張圖的 20% 失敗打開，它的平均誤差就從 0.7 點變成 2.7 點。數件數和照工作量的那兩條幾乎不受影響，因為它們本來就不準。

計畫是錯的怎麼辦

照計畫預測的那一條還有一個前提：預估是準的。現實裡的預估通常是錯的，而且錯得很有規律，例如「上傳」這種任務永遠比你以為的慢一倍。

預估一不準，照計畫排的那一條就跟著錯。我離線量的結果是它平均差 8.2 點，比只是照工作量加權的那一條（6.7 點）還差。模型比較好，餵進去的數字是錯的，輸給比較笨的算法。

打開開關。這條進度條每看到一個任務做完，就把「這一種任務實際花的時間 ÷ 預估的時間」記下來，拿去修正同一種、還沒做的任務。平均誤差從 8.2 點降到 4.0 點。它不是神經網路，只是每一種任務一個比值，但它就是這個站一直在做的事：一個很小的、在你的分頁裡學的模型。

剩下的那 4 點，一部分是每個任務自己的運氣，這個誰也學不到；一部分是工作剛開始、還沒有任何任務做完可以學的那一段。

它還有一個代價：它會倒退。 一個任務超過了預估還沒做完，它就得承認「還要更久」，進度條往回走 2 到 3 點。數件數和照工作量的進度條永遠不會倒退。真的進度條多半選擇不讓它倒退，於是它就停在原地不動，這是另一種不說實話的方式。

和真的不一樣的地方、數字怎麼量的

任務的大小是我選的分佈（對數常態）。懸殊程度我只拿這個專案自己的兩組測試對過（1.0 和 2.8，見上），沒有對過別人的工作負載；你的編譯、你的 CI 是多少，圖 04 的滑桿可以自己拉。

排程的規則是最單純的那一種：哪個任務先好就先做，失敗了立刻重試、不等待；沒有優先順序，沒有搶先，worker 自己不會壞，也沒有「這個工作要四個 worker 同時開始」這種限制。這些正是 Kubernetes、Airflow 這一類真的排程器要處理的事。訓練大模型的叢集還多一種：一個工作的所有成員要同時拿到機器，湊不齊就整組等（gang scheduling）。取消一個任務之後下游怎麼辦、誰該先做，也是另外的題目。

單位是一整份互相等待的工作，不是一個個請求。 一個請求怎麼排隊、怎麼分流、重試要等多久，Sam Rose 寫過三篇很好的互動文章（見來源），這篇沒有重講。

worker 在這裡只是一個號碼。 它可以是一台機器、一個行程，也可以是第 9 篇那座城市裡的一個小人：那三百個人各自決定下一件事要做什麼，這裡反過來，由排程器替他們決定。兩種做法遇到的是同一個問題：事情互相等，而且沒有人知道還要多久。

真的系統裡，連「有幾個任務」都常常不知道：工作會邊做邊長出來。這裡的四條進度條都假設任務清單一開始就是完整的。

數字的來源：圖 03 到 06 和上面的讀數，是你的瀏覽器跑 150 份工作的平均。文中寫「我量過」的，是離線用 200 份工作（種子 1 到 200）跑的，腳本和完整的表在這個專案的 docs/research/task-scheduler/。開場那份工作是第 77 號。

來源

• 單一請求的排隊、重試與分流：Sam Rose, Queueing、Retries（encore.dev/blog）、Load Balancing（samwho.dev）。
• 人怎麼感受進度條：Harrison, Amento, Kuznetsov, Bell, Rethinking the Progress Bar, UIST 2007, 115–118 頁。
• 最長的相依鏈決定下限：Kelley, Walker, Critical-Path Planning and Scheduling, Eastern Joint Computer Conference, 1959, 160–173 頁。