面向高維度的機器學(xué)習(xí)的計算框架-Angel

為支持超大維度機器學(xué)習(xí)模型運算，騰訊數(shù)據(jù)平臺部與香港科技大學(xué)合作開發(fā)了面向機器學(xué)習(xí)的分布式計算框架——Angel 1.0。

Angel是使用Java語言開發(fā)的專有機器學(xué)習(xí)計算系統(tǒng)，用戶可以像用Spark, MapReduce一樣，用它來完成機器學(xué)習(xí)的模型訓(xùn)練。Angel已經(jīng)支持了SGD、ADMM優(yōu)化算法，同時我們也提供了一些常用的機器學(xué)習(xí)模型；但是如果用戶有自定義需求，也可以在我們提供的最優(yōu)化算法上層比較容易地封裝模型。

Angel應(yīng)用香港科技大學(xué)的Chukonu 作為網(wǎng)絡(luò)解決方案， 在高維度機器學(xué)習(xí)的參數(shù)更新過程中，有針對性地給滯后的計算任務(wù)的參數(shù)傳遞提速，整體上縮短機器學(xué)習(xí)算法的運算時間。這一創(chuàng)新采用了香港科技大學(xué)陳凱教授及其研究小組開發(fā)的可感知上層應(yīng)用（Application-aware）的網(wǎng)絡(luò)優(yōu)化方案，以及楊強教授領(lǐng)導(dǎo)的的大規(guī)模機器學(xué)習(xí)研究方案。

另外，北京大學(xué)崔斌教授及其學(xué)生也共同參與了Angel項目的研發(fā)。

在實際的生產(chǎn)任務(wù)中，Angel在千萬級到億級的特征緯度條件下運行SGD，性能是成熟的開源系統(tǒng)Spark的數(shù)倍到數(shù)十倍不等。Angel已經(jīng)在騰訊視頻推薦、廣點通等精準推薦業(yè)務(wù)上實際應(yīng)用，目前我們正在擴大在騰訊內(nèi)部的應(yīng)用范圍，目標是支持騰訊等企業(yè)級大規(guī)模機器學(xué)習(xí)任務(wù)。

整體架構(gòu)

Angel在整體架構(gòu)上參考了谷歌的DistBelief。DistBeilef最初是為深度學(xué)習(xí)而設(shè)計，它使用了參數(shù)服務(wù)器，以解決巨大模型在訓(xùn)練時的更新問題。參數(shù)服務(wù)器同樣可用于機器學(xué)習(xí)中非深度學(xué)習(xí)的模型，如SGD、ADMM、LBFGS的優(yōu)化算法在面臨在每輪迭代上億個參數(shù)更新的場景中，需要參數(shù)分布式緩存來拓展性能。Angel在運算中支持BSP、SSP、ASP三種計算模型，其中SSP是由卡耐基梅隆大學(xué)EricXing在Petuum項目中驗證的計算模型，能在機器學(xué)習(xí)的這種特定運算場景下提升縮短收斂時間。系統(tǒng)有五個角色:

Master：負責(zé)資源申請和分配，以及任務(wù)的管理。

Task：負責(zé)任務(wù)的執(zhí)行，以線程的形式存在。

Worker：獨立進程運行于Yarn的Container中，是Task的執(zhí)行容器。

ParameterServer：隨著一個任務(wù)的啟動而生成，任務(wù)結(jié)束而銷毀，負責(zé)在該任務(wù)訓(xùn)練過程中的參數(shù)的更新和存儲。

WorkerGroup為一個虛擬概念，由若干個Worker組成，元數(shù)據(jù)由Master維護。為模型并行拓展而考慮，在一個WorkerGroup內(nèi)所有Worker運行的訓(xùn)練數(shù)據(jù)都是一樣的。雖然我們提供了一些通用模型，但并不保證都滿足需求，而用戶自定義的模型實現(xiàn)可以實現(xiàn)我們的通用接口，形式上等同于MapReduce或Spark。

1）用戶友好

1. 自動化數(shù)據(jù)切分: Angel系統(tǒng)為用戶提供了自動切分訓(xùn)練數(shù)據(jù)的功能，方便用戶進行數(shù)據(jù)并行運算：系統(tǒng)默認兼容了Hadoop FS接口，原始訓(xùn)練樣本存儲在支持Hadoop FS接口的分布式文件系統(tǒng)如HDFS、Tachyon。

2. 豐富的數(shù)據(jù)管理：樣本數(shù)據(jù)存儲在分布式文件系統(tǒng)中，系統(tǒng)在計算前從文件系統(tǒng)讀取到計算進程，放在緩存在內(nèi)存中以加速迭代運算；如果內(nèi)存中緩存不下的數(shù)據(jù)則暫存到本地磁盤，不需要向分布式文件系統(tǒng)再次發(fā)起通訊請求。

3. 豐富的線性代數(shù)及優(yōu)化算法庫: Angel更提供了高效的向量及矩陣運算庫（稀疏/稠密），方便了用戶自由選擇數(shù)據(jù)、參數(shù)的表達形式。在優(yōu)化算法方面，Angel已實現(xiàn)了SGD、ADMM；模型方面，支持了Latent DirichletAllocation (LDA)、MatrixFactorization (MF)、LogisticRegression (LR) 、Support Vector Machine(SVM) 等。

