mxnet分布式2

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

1 Intruduction

數(shù)據(jù)很大，分布式已經(jīng)是趨勢(shì)尔艇，節(jié)點(diǎn)之間共享參數(shù)是必須惧眠，但是遇到三個(gè)挑戰(zhàn)

1. 高帶寬的獲取共享參數(shù)
2. 很多機(jī)器學(xué)習(xí)是順序的，同步和高延遲的阻礙影響了性能
3. 高容錯(cuò)率

1.1 ps-lite提供了5個(gè)核心功能特征

1. 異步高效通信
2. 靈活的一致性模型始衅，平衡同步與延遲，算法設(shè)計(jì)者自己平衡算法收斂與效率
3. 節(jié)點(diǎn)彈性伸縮
4. 高容錯(cuò)率且耐用，快速?gòu)男迯?fù)中恢復(fù)粱侣，時(shí)鐘向量機(jī)制使得網(wǎng)絡(luò)失敗或者分離后行為明確
5. 容易使用

1.2 工程實(shí)現(xiàn)的挑戰(zhàn)

1. 參數(shù)在節(jié)點(diǎn)之間的高效通信
2. 容錯(cuò)性，一臺(tái)機(jī)器掛了菜秦，整個(gè)任務(wù)還是在run

2機(jī)器學(xué)習(xí)

2.1 目標(biāo)

機(jī)器學(xué)習(xí)的目標(biāo)一般是最小化目標(biāo)函數(shù)甜害，最優(yōu)解被找到或者模型收斂，訓(xùn)練結(jié)束球昨，一般需要處理的數(shù)據(jù)量會(huì)很大尔店，在這些大量數(shù)據(jù)上執(zhí)行算法是本文的目的

2.2 最小化誤差(risk minimization)

機(jī)器學(xué)習(xí)最直觀的轉(zhuǎn)化是最小化誤差，risk指的是預(yù)測(cè)值和標(biāo)準(zhǔn)值之間的差值主慰，比如預(yù)測(cè)股票嚣州，預(yù)測(cè)的股價(jià)和后來(lái)真是的股票價(jià)格之間的差值就是risk

訓(xùn)練數(shù)據(jù)包含n個(gè)樣本，xi是第i個(gè)樣本共螺，且經(jīng)常是一個(gè)長(zhǎng)度為d第矢量该肴，n和d可能是十億和萬(wàn)億級(jí)別的數(shù)據(jù)，很多場(chǎng)合下藐不，樣本xi有一個(gè)label yi 和它對(duì)應(yīng)匀哄，在廣告預(yù)測(cè)中，yi則1對(duì)應(yīng)點(diǎn)擊了雏蛮，-1對(duì)應(yīng)沒(méi)有被點(diǎn)擊涎嚼。

基于最小化誤差方法能學(xué)習(xí)一個(gè)模型，該模型之后可以用來(lái)預(yù)測(cè)其他新的樣本挑秉，為了預(yù)測(cè)未來(lái)的一個(gè)廣告是否會(huì)被點(diǎn)擊法梯，系統(tǒng)將對(duì)'clikness'求和，然后機(jī)遇這一坨參數(shù)決定未來(lái)的廣告是否會(huì)被點(diǎn)擊犀概，就是新輸入經(jīng)過(guò)訓(xùn)練好的參數(shù)提取特征立哑，得到結(jié)果

在很多學(xué)習(xí)算法中，訓(xùn)練數(shù)據(jù)和模型大小息息相關(guān)姻灶，模型越大铛绰，或者越詳細(xì)，之后能做出的預(yù)測(cè)就越準(zhǔn)確产喉，除非訓(xùn)練集太小至耻，模型太大若皱，訓(xùn)練集太小會(huì)造成過(guò)擬合，模型記住了每一個(gè)樣本的特征尘颓，導(dǎo)致它失去了泛化能力走触，模型太小則捕捉不到感興趣的特征

正則化最小風(fēng)險(xiǎn)是找到模型復(fù)雜度和訓(xùn)練誤差之間的平衡，下面公式第一項(xiàng)是訓(xùn)練誤差疤苹，第二項(xiàng)是模型復(fù)雜度互广，它的目標(biāo)是使兩者的和加起來(lái)最小，前面一項(xiàng)是loss卧土，后面一項(xiàng)是regularizer

image

image

image

