論文標題：
Ekko: A Large-Scale Deep Learning Recommender System with Low-Latency Model Update
收錄會議：
OSDI2022
論文鏈接：
https://www.usenix.org/system/files/osdi22-sima.pdf
基於深度學習的推薦系統（Deep Learning Recommender System, DLRS）是眾多大型技術公司和組織的關鍵基礎設施。一個典型的 DLRS 架構如下圖所示，它通常包含了大量參數服務器以支撐眾多的機器學習模型，例如嵌入特徵表、深度神經網絡。這些參數服務器在不同地區的數據中心進行備份，從而和處於全球不同地區的用戶進行容錯、低延遲的通信。
為了保證對新用戶和新內容進行快速服務，DLRS 必須持續地更新機器學習模型。這一過程首先利用訓練服務器收集新的訓練數據，並計算模型梯度；接着利用廣域網將模型更新傳播到各個參數服務器的備份模型。
大規模 DLRS 需要為十億級別的用戶提供服務，因此必須實現關於延遲指標的服務級別目標（Service-Level Objective, SLO），例如將一個新上傳內容提供給用戶的延遲時間。並且，DLRS 在模型更新方面需要滿足一些新的低延遲需求，從而應對以下實際場景中的新因素、最好地實現 SLO：
1. 最近的 DLRS 應用，例如 YouTube、抖音，使用戶能夠生產海量的短視頻、文章、圖片內容。這些內容需要在幾分鐘、甚至幾秒內提供給其他用戶；
2. 如 GDPR 等數據保護法規允許 DLRS 用戶進行匿名，而匿名用戶的行為必須進行在線學習；
3. 實際生產中越來越多的機器學習模型，例如強化學習，被用於提升應用的推薦質量。這些模型需要進行持續的在線更新，以達到最佳模型效果。
不幸的是，實現上述低延遲模型更新在現有的 DLRS 中極其困難。現有系統通過離線方法進行模型更新：採集新訓練數據後，離線對模型參數計算梯度，驗證模型檢查點（checkpoint），將模型更新傳輸到所有數據中心。這樣的離線流程需要花費長達數小時進行模型更新。一個替代方法是使用廣域網優化的機器學習系統，或聯邦學習系統。這些系統使用本地收集的數據更新模型，並 lazy 同步到重複的模型副本中。但 lazy 同步技術不可避免地造成相當程度的異步更新，這通常對系統實現 SLO 造成一定的負面影響。
本文希望探索一種 DLRS 系統設計方案，能夠在不降低 SLO 的前提下實現低延遲的模型更新。本文的關鍵思想是允許訓練服務器在線更新模型並立即將模型更新傳輸到所有模型推理集群。這一設計允許我們繞過離線訓練、模型檢查、驗證、傳播等高延遲步驟，從而減少模型更新延遲。
為了實現這一設計，我們需要解決以下幾個關鍵挑戰：1）面對帶寬限制、異構網絡結構等問題，怎樣基於廣域網高效地傳輸模型更新；2）當發生網絡擁塞、關鍵模型更新傳輸發生延遲時，怎樣保證 SLO 的實現；3）怎樣處理對模型準確率有害的有偏（biased）模型更新，以保證 SLO 的實現。
應對上述問題和挑戰，本文實現了 Ekko 系統，一個創新的大規模 DLRS，能夠全局地更新模型備份並實現低延遲。Ekko 系統設計的主要貢獻包括以下兩個方面：1. 高效點對點模型更新傳輸。現有參數服務器通常採用 primary-backup replication 數據備份協議進行模型更新。然而當面對海量模型更新，這一協議由於高更新延遲和 leader 瓶頸，出現擴展性不足的問題。為了解決這一問題，我們探索性地進行了點對點模型更新傳輸。我們針對分布於不同地理位置的 DLRS 設計了一種高效的無日誌基於狀態的同步算法。由於模型更新常常關注於部分熱點參數，因此這一算法能夠只傳輸最近的模型參數版本（即狀態）進行有效 DLRS 更新。Ekko 允許參數服務器高效地通過點對點方式找出模型狀態的差別。針對這一點，我們採取了如下設計：模型更新緩存，允許參數服務器高效地追蹤並比對模型狀態；共享版本，在對比模型狀態時顯著降低網絡帶寬開銷；廣域網優化的傳輸拓撲，允許參數服務器優先採用帶寬寬裕的DC內網路徑，而不是採用帶寬緊張的 DC 間網絡路徑。2. SLO 保護機制。Ekko 允許模型更新在不進行離線模型驗證的情況下到達模型推理集群。這樣的設計方案使得一些 SLO 面對網絡擁塞和有偏更新十分脆弱，特別是那些和新鮮度以及推薦質量相關的 SLO。應對網絡擁塞，我們設計了一種面向 SLO 的模型更新調度算法。這一算法通過計算各類 SLO 相關指標進行調度，包括新鮮度優先級、更新顯著性優先級、模型優先級。這些指標用於預測模型更新對 SLO 造成的影響，從而使調度算法能夠再現計算各個模型更新的優先級。我們在不改變 Ekko 點對點模型更新傳輸這一分散架構的前提下，將這一調度算法整合到參數服務器中。應對有偏模型更新，Ekko 採用了一種創新的推理模型狀態管理算法。管理算法對每組推理模型創建一個基線方法。這一基線方法只接受少量的用戶流量，作為推理模型的基準。管理算法持續地監控基線方法和推理模型在關於質量的 SLO 上的表現。當有偏模型更新對推理模型狀態產生負面影響時，管理算法通知見證服務器（witness server）將模型狀態進行回滾。
Ekko 是一個地理分散的 DLRS，它在中心化的數據中心進行模型更新，然後將更新的模型傳輸到地理分散的數據中心，從而更接近分布於全球的平台用戶。Ekko 將模型劃分為多個碎片，並存儲在鍵值對（key-value pair）中。存儲碎片的鍵值對集合被稱為參數倉庫，參數倉庫通過哈希映射為模型碎片分配鍵值對。此外，模型大小常常隨時間變化，因為模型經常需要整合新的商品和特徵。Ekko 通過基於軟件的路由方法，將參數請求對應至模型碎片。在訓練 DC 網絡中，路由算法為模型碎片指定對應的參數服務器，並且這一過程引入了碎片管理算法，對不同參數請求進行負載均衡。
Ekko 的整體系統架構設計如下圖所示。其中包含幾個特點：
1. 針對參數服務器的高效點對點模型更新，這一模型更新算法避免了核心的訓練數據中心廣播更新模型，而是利用所有網絡通路進行高吞吐量的點對點更新。這一做法不使用中心化的協調算法，每個數據中心能夠獨立地選擇最優間隔進行模型更新同步；
2. 基於面向 SLO 的模型更新調度算法，Ekko 支持同時大規模模型更新，調度算法選擇所有更新中最有利於實現 SLO 的模型更新進行網絡資源分配；
3. 基於模型狀態管理算法，Ekko 能夠通過計算 SLO 相關的模型推理指標，保護模型推理服務器免受有偏模型更新的影響。
Ekko 的高效點對點模型更新機制應當滿足以下幾個目標：
1. Ekko 需要協調數千個分布於全球的參數服務器完成每次參數更新。為了避免出現網絡延遲造成的掉隊服務器，我們設計了一種無日誌的參數服務器同步方法；
2. 作為一個共享的 DLRS，Ekko 需要支持數千個機器學習模型。這些模型可能以高達十億級別每秒的速度產生海量的線上更新。為了支持這一點，Ekko 的參數服務器能夠通過點對點方式高效地發現模型更新，並在不使用大量計算和網絡資源的情況下獲取更新；
3. Ekko 需要支持地理分散部署，這通常涉及廣域網之間的異構網絡架構，和服務器或網絡錯誤。針對這一點，Ekko 的系統設計能夠提升廣域網發送模型更新的吞吐量並降低延遲，同時容錯服務器和網絡錯誤。
下圖展示了 Ekko 進行點對點模型更新時涉及的系統模塊和步驟。假設我們希望對圖中碎片 1（shard 1）對兩個副本（replica 1 和 replica 2）進行更新。和所有其他模型碎片一樣，碎片 1 包括了：碎片知識（shard knowledge），為對參數更新的總結；更新緩存（update cache），基於參數版本對最近的模型更新進行追蹤；碎片版本（shard version），能夠用於判斷該碎片是否可能需要進行參數同步。碎片知識、更新緩存和碎片版本共同加速了不同參數服務器之間的參數同步過程。
為了完成模型更新，副本 2 從副本 1 中請求最近修改的碎片版本。收到請求後，副本 1 返回最近修改碎片版本的列表，副本 2 隨機將副本 1 的所有碎片版本與本地版本進行對比，並發送相關的碎片知識給副本 1。最終，副本 1 發送所有更新的參數給副本 2。通過這些步驟，Ekko 能夠保證模型更新最終能低延遲地傳輸到所有副本，並保持最終一致性。
在實際的 DLRS 運行過程中，我們發現最終一致性是可以接受的。即便深度神經網絡的不同副本可能在一小段時間中出現差異，他們通常表現出相近、甚至完全一致的模型推理結果。這是因為深度神經網絡通常用浮點數表示模型參數，在只有少量參數數值差別的情況下，模型副本一般會產生相近的預測結果。
為了追蹤模型參數狀態，Ekko 給每個鍵值對（即模型參數碎片）分配了一個參數版本，包含一個不重複的副本編號，和一個基於物理時間的時間戳。為了保證同一個副本上的參數版本不出現重複，Ekko 對物理時間戳額外擴充了一個計數器。值得注意的是，相對於邏輯時間戳，在分布式 DLRS 中使用物理時間戳十分重要。當需要進行回滾時，物理時間戳可以確認不同副本中更新版本之間的先後順序，從而保證更好的模型更新不會被覆蓋。
在對參數版本進行標記後，Ekko 需要決定如何對不同副本進行同步。我們觀察到一個 DLRS 通常會覆蓋之前的參數，並只將最後一次參數狀態寫入。我們因此決定只發送最後一個版本的參數。
Ekko 需要決定副本間同步的時間間隔。我們可以使用一種基於日誌的同步算法，這些算法選擇一個同步間隔，使得模型更新的發送頻率不會超過網絡中最慢連接的帶寬。然而這些算法使得網絡中的很多連接不能得到充分利用。更重要的是，這種算法常常造成掉隊服務器（straggler），顯著增加了同步延遲，使參數服務器更容易因為回滾而保持陳舊的參數狀態。因此，我們想要在參數服務器中實現一種無日誌的參數同步方法，使這些服務器可以根據和其他節點間的帶寬動態地選擇同步間隔。
我們提出使用碎片知識來實現無日誌參數同步。在每個副本中，所有碎片維護一個對應的碎片知識，它通過版本向量實現，總結了他們所學到的參數更新。碎片數據反映了一個空白的碎片，採用來自其他副本進行參數更新的狀態。
為了減少參數同步對參數服務器造成的額外開銷，Ekko 採用參數更新緩存和碎片版本控制來實現高效副本間參數同步。由於模型碎片包含了大量參數，簡單地便利所有參數來回應每個同步請求可能會造成較大的計算開銷。
針對這一問題，我們設計了參數更新緩存來減少參數同步的計算開銷。這種設計基於我們在 DLRS 中觀察到的稀疏性和時間局部性特點。不像稠密深度神經網絡的訓練那樣，DLRS 中每次模型更新只針對模型參數的子集（即參數更新的稀疏性）。例如，在我們實際運行的 DLRS 中，每小時僅有 3.08% 的模型參數進行了更新。此外，在一個時間窗口中，通常會重複更新模型的特定參數（即時間局部性）。這是因為 DLRS 通常存在潮流商品和用戶，對應的參數會在短時間內進行大量更新。
除了參數更新緩存，我們採用碎片版本維護來捕捉碎片數據和副本之間的因果關係。碎片版本中包括了一個單調遞增的不重複計數器，以及與這一版本相關的副本 id。基於這一碎片版本維護機制，副本間可以通過交換和對比碎片版本列表，確認哪些碎片可能需要更新，從而高效地尋找各個副本中需要更新的模型碎片。
Ekko 允許直接將模型更新傳輸至模型推理集群中的參數服務器，這對完成推薦服務的 SLO 造成了兩大挑戰：1）網絡擁塞可能造成重要模型更新延後送達；2）基於小批量訓練的模型更新可能由於數據中的 bias 產生負面模型預測效果。
1. 新鮮度，這一指標衡量為新內容和新用戶提供模型推理服務的延遲性。這一 SLO 對線上推薦服務至關重要，特別是例如抖音和 YouTube 這樣和用戶進行實時交互的平台應用。這類應用需要及時捕捉用戶的實時交互行為和潮流商品的實時狀況，否則用戶很容易因失去興趣而離開推薦平台。提升新鮮度通常會導致更好的用戶體驗，並能夠更快地對新內容進行更合適的曝光；
2. 質量 SLO，這一指標衡量對用戶體驗和參與度，例如推薦視頻中用戶點擊對數量、用戶觀看時長，反映了對用戶偏好預測的準確情況。下圖展示了 DLRS 中一個模型推理服務器的工作流程。
為了防止新鮮度和質量 SLO 同時被網絡擁塞影響，Ekko 採用一種面向 SLO 的模型更新調度算法，並將其整合進點對點模型更新傳輸過程中。具體來說，Ekko 使用如下幾個指標去衡量每個模型更新的優先級，並根據優先級分配網絡資源進行傳輸：
1. 更新新鮮度優先級，這一優先級指標是基於在實際生產中的觀察而設計的。如果一個參數最近被創建，則該參數擁有較高優先級，否則它的優先級較低。這是由於，新創建的模型參數相對於過去一段時間的模型參數，通常對模型推理效果產生更大對影響；
2. 更新顯著性優先級，我們使用模型更新梯度的大小來衡量該參數是否被顯著更新。具體來說，我們使用模型參數的 1 範數模除以平均值。這種做法直觀上可以反映模型參數被更新的顯著程度；
3. 模型優先級，在 DLRS 中不同模型通常收到不同頻率的預測請求，這反映了他們在滿足整體 SLO 中的不同重要程度。基於這一點，Ekko 優先分配網絡資源給具有較多更新的模型。
Ekko 使用一種推理模型狀態管理算法來防止 SLO 由於有害的模型更新受到影響。這一管理算法監控推理模型的健康（即質量 SLO）並根據需求進行低延遲的模型狀態回滾。
對於一個 DLRS 系統，Ekko 為它的所有推理模型創建基線模型，基線模型對少量用戶流量（通常<1%）進行處理，並且不需要保證其訓練數據的時效性。基於普通推理模型和基線模型的用戶預測各類指標，Ekko 的狀態管理器通過異常檢測算法判斷當前模型狀態是否健康。管理算法的判斷包含三種情況：健康、不健康、或不確定，當管理算法確定當前模型狀態不健康時，會重定向當前用戶請求到備選推理模型，並發起一次模型狀態回滾。
Ekko 採用見證服務器對不健康模型狀態進行回滾。見證服務器參與副本同本，但不參與模型訓練。與參數服務器不同，見證服務器不會立即將更新的參數儲存進參數倉庫，並且不會在同步中運行優先級調度。具體來說，Ekko 將未存儲的參數更新插入日誌中，每篇日誌與同步的物理時間戳對應。當短時間內有多個同步操作時，Ekko 對其進行合併以節省空間。下圖展示了回滾模型狀態的工作過程。
本文對 Ekko 系統進行了測試台測試和實際生產環境驗證。測試台環境為一個包括 30 台服務器的集群，我們將每三個服務器組成一個數據中心，以模擬多數據中心場景。其中一個數據中心被用於訓練，從訓練服務器中接受模型更新，其他數據中心作為推理服務器。
本文在一個同構廣域網上測試了 Ekko 的更新延遲性，對比方法為常用於同步模型更新的 Adam 方法。下圖展示了在不同數據中心數量多情況下，Ekko 和 Adam 多延遲秒數。從結果中可以看出，Ekko 相對於 Adam 取得了明顯更低的延遲，這主要歸因於 Ekko 具有較強擴展能力的點對點同步架構。同時，對比與另一個基線系統 Checkpoint-Boradcast，在基於廣域網進行 4GB 參數同步時，基線方法相對於 Ekko 花費了 7 秒更多的延遲時間。
同時，本文也在異構廣域網上進行了實驗，對比 Ekko 系統和 Adam 系統在不同同步機器數量的情況下的延遲時間，實驗效果如下所示，同樣驗證了 Ekko 的低延遲性能。
為了進一步探究 Ekko 進行同步時各個模塊的單獨時間開銷，我們進一步分解模型模塊，以驗證其對 Ekko 低延遲性能的貢獻，結果如下圖所示。首先，我們構建了一個只使用碎片知識的 Ekko 系統，在下圖中標記為 VV。之後，我們分別在這一基線模型基礎上添加更新緩存（+Cache）、碎片版本（+Shared）以及廣域網優化（+WAN-opt）。從下圖結果中可以看出各個模塊對降低同步延遲的作用。
針對 Ekko 的 SLO 保護機制，我們進一步測試了在網絡擁塞情況下 Ekko 的延遲狀況和 SLO 相關指標。實驗通過 A/B 測試進行，Ekko 在降低同步流量的同時，保持了顯著參數更新的延遲性。同時，控制組在基於 SLO 的指標中下降了 2.32%。這一結果驗證了 Ekko 的 SLO 保護機制的有效性。
本文提出了 Ekko，一個創新的深度學習推薦系統，能夠低延遲地進行大規模模型參數更新。Ekko 包括一個高效的點對點更新算法，能夠協調十億級別的模型更新，進行高效傳輸至地理分散數據中心的副本。它進一步設計了一種 SLO 保護機制，能夠保護模型狀態不受網絡擁塞和有害模型更新的影響。實驗結果顯示 Ekko 能夠大幅降低深度學習推薦系統的延遲，驗證了其創新設計的有效性。
🔍
現在，在「知乎」也能找到我們了
進入知乎首頁搜索「PaperWeekly」
點擊「關注」訂閱我們的專欄吧
留言列表