Go 語言 延時(shí)任務(wù)系統(tǒng)

原文鏈接：https://chai2010.cn/advanced-go-programming-book/ch6-cloud/ch6-03-delay-job.html

6.3 延時(shí)任務(wù)系統(tǒng)

我們在做系統(tǒng)時(shí)，很多時(shí)候是處理實(shí)時(shí)的任務(wù)，請求來了馬上就處理，然后立刻給用戶以反饋。但有時(shí)也會(huì)遇到非實(shí)時(shí)的任務(wù)，比如確定的時(shí)間點(diǎn)發(fā)布重要公告?；蛘咝枰谟脩糇隽艘患虑榈?X 分鐘 / Y 小時(shí)后，對其特定動(dòng)作，比如通知、發(fā)券等等。

如果業(yè)務(wù)規(guī)模比較小，有時(shí)我們也可以通過數(shù)據(jù)庫配合輪詢來對這種任務(wù)進(jìn)行簡單處理，但上了規(guī)模的公司，自然會(huì)尋找更為普適的解決方案來解決這一類問題。

一般有兩種思路來解決這個(gè)問題：

1. 實(shí)現(xiàn)一套類似 crontab 的分布式定時(shí)任務(wù)管理系統(tǒng)。
2. 實(shí)現(xiàn)一個(gè)支持定時(shí)發(fā)送消息的消息隊(duì)列。

兩種思路進(jìn)而衍生出了一些不同的系統(tǒng)，但其本質(zhì)是差不多的。都是需要實(shí)現(xiàn)一個(gè)定時(shí)器（timer）。在單機(jī)的場景下定時(shí)器其實(shí)并不少見，例如我們在和網(wǎng)絡(luò)庫打交道的時(shí)候經(jīng)常會(huì)調(diào)用 SetReadDeadline() 函數(shù)，就是在本地創(chuàng)建了一個(gè)定時(shí)器，在到達(dá)指定的時(shí)間后，我們會(huì)收到定時(shí)器的通知，告訴我們時(shí)間已到。這時(shí)候如果讀取還沒有完成的話，就可以認(rèn)為發(fā)生了網(wǎng)絡(luò)問題，從而中斷讀取。

下面我們從定時(shí)器開始，探究延時(shí)任務(wù)系統(tǒng)的實(shí)現(xiàn)。

6.3.1 定時(shí)器的實(shí)現(xiàn)

定時(shí)器（timer）的實(shí)現(xiàn)在工業(yè)界已經(jīng)是有解的問題了。常見的就是時(shí)間堆和時(shí)間輪。

6.3.1.1 時(shí)間堆

最常見的時(shí)間堆一般用小頂堆實(shí)現(xiàn)，小頂堆其實(shí)就是一種特殊的二叉樹，見 圖 6-4

圖 6-4 二叉堆結(jié)構(gòu)

小頂堆的好處是什么呢？對于定時(shí)器來說，如果堆頂元素比當(dāng)前的時(shí)間還要大，那么說明堆內(nèi)所有元素都比當(dāng)前時(shí)間大。進(jìn)而說明這個(gè)時(shí)刻我們還沒有必要對時(shí)間堆進(jìn)行任何處理。定時(shí)檢查的時(shí)間復(fù)雜度是 O(1)。

當(dāng)我們發(fā)現(xiàn)堆頂?shù)脑匦∮诋?dāng)前時(shí)間時(shí)，那么說明可能已經(jīng)有一批事件已經(jīng)開始過期了，這時(shí)進(jìn)行正常的彈出和堆調(diào)整操作就好。每一次堆調(diào)整的時(shí)間復(fù)雜度都是 O(LgN)。

Go 自身的內(nèi)置定時(shí)器就是用時(shí)間堆來實(shí)現(xiàn)的，不過并沒有使用二叉堆，而是使用了扁平一些的四叉堆。在最近的版本中，還加了一些優(yōu)化，我們先不說優(yōu)化，先來看看四叉的小頂堆長什么樣：

圖 6-5 四叉堆結(jié)構(gòu)

小頂堆的性質(zhì)，父節(jié)點(diǎn)比其 4 個(gè)子節(jié)點(diǎn)都小，子節(jié)點(diǎn)之間沒有特別的大小關(guān)系要求。

四叉堆中元素超時(shí)和堆調(diào)整與二叉堆沒有什么本質(zhì)區(qū)別。

6.3.1.2 時(shí)間輪

圖 6-6 時(shí)間輪

用時(shí)間輪來實(shí)現(xiàn)定時(shí)器時(shí)，我們需要定義每一個(gè)格子的 “刻度”，可以將時(shí)間輪想像成一個(gè)時(shí)鐘，中心有秒針順時(shí)針轉(zhuǎn)動(dòng)。每次轉(zhuǎn)動(dòng)到一個(gè)刻度時(shí)，我們就需要去查看該刻度掛載的任務(wù)列表是否有已經(jīng)到期的任務(wù)。

從結(jié)構(gòu)上來講，時(shí)間輪和哈希表很相似，如果我們把哈希算法定義為：觸發(fā)時(shí)間 % 時(shí)間輪元素大小。那么這就是一個(gè)簡單的哈希表。在哈希沖突時(shí)，采用鏈表掛載哈希沖突的定時(shí)器。

除了這種單層時(shí)間輪，業(yè)界也有一些時(shí)間輪采用多層實(shí)現(xiàn)，這里就不再贅述了。

