本文適合有 Java 基礎(chǔ)知識的人群

作者：HelloGitHub-Salieri

HelloGitHub 推出的《講解開源項目》系列。PowerJob 項目地址：

https://github.com/KFCFans/PowerJob

寫在前面的碎碎念：終于到了萬眾期待的調(diào)度層原理了。其實很早之前就想動筆把這部分好好給大家講講，因為問的人實在是太多了...大部分小伙伴進(jìn)用戶群的第一句話就是：“群豬，請問無鎖化調(diào)度是怎么實現(xiàn)的？”，剩下的犀利點的小伙伴甚至直接問：“群豬，你這個性能強(qiáng)勁無上限體現(xiàn)在什么地方啊？”。

可惜不巧的是，鄙人在 7 月初給自己安排了一個驚險刺激的大西北旅游，每天不是在坐車就是在前往坐車的路上，雖然感受到了祖國疆域之遼闊、風(fēng)景之秀麗、文化之璀璨，人累個半死也是確有其事。文章嘛，自然也就是一路鴿到了現(xiàn)在...

那么，是時候表演真正的技術(shù)了～

一、調(diào)度層概覽

PowerJob 目前支持 4 種定時執(zhí)行策略，分別是 CRON、固定頻率、固定延遲 和 API。API 指的是通過 PowerJob 提供的客戶端接口直接啟動任務(wù)的方式，不需要 server 來支持調(diào)度，此處忽略。而剩下的 3 種調(diào)度策略，根據(jù)其執(zhí)行頻率的不同，可以劃分為常規(guī)任務(wù)和秒級任務(wù)。我們先講常規(guī)任務(wù)。

常規(guī)任務(wù)指由 CRON 表達(dá)式指定定時策略的任務(wù)，這一類任務(wù)的特點是 執(zhí)行頻率不高。 對于這類任務(wù)，PowerJob 采用基于數(shù)據(jù)庫輪詢的策略來進(jìn)行調(diào)度，具體的原理圖如下。

PowerJob 的任務(wù)表中，除了維護(hù)任務(wù)的基礎(chǔ)元數(shù)據(jù)(如任務(wù)名稱、定時策略、執(zhí)行器信息等)之外，還會額外增加一個字段 next_trigger_time，也就是下一次調(diào)度時間，當(dāng)任務(wù)被成功創(chuàng)建時，系統(tǒng)會使用 CRON 表達(dá)式去初始化該字段，保證每一個 CRON 任務(wù)都存在可用的下一次調(diào)度時間。

有了這個字段，具體的調(diào)度就好辦了。powerjob-server 會啟用一個后臺線程定期掃描任務(wù)表，查找那些由本機(jī)調(diào)度的、即將執(zhí)行(即下一次調(diào)度時間與當(dāng)前時間的差值小于系統(tǒng)規(guī)定的閾值)的任務(wù)。

(這里埋個小小的伏筆，“由本機(jī)調(diào)度”其實是實現(xiàn)無鎖化調(diào)度的關(guān)鍵，將在下一篇文章為大家揭秘，本文主要講述調(diào)度流程，因此直接以單機(jī)為例)

一旦發(fā)現(xiàn)接下來的一段時間內(nèi)有任務(wù)需要被調(diào)度執(zhí)行，就會為這些任務(wù)生成執(zhí)行記錄并推入時間輪，最后完成任務(wù)的調(diào)度。

聽起來似乎很平淡無奇的一個流程，存在著那些精彩的設(shè)計與實現(xiàn)呢？請聽我細(xì)細(xì)分解～

二、高性能調(diào)度——時間輪

假如，現(xiàn)在給你一個任務(wù)，要求 2 秒后執(zhí)行，你會怎么解決的？

最簡單的方案，也就是利用休眠。1 秒后執(zhí)行，那么我讓當(dāng)前線程 sleep 1 秒，不就達(dá)到目的了嗎？沒錯，基于線程休眠的特性，可以用三行代碼實現(xiàn)一個最簡單的定時執(zhí)行器，但是它的性能嘛...自然也是相當(dāng)?shù)睦?..由于每一個任務(wù)都需要綁定一個單獨的線程，當(dāng)系統(tǒng)中存在大量任務(wù)時，這種方案消耗的資源極其龐大。

那么如何實現(xiàn)高效的調(diào)度呢？

也許，就和牛頓被蘋果砸出萬有引力引力一樣，發(fā)明時間輪算法的大神，在為尋找高效調(diào)度方案而苦惱不已時，低頭看了看自己的勞力士～覺得這個表如此的樸實無華的同時，似乎找到了那么一點點靈感～

根據(jù)前面分析，線程休眠型調(diào)度器之所以低效，是因為它需要用到大量的線程資源，這浪費了大量的 CPU 和內(nèi)存資源。那么有沒有辦法來避免這個消耗呢？看著這個表，有人找到了答案。