在表2和算法1中惫皱，數(shù)據(jù)被分成很多小份到每個(gè)節(jié)點(diǎn)上去聯(lián)合計(jì)算w，每個(gè)worker計(jì)算自己所得到的那份梯度尤莺，server去聚合所有worker得到的梯度旅敷，乘以學(xué)習(xí)率，然后進(jìn)行下一輪迭代

最耗時(shí)的操作是計(jì)算子梯度以便更新梯度颤霎，該任務(wù)分到每個(gè)worker中去做媳谁，每個(gè)worker執(zhí)行w?xik，對(duì)于太大的w這是不可行的友酱，幸運(yùn)的是一個(gè)worker只需要知道它的訓(xùn)練數(shù)據(jù)所對(duì)應(yīng)的那一部分參數(shù)w就行了

比如在廣告點(diǎn)擊的例子中，如果很少的廣告包括OSDI2014這個(gè)廣告語(yǔ)缔杉，那么大部分的worker就不需要更新去更新這個(gè)廣告詞所對(duì)應(yīng)的那一部分參數(shù)w锤躁，由于總的參數(shù)無(wú)法在一臺(tái)機(jī)器上放得下，每一臺(tái)機(jī)器需要的那一部分參數(shù)可以存放在本地或详，為了證明這個(gè)結(jié)論系羞，我們隨機(jī)的把數(shù)據(jù)分配到不同的worker，然后計(jì)算每個(gè)worker基于那部分?jǐn)?shù)據(jù)所需要的參數(shù)的平均大小霸琴，具體的細(xì)節(jié)在5.1章節(jié)中椒振。圖3顯示，100個(gè)worker的集群沈贝，每個(gè)worker只需要參數(shù)的7.8%，1000個(gè)只要0.15%

image

2.3 生成模型

在第二種機(jī)器學(xué)習(xí)算法中勋乾，一個(gè)樣本對(duì)應(yīng)的label是未知的宋下，這類學(xué)習(xí)叫無(wú)監(jiān)督學(xué)習(xí)，它們嘗試捕捉潛在的數(shù)據(jù)結(jié)構(gòu)辑莫，一個(gè)常見(jiàn)的例子是主題模型：給一堆文檔学歧，推導(dǎo)出每個(gè)文檔的主題

舉個(gè)例子，當(dāng)跑sosp2013的proceeding這個(gè)程序的時(shí)候各吨，一個(gè)算法可能會(huì)產(chǎn)生主題‘distribute system’, 'machine learnling', 'performance',算法通過(guò)論文內(nèi)容產(chǎn)生這些主題枝笨，而不是通過(guò)外部給的一個(gè)主題列表，在一些場(chǎng)合比如個(gè)性化推薦，問(wèn)題的規(guī)模會(huì)變得很大横浑，亟待用分布式并行處理

由于數(shù)據(jù)的規(guī)模剔桨，這些算法只有應(yīng)用在第一代參數(shù)服務(wù)器上才有商業(yè)價(jià)值，用文檔怎么產(chǎn)生當(dāng)前的主題估計(jì)的參數(shù)必須共享徙融，這是一個(gè)關(guān)鍵的挑戰(zhàn)

一個(gè)流行的主題建模是LDA洒缀，這個(gè)統(tǒng)計(jì)模型語(yǔ)其他的相當(dāng)不同，模型語(yǔ)算法1比較相似欺冀，不同的是計(jì)算的不再是梯度嗎树绩，而是文檔多大程度能被解釋,對(duì)于每一個(gè)文檔，這個(gè)算法需要額外的數(shù)據(jù)當(dāng)每次文檔被用到的時(shí)候隐轩，因?yàn)槊看挝臋n被處理的時(shí)候饺饭，文檔與元數(shù)據(jù)都會(huì)被存入取出。正如前面章節(jié)所描述职车，每個(gè)worker存儲(chǔ)了它所處理的文檔的關(guān)鍵字瘫俊，因而，采用分布式系統(tǒng)能處理更大的模型

3架構(gòu)

一個(gè)ps實(shí)例可以跑多于一個(gè)算法模型提鸟，ps由一個(gè)ps node group組成军援，worker由workergroup組成，一個(gè)server node維護(hù)著一份共享參數(shù)称勋，所有的server node之間可以相互通信胸哥，所有的server node共享一個(gè)server manage,server manager維護(hù)參數(shù)的一致性，比如收集節(jié)點(diǎn)的心跳信息赡鲜，參數(shù)的分配等等

