作者 | akinwang

調度模塊在很多系統中都是常用的模塊，比如實習生的每天簽到郵件，預約銀行的業務短信，學習通的上課通知，騰訊視頻push中臺的任務下發，調度系統在中間起到關鍵作用。

一、那么什么是調度？

本質就是通過一些自定義策略，定時或者周期性的去觸發某些事件，比如去發起一次rpc調用，和下游進行一次通信。

通用流程

調度行為可以抽象成以下幾步：

• 任務生成。
• 任務存儲。
• 任務觸發。
• 路由實例。

如果能做好這幾步，那么一個高性能的調度系統也就誕生了，而每一步的技術選型，都和未來系統想要達成的目標（高精度，高可用），有著密不可分的關系，下面我會針對這幾步進行分析。

后面會舉出一些實際的系統進行說明。

二、任務生成

• 單次任務生成：對于單次任務，通常由管理臺直接發起請求，將任務信息寫入系統。
• 周期性任務生成：周期性任務生成類似于打點計時器。每當任務觸發時，系統會計算出未來需要觸發的任務時間列表。例如，對于每小時執行的任務，系統會在第二天生成24個整點任務。
• 推送系統任務生成：對于推送系統任務，系統會根據用戶過去的行為畫像預測其最有可能點擊的時間區間。在第二天到來之前，系統會預先計算并生成第二天各個時間點的推送任務。

三、任務存儲

任務存儲的思考分為兩個方面，第一，是用什么數據結構存。第二是用什么類型的db去存。

對于高性能調度系統而言，主要看重范圍查詢效率，查詢的qps，分布式鎖的表現。

至于這里為什么提到了分布式鎖，是因為在集群模式下，哪一臺實例去執行任務掃描這一過程依賴于分布式鎖的搶占。

1.數據結構分析

列表：

• 插入：O(1)
• 查詢：O(logN)
• 實現：我們可以利用列表去存即將觸發的任務信息，通過遍歷的方式去取到大于當前時間的任務，并且觸發。
• 優點：實現簡單
• 缺點：但需要對所有任務進行遍歷，查出很多無效數據，極其低效。

大頂堆：

• 刪除：O(logN)
• 查詢：O(1)
• 實現：我們也可以利用大頂堆的性質，每次都取堆頂元素，如果堆頂元素大于當前時間，那么就取最大元素。其余元素會利用大頂堆的性質，繼續浮出最大的元素，然后繼續比較。
• 優點：查詢快，只會查到快到時間的任務，實現簡單。
• 缺點：需要維護自身堆的性質，cpu壓力高，無法抗住高并發。

B+樹：

• 查詢：O(logN)
• B+樹（B-plus tree）是一種自平衡的樹數據結構，它能夠保持數據有序，允許插入、刪除和查找操作在對數時間內完成。B+樹特別適合于磁盤或其他直接存取輔助設備的存儲系統，因為它能夠最大化地減少I/O操作次數。

跳表：

• 查詢：O(logN)
• 跳表（Skip List）是一種基于有序鏈表的高效數據結構，它通過在鏈表的基礎上增加多級索引來實現快速的查找操作。跳表允許在對數時間內完成搜索、插入和刪除操作，且插入和刪除操作不需要頻繁調整數據結構。

小總結

總的來說，列表和大頂堆由于自身的性質，并不適合這樣的場景。對于掃表+觸發的模式，其實本質是需要一個能高速范圍查詢的數據結構。

B+樹和跳表都是高效的能范圍查詢數據結構，但它們各自適用于不同的場景。B+樹更適合于磁盤存儲和范圍查詢，而跳表則更適合于內存中的快速查找和分布式環境。

2.數據庫分析

我們舉出基于內存的數據庫的代表Redis和基于磁盤的數據庫進行分析。

Redis VS MySQL：

