自從google發(fā)表著名的GFS、MapReduce、BigTable三篇paper以后，互聯(lián)網(wǎng)正式迎來了大數(shù)據(jù)時(shí)代。大數(shù)據(jù)的顯著特點(diǎn)是大，哪里都大的大。本篇主要針對(duì)volume大的數(shù)據(jù)時(shí)，使用機(jī)器學(xué)習(xí)來進(jìn)行數(shù)據(jù)處理過程中遇到的架構(gòu)方面的問題做一個(gè)系統(tǒng)的梳理。

有了GFS我們有能力積累海量的數(shù)據(jù)樣本，比如在線廣告的曝光和點(diǎn)擊數(shù)據(jù)，天然具有正負(fù)樣本的特性，累積一兩個(gè)月往往就能輕松獲得百億、千億級(jí)的訓(xùn)練樣本。這樣海量的樣本如何存儲(chǔ)？用什么樣的模型可以學(xué)習(xí)海量樣本中有用的pattern？這些問題不止是工程問題，也值得每個(gè)做算法的同學(xué)去深入思考。

1.1簡(jiǎn)單模型or復(fù)雜模型

在深度學(xué)習(xí)概念提出之前，算法工程師手頭能用的工具其實(shí)并不多，就LR、SVM、感知機(jī)等寥寥可數(shù)、相對(duì)固定的若干個(gè)模型和算法；那時(shí)候要解決一個(gè)實(shí)際的問題，算法工程師更多的工作主要是在特征工程方面。而特征工程本身并沒有很系統(tǒng)化的指導(dǎo)理論（至少目前沒有看到系統(tǒng)介紹特征工程的書籍），所以很多時(shí)候特征的構(gòu)造技法顯得光怪陸離，是否有用也取決于問題本身、數(shù)據(jù)樣本、模型以及運(yùn)氣。

在特征工程作為算法工程師主要工作內(nèi)容的時(shí)候，構(gòu)造新特征的嘗試往往很大部分都不能在實(shí)際工作中work。據(jù)我了解，國內(nèi)幾家大公司在特征構(gòu)造方面的成功率在后期一般不會(huì)超過20%。也就是80%的新構(gòu)造特征往往并沒什么正向提升效果。如果給這種方式起一個(gè)名字的話，大概是簡(jiǎn)單模型+復(fù)雜特征；簡(jiǎn)單模型說的是算法比如LR、SVM本身并不服務(wù)，參數(shù)和表達(dá)能力基本呈現(xiàn)一種線性關(guān)系，易于理解。復(fù)雜特征則是指特征工程方面不斷嘗試使用各種奇技淫巧構(gòu)造的可能有用、可能沒用的特征，這部分特征的構(gòu)造方式可能會(huì)有各種trick，比如窗口滑動(dòng)、離散化、歸一化、開方、平方、笛卡爾積、多重笛卡爾積等等；順便提一句，因?yàn)樘卣鞴こ瘫旧聿]有特別系統(tǒng)的理論和總結(jié)，所以初入行的同學(xué)想要構(gòu)造特征就需要多讀paper，特別是和自己業(yè)務(wù)場(chǎng)景一樣或類似的場(chǎng)景的paper，從里面學(xué)習(xí)作者分析、理解數(shù)據(jù)的方法以及對(duì)應(yīng)的構(gòu)造特征的技法；久而久之，有望形成自己的知識(shí)體系。

深度學(xué)習(xí)概念提出以后，人們發(fā)現(xiàn)通過深度神經(jīng)網(wǎng)絡(luò)可以進(jìn)行一定程度的表示學(xué)習(xí)（representation learning），例如在圖像領(lǐng)域，通過CNN提取圖像feature并在此基礎(chǔ)上進(jìn)行分類的方法，一舉打破了之前算法的天花板，而且是以極大的差距打破。這給所有算法工程師帶來了新的思路，既然深度學(xué)習(xí)本身有提取特征的能力，干嘛還要苦哈哈的自己去做人工特征設(shè)計(jì)呢？

深度學(xué)習(xí)雖然一定程度上緩解了特征工程的壓力，但這里要強(qiáng)調(diào)兩點(diǎn)：1.緩解并不等于徹底解決，除了圖像這種特定領(lǐng)域，在個(gè)性化推薦等領(lǐng)域，深度學(xué)習(xí)目前還沒有完全取得絕對(duì)的優(yōu)勢(shì)；究其原因，可能還是數(shù)據(jù)自身內(nèi)在結(jié)構(gòu)的問題，使得在其他領(lǐng)域目前還沒有發(fā)現(xiàn)類似圖像+CNN這樣的完美CP。2.深度學(xué)習(xí)在緩解特征工程的同時(shí)，也帶來了模型復(fù)雜、不可解釋的問題。算法工程師在網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)方面一樣要花很多心思來提升效果。概括起來，深度學(xué)習(xí)代表的簡(jiǎn)單特征+復(fù)雜模型是解決實(shí)際問題的另一種方式。

