分支路徑圖排程框架在 vivo 效果廣告業務的落地實踐

vivo效果廣告實時線上服務是提供實時AI演算法推薦的服務。在廣告投放場景，承載了一天百億級別數量的請求，支援vivo廣告收入。在可用性、可擴充套件性等方面具有非常高的要求。服務中起到排程作用的模組，上下游依賴特別多，比如特徵服務、ABT實驗平臺、實時資料流、模型計算模組等等。排程模組在請求下游服務的方式都是採用非同步的方式。那麼我們是怎麼管理這麼多非同步請求的呢？

非同步呼叫已成為系統設計中的主流方法。雖然非同步排程提升了系統性能，提升了資源的利用率，但卻對系統的可擴充套件性和可維護性提出了挑戰。回憶歷史中用過的非同步管理方法有以下三種。

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

樹排程方法，使得非同步排程進入框架調控的新階段。可擴充套件性方面較面向過程的方法要好很多。但樹結構不能準確描述複雜服務的呼叫流程。

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

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

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

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

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

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

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

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

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

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

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

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