• Redis的底層是跳表，而MySQL的底層是B+樹。就范圍查詢而言，兩者不分伯仲。
• 但Redis沒有事務概念，內部實現是單線程，沒有鎖競爭，再加上IO多路復用的特性和極其高效的數據結構實現，就注定單機qps要遠超過mysql。
• mysql在這個場景下的優勢則是有持久化能力，不容易丟數據，redis可能在RDB和AOF的過程中有丟數據的可能性。

因此，mysql和redis都有可能是作為存儲任務的數據庫，需要區分場景。

3.分布式鎖的分析

在集群模式下，哪一臺實例去執行任務掃描這一過程依賴于分布式鎖的搶占。

(1) 基于MySQL實現

select * from lock_table where lock_name = 'schedule_lock' for update

主要是利用了當前讀，將這條數據加上了行鎖，其他線程在搶鎖的時候會阻塞。

(2) 基于Redis實現

加鎖：SET key value PX expireTime NX。

解鎖：del key。

然而，僅依靠這兩行命令作為分布式鎖的實現，確實顯得過于簡單。在網絡波動或垃圾回收（GC）的情況下，很有可能出現超時時間已過，但仍嘗試釋放鎖的情況，從而導致錯誤地釋放了其他客戶端持有的鎖。

這種情況可能會引起任務的重復下發，為了避免這一問題，下游系統不得不引入去重機制。

為確保安全，建議引入Lua腳本來優化鎖的操作。在釋放鎖之前，Lua腳本可以檢查鎖的持有者是否為當前客戶端，只有確認是自身持有的鎖時，才執行釋放操作。這樣一來，GET和DEL兩個操作就能合并為一次原子操作，從而避免潛在的安全隱患。

總的而言，mysql的分布式鎖實現簡單，但性能低。redis實現稍微復雜，性能高，一般用redis的多一點。

四、任務觸發

在構建高效、可靠的分布式任務調度系統時，我們需要考慮多個方面，觸發包括定時掃描、狀態更新、任務重試等關鍵環節。

1.定時掃描

觸發的本質就是將數據從db加載進內存中，那么我們可以通過定時任務，按照一定時間間隔去加載。那么

• 誰來掃描？
• 掃描的時間間隔多少合理？

(1) 誰來掃描？

負責掃描的實例需將掃描到的任務進行下發，即發起RPC調用。

為確保實例能夠并發發起多條請求，其機器資源應具備足夠的線程數。為實現掃描與下發任務的負載均衡，各實例可通過搶鎖機制競爭掃描權限。

獲得鎖的實例將負責執行掃描及下發任務的職責。

如上圖，每個實例都有一個定時任務，x秒執行一次，去嘗試搶鎖。

(2) 掃描的時間間隔多少合理？

掃描時間間隔的設定對于確保系統性能和精度至關重要。這個間隔應當基于系統所需的實時精度以及單次掃描所生成的任務數量來合理確定。盲目降低掃描時間間隔并不總是能提高精度；相反，它可能會導致效率降低，甚至增加數據延遲。

舉個例子，如果系統每1秒執行一次掃描，但每次掃描產生大量任務，而RPC處理時間長達2秒，且在此期間無法解鎖以供其他實例掃描，那么第2秒的數據延遲將會顯著增加。也就是說，本該1s完成的事情，他拖到了第2s才完成，那么第2s的任務就會被連累到第3s才做完......

因此，在確定掃描時間間隔時，應考慮以下兩點：

• 對于精度要求不高且任務量較大的場景：可以適當延長掃描時間間隔，以確保在單次掃描周期內能夠完成所有任務的處理下發。這樣可以減輕系統負擔，提高整體效率。
• 對于精度要求高同時任務量也很大的場景：除了優化RPC處理流程外，還可以考慮改進數據存儲結構，將數據分片分桶處理。通過為每個數據分片分配獨立的掃描實例，可以實現并行處理，從而在保證高精度的同時提升系統響應速度。