兩種模式孰優(yōu)孰劣還難有定論，以點(diǎn)擊率預(yù)測(cè)為例，在計(jì)算廣告領(lǐng)域往往以海量特征+LR為主流，根據(jù)VC維理論，LR的表達(dá)能力和特征個(gè)數(shù)成正比，因此海量的feature也完全可以使LR擁有足夠的描述能力。而在個(gè)性化推薦領(lǐng)域，深度學(xué)習(xí)剛剛萌芽，目前google play采用了WDL的結(jié)構(gòu)[1]，youtube采用了雙重DNN的結(jié)構(gòu)[2]。

不管是那種模式，當(dāng)模型足夠龐大的時(shí)候，都會(huì)出現(xiàn)模型參數(shù)一臺(tái)機(jī)器無法存放的情況。比如百億級(jí)feature的LR對(duì)應(yīng)的權(quán)重w有好幾十個(gè)G，這在很多單機(jī)上存儲(chǔ)都是困難的，大規(guī)模神經(jīng)網(wǎng)絡(luò)則更復(fù)雜，不僅難以單機(jī)存儲(chǔ)，而且參數(shù)和參數(shù)之間還有邏輯上的強(qiáng)依賴；要對(duì)超大規(guī)模的模型進(jìn)行訓(xùn)練勢(shì)必要借用分布式系統(tǒng)的技法，本文主要是系統(tǒng)總結(jié)這方面的一些思路。

1.2數(shù)據(jù)并行vs模型并行

數(shù)據(jù)并行和模型并行是理解大規(guī)模機(jī)器學(xué)習(xí)框架的基礎(chǔ)概念，其緣起未深究，第一次看到是在姐夫（Jeff Dean）的blog里，當(dāng)時(shí)匆匆一瞥，以為自己懂了。多年以后，再次開始調(diào)研這個(gè)問題的時(shí)候才想起長者的教訓(xùn)，年輕人啊，還是圖樣，圖森破。如果你和我一樣曾經(jīng)忽略過這個(gè)概念，今天不放復(fù)習(xí)一下。

這兩個(gè)概念在[3]中沐帥曾經(jīng)給出了一個(gè)非常直觀而經(jīng)典的解釋，可惜不知道什么原因，當(dāng)我想引用時(shí)卻發(fā)現(xiàn)已經(jīng)被刪除了。我在這里簡(jiǎn)單介紹下這個(gè)比喻：如果要修兩棟樓，有一個(gè)工程隊(duì)，怎么操作？第一個(gè)方案是將人分成兩組，分別蓋樓，改好了就裝修；第二種做法是一組人蓋樓，等第一棟樓蓋好，另一組裝修第一棟，然后第一組繼續(xù)蓋第二棟樓，改完以后等裝修隊(duì)裝修第二棟樓。咋一看，第二種方法似乎并行度并不高，但第一種方案需要每個(gè)工程人員都擁有“蓋樓”和“裝修”兩種能力，而第二個(gè)方案只需要每個(gè)人擁有其中一種能力即可。第一個(gè)方案和數(shù)據(jù)并行類似，第二個(gè)方案則道出了模型并行的精髓。
數(shù)據(jù)并行理解起來比較簡(jiǎn)單，當(dāng)樣本比較多的時(shí)候，為了使用所有樣本來訓(xùn)練模型，我們不妨把數(shù)據(jù)分布到不同的機(jī)器上，然后每臺(tái)機(jī)器都來對(duì)模型參數(shù)進(jìn)行迭代，如下圖所示

?

圖片取材于TensorFlow的paper[4]，圖中ABC代表三臺(tái)不同的機(jī)器，上面存儲(chǔ)著不同的樣本，模型P在各臺(tái)機(jī)器上計(jì)算對(duì)應(yīng)的增量，然后在參數(shù)存儲(chǔ)的機(jī)器上進(jìn)行匯總和更新，這就是數(shù)據(jù)并行。先忽略synchronous，這是同步機(jī)制相關(guān)的概念，在第三節(jié)會(huì)有專門介紹。

數(shù)據(jù)并行概念簡(jiǎn)單，而且不依賴于具體的模型，因此數(shù)據(jù)并行機(jī)制可以作為框架的一種基礎(chǔ)功能，對(duì)所有算法都生效。與之不同的是，模型并行因?yàn)閰?shù)間存在依賴關(guān)系（其實(shí)數(shù)據(jù)并行參數(shù)更新也可能會(huì)依賴所有的參數(shù)，但區(qū)別在于往往是依賴于上一個(gè)迭代的全量參數(shù)。而模型并行往往是同一個(gè)迭代內(nèi)的參數(shù)之間有強(qiáng)依賴關(guān)系，比如DNN網(wǎng)絡(luò)的不同層之間的參數(shù)依照BP算法形成的先后依賴），無法類比數(shù)據(jù)并行這樣直接將模型參數(shù)分片而破壞其依賴關(guān)系，所以模型并行不僅要對(duì)模型分片，同時(shí)需要調(diào)度器來控制參數(shù)間的依賴關(guān)系。而每個(gè)模型的依賴關(guān)系往往并不同，所以模型并行的調(diào)度器因模型而異，較難做到完全通用。關(guān)于這個(gè)問題，CMU的Erix Xing在[5]中有所介紹，感興趣的可以參考。

