接《大規模機器學習架構的四重境界（上）》
本節假設讀者已經對随機梯度優化算法比較熟悉，如果不熟悉的同學請參考吳恩達經典課程機器學習中對SGD的介紹，或者我之前多次推薦過的書籍《最優化導論》。
我們先看一個單機算法的運作過程，假設一個模型的參數切分成三個分片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都得等待，以此類推；可以看出這樣的并行化并沒有提升性能；但是也算簡單解決了超大規模模型的存儲問題。
為了解決性能的問題，業界開始探索這裡的一緻性模型，最先出來的版本是前面提到的[11]中的ASP模式，就是完全不顧worker之間的順序，每個worker按照自己的節奏走，跑完一個疊代就update，然後繼續，這應該是大規模機器學習中的freestyle了，如圖所示
ASP的優勢是最大限度利用了叢集的計算能力，所有的worker所在的機器都不用等待，但缺點也顯而易見，除了少數幾個模型，比如LDA，ASP協定可能導緻模型無法收斂。也就是SGD徹底跑飛了，梯度不知道飛到哪裡去了。
在ASP之後提出了另一種相對極端的同步協定BSP，spark用的就是這種方式，如圖所示
每個worker都必須在同一個疊代運作，隻有一個疊代任務所有的worker都完成了，才會進行一次worker和server之間的同步和分片更新。這個算法和嚴格一直的算法非常類似，差別僅僅在于單機版本的batch size在BSP的時候變成了有所有worker的單個batch size求和得到的總的butch size替換。毫無疑問，BSP的模式和單機串行因為僅僅是batch size的差別，是以在模型收斂性上是完全一樣的。同時，因為每個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不等于無窮大的情況下，算法一定可以在若幹次疊代以後進入收斂狀态。其實在Eric提出理論證明之前，工業界已經這麼嘗試過了：）
順便提一句，考察分布式算法的性能，一般會分為statistical performance和hard performance來看。前者指不同的同步協定導緻算法收斂需要的疊代次數的多少，後者是單次疊代所對應的耗時。兩者的關系和precision\recall關系類似，就不贅述了。有了SSP，BSP就可以通過指定s=0而得到。而ASP同樣可以通過制定s=∞來達到。
除了參數伺服器的架構、同步協定之外，本節再對其他技術做一個簡要的介紹，詳細的了解請直接閱讀沐帥的博士論文和相關發表的論文。
熱備、冷備技術：為了防止server node挂掉，導緻任務中斷，可以采用兩個技術，一個是對參數分片進行熱備，每個分片存儲在三個不同的server node中，以master-slave的形式存活。如果master挂掉，可以快速從slave擷取并重新開機相關task。
除了熱備，還可以定時寫入checkpoint檔案到分布式檔案系統來對參數分片及其狀态進行備份。進一步保證其安全性。
Server node管理：可以使用一緻性哈希技術來解決server node的加入和退出問題，如圖所示
當有server node加入或退出的時候，server manager負責對參數進行重新分片或者合并。注意在對參數進行分片管理的情況下，一個分片隻需要一把鎖，這大大提升了系統的性能，也是參數伺服器可以實用的一個關鍵點。
到這裡可以回到我們的标題了，大規模機器學習的四重境界到底是什麼呢？
這四重境界的劃分是作者個人閱讀總結的一種想法，并不是業界标準，僅供大家參考。
境界1：參數可單機存儲和更新
此種境界較為簡單，但仍可以使用參數伺服器，通過資料并行來加速模型的訓練。
境界2：參數不可單機存儲，可以單機更新
此種情況對應的是一些簡單模型，比如sparse logistic regression；當feature的數量突破百億的時候，LR的權重參數不太可能在一台機器上完全存下，此時必須使用參數伺服器架構對模型參數進行分片。但是注意一點，SGD的更新公式
w’=w-α
，其中
可以分開到單個次元進行計算，但是單個次元的w i
=f(w)x i
這裡的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還沒有達到這個境界，隻能在中小規模的圈子裡厮混。Angel改造的基于Angel的Spark則達到了這個境界。
境界3：參數不可單機存儲，不可單機更新，但無需模型并行
境界3順延境界2二來，當百億級feature且feature比較稠密的時候，就需要計算架構進入到這層境界了，此時單個worker的能力有限，無法完整加載一個樣本，也無法完整計算f(w)。怎麼辦呢？其實很簡單，學過線性代數的都知道，矩陣可以分塊。向量是最簡單的矩陣，自然可以切成一段一段的來計算。隻是排程器需要支援算符分段而已了。
境界4：參數不可單機存儲，不可單機更新，需要模型并行
進入到這個層次的計算架構，可以算是世界一流了。可以處理超大規模的神經網絡。這也是最典型的應用場景。此時不僅模型的參數不能單機存儲，而且同一個疊代内，模型參數之間還有強的依賴關系，可以參見姐夫對distbelief的介紹裡的模型切分。
此時首先需要增加一個coordinator元件來進行模型并行的concurrent控制。同時參數伺服器架構需要支援namespace切分，coordinator将依賴關系通過namespace來進行表示。
一般參數間的依賴關系因模型而已，是以較難抽象出通用的coordinator來，而必須以某種形式通過腳本parser來生産整個計算任務的DAG圖，然後通過DAG排程器來完成。對這個問題的介紹可以參考Erix Xing的分享[5]。
Tensorflow
目前業界比較知名的深度學習架構有Caffee、MXNet、Torch、Keras、Theano等，但目前最炙手可熱的應該是google釋出的Tensorflow。這裡單獨拿出來稍微分解下。
前面不少圖檔引自此文，從TF的論文來看，TF架構本身是支援模型并行和資料并行的，内置了一個參數伺服器子產品，但從開源版本所曝光的API來看，TF無法用來10B級别feature的稀疏LR模型。原因是已經曝光的API隻支援在神經網絡的不同層和層間進行參數切分，而超大規模LR可以看做一個神經單元，TF不支援單個神經單元參數切分到多個參數伺服器node上。
當然，以google的實力，絕對是可以做到第四重境界的，之是以沒有曝光，可能是基于其他商業目的的考量，比如使用他們的雲計算服務。
綜上，個人認為如果能做到第四重境界，目前可以說的上是世界一流的大規模機器學習架構。僅從沐帥的ppt裡看他曾經達到過，google内部應該也是沒有問題的。第三重境界應該是國内一流，第二充應該是國内前列吧。
本文沒有涉及到的部分是資源管理，大規模機器學習架構部署的叢集往往
資源消耗也比較大，需要專門的資源管理工具來維護。這方面yarn和mesos都是佼佼者，細節這裡也就不介紹了。
除了資源管理工具，本身部署大規模機器學習叢集本身對硬體也還是有些要
求的，雖然理論上來說，所有commodity機器都可以用來搭建這類叢集，但是考慮到性能，我們建議盡量用高記憶體的機器+萬兆及以上的網卡。沒有超快速的網卡，玩參數傳遞和樣本加載估計會比較苦逼。
從背景轉算法以來，長期沉浸于算法推理的論文無法自拔，對自己之前的背景工程能力漸漸輕視起來，覺得工程對算法的幫助不大。直到最近一個契機，需要做一個這方面的調研，才豁然發現，之前的工程經驗對我了解大規模機器學習架構非常有用，果然如李宗盛所說，人生每一步路，都不是白走的。
在一個月左右的調研中，腦子每天都充斥這各種疑問和困惑，曾經半夜4點醒來，思考同步機制而再也睡不着，幹脆起來躲衛生間看書，而那天我一點多才睡。當腦子裡有放不下的問題的時候，整個人會處于一種非常亢奮的狀态，除非徹底想清楚這個問題，否則失眠是必然的，上一次這種狀态已經是很多年前了。好在最後我總算理清了這方面的所有關鍵細節。以此，記之。Carbonzhang于2017年8月26日淩晨！
感謝wills、janwang、joey、roberty、suzi等同學一起讨論，特别感謝burness在TF方面的深厚造詣和調研。因為本人水準所限，錯漏難免，另外還有相當多的細節因為篇幅限制并未一一展開，僅僅是從較高抽象層面上簡述了下大規模機器學習架構的關鍵思路，其他如分片向量鎖、通信協定、時鐘邏輯、DAG排程器、資源排程子產品等均為展開來講，希望以後有機會能補上。
Wide & Deep Learning for Recommender Systems
Deep Neural Networks for YouTube Recommendations
https://www.zhihu.com/question/53851014
TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
http://www.jianshu.com/p/00736aa21dc8
Large Scale Distributed Deep Networks
MapReduce: Simplified Data Processing on Large Clusters
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
https://www.zhihu.com/question/55119470
KunPeng: Parameter Server based Distributed Learning Systems and Its Applications in Alibaba and Ant Financial
An Architecture for Parallel Topic Models
Scaling Distributed Machine Learning with the Parameter Server
Piccolo: Building fast, distributed pro- grams with partitioned tables
More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server
Angel-A Flexible and Powerful Parameter Server；黃明ppt