綜上所述，合理的掃描時間間隔應當根據具體應用場景和系統需求進行細致調整，以達到最佳的性能和精度平衡點。

2.狀態更新

為了讓我們的系統展現出卓越的性能和高精度，我們采用了異步方式來下發任務。異步處理的明顯優勢在于它能夠使任務并發執行，無需等待響應，從而顯著提升了系統的信息處理能力。然而，這也帶來了一個問題：我們無法確切知道下游系統是否真正收到了任務。即便上游系統竭盡全力發送任務，如果下游系統接收不到，這些努力也將化為泡影。

因此，我們需要下游系統在成功接收到信息后，主動發送一個確認信號（ACK）。一旦系統接收到這個ACK，我們就能記錄下觸發時間和執行時間等相關信息，以便后續的任務重試模塊進行相應的處理。

考慮到任務是并發下發的，返回的信息量可能會非常龐大，每條返回信息都可能觸發一次遠程過程調用（RPC），這無疑會大量消耗連接資源。為了解決這個問題，我們引入了隊列機制。

隊列機制的工作原理如下：

通過引入ACK隊列，我們實現了以下幾個關鍵效果：

• 當任務隊列滿載時，我們可以一次性取出所有元素，觸發一次RPC請求。這樣，原本需要多次請求的單個數據處理，現在可以合并為一次批量處理。
• 即使任務隊列未滿，但如果自上次取元素以來經過的時間超過了預設的閾值，我們也會將隊列中的所有數據一次性取出，觸發一次RPC請求。

通過這種方式，我們成功地實現了連接復用和即時響應的雙重效果，這也是一個寫聚合的思想。

但是壞處也很明顯，就是我們這個隊列是基于內存的，實例宕機有丟消息的可能性。時間的閾值也需要經驗去設置，如果設置短了，連接不會復用，設置長了，可能影響后續任務重試時的掃描，造成誤判。

這種思想源于Kafka提供的Micro-Batch的概念，他會將相同Topic和Partition的消息聚合成一個批次，然后一次性發送到Kafka集群

3.任務重試

上文我們分析了如何讓海量任務下發，但仍然做不到能讓調度系統擁有可靠性。在分布式環境下，服務器可能因為網絡延遲，服務器故障，資源競爭等原因，任務執行可能會失敗。那么如何處理這些失敗的任務呢？

其實這個問題可以拆解成幾個小任務：

(1) 如何檢測到失敗的任務？

我們上個步驟的下發回流，就是為了收集任務的執行上下文信息。有了這些信息，我們只需要去設置一個定時任務，快速的掃描這個任務信息即可。

(2) 如何定義一個失敗的任務？

在下發一段較長的時間后，仍然沒有回流信息寫入。

回流信息寫入成功，但回流信息中的響應code為失敗。

(3) 檢測到失敗任務以后的重試策略？

重試策略分為重試次數和重試間隔。

每次重試完成，我們需要去更新這個已經重試次數，并檢測他是否等于最大重試次數，之所有有這個最大重試次數，是為了防止他無限重試，造成重試風暴，而超過這個最大重試次數的，我們可以把它塞入死信隊列中，讓負責這個任務的人手動的去處理。

而重試間隔主要也分為幾種：

(1) 固定間隔重試

在這種策略中，每次重試之間都有一個固定的時間間隔。例如，如果操作失敗，系統會在1秒后重試，然后是2秒后重試，依此類推。

(2) 指數退避重試

指數退避重試策略是一種更復雜的重試策略，其中每次重試之間的時間間隔呈指數增長。例如，第一次重試可能在1秒后，第二次在2秒后，第三次在4秒后，以此類推。這種策略有助于減少對系統的沖擊，特別是在高負載或網絡擁塞的情況下。

之所以采用以上這兩種策略是因為rpc接口調用在遇到服務質量異常的錯誤的時候，由于服務質量異常是有一定時間的，因此有各種退避策略，一定程度上給足下游恢復的時間。