模型并行的問題定義可以參考姐夫的[6]，這篇paper也是tensorflow的前身相關(guān)的總結(jié)，其中圖

?

解釋了模型并行的物理圖景，當(dāng)一個(gè)超大神經(jīng)網(wǎng)絡(luò)無法存儲(chǔ)在一臺(tái)機(jī)器上時(shí)，我們可以切割網(wǎng)絡(luò)存到不同的機(jī)器上，但是為了保持不同參數(shù)分片之間的依賴，如圖中粗黑線的部分，則需要在不同的機(jī)器之間進(jìn)行concurrent控制；同一個(gè)機(jī)器內(nèi)部的參數(shù)依賴，即途中細(xì)黑線部分在機(jī)器內(nèi)即可完成控制。

黑線部分如何有效控制呢？如下圖所示

在將模型切分到不同機(jī)器以后，我們將參數(shù)和樣本一起在不同機(jī)器間流轉(zhuǎn)，圖中ABC代表模型的不同部分的參數(shù)；假設(shè)C依賴B，B依賴A，機(jī)器1上得到A的一個(gè)迭代后，將A和必要的樣本信息一起傳到機(jī)器2，機(jī)器2根據(jù)A和樣本對(duì)P2更新得到，以此類推；當(dāng)機(jī)器2計(jì)算B的時(shí)候，機(jī)器1可以展開A的第二個(gè)迭代的計(jì)算。了解CPU流水線操作的同學(xué)一定感到熟悉，是的，模型并行是通過數(shù)據(jù)流水線來實(shí)現(xiàn)并行的。想想那個(gè)蓋樓的第二種方案，就能理解模型并行的精髓了。

?

上圖則是對(duì)控制模型參數(shù)依賴的調(diào)度器的一個(gè)示意圖，實(shí)際框架中一般都會(huì)用DAG（有向無環(huán)圖）調(diào)度技術(shù)來實(shí)現(xiàn)類似功能，未深入研究，以后有機(jī)會(huì)再補(bǔ)充說明。

理解了數(shù)據(jù)并行和模型并行對(duì)后面參數(shù)服務(wù)器的理解至關(guān)重要，但現(xiàn)在讓我先蕩開一筆，簡(jiǎn)單介紹下并行計(jì)算框架的一些背景信息。

2. 并行算法演進(jìn)

2.1 MapReduce路線

從函數(shù)式編程中的受到啟發(fā)，google發(fā)布了MapReduce[7]的分布式計(jì)算方式；通過將任務(wù)切分成多個(gè)疊加的Map+Reduce任務(wù)，來完成復(fù)雜的計(jì)算任務(wù)，示意圖如下

?

MapReduce的主要問題有兩個(gè)，一是原語的語義過于低級(jí)，直接使用其來寫復(fù)雜算法，開發(fā)量比較大；另一個(gè)問題是依賴于磁盤進(jìn)行數(shù)據(jù)傳遞，性能跟不上業(yè)務(wù)需求。

為了解決MapReduce的兩個(gè)問題，Matei在[8]中提出了一種新的數(shù)據(jù)結(jié)構(gòu)RDD，并構(gòu)建了Spark框架。Spark框架在MR語義之上封裝了DAG調(diào)度器，極大降低了算法使用的門檻。較長時(shí)間內(nèi)spark幾乎可以說是大規(guī)模機(jī)器學(xué)習(xí)的代表，直至后來沐帥的參數(shù)服務(wù)器進(jìn)一步開拓了大規(guī)模機(jī)器學(xué)習(xí)的領(lǐng)域以后，spark才暴露出一點(diǎn)點(diǎn)不足。如下圖

從圖中可以看出，spark框架以Driver為核心，任務(wù)調(diào)度和參數(shù)匯總都在driver，而driver是單機(jī)結(jié)構(gòu)，所以spark的瓶頸非常明顯，就在Driver這里。當(dāng)模型規(guī)模大到一臺(tái)機(jī)器存不下的時(shí)候，Spark就無法正常運(yùn)行了。所以從今天的眼光來看，Spark只能稱為一個(gè)中等規(guī)模的機(jī)器學(xué)習(xí)框架。劇透一句，公司開源的Angel通過修改Driver的底層協(xié)議將Spark擴(kuò)展到了一個(gè)高一層的境界。后面還會(huì)再詳細(xì)介紹這部分。

MapReduce不僅是一個(gè)框架，還是一種思想，google開創(chuàng)性的工作為我們找到了大數(shù)據(jù)分析的一個(gè)可行方向，時(shí)至今日，仍不過時(shí)。只是逐漸從業(yè)務(wù)層下沉到底層語義應(yīng)該處于的框架下層。