image

每一個(gè)worker group運(yùn)行一個(gè)程序空厌，一個(gè)worker保存部分?jǐn)?shù)據(jù)并對(duì)它進(jìn)行計(jì)算，比如深度學(xué)習(xí)中的梯度計(jì)算银酬，worker只與serveer node之間通信嘲更，而不會(huì)在workers之間它們自己通信，和server通信比如將計(jì)算好的梯度推送到server或者從server獲取聚合后到參數(shù)揩瞪，每一個(gè)worker group都有一個(gè)worker scheduler赋朦，它負(fù)責(zé)向每個(gè)worker分配任務(wù)，并且管理它們的生命周期等等

參數(shù)服務(wù)器支持獨(dú)立的參數(shù)命名空間李破，這使得不同worker group之間的參數(shù)集互相獨(dú)立宠哄，同時(shí)不同的worker group也可以使用一個(gè)相同的命名空間，這樣可以以更大的并行程度去解決一個(gè)深度學(xué)習(xí)問(wèn)題嗤攻，另外一個(gè)例子是模型經(jīng)常被節(jié)點(diǎn)訪問(wèn)毛嫉，比如在線服務(wù)來(lái)訪問(wèn)這個(gè)模型(這坨參數(shù))，同時(shí)當(dāng)新的參數(shù)到一個(gè)worker時(shí)并計(jì)算出結(jié)果時(shí)妇菱，模型被這個(gè)worker所更新

參數(shù)服務(wù)器被設(shè)計(jì)用來(lái)簡(jiǎn)化分布式的應(yīng)用承粤，如第二章所提到的那些應(yīng)用暴区。被共享的參數(shù)用k-v對(duì)來(lái)表示，這樣對(duì)代數(shù)運(yùn)算更容易被處理辛臊，詳細(xì)介紹在3.2節(jié)仙粱，這些參數(shù)被分布式的存儲(chǔ)在server group不同的節(jié)點(diǎn)中，任何節(jié)點(diǎn)可以從服務(wù)器pull參數(shù)和push本地的參數(shù)(梯度)到server node浪讳。在默認(rèn)情況下缰盏，任務(wù)是由worker來(lái)完成了，少數(shù)情況下任務(wù)也可以由server節(jié)點(diǎn)完成淹遵。通過(guò)任務(wù)狀態(tài)依賴圖和與哪一部分參數(shù)通信口猜，ps讓算法開(kāi)發(fā)者可以靈活的選擇一致模型。

3.1 (key, value)向量

被不同的worker node共享的模型可以用key-value的鍵值對(duì)所表示透揣，比如在最小化損失函數(shù)的例子中济炎，key是特征ID,values是它所對(duì)應(yīng)的權(quán)重，對(duì)于LDA,key-value對(duì)是word-ID-topicID,模型的每一個(gè)實(shí)體可以被本地或遠(yuǎn)程的讀取或?qū)懭敕妫I值對(duì)的概念被很多框架所采用须尚。

ps框架在也采取了key-value這種策略，并且給予這樣的觀點(diǎn)：典型的機(jī)器學(xué)習(xí)算法把模型當(dāng)作線性代數(shù)對(duì)象來(lái)對(duì)待侍咱，在目標(biāo)函數(shù)和最小化風(fēng)險(xiǎn)的例子中耐床，w都被當(dāng)作向量對(duì)待。把這些鍵值對(duì)當(dāng)作線性代數(shù)對(duì)象楔脯，parameter server可以應(yīng)用同樣概念的運(yùn)算規(guī)則撩轰，比如向量加減乘除等，將向量的代數(shù)運(yùn)算也移植到key-value這樣的對(duì)象上來(lái)昧廷。

為了支持這些優(yōu)化堪嫂，ps框架假設(shè)這些key是按順序排列的，賦予這些鍵值對(duì)矩陣的語(yǔ)義木柬，key不能為0皆串，這把大量的編程問(wèn)題簡(jiǎn)化成了實(shí)現(xiàn)優(yōu)化算法，不僅僅是為了更高效的code眉枕，key-value這套接口還借力了CPU的一些線性代數(shù)多線程編程庫(kù)比如BLAS,PLACK,ATLAS等等恶复，簡(jiǎn)單的理解就是模型用鍵值對(duì)表示，這樣有一堆好處速挑。