(3) 下游應該如何處理重試的任務？

在掃描的過程中，如果因為網絡波動的原因，導致回流消息的時間被拉長，而我們上游在掃描的時候誤認為沒有下發成功，而實際上已經下發成功了，我們依舊發起了重試，那么就會導致重復下發。

為了避免這一現象發生，下游有必要去做一次去重。我們可以給每次下發的任務都冠以一個唯一id，然后用位圖對當日的下發進行去重處理。

我們可以使用雪花算法去生成唯一id，也可以通過每次生成的業務id去拼接當前下發的秒數去生成唯一id，這個方案很多，不多贅述。

五、路由實例

在經過上述流程之后，我們需要做的是，選擇一個合適的實例進行觸發，往往通過線程池，協程池進行rpc調度。

總結了市面上的開源中間件主要有以下幾種路由算法的實現：

這些路由算法都是為了能讓不同執行器的負載變得均衡，需要根據場景選擇合適的路由算法。

六、優秀系統的設計

1.xxl-job的實現

XXL-JOB是一款知名的分布式任務調度框架，它采用內存中的時間輪算法結合MySQL作為持久化存儲來管理調度任務，其調度粒度精準至秒級。

以下是XXL-JOB的核心工作流程：

• 調度線程預讀與更新：調度線程負責提前讀取未來5秒內即將執行的任務，將這些任務載入內存中的時間輪，并同步更新它們的下一次觸發時刻。
• 時間輪線程輪詢執行：時間輪線程每隔一秒從等待狀態激活為可運行狀態。它會捕獲當前時間的秒級信息，并在時間輪中定位到對應的任務。一旦找到，時間輪線程便會利用預先配置的線程池發起RPC調用，觸發任務執行。

下面是簡易版的偽代碼(筆者憑借之前的印象寫的，可能并不完整)：

// 時間輪 秒數為key,task列表為value
Map<Integer,List<Task>> ringData = new HashMap<>();
// rpc線程池
ThreadPoolExecutor threadPool = new ThreadPoolExecutor();

// 調度線程
Thread schedulerThread = new Thread(() -> {
    while(true){
        1. 從數據庫預讀未來5s的任務
        List<Task> tasks = mapper.loadTask(now() + 5000)  
        for(task in tasks){
            long time = task.getTriggerTime();
            // 根據觸發時間計算秒數。比如觸發時間是 21：00：01 那么秒數就是 1
            Integer second = time.calculateSecond();
            ringData.put(task.getSecond(), task)
            // 更新下一次觸發事件，運行狀態等信息，
            updateTask(task)
        }
        Thread.sleep(5000)
    }
})
schedulerThread.start();

// 時間輪線程
Thread ringThread = new Thread(() -> {
    while(true){
       //秒數對齊，整秒數激活為可運行狀態
       Thread.sleep(1000 - System.currentTimeMillis() % 1000);
       //獲取蘇醒時候的秒數
       Integer currentSecond = now().getSecond();
       List<Task> tasks = ringData.get(currentSecond);
       //放入線程池發起rpc調度
       threadPool.trigger(tasks)
       // help gc
       tasks.clear();
    }
})
ringThread.start();

這里的時間輪就是一個key為秒數，value為即將要執行的任務id列表。

時間輪分為單級時間輪和多級時間輪。xxl-job并沒有像kafka那樣采用多級時間輪，主要是因為設計理念的不同，他為了簡化設計，并且單級時間輪已經滿足大部分任務調度的需求。

優點：

• 高效檢索與持久化：借助MySQL B+樹的特性，搜索操作的時間復雜度降至O(logN)，同時提供數據的持久化存儲，確保數據安全不易丟失。
• 高精度調度：通過將任務提前預讀至內存，提升了任務調度的精度和響應速度。
• 生產者-消費者模型：調度線程與時間輪線程的協同工作構成了經典的生產者-消費者模型。時間輪作為任務緩沖區，有效實現流量削峰，減輕系統瞬時負載壓力。

