mxnet分散式2

ps-lite論文閱讀

論文閱讀https://www.usenix.org/system/files/conference/osdi14/osdi14-paper-li_mu.pdf

1 Intruduction

數據很大，分散式已經是趨勢，節點之間共享參數是必須，但是遇到三個挑戰

1. 高帶寬的獲取共享參數
2. 很多機器學習是順序的，同步和高延遲的阻礙影響了性能
3. 高容錯率

1.1 ps-lite提供了5個核心功能特徵

1. 非同步高效通信
2. 靈活的一致性模型，平衡同步與延遲，演算法設計者自己平衡演算法收斂與效率
3. 節點彈性伸縮
4. 高容錯率且耐用，快速從修復中恢復，時鐘向量機制使得網路失敗或者分離後行為明確
5. 容易使用

1.2 工程實現的挑戰

1. 參數在節點之間的高效通信
2. 容錯性，一台機器掛了，整個任務還是在run

2機器學習

2.1 目標

機器學習的目標一般是最小化目標函數，最優解被找到或者模型收斂，訓練結束，一般需要處理的數據量會很大，在這些大量數據上執行演算法是本文的目的

2.2 最小化誤差(risk minimization)

機器學習最直觀的轉化是最小化誤差，risk指的是預測值和標準值之間的差值，比如預測股票，預測的股價和後來真是的股票價格之間的差值就是risk

訓練數據包含n個樣本，xi是第i個樣本，且經常是一個長度為d第矢量，n和d可能是十億和萬億級別的數據，很多場合下，樣本xi有一個label yi 和它對應，在廣告預測中，yi則1對應點擊了，-1對應沒有被點擊。

基於最小化誤差方法能學習一個模型，該模型之後可以用來預測其他新的樣本，為了預測未來的一個廣告是否會被點擊，系統將對clikness求和，然後機遇這一坨參數決定未來的廣告是否會被點擊，就是新輸入經過訓練好的參數提取特徵，得到結果

在很多學習演算法中，訓練數據和模型大小息息相關，模型越大，或者越詳細，之後能做出的預測就越準確，除非訓練集太小，模型太大，訓練集太小會造成過擬合，模型記住了每一個樣本的特徵，導致它失去了泛化能力，模型太小則捕捉不到感興趣的特徵

正則化最小風險是找到模型複雜度和訓練誤差之間的平衡，下面公式第一項是訓練誤差，第二項是模型複雜度，它的目標是使兩者的和加起來最小，前面一項是loss，後面一項是regularizer

在表2和演算法1中，數據被分成很多小份到每個節點上去聯合計算w，每個worker計算自己所得到的那份梯度，server去聚合所有worker得到的梯度，乘以學習率，然後進行下一輪迭代

最耗時的操作是計運算元梯度以便更新梯度，該任務分到每個worker中去做，每個worker執行wxik，對於太大的w這是不可行的，幸運的是一個worker只需要知道它的訓練數據所對應的那一部分參數w就行了

比如在廣告點擊的例子中，如果很少的廣告包括OSDI2014這個廣告語，那麼大部分的worker就不需要更新去更新這個廣告詞所對應的那一部分參數w，由於總的參數無法在一台機器上放得下，每一台機器需要的那一部分參數可以存放在本地，為了證明這個結論，我們隨機的把數據分配到不同的worker，然後計算每個worker基於那部分數據所需要的參數的平均大小，具體的細節在5.1章節中。圖3顯示，100個worker的集群，每個worker只需要參數的7.8%，1000個只要0.15%

2.3 生成模型

在第二種機器學習演算法中，一個樣本對應的label是未知的，這類學習叫無監督學習，它們嘗試捕捉潛在的數據結構，一個常見的例子是主題模型：給一堆文檔，推導出每個文檔的主題

舉個例子，當跑sosp2013的proceeding這個程序的時候，一個演算法可能會產生主題『distribute system』, machine learnling, performance,演算法通過論文內容產生這些主題，而不是通過外部給的一個主題列表，在一些場合比如個性化推薦，問題的規模會變得很大，亟待用分散式並行處理

由於數據的規模，這些演算法只有應用在第一代參數伺服器上才有商業價值，用文檔怎麼產生當前的主題估計的參數必須共享，這是一個關鍵的挑戰