2.2 MPI技術(shù)

沐帥在[9]中對(duì)MPI的前景做了簡(jiǎn)要介紹；和Spark不同，MPI是類似socket的一種系統(tǒng)通信API，只是支持了消息廣播等功能。因?yàn)閷?duì)MPI研究不深入，這里簡(jiǎn)單介紹下優(yōu)點(diǎn)和缺點(diǎn)吧；優(yōu)點(diǎn)是系統(tǒng)級(jí)支持，性能杠杠的；缺點(diǎn)也比較多，一是和MR一樣因?yàn)樵Z過于低級(jí)，用MPI寫算法，往往代碼量比較大。另一方面是基于MPI的集群，如果某個(gè)任務(wù)失敗，往往需要重啟整個(gè)集群，而MPI集群的任務(wù)成功率并不高。阿里在[10]中給出了下圖：

?

從圖中可以看出，MPI作業(yè)失敗的幾率接近五成。MPI也并不是完全沒有可取之處，正如沐帥所說，在超算集群上還是有場(chǎng)景的。對(duì)于工業(yè)屆依賴于云計(jì)算、依賴于commodity計(jì)算機(jī)來說，則顯得性價(jià)比不夠高。當(dāng)然如果在參數(shù)服務(wù)器的框架下，對(duì)單組worker再使用MPI未嘗不是個(gè)好的嘗試，[10]的鯤鵬系統(tǒng)正式這么設(shè)計(jì)的。

3. 參數(shù)服務(wù)器演進(jìn)

3.1 歷史演進(jìn)

沐帥在[12]中將參數(shù)服務(wù)器的歷史劃分為三個(gè)階段，第一代參數(shù)服務(wù)器萌芽于沐帥的導(dǎo)師Smola的[11]，如下圖所示：

?

這個(gè)工作中僅僅引入memcached來存放key-value數(shù)據(jù)，不同的處理進(jìn)程并行對(duì)其進(jìn)行處理。[13]中也有類似的想法，第二代參數(shù)服務(wù)器叫application-specific參數(shù)服務(wù)器，主要針對(duì)特定應(yīng)用而開發(fā)，其中最典型的代表應(yīng)該是tensorflow的前身[6]。

第三代參數(shù)服務(wù)器，也即是通用參數(shù)服務(wù)器框架是由百度少帥李沐正式提出的，和前兩代不同，第三代參數(shù)服務(wù)器從設(shè)計(jì)上就是作為一個(gè)通用大規(guī)模機(jī)器學(xué)習(xí)框架來定位的。要擺脫具體應(yīng)用、算法的束縛，做一個(gè)通用的大規(guī)模機(jī)器學(xué)習(xí)框架，首先就要定義好框架的功能；而所謂框架，往往就是把大量重復(fù)的、瑣碎的、做了一次就不想再來第二次的臟活、累活進(jìn)行良好而優(yōu)雅的封裝，讓使用框架的人可以只關(guān)注與自己的核心邏輯。第三代參數(shù)服務(wù)器要對(duì)那些功能進(jìn)行封裝呢？沐帥總結(jié)了這幾點(diǎn)，我照搬如下：

1）高效的網(wǎng)絡(luò)通信：因?yàn)椴还苁悄Ｐ瓦€是樣本都十分巨大，因此對(duì)網(wǎng)絡(luò)通信的高效支持以及高配的網(wǎng)絡(luò)設(shè)備都是大規(guī)模機(jī)器學(xué)習(xí)系統(tǒng)不可缺少的；

2）靈活的一致性模型：不同的一致性模型其實(shí)是在模型收斂速度和集群計(jì)算量之間做tradeoff；要理解這個(gè)概念需要對(duì)模型性能的評(píng)價(jià)做些分析，暫且留到下節(jié)再介紹。

3）彈性可擴(kuò)展：顯而易見

4）容災(zāi)容錯(cuò)：大規(guī)模集群協(xié)作進(jìn)行計(jì)算任務(wù)的時(shí)候，出現(xiàn)Straggler或者機(jī)器故障是非常常見的事，因此系統(tǒng)設(shè)計(jì)本身就要考慮到應(yīng)對(duì)；沒有故障的時(shí)候，也可能因?yàn)閷?duì)任務(wù)時(shí)效性要求的變化而隨時(shí)更改集群的機(jī)器配置。這也需要框架能在不影響任務(wù)的情況下能做到機(jī)器的熱插拔。

5）易用性：主要針對(duì)使用框架進(jìn)行算法調(diào)優(yōu)的工程師而言，顯然，一個(gè)難用的框架是沒有生命力的。

在正式介紹第三代參數(shù)服務(wù)器的主要技術(shù)之前，先從另一個(gè)角度來看下大規(guī)模機(jī)器學(xué)習(xí)框架的演進(jìn)