3.2 Range Push and Pull

Range push就是將指定范圍的key-value推送谤牡，公式：w.push(R, dest),如果R只是一個(gè)值，那就是push單個(gè)key對(duì)應(yīng)的value梗摇，如果R對(duì)應(yīng)的范圍是所有參數(shù)的key拓哟，那就是一次完整的push想许，即將全部的參數(shù)推送到服務(wù)器伶授。這個(gè)接口也可以擴(kuò)展到和參數(shù)w共享key到其他數(shù)據(jù)通信断序，比如對(duì)于算法1中從worker中向server更新梯度，可以更新帶范圍的梯度糜烹，這樣寫w.push(R, g, dest)

3.3用戶自定義的函數(shù)-server node上執(zhí)行

除了聚合worker的參數(shù)到server上违诗，server node上還可以執(zhí)行用戶自定義的參數(shù)，因?yàn)閟erver上有更加完整疮蹦，更實(shí)時(shí)的參數(shù)诸迟，算法1將各個(gè)worker的梯度在server上進(jìn)行聚合，在算法3中有一些復(fù)雜的運(yùn)算愕乎，則需要在server上進(jìn)行阵苇，在上下的處理上，幾乎所有的操作都在server端

3.4異步任務(wù)和依賴

一個(gè)任務(wù)被遠(yuǎn)程調(diào)用者所觸發(fā)感论，它可以是worker node向server node發(fā)起的push／pull請(qǐng)求绅项，也可以是一個(gè)自定義的函數(shù)scheduler發(fā)送到任何node上，一個(gè)task可能包含許多子任務(wù)比肄，比如在算法1中一個(gè)數(shù)據(jù)迭代(workeriter)包含一個(gè)pull和一個(gè)push

任務(wù)被異步執(zhí)行快耿，調(diào)用者發(fā)出任務(wù)請(qǐng)求后就自己干別動(dòng)事情去了，調(diào)用方表記一個(gè)任務(wù)為執(zhí)行完當(dāng)且僅當(dāng)它收到任務(wù)的返回芳绩，比如用戶定義的函數(shù)被返回掀亥，pull或push的參數(shù)被pull／push成功的返回碼被接受到，任務(wù)處理者標(biāo)記一個(gè)任務(wù)被處理的的標(biāo)志是這個(gè)任務(wù)已經(jīng)完成且所有的子任務(wù)也被執(zhí)行完畢

默認(rèn)情況下任務(wù)是并行執(zhí)行的妥色，在圖5中搪花，iter10和iter11是并行執(zhí)行的，但是iter12的計(jì)算卻是依賴于iter11的結(jié)果的垛膝，iter12要等到iter11的計(jì)算結(jié)果push完后它才能開(kāi)始

image

任務(wù)依賴可以幫助算法實(shí)現(xiàn)鳍侣，比如在算法1中，只有所有worker的梯度被push到server的時(shí)候吼拥，server node才開(kāi)始做參數(shù)聚合倚聚，依賴的第二個(gè)作用是用于實(shí)現(xiàn)靈活的一致性

3.5靈活的一致性

通過(guò)并行地使用CPU，磁盤凿可，帶寬等資源惑折，可以提升系統(tǒng)等性能，但是這會(huì)使得數(shù)據(jù)出現(xiàn)不一致的現(xiàn)象枯跑。數(shù)據(jù)不一致的舉例：在圖5中惨驶，iter10和iter11是并行的，因而10和11獲取的是一樣的參數(shù)敛助，所以它們得到的數(shù)據(jù)是不一致的粗卜，但是12和11就是一致的，因?yàn)?2依賴了11纳击，10和11計(jì)算出來(lái)的東西一樣续扔，這個(gè)不一致導(dǎo)致了收斂變慢攻臀，如果用這個(gè)優(yōu)化算法來(lái)計(jì)算算法1，那么就會(huì)出現(xiàn)上面所說(shuō)的收斂變慢纱昧，但是在有一些例子中刨啸，算法對(duì)數(shù)據(jù)不一致性不是那么的敏感，每次迭代只有一部分的參數(shù)被更新识脆，比如在算法3中设联，并行的是特征(這個(gè)并行暫時(shí)也不是特別明白，模型并行),最好的折中往往要取決于各種參數(shù)灼捂，比如模型對(duì)數(shù)據(jù)不一致性的敏感程度离例，特征對(duì)數(shù)據(jù)的相關(guān)性，硬件組件等容量能力等悉稠。ps沒(méi)有規(guī)定死用戶必須采用哪些方案來(lái)適配具體固定的問(wèn)題粘招，而是算法設(shè)計(jì)者可以靈活的，根據(jù)具體情況選擇不同的折衷方案偎球。這里示出3種使用依賴可以實(shí)現(xiàn)的模型洒扎，它們的有向無(wú)環(huán)圖見(jiàn)圖6