時間輪是一種高效利用線程資源來進(jìn)行批量化調(diào)度的一種調(diào)度模型。把大批量的調(diào)度任務(wù)全部都綁定到同一個的調(diào)度器(一個線程)上面，使用這一個調(diào)度器來進(jìn)行所有任務(wù)的管理，觸發(fā)以及運行，能夠高效的管理各種延時任務(wù)，周期任務(wù)，通知任務(wù)等等。

時間輪的算法模型如上圖所示，每個時間輪存在著 N 個槽，兩個槽之間的間隔時間固定。每走一個時間間隔，指針就向前推進(jìn)一格，然后開始處理當(dāng)前槽內(nèi)的所有任務(wù)。指針不斷循環(huán)推進(jìn)，直到時間輪中不存在任何任務(wù)。

當(dāng)新增調(diào)度任務(wù)時，可根據(jù)任務(wù)的調(diào)度時間和當(dāng)前時間計算出具體的時間槽。為了能以時間復(fù)雜度 O(1) 的代價將任務(wù)放入指定位置，需要時間槽具有隨機(jī)訪問的能力，為此該部分使用循環(huán)數(shù)組實現(xiàn)。每一個時間槽對應(yīng)的任務(wù)隊列長度不確定，且只需要提供順序訪問能力，為此任務(wù)隊列使用單向鏈表實現(xiàn)。

每一個時間輪都有兩個必備參數(shù)，時間間隔 tickDuration 和 刻度數(shù)量 ticksPerWheel。這兩個參數(shù)也很好理解，時間間隔就是指針轉(zhuǎn)動的頻率，刻度數(shù)量就是這個表盤內(nèi)任務(wù)槽的數(shù)量，拿現(xiàn)實中的手表來說，tickDuration 就是 1，ticksPerWheel 是 12。

講了那么多理論，這里舉個具體的例子來幫助大家理解時間輪(其實時間輪的概念非常好理解，具體的實現(xiàn)也不算很難，可以說是一種性價比超高的數(shù)據(jù)結(jié)構(gòu)了～)

假如我現(xiàn)在有一個時間間隔為 1 秒，刻度數(shù)為 12 的時間輪，現(xiàn)在需要調(diào)度 3 個定時任務(wù)，分別在 1 秒、6 秒和 13 秒后執(zhí)行，那么時間輪的工作流程是怎么樣的呢？

首先，第一步是任務(wù)的插入。由于表盤的設(shè)計是環(huán)形數(shù)據(jù)，通過 (預(yù)計執(zhí)行時間 - 時間輪啟動時間)% 刻度數(shù) 這個公式便能算出該任務(wù)的插槽下標(biāo)，即這些任務(wù)會分別被插入到 0、5 和 0 號槽對應(yīng)的鏈表中。

完成任務(wù)的插入后，接下來就等著調(diào)度線程取出任務(wù)并執(zhí)行了。調(diào)度線程通過休眠 tickDuration 的方式，循環(huán)讀取下一個槽中鏈表中的任務(wù)并執(zhí)行。由于鏈表中的任務(wù)可能不是本輪需要調(diào)度的(就比如 13 秒后執(zhí)行的任務(wù)，其實是下一個調(diào)度周期才需要執(zhí)行)，需要額外對任務(wù)的預(yù)計執(zhí)行時間做判斷，只有符合要求的任務(wù)才會被調(diào)度執(zhí)行，并從鏈表中移除。

這樣就做到了 1 個線程完成大量任務(wù)的調(diào)度，兼?zhèn)湫阅芎托?。唯一的缺點是由于采取了 tickDuration，那么調(diào)度會存在著一定的誤差。如果你對調(diào)度執(zhí)行的時間精度要求極高，那時間輪可能不是你的菜，否則，還不趕緊抱走？

時間輪的概念講完了，接下來回歸框架本身。PowerJob 所使用的時間輪設(shè)計整體參考 Netty，并在一些地方做了定制化處理，比如由于 PowerJob 調(diào)度后執(zhí)行任務(wù)有一定的開銷(涉及數(shù)據(jù)庫操作)，因此除了指針線程，還額外引入了處理線程池來保證調(diào)度的精度。源碼一共 326 行，有興趣的話，快去看吧，類名都給你準(zhǔn)備好啦！

com.github.kfcfans.powerjob.server.common.utils.timewheel.HashedWheelTimer

三、可靠調(diào)度——WAL

可靠調(diào)度也是大家廣為關(guān)注的一個問題，甚至還有同學(xué)在 GitHub Issue 留言告訴我他們自研的調(diào)度系統(tǒng)在生產(chǎn)環(huán)境中遇到的不可靠調(diào)度問題：

