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

語言: CN / TW / HK

作者:

vivo 互聯網AI團隊- Liu Zuocheng、Zhou Baojian



本文根據周保建老師在“2022 vivo開發者大會"現場演講內容整理而成。公眾號回覆【2022 VDC】獲取互聯網技術分會場議題相關資料。



使用基於有限有向圖的調度框架,可以控制在線服務中異步調度的流程,但這對分支路徑的管理不夠友好,隨着節點增多,調度流程會越來越複雜而難以控制。因此我們實現了支持分支路徑的圖調度框架,解決普通圖調度框架可擴展性差的問題。


一、圖調度框架簡介


1.1 vivo效果廣告預估服務



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


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

  • 面向過程方法

  • 樹調度

  • 有限有向圖管理



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


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


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


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




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


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


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



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


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



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



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


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



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


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


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



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


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




END

猜你喜歡

本文分享自微信公眾號 - vivo互聯網技術(vivoVMIC)。
如有侵權,請聯繫 [email protected] 刪除。
本文參與“OSC源創計劃”,歡迎正在閲讀的你也加入,一起分享。