MapReduce的替代者-Parameter Server

一.背景

隨著互聯網的發展，數據量的增大，很多對于數據的處理工作（例如一些推薦系統、廣告推送等）都遷移到了云端，也就是分布式計算系統上。衍生了很多牛逼的分布式計算的計算模型，比較著名的就是MapReduce、MPI、BSP等。后來也產生了一些分布式計算系統，大家耳熟能詳的Hadoop就是基于 MapReduce實現的。

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

引用一位算法大神的話簡單描述下什么事Parameter Server：總結是一種計算模型SSP+一種分布式設計看板模式Client+Server(partitioned table)+基于算法的調度策略(Scheduler)。可能有些同學還不太理解這句話，沒關系，下面通過一個實例來介紹一下PS。

二.場景

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

三.Work Flow

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

1.Map-Reduce處理LR

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

先來看看整體的流程圖：

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

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

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

第三步：負責reduce的服務器統一出一個模型輸出。

2.Parameter Server的一些機制

下面我們看下Parameter Server是怎么解決這個問題。首先看下PS的總體架構，PS是由client和server組成的，client對應于上文的worker，負責計算。server是負責統一所有的client它們的參數，server間是聯通的。
如下圖：

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

1）.并行化設計
PS可以運用很多并行化的思想從而提高效率。
（1）首先在client端，計算和上傳數據是采用的多線程機制，計算和數據傳輸在不同的線程中進行從而增加了效率。同時server并不是等待所有參數都上傳完成，才向下分發的。如果一個client_a計算比較慢，server可以暫時不采用client_a的數據，而采用歷史數據。
（2）數據上傳也可以用樹狀結構代替直接上傳，在client和server之間增加一層樹狀結構可以提高數據傳輸效率，節約server的處理資源。可以從下圖的左邊，變為右邊。

2）.pull和push機制
首先，是在client端應該上傳怎樣的數據，因為每個client節點都會不停的接受和反饋數據給server，那么到底應該push怎樣的數據上去呢？這個一般來講是選擇步長最長的參數，也就是最大的梯度值的參數push上去。

3）.server端的異構形式
因為每個client只處理一部分參數，server端需要將這些參數拼接起來，所以server端是一個異構的組成形式。

3.Parameter Server處理LR

上面講了很多PS的機制，這里具體說一下PS怎么實現LR。因為LR的輸出是一個線性的回歸模型。輸出的結果是下面的這種式子：
z=w1*x1+w2*x2…..+w10*x2+….
我們要求的是里面的w1，w2，w3….這些參數，在PS中每個client計算的是其中的某些△w。通過server將這些△w同步上去，然后再push下去繼續迭代計算。這樣的好處是對于梯度問題，每個client可以沿著一個方向走。

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

本文來自博客 “李博Garvin“
轉載請標明出處:http://blog.csdn.net/buptgshengod]