一、圖調度框架簡介

1.1 vivo效果廣告預估服務

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

異步調用已成為系統設計中的主流方法。雖然異步調度提升了系統性能，提升了資源的利用率，但卻對系統的可擴展性和可維護性提出了挑戰。回憶歷史中用過的異步管理方法有以下三種。

• 面向過程方法
• 樹調度
• 有限有向圖管理

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

樹調度方法，使得異步調度進入框架調控的新階段。可擴展性方面較面向過程的方法要好很多。但樹結構不能準確描述復雜服務的調用流程。

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

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

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

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

二、分支路徑圖調度框架的實現

全路徑圖調度框架具體有什么痛點，逼迫讓我們去尋找新的方法。具體原因就在這里，有限有向圖在落地實踐中，使用skip狀態變量約束路徑。系統在處理一次任務的過程中，不經過的路徑上的所有節點狀態都會被設置為skip。

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

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

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

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

三、在vivo 效果廣告推薦系統中的落地過程

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

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

當圖與實時在線系統融合在一起的時候，我們發現了分支路徑圖調度框架更多的提升空間。比如，圖的整體的超時、異常管理，圖中節點的超時、異常管理，以及復雜圖結構的自動化簡，會成為我們以后進一步升級的空間。

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