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

　　1. 背景

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

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

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

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

　　在特征工程作為算法工程師主要工作內(nèi)容的時(shí)候，構(gòu)造新特征的嘗試往往很大部分都不能在實(shí)際工作中work。據(jù)我了解，國(guó)內(nèi)幾家大公司在特征構(gòu)造方面的成功率在后期一般不會(huì)超過(guò)20%。也就是80%的新構(gòu)造特征往往并沒(méi)什么正向提升效果。如果給這種方式起一個(gè)名字的話，大概是簡(jiǎn)單模型+復(fù)雜特征;簡(jiǎn)單模型說(shuō)的是算法比如LR、SVM本身并不服務(wù)，參數(shù)和表達(dá)能力基本呈現(xiàn)一種線性關(guān)系，易于理解。復(fù)雜特征則是指特征工程方面不斷嘗試使用各種奇技淫巧構(gòu)造的可能有用、可能沒(méi)用的特征，這部分特征的構(gòu)造方式可能會(huì)有各種trick，比如窗口滑動(dòng)、離散化、歸一化、開方、平方、笛卡爾積、多重笛卡爾積等等;順便提一句，因?yàn)樘卣鞴こ瘫旧聿](méi)有特別系統(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)通過(guò)深度神經(jīng)網(wǎng)絡(luò)可以進(jìn)行一定程度的表現(xiàn)學(xué)習(xí)(representation learning)，例如在圖像領(lǐng)域，通過(guò)CNN提取圖像feature并在此基礎(chǔ)上進(jìn)行分類的方法，一舉打破了之前算法的天花板，而且是以極大的差距打破。這給所有算法工程師帶來(lái)了新的思路，既然深度學(xué)習(xí)本身有提取特征的能力，干嘛還要苦哈哈的自己去做人工特征設(shè)計(jì)呢?

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

　　兩種模式孰優(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ī)器無(wú)法存放的情況。比如百億級(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è)問(wèn)題的時(shí)候才想起長(zhǎng)者的教訓(xùn)，年輕人啊，還是圖樣，圖森破。如果你和我一樣曾經(jīng)忽略過(guò)這個(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ù)并行理解起來(lái)比較簡(jiǎn)單，當(dāng)樣本比較多的時(shí)候，為了使用所有樣本來(lái)訓(xùn)練模型，我們不妨把數(shù)據(jù)分布到不同的機(jī)器上，然后每臺(tái)機(jī)器都來(lái)對(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算法形成的先后依賴)，無(wú)法類比數(shù)據(jù)并行這樣直接將模型參數(shù)分片而破壞其依賴關(guān)系，所以模型并行不僅要對(duì)模型分片，同時(shí)需要調(diào)度器來(lái)控制參數(shù)間的依賴關(guān)系。而每個(gè)模型的依賴關(guān)系往往并不同，所以模型并行的調(diào)度器因模型而異，較難做到完全通用。關(guān)于這個(gè)問(wèn)題，CMU的Erix Xing在[5]中有所介紹，感興趣的可以參考。

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

　　解釋了模型并行的物理圖景，當(dāng)一個(gè)超大神經(jīng)網(wǎng)絡(luò)無(wú)法存儲(chǔ)在一臺(tái)機(jī)器上時(shí)，我們可以切割網(wǎng)絡(luò)存到不同的機(jī)器上，但是為了保持不同參數(shù)分片之間的一來(lái)，如圖中粗黑線的部分，則需要在不同的機(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é)一定感到熟悉，是的，模型并行是通過(guò)數(shù)據(jù)流水線來(lái)實(shí)現(xiàn)并行的。想想那個(gè)蓋樓的第二種方案，就能理解模型并行的精髓了。

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

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

　　2. 并行算法演進(jìn)2.1MapReduce路線

　　從函數(shù)式編程中的受到啟發(fā)，google發(fā)布了MapReduce[7]的分布式計(jì)算方

　　式;通過(guò)將任務(wù)切分成多個(gè)疊加的Map+Reduce任務(wù)，來(lái)完成復(fù)雜的計(jì)算任務(wù)，示意圖如下

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

　　為了解決MapReduce的兩個(gè)問(wèn)題，Matei在[8]中提出了一種新的數(shù)據(jù)結(jié)構(gòu)RDD，并構(gòu)建了Spark框架。Spark框架在MR語(yǔ)義之上封裝了DAG調(diào)度器，極大降低了算法使用的門檻。較長(zhǎng)時(shí)間內(nèi)spark幾乎可以說(shuō)是大規(guī)模機(jī)器學(xué)習(xí)的代表，直至后來(lái)沐帥的參數(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就無(wú)法正常運(yùn)行了。所以從今天的眼光來(lái)看，Spark只能稱為一個(gè)中等規(guī)模的機(jī)器學(xué)習(xí)框架。劇透一句，公司開源的Angel通過(guò)修改Driver的底層協(xié)議將Spark擴(kuò)展到了一個(gè)高一層的境界。后面還會(huì)再詳細(xì)介紹這部分。

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

　　2.2MPI技術(shù)

　　沐帥在[9]中對(duì)MPI的前景做了簡(jiǎn)要介紹;和Spark不同，MPI是類似socket

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

　　從圖中可以看出，MPI作業(yè)失敗的幾率接近五成。MPI也并不是完全沒(méi)有可取之處，正如沐帥所說(shuō)，在超算集群上還是有場(chǎng)景的。對(duì)于工業(yè)屆依賴于云計(jì)算、依賴于commodity計(jì)算機(jī)來(lái)說(shuō)，則顯得性價(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來(lái)存放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í)框架來(lái)定位的。要擺脫具體應(yīng)用、算法的束縛，做一個(gè)通用的大規(guī)模機(jī)器學(xué)習(xí)框架，首先就要定義好框架的功能;而所謂框架，往往就是把大量重復(fù)的、瑣碎的、做了一次就不想再來(lái)第二次的臟活、累活進(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ì);沒(méi)有故障的時(shí)候，也可能因?yàn)閷?duì)任務(wù)時(shí)效性要求的變化而隨時(shí)更改集群的機(jī)器配置。這也需要框架能在不影響任務(wù)的情況下能做到機(jī)器的熱插拔。

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

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

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

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

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