這張圖可以看出，在參數(shù)服務(wù)器出來之前，人們已經(jīng)做了多方面的并行嘗試，不過往往只是針對(duì)某個(gè)特定算法或特定領(lǐng)域，比如YahooLDA是針對(duì)LDA算法的。當(dāng)模型參數(shù)突破十億以后，則可以看出參數(shù)服務(wù)器一統(tǒng)江湖，再無敵手。

首先我們看看第三代參數(shù)服務(wù)器的基本架構(gòu)

?

上圖的resource manager可以先放一放，因?yàn)閷?shí)際系統(tǒng)中這部分往往是復(fù)用現(xiàn)有的資源管理系統(tǒng)，比如yarn或者mesos；底下的training data毋庸置疑的需要類似GFS的分布式文件系統(tǒng)的支持；剩下的部分就是參數(shù)服務(wù)器的核心組件了。

圖中畫了一個(gè)server group和三個(gè)worker group；實(shí)際應(yīng)用中往往也是類似，server group用一個(gè)，而worker group按需配置；server manager是server group中的管理節(jié)點(diǎn)，一般不會(huì)有什么邏輯，只有當(dāng)有server node加入或退出的時(shí)候，為了維持一致性哈希而做一些調(diào)整。

Worker group中的task schedule則是一個(gè)簡(jiǎn)單的任務(wù)協(xié)調(diào)器，一個(gè)具體任務(wù)運(yùn)行的時(shí)候，task schedule負(fù)責(zé)通知每個(gè)worker加載自己對(duì)應(yīng)的數(shù)據(jù)，然后去server node上拉取一個(gè)要更新的參數(shù)分片，用本地?cái)?shù)據(jù)樣本計(jì)算參數(shù)分片對(duì)應(yīng)的變化量，然后同步給server node；server node在收到本機(jī)負(fù)責(zé)的參數(shù)分片對(duì)應(yīng)的所有worker的更新后，對(duì)參數(shù)分片做一次update。

?

如圖所示，不同的worker同時(shí)并行運(yùn)算的時(shí)候，可能因?yàn)榫W(wǎng)絡(luò)、機(jī)器配置等外界原因，導(dǎo)致不同的worker的進(jìn)度是不一樣的，如何控制worker的同步機(jī)制是一個(gè)比較重要的課題。詳見下節(jié)分解。

3.2同步協(xié)議

本節(jié)假設(shè)讀者已經(jīng)對(duì)隨機(jī)梯度優(yōu)化算法比較熟悉，如果不熟悉的同學(xué)請(qǐng)參考吳恩達(dá)經(jīng)典課程機(jī)器學(xué)習(xí)中對(duì)SGD的介紹，或者我之前多次推薦過的書籍《最優(yōu)化導(dǎo)論》。

我們先看一個(gè)單機(jī)算法的運(yùn)行過程，假設(shè)一個(gè)模型的參數(shù)切分成三個(gè)分片k1，k2，k3；比如你可以假設(shè)是一個(gè)邏輯回歸算法的權(quán)重向量被分成三段。我們將訓(xùn)練樣本集合也切分成三個(gè)分片s1，s2，s3；在單機(jī)運(yùn)行的情況下，我們假設(shè)運(yùn)行的序列是（k1，s1）、（k2，s1）、（k3、s1）、（k1、s2）、（k2、s2）、（k3、s2）。。?？疵靼琢藛幔烤褪羌僭O(shè)先用s1中的樣本一次對(duì)參數(shù)分片k1、k2、k3進(jìn)行訓(xùn)練，然后換s2；這就是典型的單機(jī)運(yùn)行的情況，而我們知道這樣的運(yùn)行序列最后算法會(huì)收斂。

現(xiàn)在我們開始并行化，假設(shè)k1、k2、k3分布在三個(gè)server node上，s1、s2、s3分布在三個(gè)worker上，這時(shí)候如果我們還要保持之前的計(jì)算順序，則會(huì)變成怎樣？work1計(jì)算的時(shí)候，work2和worker3只能等待，同樣worker2計(jì)算的時(shí)候，worker1和work3都得等待，以此類推；可以看出這樣的并行化并沒有提升性能；但是也算簡(jiǎn)單解決了超大規(guī)模模型的存儲(chǔ)問題。

為了解決性能的問題，業(yè)界開始探索這里的一致性模型，最先出來的版本是前面提到的[11]中的ASP模式，就是完全不顧worker之間的順序，每個(gè)worker按照自己的節(jié)奏走，跑完一個(gè)迭代就update，然后繼續(xù)，這應(yīng)該是大規(guī)模機(jī)器學(xué)習(xí)中的freestyle了，如圖所示

?

ASP的優(yōu)勢(shì)是最大限度利用了集群的計(jì)算能力，所有的worker所在的機(jī)器都不用等待，但缺點(diǎn)也顯而易見，除了少數(shù)幾個(gè)模型，比如LDA，ASP協(xié)議可能導(dǎo)致模型無法收斂。也就是SGD徹底跑飛了，梯度不知道飛到哪里去了。