4. 可選擇的計算模型:綜述中我們提到了，Angel的參數(shù)服務(wù)器可以支持BSP，SSP，ASP計算模型。

5. 更細粒度的容錯:在系統(tǒng)中容錯主要分為Master的容錯，參數(shù)服務(wù)器的容災(zāi)，Worker進程內(nèi)的參數(shù)快照的緩存，RPC調(diào)用的容錯。

6. 友好的任務(wù)運行及監(jiān)控: Angel也具有友好的任務(wù)運行方式，支持基于Yarn的任務(wù)運行模式。同時，Angel的Web App頁面也方便了用戶查看集群進度。

2）參數(shù)服務(wù)器

在實際的生產(chǎn)環(huán)境中，可以直觀的感受到Spark的Driver單點更新參數(shù)和廣播的瓶頸，雖然可以通過線性拓展來減少計算時的耗時，但是帶來了收斂性下降的問題，同時更嚴重的是在數(shù)據(jù)并行的運算過程中，由于每個Executor都保持一個完整的參數(shù)快照，線性拓展帶來了N x 參數(shù)快照的流量，而這個流量集中到了Driver一個節(jié)點上！

從圖中看到，在機器學(xué)習(xí)任務(wù)中，Spark即使有更多的機器資源也無法利用，機器只在特定較少的規(guī)模下才能發(fā)揮最佳性能，但是這個最佳性能其實也并不理想。

采用參數(shù)服務(wù)器方案，我們與Spark做了如下比較：在有5000萬條訓(xùn)練樣本的數(shù)據(jù)集上，采用SGD解的邏輯回歸模型，使用10個工作節(jié)點(Worker)，針對不同維度的特征逐一進行了每輪迭代時間和整體收斂時間的比較（這里Angel使用的是BSP模式）。

通過數(shù)據(jù)可見，模型越大Angel對比Spark的優(yōu)勢就越明顯。

3）內(nèi)存優(yōu)化

在運算過程中為減少內(nèi)存消耗和提升單進程內(nèi)運算收斂性使用了異步無鎖的Hogwild! 模式。同一個運算進程中的N個Task如果在運算中都各自保持一個獨立的參數(shù)快照，對參數(shù)的內(nèi)存開銷就N倍，模型維度越大時消耗越明顯！SGD的優(yōu)化算法中，實際場景中，訓(xùn)練數(shù)據(jù)絕大多數(shù)情況下是稀疏的，因此參數(shù)更新沖突的概率就大大降低了，即便沖突了梯度也不完全是往差的方向發(fā)展，畢竟都是朝著梯度下降的方向更新的。我們使用了Hogwild!模式之后，讓多個Task在一個進程內(nèi)共享同一個參數(shù)快照，減少內(nèi)存消耗并提升了收斂速度。

4）網(wǎng)絡(luò)優(yōu)化

我們有兩個主要優(yōu)化點：

1）進程內(nèi)的Task運算之后的參數(shù)更新合并之后平滑的推送到參數(shù)服務(wù)器更新，這減少了Task所在機器的上行消耗，也減少了參數(shù)服務(wù)器的下行消耗，同時減少在推送更新的過程中的峰值瓶頸次數(shù)；

2）針對SSP進行更深一步的網(wǎng)絡(luò)優(yōu)化：由于SSP是一種半同步的運算協(xié)調(diào)機制，在有限的窗口運行訓(xùn)練，快的節(jié)點達到窗口邊緣時，任務(wù)就必須停下來等待最慢的節(jié)點更新最新的參數(shù)。針對這一問題，我們通過網(wǎng)絡(luò)流量的再分配來加速較慢的工作節(jié)點。我們給較慢的節(jié)點以更高的帶寬；相應(yīng)的，快的工作節(jié)點就分得更少的帶寬。這樣一來，快的節(jié)點和慢的節(jié)點的迭代次數(shù)的差距就得以控制，減少了窗口被突破（發(fā)生等待）的概率，也就是減少了工作節(jié)點由于SSP窗口而空閑等待時間。

如下圖所示，在1億維度、迭代30輪的效果評測中，可以看到Chukonu使得累積的空閑等待時間大幅度減少，達3.79倍。

下圖展示的是優(yōu)化前后的執(zhí)行時間，以5000萬維度的模型為例，20個工作節(jié)點和10個參數(shù)服務(wù)器，Staleness=5，執(zhí)行30輪迭代?？梢钥闯觯_啟Chukonu后平均每輪的完成時間只需7.97秒，相比于比原始的任務(wù)平均每輪9.2秒有了15%的提升。

另外，針對性加速慢的節(jié)點可以使慢的節(jié)點更大可能的獲得最新的參數(shù)，因此對比原始的SSP計算模型，算法收斂性得到了提升。下圖所示，同樣是針對五千萬維度的模型在SSP下的效果評測，原生的Angel任務(wù)在30輪迭代后（276秒）loss達到了0.0697，而開啟了Chukonu后，在第19輪迭代（145秒）就已達到更低的loss。從這種特定場景來看有一個接近90%的收斂速度提升。

后續(xù)計劃

未來，項目組將擴大應(yīng)用的規(guī)模，同時，項目組已經(jīng)在繼續(xù)研發(fā)Angel的下一版本，下一個版本會在模型并行方面做一些深入的優(yōu)化。另外，項目組正在計劃把Angel進行開源，我們會在后續(xù)合適的時機進行公開。