image

• Sequential, 一個(gè)一個(gè)的執(zhí)行，后者只有在前者執(zhí)行完才能開(kāi)始
• Eventual, 各干個(gè)的衰絮，互不關(guān)聯(lián)
• Bounded delay, 某個(gè)任務(wù)開(kāi)始執(zhí)行還是阻塞取決于在它之間t時(shí)刻起的任務(wù)已經(jīng)被執(zhí)行完畢袍冷，如果t設(shè)置為0，那么他就是第一種順序執(zhí)行猫牡，如果是t為無(wú)窮胡诗，那么它就是第二種，互不影響

以上舉例的圖是可以動(dòng)態(tài)變化的淌友，比如scheduler想讓收斂點(diǎn)快一點(diǎn)煌恢，活著計(jì)算慢一點(diǎn)，活著有新的節(jié)點(diǎn)加入了計(jì)算圖震庭，那么可以修改這些因素

3.6用戶定義的過(guò)濾器

基于scheduler瑰抵，ps可以實(shí)現(xiàn)細(xì)粒度的控制同步，只有符合過(guò)濾器條件的worker的參數(shù)才會(huì)同步到server上器联，這樣做是因?yàn)閮?yōu)化器本身有更多的參數(shù)的信息二汛，舉個(gè)例子,significantly modified filter,在worker上計(jì)算出來(lái)的條目(entry)-比如梯度，只有超過(guò)閾值的才會(huì)被推送到server服務(wù)器上拨拓，在5.1節(jié)中肴颊，討論了另外一種KKT的方案，它利用了優(yōu)化問(wèn)題的最優(yōu)條件-只有能影響權(quán)重的梯度才會(huì)被發(fā)送到srver上(這和上文提到的不是一樣嗎渣磷，稀疏)

image

4實(shí)現(xiàn)

服務(wù)器使用連續(xù)的hash(鍵值對(duì))存儲(chǔ)參數(shù)見(jiàn)4.3婿着，為了容錯(cuò)，參數(shù)會(huì)被鏈?zhǔn)絺浞荩?jiàn)4.4節(jié)竟宋；與以往系統(tǒng)不同奥务，ps-lite用‘’基于范圍通信‘’優(yōu)化了服務(wù)器，優(yōu)化了數(shù)據(jù)和向量時(shí)鐘

4.1時(shí)間向量

由于計(jì)算圖的復(fù)雜性及快速恢復(fù)參數(shù)的需求袜硫，每一個(gè)參數(shù)都有一個(gè)時(shí)間戳和它對(duì)應(yīng)，時(shí)間戳對(duì)于追蹤聚合狀態(tài)或拒絕發(fā)送數(shù)據(jù)有很大的好處挡篓，假如有n個(gè)node和m個(gè)參數(shù)婉陷，時(shí)鐘向量需要O(mn)的空間復(fù)雜度，這樣是不可行且占帶寬的

但是ps使用了range-push/pull的策略官研，那么那一個(gè)range的key/value對(duì)的時(shí)間戳肯定是一樣的秽澳，這一個(gè)range的參數(shù)所對(duì)應(yīng)的時(shí)間戳可以壓縮到一個(gè)值，一個(gè)參數(shù)向量假如包含了k個(gè)range set戏羽，那么時(shí)鐘向量只有k個(gè)值担神，對(duì)于整個(gè)ps系統(tǒng)，只需要O(mk)空間復(fù)雜度的時(shí)鐘向量始花，m是server節(jié)點(diǎn)的個(gè)數(shù)

4.2消息