在ASP之后提出了另一種相對(duì)極端的同步協(xié)議BSP，spark用的就是這種方式，如圖所示

?

每個(gè)worker都必須在同一個(gè)迭代運(yùn)行，只有一個(gè)迭代任務(wù)所有的worker都完成了，才會(huì)進(jìn)行一次worker和server之間的同步和分片更新。這個(gè)算法和嚴(yán)格一直的算法非常類似，區(qū)別僅僅在于單機(jī)版本的batch size在BSP的時(shí)候變成了有所有worker的單個(gè)batch size求和得到的總的butch size替換。毫無疑問，BSP的模式和單機(jī)串行因?yàn)閮H僅是batch size的區(qū)別，所以在模型收斂性上是完全一樣的。同時(shí)，因?yàn)槊總€(gè)worker在一個(gè)周期內(nèi)是可以并行計(jì)算的，所以有了一定的并行能力。

以此協(xié)議為基礎(chǔ)的spark在很長時(shí)間內(nèi)成為機(jī)器學(xué)習(xí)領(lǐng)域?qū)嶋H的霸主，不是沒有理由的。此種協(xié)議的缺陷之處在于，整個(gè)worker group的性能由其中最慢的worker決定；這個(gè)worker一般稱為straggler。讀過GFS文章的同學(xué)應(yīng)該都知道straggler的存在是非常普遍的現(xiàn)象。

能否將ASP和BSP做一下折中呢？答案當(dāng)然是可以的，這就是目前我認(rèn)為最好的同步協(xié)議SSP；SSP的思路其實(shí)很簡(jiǎn)單，既然ASP是允許不同worker之間的迭代次數(shù)間隔任意大，而BSP則只允許為0，那我是否可以取一個(gè)常數(shù)s？如圖所示

?

不同的worker之間允許有迭代的間隔，但這個(gè)間隔數(shù)不允許超出一個(gè)指定的數(shù)值s，圖中s=3.

SSP協(xié)議的詳細(xì)介紹參見[14]，CMU的大拿Eric Xing在其中詳細(xì)介紹了SSP的定義，以及其收斂性的保證。理論推導(dǎo)證明常數(shù)s不等于無窮大的情況下，算法一定可以在若干次迭代以后進(jìn)入收斂狀態(tài)。其實(shí)在Eric提出理論證明之前，工業(yè)界已經(jīng)這么嘗試過了：）

順便提一句，考察分布式算法的性能，一般會(huì)分為statistical performance和hard performance來看。前者指不同的同步協(xié)議導(dǎo)致算法收斂需要的迭代次數(shù)的多少，后者是單次迭代所對(duì)應(yīng)的耗時(shí)。兩者的關(guān)系和precision\recall關(guān)系類似，就不贅述了。有了SSP，BSP就可以通過指定s=0而得到。而ASP同樣可以通過制定s=∞來達(dá)到。

3.3核心技術(shù)

除了參數(shù)服務(wù)器的架構(gòu)、同步協(xié)議之外，本節(jié)再對(duì)其他技術(shù)做一個(gè)簡(jiǎn)要的介紹，詳細(xì)的了解請(qǐng)直接閱讀沐帥的博士論文和相關(guān)發(fā)表的論文。

熱備、冷備技術(shù)：為了防止server node掛掉，導(dǎo)致任務(wù)中斷，可以采用兩個(gè)技術(shù)，一個(gè)是對(duì)參數(shù)分片進(jìn)行熱備，每個(gè)分片存儲(chǔ)在三個(gè)不同的server node中，以master-slave的形式存活。如果master掛掉，可以快速從slave獲取并重啟相關(guān)task。

除了熱備，還可以定時(shí)寫入checkpoint文件到分布式文件系統(tǒng)來對(duì)參數(shù)分片及其狀態(tài)進(jìn)行備份。進(jìn)一步保證其安全性。

Server node管理：可以使用一致性哈希技術(shù)來解決server node的加入和退出問題，如圖所示

?

當(dāng)有server node加入或退出的時(shí)候，server manager負(fù)責(zé)對(duì)參數(shù)進(jìn)行重新分片或者合并。注意在對(duì)參數(shù)進(jìn)行分片管理的情況下，一個(gè)分片只需要一把鎖，這大大提升了系統(tǒng)的性能，也是參數(shù)服務(wù)器可以實(shí)用的一個(gè)關(guān)鍵點(diǎn)。

4. 大規(guī)模機(jī)器學(xué)習(xí)的四重境界

到這里可以回到我們的標(biāo)題了，大規(guī)模機(jī)器學(xué)習(xí)的四重境界到底是什么呢？

這四重境界的劃分是作者個(gè)人閱讀總結(jié)的一種想法，并不是業(yè)界標(biāo)準(zhǔn)，僅供大家參考。

境界1：參數(shù)可單機(jī)存儲(chǔ)和更新

