首先還是要聲明一下，這個(gè)文章是我在入職阿里云1個(gè)月以來，對(duì)于分布式計(jì)算的一點(diǎn)膚淺的認(rèn)識(shí)，可能有些地方不夠妥善，還請(qǐng)看官可以指出不足的地方，共同進(jìn)步。

一.背景

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

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

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

二.場(chǎng)景

因?yàn)槲以趯W(xué)習(xí)PS的過程中是對(duì)照Map Reduce來學(xué)習(xí)的。所以也通過一個(gè)機(jī)器學(xué)習(xí)算法的并行計(jì)算的實(shí)例，來比較Map Reduce和PS。為了更好地突出PS的優(yōu)勢(shì)，這里用到的算法是一個(gè)梯度逼近***結(jié)果的一種算法-邏輯回歸(Logical Regression)。

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

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

2.隨機(jī)梯度下降SGD

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

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

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

三.Work Flow

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

1.Map-Reduce處理LR

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

先來看看整體的流程圖：

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

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

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

第三步：負(fù)責(zé)reduce的服務(wù)器統(tǒng)一出一個(gè)模型輸出。

#p#

2.Parameter Server的一些機(jī)制

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

如下圖：

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

1).并行化設(shè)計(jì)

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

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

首先，是在client端應(yīng)該上傳怎樣的數(shù)據(jù)，因?yàn)槊總€(gè)client節(jié)點(diǎn)都會(huì)不停的接受和反饋數(shù)據(jù)給server，那么到底應(yīng)該push怎樣的數(shù)據(jù)上去呢?這個(gè)一般來講是選擇步長(zhǎng)最長(zhǎng)的參數(shù)，也就是***的梯度值的參數(shù)push上去。

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

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

3.Parameter Server處理LR

上面講了很多PS的機(jī)制，這里具體說一下PS怎么實(shí)現(xiàn)LR。因?yàn)長(zhǎng)R的輸出是一個(gè)線性的回歸模型。輸出的結(jié)果是下面的這種式子：

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

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

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

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