一個(gè)節(jié)點(diǎn)可能發(fā)送消息到其他的節(jié)點(diǎn)或者節(jié)點(diǎn)組妄讯，一個(gè)消息實(shí)體包括一個(gè)key-value的列表和一個(gè)時(shí)鐘向量列表，通信與任務(wù)的格式都基于這種格式酷宵，對(duì)于后文碰到的格式亥贸，可能都是基于這種形式

消息可能是一個(gè)有效列表的子集，在一個(gè)range R里面浇垦，缺失的key可以分配給一個(gè)相同的時(shí)間戳炕置，當(dāng)一個(gè)worker向所有的server或一個(gè)server group發(fā)送消息的時(shí)候，或者一個(gè)key分配給一個(gè)server node改變了的時(shí)候男韧，這時(shí)候一條消息可能被key range 分開(kāi)朴摊，通過(guò)這種辦法，我們把數(shù)據(jù)列表以及它們所對(duì)應(yīng)的時(shí)間戳分開(kāi)(這說(shuō)明對(duì)于一個(gè)完整的消息此虑，每個(gè)server node只保存了部分參數(shù))

壓縮-每次數(shù)據(jù)迭代所產(chǎn)生的key-value的key其實(shí)是一樣的甚纲，這樣可以把key緩存起來(lái)，下次push或pull的時(shí)候只要push那一坨數(shù)據(jù)的hash值就行了朦前。values同樣可以壓縮贩疙，worker向服務(wù)器更新參數(shù)的時(shí)候很多值可能都是不變的，舉個(gè)例子之前介紹的用戶自定義的過(guò)濾器函數(shù)况既，這個(gè)函數(shù)只要是0活著閾值以下的都不會(huì)被push到服務(wù)器端这溅，因而在push的時(shí)候肯定push了很多0值到服務(wù)器，這樣可以對(duì)這些0值壓縮棒仍，ps使用了一個(gè)叫做Snappy的庫(kù)對(duì)數(shù)據(jù)進(jìn)行壓縮

4.3hash一致性

Ps 分key對(duì)辦法和傳統(tǒng)的分布式hash表很像：key和serverID都被插入到圖7這樣的一個(gè)環(huán)中悲靴，每一個(gè)server node管理它的插入點(diǎn)到逆時(shí)針?lè)较虻南乱粋€(gè)server node插入點(diǎn)之間的那些key range,這個(gè)節(jié)點(diǎn)被稱作是這個(gè)key range的master，一個(gè)物理節(jié)點(diǎn)被復(fù)制成多分稱為虛擬節(jié)點(diǎn)莫其，這樣做的目的是負(fù)載平衡

ps使用一個(gè)直接映射DHT的hash一致性算法設(shè)計(jì)癞尚，server manager節(jié)點(diǎn)管理ring manager,所有的節(jié)點(diǎn)緩存它所對(duì)應(yīng)的key在本地耸三，這樣所有的server node 就能夠找到它所對(duì)應(yīng)的key range，總之這里的hash一致性的算法與百度一把的hash一致性差不多浇揩，就是把server node和key都映射到一個(gè)環(huán)上仪壮，然后數(shù)據(jù)就近存儲(chǔ)到server節(jié)點(diǎn)

4.4 Replication and Consistence

每一個(gè)server節(jié)點(diǎn)存儲(chǔ)了k個(gè)它的鄰居節(jié)點(diǎn)的key range，也就是一份key range被k+1個(gè)server節(jié)點(diǎn)所保存胳徽，每個(gè)server保存的參數(shù)都有其對(duì)應(yīng)參數(shù)的key range积锅，每個(gè)節(jié)點(diǎn)都保存了其他k個(gè)server的這個(gè)key range表，在上面舉例中也就是圖7中k=2养盗，server node1保存了server node2和server node3所擁有的key range

master節(jié)點(diǎn)數(shù)據(jù)的任何修改都會(huì)被copy到它的slaves機(jī)器上缚陷，圖8展示了work1推送x到server1, server1調(diào)用函數(shù)f得到新的值，只有這份修改后的數(shù)據(jù)被拷貝到server2這個(gè)操作才算結(jié)束往核。根據(jù)圖理解起來(lái)就是箫爷，worker1計(jì)算的梯度推送到server1，server1聚合梯度為參數(shù)聂儒，server1將含有時(shí)間戳到參數(shù)發(fā)送給server2, 這個(gè)操作才算結(jié)束虎锚。

