一、圖調(diào)度框架簡(jiǎn)介

1.1 vivo效果廣告預(yù)估服務(wù)

vivo效果廣告實(shí)時(shí)在線服務(wù)是提供實(shí)時(shí)AI算法推薦的服務(wù)。在廣告投放場(chǎng)景，承載了一天百億級(jí)別數(shù)量的請(qǐng)求，支持vivo廣告收入。在可用性、可擴(kuò)展性等方面具有非常高的要求。服務(wù)中起到調(diào)度作用的模塊，上下游依賴特別多，比如特征服務(wù)、ABT實(shí)驗(yàn)平臺(tái)、實(shí)時(shí)數(shù)據(jù)流、模型計(jì)算模塊等等。調(diào)度模塊在請(qǐng)求下游服務(wù)的方式都是采用異步的方式。那么我們是怎么管理這么多異步請(qǐng)求的呢？

異步調(diào)用已成為系統(tǒng)設(shè)計(jì)中的主流方法。雖然異步調(diào)度提升了系統(tǒng)性能，提升了資源的利用率，但卻對(duì)系統(tǒng)的可擴(kuò)展性和可維護(hù)性提出了挑戰(zhàn)?；貞洑v史中用過(guò)的異步管理方法有以下三種。

• 面向過(guò)程方法
• 樹調(diào)度
• 有限有向圖管理

單純使用面向過(guò)程的方法，簡(jiǎn)單卻粗放，隨著下游服務(wù)增多，代碼邏輯中產(chǎn)生大量的callback函數(shù)和類使，得系統(tǒng)調(diào)度過(guò)程繁雜無(wú)序，可擴(kuò)展性和可維護(hù)性變差。

樹調(diào)度方法，使得異步調(diào)度進(jìn)入框架調(diào)控的新階段。可擴(kuò)展性方面較面向過(guò)程的方法要好很多。但樹結(jié)構(gòu)不能準(zhǔn)確描述復(fù)雜服務(wù)的調(diào)用流程。

有限有向圖，是目前使用最為廣泛的方法。擴(kuò)展性較好，能管理復(fù)雜的調(diào)用流程。但這是否是一種完美的方法呢？不是的。有限有向圖，對(duì)圖中節(jié)點(diǎn)是全路徑訪問(wèn)，對(duì)分支路徑的管理不夠友好。因此我們依然要探索新的方法。

為了解釋有限有向圖在實(shí)時(shí)在線服務(wù)中的局限性，我們以vivo效果廣告預(yù)估服務(wù)的調(diào)度流程為例，進(jìn)行說(shuō)明。把調(diào)度流程經(jīng)過(guò)抽象后，調(diào)度流程如左圖一樣簡(jiǎn)潔明了，但這只是理想狀態(tài)。

那么現(xiàn)實(shí)狀況又是什么樣子的呢？大家來(lái)看，和所有的實(shí)時(shí)在線服務(wù)一樣，我們?cè)谙到y(tǒng)設(shè)計(jì)時(shí)，為了系統(tǒng)健壯，總要和大量的異常和超時(shí)做斗爭(zhēng)。并且除了異常和超時(shí)，系統(tǒng)還需要有兜底邏輯。上一個(gè)簡(jiǎn)潔明了的有限有向圖已經(jīng)不復(fù)存在。

為了進(jìn)一步說(shuō)明，有限有向圖不能完全把控在線服務(wù)中異步調(diào)度的流程。我們依據(jù)剛才展示的流程調(diào)度圖，做了一個(gè)狀態(tài)轉(zhuǎn)換圖。在這個(gè)圖中，展示了系統(tǒng)中各個(gè)狀態(tài)的流轉(zhuǎn)路徑，總數(shù)達(dá)到了7條之多。有限有向圖是一種全路徑圖調(diào)度框架，已經(jīng)難以適用復(fù)雜度不斷增長(zhǎng)的系統(tǒng)。

二、分支路徑圖調(diào)度框架的實(shí)現(xiàn)