6.3.2 任務(wù)分發(fā)

有了基本的定時(shí)器實(shí)現(xiàn)方案，如果我們開發(fā)的是單機(jī)系統(tǒng)，那么就可以擼起袖子開干了，不過本章我們討論的是分布式，距離 “分布式” 還稍微有一些距離。

我們還需要把這些 “定時(shí)” 或是“延時(shí)”（本質(zhì)也是定時(shí)）任務(wù)分發(fā)出去。下面是一種思路：

圖 6-7 分布式任務(wù)分發(fā)

每一個(gè)實(shí)例每隔一小時(shí)，會(huì)去數(shù)據(jù)庫里把下一個(gè)小時(shí)需要處理的定時(shí)任務(wù)撈出來，撈取的時(shí)候只要取那些 task_id % shard_count = shard_id 的那些任務(wù)即可。

當(dāng)這些定時(shí)任務(wù)被觸發(fā)之后需要通知用戶側(cè)，有兩種思路：

1. 將任務(wù)被觸發(fā)的信息封裝為一條消息，發(fā)往消息隊(duì)列，由用戶側(cè)對消息隊(duì)列進(jìn)行監(jiān)聽。
2. 對用戶預(yù)先配置的回調(diào)函數(shù)進(jìn)行調(diào)用。

兩種方案各有優(yōu)缺點(diǎn)，如果采用 1，那么如果消息隊(duì)列出故障會(huì)導(dǎo)致整個(gè)系統(tǒng)不可用，當(dāng)然，現(xiàn)在的消息隊(duì)列一般也會(huì)有自身的高可用方案，大多數(shù)時(shí)候我們不用擔(dān)心這個(gè)問題。其次一般業(yè)務(wù)流程中間走消息隊(duì)列的話會(huì)導(dǎo)致延時(shí)增加，定時(shí)任務(wù)若必須在觸發(fā)后的幾十毫秒到幾百毫秒內(nèi)完成，那么采用消息隊(duì)列就會(huì)有一定的風(fēng)險(xiǎn)。如果采用 2，會(huì)加重定時(shí)任務(wù)系統(tǒng)的負(fù)擔(dān)。我們知道，單機(jī)的定時(shí)器執(zhí)行時(shí)最害怕的就是回調(diào)函數(shù)執(zhí)行時(shí)間過長，這樣會(huì)阻塞后續(xù)的任務(wù)執(zhí)行。在分布式場景下，這種憂慮依然是適用的。一個(gè)不負(fù)責(zé)任的業(yè)務(wù)回調(diào)可能就會(huì)直接拖垮整個(gè)定時(shí)任務(wù)系統(tǒng)。所以我們還要考慮在回調(diào)的基礎(chǔ)上增加經(jīng)過測試的超時(shí)時(shí)間設(shè)置，并且對由用戶填入的超時(shí)時(shí)間做慎重的審核。

6.3.3 數(shù)據(jù)再平衡和冪等考量

當(dāng)我們的任務(wù)執(zhí)行集群有機(jī)器故障時(shí)，需要對任務(wù)進(jìn)行重新分配。按照之前的求模策略，對這臺(tái)機(jī)器還沒有處理的任務(wù)進(jìn)行重新分配就比較麻煩了。如果是實(shí)際運(yùn)行的線上系統(tǒng)，還要在故障時(shí)的任務(wù)平衡方面花更多的心思。

下面給出一種思路：

我們可以參考 Elasticsearch 的數(shù)據(jù)分布設(shè)計(jì)，每份任務(wù)數(shù)據(jù)都有多個(gè)副本，這里假設(shè)兩副本，如 圖 6-8 所示：

圖 6-8 任務(wù)數(shù)據(jù)分布

一份數(shù)據(jù)雖然有兩個(gè)持有者，但持有者持有的副本會(huì)進(jìn)行區(qū)分，比如持有的是主副本還是非主副本，主副本在圖中為摸黑部分，非主副本為正常線條。

一個(gè)任務(wù)只會(huì)在持有主副本的節(jié)點(diǎn)上被執(zhí)行。

當(dāng)有機(jī)器故障時(shí)，任務(wù)數(shù)據(jù)需要進(jìn)行數(shù)據(jù)再平衡的工作，比如節(jié)點(diǎn) 1 掛了，見 圖 6-9。

圖 6-9 故障時(shí)數(shù)據(jù)分布

節(jié)點(diǎn) 1 的數(shù)據(jù)會(huì)被遷移到節(jié)點(diǎn) 2 和節(jié)點(diǎn) 3 上。

當(dāng)然，也可以用稍微復(fù)雜一些的思路，比如對集群中的節(jié)點(diǎn)進(jìn)行角色劃分，由協(xié)調(diào)節(jié)點(diǎn)來做這種故障時(shí)的任務(wù)重新分配工作，考慮到高可用，協(xié)調(diào)節(jié)點(diǎn)可能也需要有 1 至 2 個(gè)備用節(jié)點(diǎn)以防不測。

之前提到我們會(huì)用消息隊(duì)列觸發(fā)對用戶的通知，在使用消息隊(duì)列時(shí)，很多隊(duì)列是不支持 exactly once 的語義的，這種情況下我們需要讓用戶自己來負(fù)責(zé)消息的去重或者消費(fèi)的冪等處理。