此種境界較為簡(jiǎn)單，但仍可以使用參數(shù)服務(wù)器，通過數(shù)據(jù)并行來加速模型的訓(xùn)練。

境界2：參數(shù)不可單機(jī)存儲(chǔ)，可以單機(jī)更新

此種情況對(duì)應(yīng)的是一些簡(jiǎn)單模型，比如sparse logistic regression；當(dāng)feature的數(shù)量突破百億的時(shí)候，LR的權(quán)重參數(shù)不太可能在一臺(tái)機(jī)器上完全存下，此時(shí)必須使用參數(shù)服務(wù)器架構(gòu)對(duì)模型參數(shù)進(jìn)行分片。但是注意一點(diǎn)，SGD的更新公式

w’=w-α，其中可以分開到單個(gè)維度進(jìn)行計(jì)算，但是單個(gè)維度的wi=f(w)xi

這里的f(w)表示是全部參數(shù)w的一個(gè)函數(shù)，具體推倒比較簡(jiǎn)單，這里篇幅所限就不贅述了。只是想說明worker在計(jì)算梯度的時(shí)候可能需要使用到上一輪迭代的所有參數(shù)。而我們之所以對(duì)參數(shù)進(jìn)行分片就是因?yàn)槲覀儫o法將所有參數(shù)存放到一臺(tái)機(jī)器，現(xiàn)在單個(gè)worker有需要使用所有的參數(shù)才能計(jì)算某個(gè)參數(shù)分片的梯度，這不是矛盾嗎？可能嗎？

答案是可能的，因?yàn)閱蝹€(gè)樣本的feature具有很高的稀疏性（sparseness）。例如一個(gè)百億feature的模型，單個(gè)訓(xùn)練樣本往往只在其中很小一部分feature上有取值，其他都為0（假設(shè)feature取值都已經(jīng)離散化了）。因此計(jì)算f(w)的時(shí)候可以只拉取不為0的feature對(duì)應(yīng)的那部分w即可。有文章統(tǒng)計(jì)一般這個(gè)級(jí)別的系統(tǒng)，稀疏性往往在0.1%（or 0.01%，記得不是很準(zhǔn)，大致這樣）以下。這樣的稀疏性，可以讓單機(jī)沒有任何阻礙的計(jì)算f(w)。

目前公司開源的angel和AILab正在做的系統(tǒng)都處于這個(gè)境界。而原生spark還沒有達(dá)到這個(gè)境界，只能在中小規(guī)模的圈子里廝混。Angel改造的基于Angel的Spark則達(dá)到了這個(gè)境界。

境界3：參數(shù)不可單機(jī)存儲(chǔ)，不可單機(jī)更新，但無需模型并行

境界3順延境界2二來，當(dāng)百億級(jí)feature且feature比較稠密的時(shí)候，就需要計(jì)算框架進(jìn)入到這層境界了，此時(shí)單個(gè)worker的能力有限，無法完整加載一個(gè)樣本，也無法完整計(jì)算f(w)。怎么辦呢？其實(shí)很簡(jiǎn)單，學(xué)過線性代數(shù)的都知道，矩陣可以分塊。向量是最簡(jiǎn)單的矩陣，自然可以切成一段一段的來計(jì)算。只是調(diào)度器需要支持算符分段而已了。

境界4：參數(shù)不可單機(jī)存儲(chǔ)，不可單機(jī)更新，需要模型并行

進(jìn)入到這個(gè)層次的計(jì)算框架，可以算是世界一流了?？梢蕴幚沓笠?guī)模的神經(jīng)網(wǎng)絡(luò)。這也是最典型的應(yīng)用場(chǎng)景。此時(shí)不僅模型的參數(shù)不能單機(jī)存儲(chǔ)，而且同一個(gè)迭代內(nèi)，模型參數(shù)之間還有強(qiáng)的依賴關(guān)系，可以參見姐夫?qū)istbelief的介紹里的模型切分。

此時(shí)首先需要增加一個(gè)coordinator組件來進(jìn)行模型并行的concurrent控制。同時(shí)參數(shù)服務(wù)器框架需要支持namespace切分，coordinator將依賴關(guān)系通過namespace來進(jìn)行表示。

一般參數(shù)間的依賴關(guān)系因模型而已，所以較難抽象出通用的coordinator來，而必須以某種形式通過腳本parser來生產(chǎn)整個(gè)計(jì)算任務(wù)的DAG圖，然后通過DAG調(diào)度器來完成。對(duì)這個(gè)問題的介紹可以參考Erix Xing的分享[5]。

Tensorflow

目前業(yè)界比較知名的深度學(xué)習(xí)框架有Caffee、MXNet、Torch、Keras、Theano等，但目前最炙手可熱的應(yīng)該是google發(fā)布的Tensorflow。這里單獨(dú)拿出來稍微分解下。