全路徑圖調(diào)度框架具體有什么痛點(diǎn)，逼迫讓我們?nèi)ふ倚碌姆椒?。具體原因就在這里，有限有向圖在落地實(shí)踐中，使用skip狀態(tài)變量約束路徑。系統(tǒng)在處理一次任務(wù)的過(guò)程中，不經(jīng)過(guò)的路徑上的所有節(jié)點(diǎn)狀態(tài)都會(huì)被設(shè)置為skip。

全路徑的圖調(diào)度框架中，每增添一個(gè)節(jié)點(diǎn)，會(huì)導(dǎo)致：控制變量數(shù)量 +1，狀態(tài)全集 x2， 復(fù)雜度成指數(shù)增長(zhǎng)。在如此狀態(tài)下，對(duì)復(fù)雜系統(tǒng)添加流程或調(diào)整流程，就會(huì)變成工程師的噩夢(mèng)。設(shè)計(jì)開發(fā)時(shí)必須小心甚微，上線時(shí)則如履薄冰。

為了安全開發(fā)和提升迭代效率，新的調(diào)度方法被迫切地創(chuàng)建出來(lái)，那就支持分支路徑的圖調(diào)度框架。它的原理，則是在原有的圖調(diào)度框架中，添加兩處功能，一是加入了分支節(jié)點(diǎn)，二是對(duì)于圖中節(jié)點(diǎn)的觸發(fā)和激活支持“與”激活和“或”激活。是不是像極了邏輯電路呢？

大家是否有疑問(wèn)，添加兩處修改就可以了嗎？這樣做真的有效嗎？其實(shí)依據(jù)，就來(lái)自于我們的《編譯原理》里的常見概念和常見規(guī)律。

有限有向圖，是一種NFA，即不確定的有限自動(dòng)機(jī)。我們都知道，在實(shí)踐中NFA實(shí)現(xiàn)難度很大，它不如DFA簡(jiǎn)潔和簡(jiǎn)單。所以結(jié)論呼之欲出，支持分支路徑的圖調(diào)度框架，則是把圖變成DFA。我們還給它起了新名字，DDAG。

三、在vivo 效果廣告推薦系統(tǒng)中的落地過(guò)程

實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)，我們?cè)偻ㄟ^(guò)實(shí)際的落地過(guò)程看，分支路徑調(diào)度框架是否滿足我們的預(yù)期。

我們回憶一下vivo效果廣告預(yù)估服務(wù)的調(diào)度流程，那一個(gè)充滿著異常、超時(shí)、兜底邏輯的調(diào)用圖。為了便于說(shuō)明，我們把它化簡(jiǎn)了一下，變成一個(gè)流程圖，如左圖，目前它還是一個(gè)全路徑的調(diào)度圖。使用分支路徑調(diào)度框架改造后，變成右圖，圖中添加了判斷節(jié)點(diǎn)，具體路徑的走向則由判斷邏輯來(lái)控制。大量Skip的狀態(tài)控制變量依然不復(fù)存在。圖中藍(lán)、青、紅分別代表了3條路徑，讓路徑和流程一目了然。

當(dāng)圖與實(shí)時(shí)在線系統(tǒng)融合在一起的時(shí)候，我們發(fā)現(xiàn)了分支路徑圖調(diào)度框架更多的提升空間。比如，圖的整體的超時(shí)、異常管理，圖中節(jié)點(diǎn)的超時(shí)、異常管理，以及復(fù)雜圖結(jié)構(gòu)的自動(dòng)化簡(jiǎn)，會(huì)成為我們以后進(jìn)一步升級(jí)的空間。

分支路徑圖調(diào)度框架在vivo效果廣告預(yù)估服務(wù)中做了一次成功的實(shí)踐。它幫助工程師降低在開發(fā)過(guò)程中的風(fēng)險(xiǎn)，提速在項(xiàng)目中的迭代效率。讓算法預(yù)估服務(wù)的飛輪越轉(zhuǎn)越快！