首先還是要聲明一下，這個文章是我在入職阿里云1個月以來，對于分布式計算的一點膚淺的認識，可能有些地方不夠妥善，還請看官可以指出不足的地方，共同進步。

一.背景

隨著互聯(lián)網(wǎng)的發(fā)展，數(shù)據(jù)量的增大，很多對于數(shù)據(jù)的處理工作(例如一些推薦系統(tǒng)、廣告推送等)都遷移到了云端，也就是分布式計算系統(tǒng)上。衍生了很多牛逼的分布式計算的計算模型，比較著名的就是MapReduce、MPI、BSP等。后來也產(chǎn)生了一些分布式計算系統(tǒng)，大家耳熟能詳?shù)腍adoop就是基于 MapReduce實現(xiàn)的。

本文的主人公是Parameter Server，其實也不算是新寵了，這個模型已經(jīng)被提出好幾年了，只不過在國內(nèi)還不是特別熱。不過最近一些云服務巨頭們開始了對于PS的深入開發(fā)和研究。

引用一位算法大神的話簡單描述下什么事Parameter Server：總結(jié)是一種計算模型SSP+一種分布式設計看板模式Client+Server(partitioned table)+基于算法的調(diào)度策略(Scheduler)?？赡苡行┩瑢W還不太理解這句話，沒關(guān)系，下面通過一個實例來介紹一下PS。

二.場景

因為我在學習PS的過程中是對照Map Reduce來學習的。所以也通過一個機器學習算法的并行計算的實例，來比較Map Reduce和PS。為了更好地突出PS的優(yōu)勢，這里用到的算法是一個梯度逼近***結(jié)果的一種算法-邏輯回歸(Logical Regression)。

為了更好地幫大家理解這些內(nèi)容，我也羅列了一些必須的知識儲備：

1.邏輯回歸算法-***fork里面的代碼看一下

2.隨機梯度下降SGD

3.李沐大神實現(xiàn)的一個PS開源庫，上面有一個論文，一定要讀

4.并行邏輯回歸-等會會借用里面的內(nèi)容來講

5.ps開源代碼網(wǎng)站

三.Work Flow

首先還是要補充幾句，Map-Reduce在實現(xiàn)并行算法的過程中有它的優(yōu)勢，但是也有很大的弊端，它在處理梯度問題上沒有很好的效率。這一點PS通過client+server的模式很好的解決了這個問題。

1.Map-Reduce處理LR

首先來看下Map-Reduce是如何解決邏輯回歸(下文統(tǒng)一稱為LR)的。首先是map的過程，將很大的數(shù)據(jù)切割成key-value的形式，我們在這里假設所有的數(shù)據(jù)都是稠密的。比如說你有100行數(shù)據(jù)，切割成5份，那么每一個worker就處理其中的20行數(shù)據(jù)。Reduce主要是負責統(tǒng)一 worker的計算結(jié)果。下面具體到LR的算法實現(xiàn)來講解下Map-Reduce的過程。

先來看看整體的流程圖：

***步：首先是進行map階段對于長尾數(shù)據(jù)的分割，我們假設數(shù)據(jù)是稠密非稀疏的。邏輯回歸的并行計算的數(shù)據(jù)分割，可以按行分、按列分或者行列一起分。分好的數(shù)據(jù)通過key-value的形式傳到每一個worker中，對應上圖的map phase階段的worker。當然，map里也包含LR的計算邏輯，邏輯請大家看上面的資料自己學習下。分割圖如下：

第二步：利用隨機梯度(SGD)方法逼近***解，在凸函數(shù)中LR是可以***接近***模型的，可以通過限定循環(huán)次數(shù)和收斂條件來實現(xiàn)。這其中就有一個問題，認真研究LR的同學可能會發(fā)現(xiàn)，如果我們使用SGD的話，因為worker之間雖然有一定的通信機制，但是并不是實時同步的，所以每一個worker并不知道對方的梯度是多少，形象的描述一下就是我們可以把SGD看成一個下坡問題。

每個worker都在往終點方向下山(收斂模型)，但是它們彼此間并不能實時協(xié)作，也就是說A不知道B爬到哪里，C不知道A爬到哪里。傳入一個路徑，我就接著向下爬一點，可能會走重復的路徑。所以說Map-Reduce的SGD是一種范圍的梯度。每個worker不一定一直往下走，可能走走停停甚至往后走一點，但是因為數(shù)據(jù)量巨大總是可以走到終點的。 但是這樣就會浪費了很多效率，這也就是Parameter Server重點解決的問題。

第三步：負責reduce的服務器統(tǒng)一出一個模型輸出。

#p#

2.Parameter Server的一些機制

下面我們看下Parameter Server是怎么解決這個問題。首先看下PS的總體架構(gòu)，PS是由client和server組成的，client對應于上文的worker，負責計算。server是負責統(tǒng)一所有的client它們的參數(shù)，server間是聯(lián)通的。

如下圖：

總體來看，PS的優(yōu)勢是通過server來協(xié)同client的輸出，如上一節(jié)的下山問題，PS可以協(xié)同每一個client按照一個方向直線下山，從而提高了效率。而這其中也有很多的技術(shù)細節(jié)需要考慮。

1).并行化設計

PS可以運用很多并行化的思想從而提高效率。

(1)首先在client端，計算和上傳數(shù)據(jù)是采用的多線程機制，計算和數(shù)據(jù)傳輸在不同的線程中進行從而增加了效率。同時server并不是等待所有參數(shù)都上傳完成，才向下分發(fā)的。如果一個client_a計算比較慢，server可以暫時不采用client_a的數(shù)據(jù)，而采用歷史數(shù)據(jù)。

(2)數(shù)據(jù)上傳也可以用樹狀結(jié)構(gòu)代替直接上傳，在client和server之間增加一層樹狀結(jié)構(gòu)可以提高數(shù)據(jù)傳輸效率，節(jié)約server的處理資源?？梢詮南聢D的左邊，變?yōu)橛疫叀?/p>

2).pull和push機制

首先，是在client端應該上傳怎樣的數(shù)據(jù)，因為每個client節(jié)點都會不停的接受和反饋數(shù)據(jù)給server，那么到底應該push怎樣的數(shù)據(jù)上去呢?這個一般來講是選擇步長最長的參數(shù)，也就是***的梯度值的參數(shù)push上去。

3).server端的異構(gòu)形式

因為每個client只處理一部分參數(shù)，server端需要將這些參數(shù)拼接起來，所以server端是一個異構(gòu)的組成形式。

3.Parameter Server處理LR

上面講了很多PS的機制，這里具體說一下PS怎么實現(xiàn)LR。因為LR的輸出是一個線性的回歸模型。輸出的結(jié)果是下面的這種式子：

z=w1*x1+w2*x2…..+w10*x2+….

我們要求的是里面的w1，w2，w3….這些參數(shù)，在PS中每個client計算的是其中的某些△w。通過server將這些△w同步上去，然后再push下去繼續(xù)迭代計算。這樣的好處是對于梯度問題，每個client可以沿著一個方向走。

后話：我的理解還很淺，具體實現(xiàn)還有非常多的技術(shù)細節(jié)要敲定，部署在集群上也會出現(xiàn)各種問題，如：log怎么輸出，有的client掛了怎么辦等等。建議有空可以看下李沐的開源項目的代碼，還有上面提到的一些文檔。

博文出處：http://blog.csdn.net/buptgshengod/article/details/46819051