一個流行的主題建模是LDA，這個統計模型語其他的相當不同，模型語演算法1比較相似，不同的是計算的不再是梯度嗎，而是文檔多大程度能被解釋,對於每一個文檔，這個演算法需要額外的數據當每次文檔被用到的時候，因為每次文檔被處理的時候，文檔與元數據都會被存入取出。正如前面章節所描述，每個worker存儲了它所處理的文檔的關鍵字，因而，採用分散式系統能處理更大的模型

3架構

一個ps實例可以跑多於一個演算法模型，ps由一個ps node group組成，worker由workergroup組成，一個server node維護著一份共享參數，所有的server node之間可以相互通信，所有的server node共享一個server manage,server manager維護參數的一致性，比如收集節點的心跳信息，參數的分配等等

每一個worker group運行一個程序，一個worker保存部分數據並對它進行計算，比如深度學習中的梯度計算，worker只與serveer node之間通信，而不會在workers之間它們自己通信，和server通信比如將計算好的梯度推送到server或者從server獲取聚合後到參數，每一個worker group都有一個worker scheduler，它負責向每個worker分配任務，並且管理它們的生命周期等等

參數伺服器支持獨立的參數命名空間，這使得不同worker group之間的參數集互相獨立，同時不同的worker group也可以使用一個相同的命名空間，這樣可以以更大的並行程度去解決一個深度學習問題，另外一個例子是模型經常被節點訪問，比如在線服務來訪問這個模型(這坨參數)，同時當新的參數到一個worker時並計算出結果時，模型被這個worker所更新

參數伺服器被設計用來簡化分散式的應用，如第二章所提到的那些應用。被共享的參數用k-v對來表示，這樣對代數運算更容易被處理，詳細介紹在3.2節，這些參數被分散式的存儲在server group不同的節點中，任何節點可以從伺服器pull參數和push本地的參數(梯度)到server node。在默認情況下，任務是由worker來完成了，少數情況下任務也可以由server節點完成。通過任務狀態依賴圖和與哪一部分參數通信，ps讓演算法開發者可以靈活的選擇一致模型。

3.1 (key, value)向量

被不同的worker node共享的模型可以用key-value的鍵值對所表示，比如在最小化損失函數的例子中，key是特徵ID,values是它所對應的權重，對於LDA,key-value對是word-ID-topicID,模型的每一個實體可以被本地或遠程的讀取或寫入，鍵值對的概念被很多框架所採用。

ps框架在也採取了key-value這種策略，並且給予這樣的觀點：典型的機器學習演算法把模型當作線性代數對象來對待，在目標函數和最小化風險的例子中，w都被當作向量對待。把這些鍵值對當作線性代數對象，parameter server可以應用同樣概念的運算規則，比如向量加減乘除等，將向量的代數運算也移植到key-value這樣的對象上來。

為了支持這些優化，ps框架假設這些key是按順序排列的，賦予這些鍵值對矩陣的語義，key不能為0，這把大量的編程問題簡化成了實現優化演算法，不僅僅是為了更高效的code，key-value這套介面還借力了CPU的一些線性代數多線程編程庫比如BLAS,PLACK,ATLAS等等，簡單的理解就是模型用鍵值對表示，這樣有一堆好處。

3.2 Range Push and Pull

Range push就是將指定範圍的key-value推送，公式：w.push(R, dest),如果R只是一個值，那就是push單個key對應的value，如果R對應的範圍是所有參數的key，那就是一次完整的push，即將全部的參數推送到伺服器。這個介面也可以擴展到和參數w共享key到其他數據通信，比如對於演算法1中從worker中向server更新梯度，可以更新帶範圍的梯度，這樣寫w.push(R, g, dest)

3.3用戶自定義的函數-server node上執行

除了聚合worker的參數到server上，server node上還可以執行用戶自定義的參數，因為server上有更加完整，更實時的參數，演算法1將各個worker的梯度在server上進行聚合，在演算法3中有一些複雜的運算，則需要在server上進行，在上下的處理上，幾乎所有的操作都在server端

3.4非同步任務和依賴

一個任務被遠程調用者所觸發，它可以是worker node向server node發起的push／pull請求，也可以是一個自定義的函數scheduler發送到任何node上，一個task可能包含許多子任務，比如在演算法1中一個數據迭代(workeriter)包含一個pull和一個push

