3.2同步協(xié)議

本節(jié)假設(shè)讀者已經(jīng)對(duì)隨機(jī)梯度優(yōu)化算法比較熟悉，如果不熟悉的同學(xué)請(qǐng)參考吳恩達(dá)經(jīng)典課程機(jī)器學(xué)習(xí)中對(duì)SGD的介紹，或者我之前多次推薦過(guò)的書(shū)籍《最優(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)在我們開(kāi)始并行化，假設(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都得等待，以此類推；可以看出這樣的并行化并沒(méi)有提升性能；但是也算簡(jiǎn)單解決了超大規(guī)模模型的存儲(chǔ)問(wèn)題。

為了解決性能的問(wèn)題，業(yè)界開(kāi)始探索這里的一致性模型，最先出來(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)也顯而易見(jià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和server之間的同步和分片更新。這個(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ù)間隔任意大，而B(niǎo)SP則只允許為0，那我是否可以取一個(gè)常數(shù)s？如圖所示

?

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

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

順便提一句，考察分布式算法的性能，一般會(huì)分為statistical performance和hard performance來(lái)看。前者指不同的同步協(xié)議導(dǎo)致算法收斂需要的迭代次數(shù)的多少，后者是單次迭代所對(duì)應(yīng)的耗時(shí)。兩者的關(guān)系和precision\recall關(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ù)：為了防止server node掛掉，導(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í)寫(xiě)入checkpoint文件到分布式文件系統(tǒng)來(lái)對(duì)參數(shù)分片及其狀態(tài)進(jìn)行備份。進(jìn)一步保證其安全性。

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

?

當(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ù)器，通過(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-α，其中可以分開(kāi)到單個(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)，大致這樣）以下。這樣的稀疏性，可以讓單機(jī)沒(méi)有任何阻礙的計(jì)算f(w)。

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

境界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)系，可以參見(jiàn)姐夫?qū)istbelief的介紹里的模型切分。

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

一般參數(shù)間的依賴關(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ù)器模塊，但從開(kāi)源版本所曝光的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ù)。

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

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)，覺(jué)得工程對(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)生間看書(shū)，而那天我一點(diǎn)多才睡。當(dāng)腦子里有放不下的問(wèn)題的時(shí)候，整個(gè)人會(huì)處于一種非常亢奮的狀態(tài)，除非徹底想清楚這個(gè)問(wèn)題，否則失眠是必然的，上一次這種狀態(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)槠拗撇⑽匆灰徽归_(kāi)，僅僅是從較高抽象層面上簡(jiǎn)述了下大規(guī)模機(jī)器學(xué)習(xí)框架的關(guān)鍵思路，其他如分片向量鎖、通信協(xié)議、時(shí)鐘邏輯、DAG調(diào)度器、資源調(diào)度模塊等均為展開(kāi)來(lái)講，希望以后有機(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