原始的復(fù)制會(huì)備份k次，每一個(gè)worker更新梯度后master server處理了梯度后都會(huì)將其復(fù)制到備節(jié)點(diǎn)的機(jī)器上衩婚，ps框架提供了新的方法翁都，等到所有的worker的梯度都被server聚合后，再去備份谅猾。

image

4.5 server manager

為了增加容錯(cuò)的能力柄慰，需要支持添加與刪除節(jié)點(diǎn)

當(dāng)添加一個(gè)新的節(jié)點(diǎn)時(shí)：

• 分配key range 給這個(gè)新的節(jié)點(diǎn)，這可能導(dǎo)致其他節(jié)點(diǎn)所維護(hù)的key被拆分
• 新節(jié)點(diǎn)獲取分配給它點(diǎn)數(shù)據(jù)税娜，并且保存k個(gè)備份
• 新節(jié)點(diǎn)向其他節(jié)點(diǎn)廣播信息

分兩步獲取和range R相關(guān)的數(shù)據(jù)坐搔，首先對(duì)S節(jié)點(diǎn)拷貝所有的key-value對(duì)的數(shù)據(jù)及時(shí)鐘向量，這可能會(huì)導(dǎo)致一個(gè)range的時(shí)鐘向量被拆分敬矩，這個(gè)過(guò)程一樣算法2相似概行，如果這個(gè)過(guò)程失敗，S node會(huì)返回之前的狀態(tài)弧岳，這個(gè)操作有原子性凳忙，第二步，S node不在執(zhí)行相關(guān)的消息請(qǐng)求與處理禽炬，同時(shí)S node會(huì)將所有有關(guān) range R的變化發(fā)送給新的節(jié)點(diǎn)涧卵。一個(gè)server節(jié)點(diǎn)N如果收到了相關(guān)廣播，它首先檢查自己是否和廣播中的R有關(guān)系腹尖，如果有則作相關(guān)的操作

當(dāng)一個(gè)節(jié)點(diǎn)離開(kāi)時(shí)：

節(jié)點(diǎn)的離開(kāi)與新增節(jié)點(diǎn)類似柳恐，通過(guò)server node節(jié)點(diǎn)的心跳信息，server manager判斷一個(gè)節(jié)點(diǎn)是否還在工作，如果不在了乐设，則將與其相關(guān)的range R的數(shù)據(jù)發(fā)送給其他的server node

4.6 worker managerment

增加新的worker和增加新的server node類似但是更簡(jiǎn)單：

• Taske scheduler 分配新的數(shù)據(jù)給這個(gè)worker
• 新的worker從文件系統(tǒng)中或者已經(jīng)存在的worker中獲取數(shù)據(jù)讼庇，然后從server中pull參數(shù)下來(lái)進(jìn)行訓(xùn)練
• Task scheduler廣播這一變化，這個(gè)變化可能會(huì)引起其他數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)減少

當(dāng)一個(gè)worker離開(kāi)的時(shí)候近尚，算法開(kāi)發(fā)者有兩種選擇蠕啄，一個(gè)是啟動(dòng)一個(gè)新的worker來(lái)替代這個(gè)掛掉的worker，或者干脆不管這個(gè)worker戈锻，因?yàn)閺囊慧缇薮蟮臄?shù)據(jù)中恢復(fù)一個(gè)worker的代價(jià)是很大的歼跟，另外一個(gè)原因是對(duì)與分布式訓(xùn)練，失去這個(gè)worker對(duì)整體的性能其實(shí)沒(méi)什么影響

測(cè)評(píng)

所有測(cè)評(píng)基于稀疏的邏輯回歸和隱含的狄利克雷分布

所用的兩個(gè)對(duì)比都是基于大的逆天的搜索數(shù)據(jù)舶沛，基于稀疏的邏輯回歸的實(shí)驗(yàn)主要和其他兩個(gè)系統(tǒng)A和B做了比較，對(duì)比了目標(biāo)loss下降與所花時(shí)間到關(guān)系窗价，ps快到不行如庭；另一幅圖的結(jié)果則展示了ps幾乎沒(méi)有等待時(shí)間但是A和B系統(tǒng)缺花了大量的時(shí)間阻塞在等待上面，文章中解釋了異步撼港，壓縮等上文所提到的原因加速了訓(xùn)練的速度坪它，提升資源利用率等