DCAF: A Dynamic Computation Allocation Framework for Online Serving System
論文地址：https://arxiv.org/pdf/2006.09684.pdf
來源：DLP-KDD 2020 阿里巴巴論文

摘要

現代大規模在線廣告推薦系統的目標是有限資源的情況下最大化其收益（比如GMV）。通常的解決辦法是用多階段級聯架構來解決，比如增加召回，粗排，精排階段來解決。每一階段的數目根據計算力來人為分配。這種方案很容易陷入計算力的局部最優點的情況，另外從請求的緯度來講，每個請求的價值其實是不一樣的，但是都用了同樣的計算力，其實是可以優化的。
本文的方法會對不同的請求，根據其價值個性化的給予算力。我們將其問題抽象成為了背包問題，并將這個架構稱為DCAF。DCAF能在給定計算資源的情況下，獲得最大收益。目前已經在淘寶廣告上線了，在同等效果情況下，機器資源節省了20%。

引言

淘寶網的流量很大，以及在特定時候會有尖峰（例如雙十一），那么過去的解決辦法：
（1） 推薦架構采用多階段級聯架構，根據經驗去調整每一層的數目。
（2） 設計多層的降級手段，在突發情況的時候，手動開啟降級。

這些解決辦法存在一些問題：
（1） 缺乏靈活性，往往需要人工手動干預
（2） 降級策略一視同仁，價值高的請求和價值低的請求，會被用以同樣的計算力。
那么里面顯然能看到一個簡單且有效的方案：為了使得總收益最大，我們可以降級低價值請求，將資源傾斜給高價值請求。

根據以上的問題，DCAF最主要的貢獻是：
（1） “個性化”的給予每個請求不同的算力。
（2） 追求總價值最大；且能夠在請求量突發的情況下，保持穩定。
（3） 能夠帶來機器資源的節省。同樣的效果下，淘寶廣告降低了20%的GPU消耗。
（4） DCAF提高了推薦系統穩定性的天花板（吐槽。。。）

FORMULATION

將該問題抽象成為背包問題。
假設現在有N個請求{i=1....N}，請求都需要在 T 時間內預估完成。每個請求我們能選擇M個行為{j=1,...,M}。（可以理解為，每個行為就是針對每個請求采用的不同算力）
qj定義為進行第j個行為的花費。（由廣告系統的engine來統計）
Qij定義為第i個請求進行第j個行為的收益。（與qij成正比例，廣告系統為eCPM）
C表示總的計算資源。
xij表示我們對于第i個請求采用第j個行為，顯然我們對于每一個請求，只能選擇其中一個行為。
每次廣告預估下，對于每個請求，我們只能選擇其中一個行為，那么整體的問題公式就可以抽象為：

這個公式也會存在一些其他問題：
（1） 請求量在實時變化，所以該背包問題也需要實時計算。
（2） Qij是未知的，所以需要實時且有效的計算；另外還得足夠輕的計算。

METHODOLOGY

推導

如何求解這個問題，我們先將背包問題用拉格朗日松弛：

其對偶函數為：
分析該函數，因為xij >= 0，所以對于xij是一個向下的線性函數，故只會在

的時候xij會取1。
那么函數也可以轉化為：

因為μ與其對偶目標是負相關，那么對于μ而言的全局最優解為：

因此對于xij的全局最優解為：

求解

為了求解拉格朗日乘子，提出一些假設：
（1） Qij是隨著j增大而增大的。
（2） Qij/qj是隨著j增大而減小的。
那么根據其假設，我們可以得到結論：
（1） 對于每個i，如果Qij1/qj1 > Qij2/qj2，那么λ1 ≥ λ2
（2） max(sigma(xijQij))和sigma(xijqj)都會隨著λ增大而減小。
最后我們可以得到用二分法來計算λ，從而得到每個i的最優action j

得到其二分法的計算方案：

另外：Qij的預估，我們會用4類特征進行預估：用戶畫像，用戶行為，上下文特征，系統狀態。

架構

分為兩部分，在線決策部分，離線預估部分。

在線部分

每個模塊的介紹：
Information Collection and Monitoring：收集系統狀態，包含CPU，GPU，運行時間，錯誤率等。
Request Value Estimation：用以模型計算Qij，該階段的模型要求輕量級，用了部分其他模型的上下文特征。
Policy Execution：通過類似PID系統，來給予每個請求i的最優行為j。具體操作如下：

離線部分

Lagrange Multiplier Solver：用以計算全局λ，流程：
（1） 每次離線log獲取N個請求，每個請求都帶有Qij，qj以及C。
（2） 用當前的系統情況來調整C
（3） 通過二分搜索來得到λ

Expected Gain Estimator：計算收益Qij，廣告領域為ctr*bid(廣告主出價） = eCPM，所以需要訓練一個CTR模型，來得到Qij。這里定期更新，然后提供給Policy Execution來使用。

實驗

離線實驗

同消耗情況下，DCAF的ecpm + 3.7%
同效果情況下，DCAF的資源節省49%
在用隨機策略的情況下，同機器的情況下，ecpm會下降36.8%。

在線實驗

todo

（1） 因為引入了user profile，所以不可避免的會影響到部分用戶的體驗，如何優化“Fairness”
（2） DCAF僅考慮了推薦流程的單一階段，未考慮全流程，未來需要實現全鏈路最優。