那么 PowerJob 存在著錯過調(diào)度的問題嗎？答案顯然是否定的。(作為一款一直強(qiáng)調(diào)極高可用性和穩(wěn)定性的生產(chǎn)級調(diào)度中間件，要是這一點都做不到，那還有臉見人嗎？

那么問題又來了，這，又是如何實現(xiàn)的呢？

不知道大家有沒有聽說過 WAL(Write-Ahead Logging，預(yù)寫式日志)，這是主流關(guān)系型數(shù)據(jù)庫(MS SQLServer、MySQL、Oracle)用來確保了事務(wù)原子性和持久性的關(guān)鍵技術(shù)。WAL 的核心思想是：在數(shù)據(jù)寫入到數(shù)據(jù)庫之前，先寫入到日志中。這樣，在硬盤數(shù)據(jù)不損壞的情況下，預(yù)寫式日志允許存儲系統(tǒng)在崩潰后能夠在日志的指導(dǎo)下恢復(fù)到崩潰前的狀態(tài)，避免數(shù)據(jù)丟失。

PowerJob 為了實現(xiàn)任務(wù)的可靠調(diào)度，也借鑒了該思想。每一個任務(wù)被調(diào)度執(zhí)行時，系統(tǒng)都會為其生成一條記錄，這條記錄包含了該任務(wù)實例(任務(wù)的一次運行叫任務(wù)實例)的預(yù)期調(diào)度時間。之后，PowerJob 會首先將該記錄持久化到數(shù)據(jù)庫中，只有持久化成功后，該任務(wù)才會被正式推入時間輪進(jìn)行調(diào)度。

一旦這一臺 server 宕機(jī)，任務(wù)沒有被準(zhǔn)時執(zhí)行。其他 server 就能根據(jù)已經(jīng)寫入數(shù)據(jù)庫中的任務(wù)實例記錄將其恢復(fù)，做到可靠調(diào)度～

也就是說，只要你的系統(tǒng)中還有一臺 powerjob-server 活著，就不會有缺失調(diào)度的情況。

四、秒級任務(wù)

說夠了常規(guī)任務(wù)的調(diào)度，讓我們來侃侃秒級任務(wù)～

秒級任務(wù)的特點是運行頻率極高(吐槽：這不是廢話嗎)，那么能不能用支持常規(guī)任務(wù)調(diào)度的這套方法來支撐秒級任務(wù)的調(diào)度呢？

首先是任務(wù)的獲取。emmm...“一定時間間隔掃描任務(wù)表獲取待執(zhí)行任務(wù)”，這...等你獲取到任務(wù)，黃花菜都涼了...這不中啊...沒錯，使用傳統(tǒng)調(diào)度方案，第一步就掛了。(我想到了路途艱難，但沒想到居然那么難！)

不過，比較聰明的同學(xué)可能想到了。既然秒級任務(wù)執(zhí)行頻率很高，那 server 獲取這個任務(wù)后，可以將它保存起來，這樣下一次調(diào)度就不需要單獨查數(shù)據(jù)庫了，而是選擇內(nèi)存遍歷，要多快有多快，似乎就解決了這個問題。

然而，這種方式仍不完美。俗話說得好，物以稀為貴，秒級任務(wù)的執(zhí)行頻率那么高，在大部分情況下，其實失敗個一兩次也沒什么關(guān)系，畢竟立即就會有下一個任務(wù)補(bǔ)上。因此，傳統(tǒng)任務(wù)那一套為了可靠調(diào)度而生的機(jī)制并不適用于秒級任務(wù)，秒級任務(wù)使用了那套機(jī)制后，也會對數(shù)據(jù)庫產(chǎn)生較大的沖擊，導(dǎo)致 PowerJob 整體的性能大幅度下降。那么出路究竟在何方呢？

此時就不得不提解決計算機(jī)領(lǐng)域問題的終極神器了：分治。既然不強(qiáng)要求任務(wù)執(zhí)行有非常高的可靠性，那么 powerjob-server 此時就可以放權(quán)了。

每一個秒級任務(wù)，都會直接被投遞到集群中的某一臺 powerjob-worker 上，由 powerjob-worker 全權(quán)負(fù)責(zé)執(zhí)行。而 powerjob-server 此時只需要負(fù)責(zé)故障恢復(fù)即可。

這樣一來，server 的壓力進(jìn)一步減輕，同時，由于秒級任務(wù)的調(diào)度與執(zhí)行全部落在了 worker 身上，調(diào)度的精度也會上升(至少能省下通訊的網(wǎng)絡(luò)延遲)，可謂是一個完美至極的雙贏方案。

五、最后

那么以上就是本篇文章全部的內(nèi)容啦～

本篇文章講述了 PowerJob 調(diào)度層的實現(xiàn)與其中一些精巧的設(shè)計。不過限于篇幅，整個調(diào)度層其實并沒有完全呈現(xiàn)在大家眼前，目前還是猶抱琵琶半遮面的狀態(tài)～大家最關(guān)心的多 server 下任務(wù)如何避免重復(fù)調(diào)度、多 server 如何實現(xiàn)水平的能力擴(kuò)展本文都沒有詳細(xì)提及，只是簡單說了幾個字。具體的內(nèi)容，就放在下一篇文章講啦～提前劇透一下吧，核心就四個字：分組隔離。等不及的話，自己去代碼中尋找答案吧，少年～

PowerJob 項目地址：

https://github.com/KFCFans/PowerJob

總結(jié)

以上是生活随笔為你收集整理的每天九点十分开始每半小时一次执行一个cron_趣讲 PowerJob 超强大的调度层，开始表演真正的技术了...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。