任務被非同步執行，調用者發出任務請求後就自己干別動事情去了，調用方表記一個任務為執行完當且僅當它收到任務的返回，比如用戶定義的函數被返回，pull或push的參數被pull／push成功的返回碼被接受到，任務處理者標記一個任務被處理的的標誌是這個任務已經完成且所有的子任務也被執行完畢

默認情況下任務是並行執行的，在圖5中，iter10和iter11是並行執行的，但是iter12的計算卻是依賴於iter11的結果的，iter12要等到iter11的計算結果push完後它才能開始

任務依賴可以幫助演算法實現，比如在演算法1中，只有所有worker的梯度被push到server的時候，server node才開始做參數聚合，依賴的第二個作用是用於實現靈活的一致性

3.5靈活的一致性

通過並行地使用CPU，磁碟，帶寬等資源，可以提升系統等性能，但是這會使得數據出現不一致的現象。數據不一致的舉例：在圖5中，iter10和iter11是並行的，因而10和11獲取的是一樣的參數，所以它們得到的數據是不一致的，但是12和11就是一致的，因為12依賴了11，10和11計算出來的東西一樣，這個不一致導致了收斂變慢，如果用這個優化演算法來計算演算法1，那麼就會出現上面所說的收斂變慢，但是在有一些例子中，演算法對數據不一致性不是那麼的敏感，每次迭代只有一部分的參數被更新，比如在演算法3中，並行的是特徵(這個並行暫時也不是特別明白，模型並行),最好的折中往往要取決於各種參數，比如模型對數據不一致性的敏感程度，特徵對數據的相關性，硬體組件等容量能力等。ps沒有規定死用戶必須採用哪些方案來適配具體固定的問題，而是演算法設計者可以靈活的，根據具體情況選擇不同的折衷方案。這裡示出3種使用依賴可以實現的模型，它們的有向無環圖見圖6

• Sequential, 一個一個的執行，後者只有在前者執行完才能開始
• Eventual, 各幹個的，互不關聯
• Bounded delay, 某個任務開始執行還是阻塞取決於在它之間t時刻起的任務已經被執行完畢，如果t設置為0，那麼他就是第一種順序執行，如果是t為無窮，那麼它就是第二種，互不影響

以上舉例的圖是可以動態變化的，比如scheduler想讓收斂點快一點，活著計算慢一點，活著有新的節點加入了計算圖，那麼可以修改這些因素

3.6用戶定義的過濾器

基於scheduler，ps可以實現細粒度的控制同步，只有符合過濾器條件的worker的參數才會同步到server上，這樣做是因為優化器本身有更多的參數的信息，舉個例子,significantly modified filter,在worker上計算出來的條目(entry)-比如梯度，只有超過閾值的才會被推送到server伺服器上，在5.1節中，討論了另外一種KKT的方案，它利用了優化問題的最優條件-只有能影響權重的梯度才會被發送到srver上(這和上文提到的不是一樣嗎，稀疏)

4實現

伺服器使用連續的hash(鍵值對)存儲參數見4.3，為了容錯，參數會被鏈式備份，見4.4節；與以往系統不同，ps-lite用『』基於範圍通信『』優化了伺服器，優化了數據和向量時鐘

4.1時間向量

由於計算圖的複雜性及快速恢復參數的需求，每一個參數都有一個時間戳和它對應，時間戳對於追蹤聚合狀態或拒絕發送數據有很大的好處，假如有n個node和m個參數，時鐘向量需要O(mn)的空間複雜度，這樣是不可行且占帶寬的

但是ps使用了range-push/pull的策略，那麼那一個range的key/value對的時間戳肯定是一樣的，這一個range的參數所對應的時間戳可以壓縮到一個值，一個參數向量假如包含了k個range set，那麼時鐘向量只有k個值，對於整個ps系統，只需要O(mk)空間複雜度的時鐘向量，m是server節點的個數

4.2消息

一個節點可能發送消息到其他的節點或者節點組，一個消息實體包括一個key-value的列表和一個時鐘向量列表，通信與任務的格式都基於這種格式，對於後文碰到的格式，可能都是基於這種形式

消息可能是一個有效列表的子集，在一個range R裡面，缺失的key可以分配給一個相同的時間戳，當一個worker向所有的server或一個server group發送消息的時候，或者一個key分配給一個server node改變了的時候，這時候一條消息可能被key range 分開，通過這種辦法，我們把數據列表以及它們所對應的時間戳分開(這說明對於一個完整的消息，每個server node只保存了部分參數)

