3.2同步協議

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

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

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

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

?

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

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

?

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

以此協議為基礎的spark在很長時間內成為機器學習領域實際的霸主，不是沒有理由的。此種協議的缺陷之處在于，整個worker group的性能由其中最慢的worker決定；這個worker一般稱為straggler。讀過GFS文章的同學應該都知道straggler的存在是非常普遍的現象。

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

?

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

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

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

3.3核心技術

除了參數服務器的架構、同步協議之外，本節(jié)再對其他技術做一個簡要的介紹，詳細的了解請直接閱讀沐帥的博士論文和相關發(fā)表的論文。

熱備、冷備技術：為了防止server node掛掉，導致任務中斷，可以采用兩個技術，一個是對參數分片進行熱備，每個分片存儲在三個不同的server node中，以master-slave的形式存活。如果master掛掉，可以快速從slave獲取并重啟相關task。

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

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

?

當有server node加入或退出的時候，server manager負責對參數進行重新分片或者合并。注意在對參數進行分片管理的情況下，一個分片只需要一把鎖，這大大提升了系統的性能，也是參數服務器可以實用的一個關鍵點。

4. 大規(guī)模機器學習的四重境界

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

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

境界1：參數可單機存儲和更新

此種境界較為簡單，但仍可以使用參數服務器，通過數據并行來加速模型的訓練。

境界2：參數不可單機存儲，可以單機更新

此種情況對應的是一些簡單模型，比如sparse logistic regression；當feature的數量突破百億的時候，LR的權重參數不太可能在一臺機器上完全存下，此時必須使用參數服務器架構對模型參數進行分片。但是注意一點，SGD的更新公式

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

這里的f(w)表示是全部參數w的一個函數，具體推倒比較簡單，這里篇幅所限就不贅述了。只是想說明worker在計算梯度的時候可能需要使用到上一輪迭代的所有參數。而我們之所以對參數進行分片就是因為我們無法將所有參數存放到一臺機器，現在單個worker有需要使用所有的參數才能計算某個參數分片的梯度，這不是矛盾嗎？可能嗎？

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

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

境界3：參數不可單機存儲，不可單機更新，但無需模型并行

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

境界4：參數不可單機存儲，不可單機更新，需要模型并行

進入到這個層次的計算框架，可以算是世界一流了?？梢蕴幚沓笠?guī)模的神經網絡。這也是最典型的應用場景。此時不僅模型的參數不能單機存儲，而且同一個迭代內，模型參數之間還有強的依賴關系，可以參見姐夫對distbelief的介紹里的模型切分。

此時首先需要增加一個coordinator組件來進行模型并行的concurrent控制。同時參數服務器框架需要支持namespace切分，coordinator將依賴關系通過namespace來進行表示。

一般參數間的依賴關系因模型而已，所以較難抽象出通用的coordinator來，而必須以某種形式通過腳本parser來生產整個計算任務的DAG圖，然后通過DAG調度器來完成。對這個問題的介紹可以參考Erix Xing的分享[5]。

Tensorflow

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

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

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

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

5. 其他

5.1 資源管理

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

5.2 設備

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

6. 結語

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

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

致謝

感謝wills、janwang、joey、roberty、suzi等同學一起討論，特別感謝burness在TF方面的深厚造詣和調研。因為本人水平所限，錯漏難免，另外還有相當多的細節(jié)因為篇幅限制并未一一展開，僅僅是從較高抽象層面上簡述了下大規(guī)模機器學習框架的關鍵思路，其他如分片向量鎖、通信協議、時鐘邏輯、DAG調度器、資源調度模塊等均為展開來講，希望以后有機會能補上。

引用

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