前面不少圖片引自此文，從TF的論文來看，TF框架本身是支持模型并行和數(shù)據(jù)并行的，內(nèi)置了一個(gè)參數(shù)服務(wù)器模塊，但從開源版本所曝光的API來看，TF無法用來10B級(jí)別feature的稀疏LR模型。原因是已經(jīng)曝光的API只支持在神經(jīng)網(wǎng)絡(luò)的不同層和層間進(jìn)行參數(shù)切分，而超大規(guī)模LR可以看做一個(gè)神經(jīng)單元，TF不支持單個(gè)神經(jīng)單元參數(shù)切分到多個(gè)參數(shù)服務(wù)器node上。

當(dāng)然，以google的實(shí)力，絕對(duì)是可以做到第四重境界的，之所以沒有曝光，可能是基于其他商業(yè)目的的考量，比如使用他們的云計(jì)算服務(wù)。

綜上，個(gè)人認(rèn)為如果能做到第四重境界，目前可以說的上是世界一流的大規(guī)模機(jī)器學(xué)習(xí)框架。僅從沐帥的ppt里看他曾經(jīng)達(dá)到過，google內(nèi)部應(yīng)該也是沒有問題的。第三重境界應(yīng)該是國內(nèi)一流，第二充應(yīng)該是國內(nèi)前列吧。

5. 其他

5.1 資源管理

本文沒有涉及到的部分是資源管理，大規(guī)模機(jī)器學(xué)習(xí)框架部署的集群往往資源消耗也比較大，需要專門的資源管理工具來維護(hù)。這方面yarn和mesos都是佼佼者，細(xì)節(jié)這里也就不介紹了。

5.2 設(shè)備

除了資源管理工具，本身部署大規(guī)模機(jī)器學(xué)習(xí)集群本身對(duì)硬件也還是有些要求的，雖然理論上來說，所有commodity機(jī)器都可以用來搭建這類集群，但是考慮到性能，我們建議盡量用高內(nèi)存的機(jī)器+萬兆及以上的網(wǎng)卡。沒有超快速的網(wǎng)卡，玩參數(shù)傳遞和樣本加載估計(jì)會(huì)比較苦逼。

6. 結(jié)語

從后臺(tái)轉(zhuǎn)算法以來，長期沉浸于算法推理的論文無法自拔，對(duì)自己之前的后臺(tái)工程能力漸漸輕視起來，覺得工程對(duì)算法的幫助不大。直到最近一個(gè)契機(jī)，需要做一個(gè)這方面的調(diào)研，才豁然發(fā)現(xiàn)，之前的工程經(jīng)驗(yàn)對(duì)我理解大規(guī)模機(jī)器學(xué)習(xí)框架非常有用，果然如李宗盛所說，人生每一步路，都不是白走的。

在一個(gè)月左右的調(diào)研中，腦子每天都充斥這各種疑問和困惑，曾經(jīng)半夜4點(diǎn)醒來，思考同步機(jī)制而再也睡不著，干脆起來躲衛(wèi)生間看書，而那天我一點(diǎn)多才睡。當(dāng)腦子里有放不下的問題的時(shí)候，整個(gè)人會(huì)處于一種非常亢奮的狀態(tài)，除非徹底想清楚這個(gè)問題，否則失眠是必然的，上一次這種狀態(tài)已經(jīng)是很多年前了。好在最后我總算理清了這方面的所有關(guān)鍵細(xì)節(jié)。以此，記之。Carbon zhang于2017年8月26日凌晨！

致謝

感謝wills、janwang、joey、roberty、suzi等同學(xué)一起討論，特別感謝burness在TF方面的深厚造詣和調(diào)研。因?yàn)楸救怂剿?，錯(cuò)漏難免，另外還有相當(dāng)多的細(xì)節(jié)因?yàn)槠拗撇⑽匆灰徽归_，僅僅是從較高抽象層面上簡(jiǎn)述了下大規(guī)模機(jī)器學(xué)習(xí)框架的關(guān)鍵思路，其他如分片向量鎖、通信協(xié)議、時(shí)鐘邏輯、DAG調(diào)度器、資源調(diào)度模塊等均為展開來講，希望以后有機(jī)會(huì)能補(bǔ)上。

引用

1. Wide& Deep Learning for Recommender Systems

2. Deep Neural Networks for YouTube Recommendations
3. https://www.zhihu.com/question/53851014

4. TensorFlow:Large-Scale Machine Learning on Heterogeneous Distributed Systems

5.

6. Large Scale Distributed Deep Networks

7. MapReduce: Simplified Data Processing on Large
Clusters

8. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing

9. https://www.zhihu.com/question/55119470

10. KunPeng:Parameter Server based Distributed Learning Systems and Its Applications in
Alibaba and Ant Financial

11. An Architecture for Parallel Topic Models

12. Scaling Distributed Machine Learning with the Parameter Server

13. Piccolo:Building fast, distributed pro- grams with partitioned tables

14. More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server

15. Angel-A Flexible and Powerful Parameter Server；黃明ppt

原文鏈接： https://zhuanlan.zhihu.com/p/29968773