壓縮-每次數據迭代所產生的key-value的key其實是一樣的，這樣可以把key緩存起來，下次push或pull的時候只要push那一坨數據的hash值就行了。values同樣可以壓縮，worker向伺服器更新參數的時候很多值可能都是不變的，舉個例子之前介紹的用戶自定義的過濾器函數，這個函數只要是0活著閾值以下的都不會被push到伺服器端，因而在push的時候肯定push了很多0值到伺服器，這樣可以對這些0值壓縮，ps使用了一個叫做Snappy的庫對數據進行壓縮

4.3hash一致性

Ps 分key對辦法和傳統的分散式hash表很像：key和serverID都被插入到圖7這樣的一個環中，每一個server node管理它的插入點到逆時針方向的下一個server node插入點之間的那些key range,這個節點被稱作是這個key range的master，一個物理節點被複製成多分稱為虛擬節點，這樣做的目的是負載平衡

ps使用一個直接映射DHT的hash一致性演算法設計，server manager節點管理ring manager,所有的節點緩存它所對應的key在本地，這樣所有的server node 就能夠找到它所對應的key range，總之這裡的hash一致性的演算法與百度一把的hash一致性差不多，就是把server node和key都映射到一個環上，然後數據就近存儲到server節點

4.4 Replication and Consistence

每一個server節點存儲了k個它的鄰居節點的key range，也就是一份key range被k+1個server節點所保存，每個server保存的參數都有其對應參數的key range，每個節點都保存了其他k個server的這個key range表，在上面舉例中也就是圖7中k=2，server node1保存了server node2和server node3所擁有的key range

master節點數據的任何修改都會被copy到它的slaves機器上，圖8展示了work1推送x到server1, server1調用函數f得到新的值，只有這份修改後的數據被拷貝到server2這個操作才算結束。根據圖理解起來就是，worker1計算的梯度推送到server1，server1聚合梯度為參數，server1將含有時間戳到參數發送給server2, 這個操作才算結束。

原始的複製會備份k次，每一個worker更新梯度後master server處理了梯度後都會將其複製到備節點的機器上，ps框架提供了新的方法，等到所有的worker的梯度都被server聚合後，再去備份。

4.5 server manager

為了增加容錯的能力，需要支持添加與刪除節點

當添加一個新的節點時：

• 分配key range 給這個新的節點，這可能導致其他節點所維護的key被拆分
• 新節點獲取分配給它點數據，並且保存k個備份
• 新節點向其他節點廣播信息

分兩步獲取和range R相關的數據，首先對S節點拷貝所有的key-value對的數據及時鐘向量，這可能會導致一個range的時鐘向量被拆分，這個過程一樣演算法2相似，如果這個過程失敗，S node會返回之前的狀態，這個操作有原子性，第二步，S node不在執行相關的消息請求與處理，同時S node會將所有有關 range R的變化發送給新的節點。一個server節點N如果收到了相關廣播，它首先檢查自己是否和廣播中的R有關係，如果有則作相關的操作

當一個節點離開時：

節點的離開與新增節點類似，通過server node節點的心跳信息，server manager判斷一個節點是否還在工作，如果不在了，則將與其相關的range R的數據發送給其他的server node

4.6 worker managerment

增加新的worker和增加新的server node類似但是更簡單：

• Taske scheduler 分配新的數據給這個worker
• 新的worker從文件系統中或者已經存在的worker中獲取數據，然後從server中pull參數下來進行訓練
• Task scheduler廣播這一變化，這個變化可能會引起其他數據節點的數據減少

當一個worker離開的時候，演算法開發者有兩種選擇，一個是啟動一個新的worker來替代這個掛掉的worker，或者乾脆不管這個worker，因為從一坨巨大的數據中恢復一個worker的代價是很大的，另外一個原因是對與分散式訓練，失去這個worker對整體的性能其實沒什麼影響

測評

所有測評基於稀疏的邏輯回歸和隱含的狄利克雷分布

所用的兩個對比都是基於大的逆天的搜索數據，基於稀疏的邏輯回歸的實驗主要和其他兩個系統A和B做了比較，對比了目標loss下降與所花時間到關係，ps快到不行；另一幅圖的結果則展示了ps幾乎沒有等待時間但是A和B系統缺花了大量的時間阻塞在等待上面，文章中解釋了非同步，壓縮等上文所提到的原因加速了訓練的速度，提升資源利用率等