　　圖中畫了一個(gè)servergroup和三個(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的介紹，或者我之前多次推薦過(guò)的書籍《最優(yōu)化導(dǎo)論》。

　　我們先看一個(gè)單機(jī)算法的運(yùn)行過(guò)程，假設(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)。。。看明白了嗎?就是假設(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è)servernode上，s1、s2、s3分布在三個(gè)worker上，這時(shí)候如果我們還要保持之前的計(jì)算順序，則會(huì)變成怎樣?work1計(jì)算的時(shí)候，work2和worker3只能等待，同樣worker2計(jì)算的時(shí)候，worker1和work3都得等待，以此類推;可以看出這樣的并行化并沒(méi)有提升性能;但是也算簡(jiǎn)單解決了超大規(guī)模模型的存儲(chǔ)問(wèn)題。

　　為了解決性能的問(wèn)題，業(yè)界開始探索這里的一致性模型，最先出來(lái)的版本是前面提到的[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)致模型無(wú)法收斂。也就是SGD徹底跑飛了，梯度不知道飛到哪里去了。

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

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

　　以此協(xié)議為基礎(chǔ)的spark在很長(zhǎng)時(shí)間內(nèi)成為機(jī)器學(xué)習(xí)領(lǐng)域?qū)嶋H的霸主，不是沒(méi)有理由的。此種協(xié)議的缺陷之處在于，整個(gè)worker group的性能由其中最慢的worker決定;這個(gè)worker一般成為straggler。讀過(guò)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不等于無(wú)窮大的情況下，算法一定可以在若干次迭代以后進(jìn)入收斂狀態(tài)。

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

　　3.3核心技術(shù)

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

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

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

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

　　當(dāng)有server node加入或退出的時(shí)候，servermanager負(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ù)器，通過(guò)數(shù)據(jù)并行來(lái)加速模型的訓(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)單，這里篇幅所限就不贅述了。只是想說(shuō)明worker在計(jì)算梯度的時(shí)候可能需要使用到上一輪迭代的所有參數(shù)。

　　而我們之所以對(duì)參數(shù)進(jìn)行分片就是因?yàn)槲覀儫o(wú)法將所有參數(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)，大致這樣)一下。這樣的系數(shù)性，可以讓單機(jī)沒(méi)有任何阻礙的計(jì)算f(w)。

　　目前公司開源的angel等系統(tǒng)都處于這個(gè)境界。而原生spark還沒(méi)有達(dá)到這個(gè)境界，只能在中小規(guī)模的圈子里廝混。

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

　　境界3順延境界2二來(lái)，當(dāng)百億級(jí)feature且feature比較稠密的時(shí)候，就需要計(jì)算框架進(jìn)入到這層境界了，此時(shí)單個(gè)worker的能力有限，無(wú)法完整加載一個(gè)樣本，也無(wú)法完整計(jì)算f(w)。怎么辦呢?其實(shí)很簡(jiǎn)單，學(xué)過(guò)線性代數(shù)的都知道，矩陣可以分塊。向量是最簡(jiǎn)單的矩陣，自然可以切成一段一段的來(lái)計(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組件來(lái)進(jìn)行模型并行的concurrent控制。而一般參數(shù)間的一來(lái)關(guān)系因模型而已，所以較難抽象出通用的coordinator來(lái)，而必須以某種形式通過(guò)腳本parser來(lái)生產(chǎn)整個(gè)計(jì)算任務(wù)的DAG圖，然后通過(guò)DAG調(diào)度器來(lái)完成。對(duì)這個(gè)問(wèn)題的介紹可以參考Erix Xing的分享[5]。

　　Tensorflow

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

　　前面不少圖片引自此文，從TF的論文來(lái)看，TF框架本身是支持模型并行和數(shù)據(jù)并行的，內(nèi)置了一個(gè)參數(shù)服務(wù)器模塊，但從開源版本所曝光的API來(lái)看，TF無(wú)法用來(lái)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ì)是可以做到第四重境界的，之所以沒(méi)有曝光，可能是基于其他商業(yè)目的的考量，比如使用他們的云計(jì)算服務(wù)。

　　5. 其他

5.1資源管理

　　本文沒(méi)有涉及到的部分是資源管理，大規(guī)模機(jī)器學(xué)習(xí)框架部署的集群往往

　　資源消耗也比較大，需要專門的資源管理工具來(lái)維護(hù)。這方面yarn和mesos都是佼佼者，細(xì)節(jié)這里也就不介紹了。

　　5.2設(shè)備

　　除了資源管理工具，本身部署大規(guī)模機(jī)器學(xué)習(xí)集群本身對(duì)硬件也還是有些要

　　求的，雖然理論上來(lái)說(shuō)，所有commodity機(jī)器都可以用來(lái)搭建這類集群，但是考慮到性能，我們建議盡量用高內(nèi)存的機(jī)器+萬(wàn)兆及以上的網(wǎng)卡。沒(méi)有超快速的網(wǎng)卡，玩參數(shù)傳遞和樣本加載估計(jì)會(huì)比較苦逼。

　　6. 結(jié)語(yǔ)

　　從后臺(tái)轉(zhuǎn)算法以來(lái)，長(zhǎng)期沉浸于算法推理的論文無(wú)法自拔，對(duì)自己之前的后

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

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

　　致謝

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