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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實踐是檢驗真理的唯一標準，我們再通過實際的落地過程看，分支路徑調(diào)度框架是否滿足我們的預(yù)期。

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

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

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