缺點：

• 調度器集群性能瓶頸：現有架構依賴調度器集群間的鎖機制來執行任務，這可能導致單個調度器承受過大壓力，限制了系統的并發處理能力（QPS）。在任務量激增時，難以通過水平擴展提升調度能力，從而可能導致部分任務延遲過高。
• 磁盤存儲的性能局限：雖然MySQL提供了可靠的數據存儲，但作為基于磁盤的數據庫，在高并發場景下的性能可能不如內存型數據庫如Redis。

總體而言，XXL-JOB采用內存結合MySQL的部署方式簡單易行，無需額外引入中間件。這種設計在追求調度精度的同時犧牲了一定的水平擴展性。對于任務量適中的場景而言，它仍然是一個值得考慮的優秀調度框架選項。

2.騰訊視頻push中臺的實現

騰訊視頻push中臺為了應對海量的并發，犧牲了調度的精度，以redis作為db，ZSet(跳表)作為底層數據結構來支持任務的范圍查詢。

主要流程：將任務id作為key，時間戳作為value進行任務的新增，利用Zrange 命令獲取要觸發的任務，并判斷是否需要觸發。而任務拉取任務依賴不同實例去搶分布式鎖，然后執行。

優點：

• 基于redis，查詢快，qps是mysql的好幾倍，實現簡單，易于維護。
• redis的分布式鎖性能優秀，加鎖解鎖快。
• 無需依賴其他中間件，成本小。
• 讓搜素的時間復雜度降低到O(logN)，查詢快，無需遍歷額外數據。

缺點：精度無法保證。

3.Redis的高精度版本實現

(1) 分片

為了實現更高精度的Redis調度，我們需要確保跳表中的數據量保持在合理范圍內。過多的數據可能導致內存占用過高、成本不足以及讀寫響應時間變長等問題(大Key問題)。因此，為了降低Redis訪問的響應時間（即提高精度），我們對數據進行分片處理，使調度器每次只需掃描一個分片的數據。

如下圖：

我們可以把一天的數據分為多個分鐘級別的數據，雖然搜索的時間復雜度仍為O(logN)，但由于N大大減小，搜索效率得到提高，響應速度更快。

然而，這仍然無法解決一個問題：如果某個實例通過搶鎖方式獲得某一分鐘分片的掃描權限，但該分鐘內的數據量仍然很大，可能會導致實例的線程數不足，無法實現并發處理。

(2) 分桶

為了解決這個問題，我們可以采用分桶策略，將這一分鐘的數據劃分為多個bucket。

在集群模式的調度器下，每個實例競爭的是各個bucket的鎖，獲得鎖后，只需掃描相應分桶的數據。這種方法可以實現每分鐘級別的tasklist調度，多臺機器可以同時掃描和下發，避免了單個實例線程不足的問題。

如下圖：

若即使分成三個桶，數據量仍然過大，我們可以引入一個決策服務來監控任務的延時情況。如果任務的延時率持續較高，可以根據實際情況動態調整分桶數量，從而更好地滿足實際需求。

總結

本文詳細探討了調度模塊在多種系統中的應用及其重要性，并深入分析了調度系統的通用流程，包括任務生成、任務存儲、定時掃描和路由實例等關鍵步驟。

文章針對每個步驟的技術選型進行了探討，并結合實際系統（如XXL-JOB和騰訊視頻push中臺）進行了案例分析。此外，還討論了各種路由算法的實現及其適用場景。

總的來說，一個高性能的調度系統需要綜合考慮任務生成策略、存儲數據結構的選擇、數據庫選型、分布式鎖的實現以及定時掃描的機制等多個方面。通過合理的技術選型和系統設計，可以實現高精度和高可用的調度目標。同時，根據具體的應用場景和需求，靈活調整調度策略和路由算法，以達到最佳的性能和效率平衡點。