網絡斷路感知的同步機制*

項哲慧，秦小麟+，猶 鋒，劉 亮

1.南京航空航天大學 計算機科學與技術學院，南京 210016

2.南瑞集團有限公司，南京 210003

1 引言

近年來隨著數據規模的增大，優化各種大數據處理平臺的性能已成為研究的熱點。圖計算平臺Pregel[1]和Giraph[2]等基于并行計算加快圖數據的處理，它們采用BSP[3]編程模型作為并行算法的基礎框架。Barrier（柵欄）同步是并行計算常采用的一種同步方法,用于BSP的兩個超步（super-step）之間的同步。一個線程調用Barrier意味著該線程需要在該點等待所有線程到達，控制線程的執行進度確保并行計算的正確性。在并行最小生成樹算法中[4]，對多個連通分量進行合并需要先統計所有連通分量選擇的邊，再確定該邊是否同時被兩個連通分量選中，進而合并連通分量。因此線程在計算完連通分量選擇的邊之后需要同步，否則會出現先計算完的線程無法判斷邊是否同時被兩個分量選中，因為選擇該邊的另一個連通分量可能由其他線程處理。可見Barrier同步是保證并行計算正確性不可或缺的部分，它的效率直接影響并行計算的性能。

并行計算有兩種計算結構：共享內存結構和消息傳遞結構。后者在大數據處理平臺中更常見，如Pregel，Giraph的Barrier同步機制是通過消息傳遞實現線程之間的同步的。然而在網絡中，消息過量、消息重發以及消息的輸入速率超過輸出速率[5-6]等原因都能造成網絡擁堵或者網絡斷路。而現有的Barrier算法在遇到網絡擁堵或者網絡斷路時只能等待或者選擇一條更遠的路由傳遞消息，降低了同步算法的效率。

造成上述問題的主要原因是現有Barrier算法的通信模式[7](communication pattern)是固定的。如圖1（a）所示：在由節點a、b和c組成的網絡上進行同步，3個節點兩兩之間有物理鏈路連接（雙向箭頭表示物理鏈路）。Barrier算法設定由a匯總3個節點的狀態，則節點b、c需分別向a傳送同步消息，此時，節點b、c消息傳遞分別只需1跳的距離（實線箭頭）。如果ab鏈路斷路，節點c向a傳送消息的路徑不變，但節點b與a通信時要通過節點c轉送消息，導致節點a、b的通信距離增加到2跳（虛線箭頭），且加重了ac鏈路上的擁堵狀況。但如果能改變通信模式，由c來匯總消息，則節點a、b分別向c傳遞同步消息，均可1跳到達，避開了斷掉的ab鏈路。然而直接修改通信模式代價較大，如調整最小生成樹結構的Tree算法的通信模式時需重新構建最小生成樹，調整過程依賴多個輪次的同步[4]、額外的消息來確認節點間的通信關系以及額外的空間來存儲新的通信模式結構，避免與調整過程中依賴的通信模式混淆。

Fig.1 Network topology圖1 網絡拓撲

此外，通信模式的結構與網絡拓撲的契合度會影響算法效率。現有的大數據平臺[1-2]使用的同步算法（如PUB[8]）的通信模式結構為主從結構(masterslave，MS)，而MS結構僅適合星型拓撲的網絡結構。如圖1（b）所示：由節點a、b和c組成的線型網絡由ab、bc兩條物理鏈路連通（雙向箭頭表示物理鏈路），設定由a匯總3個節點的狀態，在MS結構中，節點b給a發送同步消息需要1跳，節點c給a發送同步消息需要2跳（實線箭頭）。在2層樹形結構中，節點a為樹根，b為中間節點，c為葉子節點，葉子節點c給b發送同步消息，中間節點b匯總自身及子節點（節點b、c）的消息再發送給根節點a，節點b、c發送消息分別只需1跳距離（虛線箭頭）。可知通信模式決定的需要通信的節點間的距離（跳數）越小越好（更契合網絡拓撲）。

針對上述問題，本文在原來的Barrier算法基礎上提出一種新的同步算法，可調整通信模式，提高同步算法在網絡斷路下的效率。本文貢獻如下：

（1）引入節點編碼將通信模式與網絡拓撲結構分離開，并提出一個異步調整算子（asynchronous adjustment operator，AAO）通過修改節點編碼的方式達到調整通信模式的目的，這種調整方式比直接調整通信模式的代價低。

（2）提出了局部連續樹（local continuous tree,LCT）結構的通信模式，LCT結構具有局部連續性，可以減小網絡中需要相互通信的節點之間的距離，提高通信效率。

（3）結合LCT結構和AAO算子，提出了動態局部連續樹(dynamic local continuous tree，DLCT)算法。并實驗比較了DLCT算法與其他5種Barrier算法在網絡斷路情況下的效率，結果表明DLCT比其他算法的效率高30%到50%。

本文結構如下：第2章介紹Barrier算法的相關工作以及現有算法在網絡斷路下的局限性；第3章介紹提出的DLCT算法；第4章實驗評估DLCT在網絡斷路下的效率；第5章總結工作。

2 相關工作

Barrier算法可分為三類：單相、雙相和多層。單相算法用消息散播的方式，使得各節點都獲得全局節點的同步狀態并進行獨立判斷；雙相算法有個中心節點來獲取并判斷全局節點的同步狀態，在Gather階段中心節點匯總所有節點的同步消息，判斷全局的同步狀態，并在Release階段通知其他節點所有節點已到達同步狀態并結束同步；多層算法將網絡分層，每層應用不同的Barrier算法，使得不同算法間進行優勢互補，并提高算法的拓展性。然而這些算法均不能很好地適應網絡斷路狀況。

單相 Barrier算法有 All to All、Butterfly[9]、Dissemination[7]和Pairwise exchange[10]。其中后3種采用了Han等提出的消息散播模式[11]，把All to All的O(N2)的消息復雜度降低到O(NlbN)。此類算法適用于共享內存的多核框架，可以減少鎖的使用。但是在網絡框架下，該類算法的消息量比雙相Barrier算法O(N)大，導致同步效率相對較差，且通信模式復雜，不易調整。

雙相Barrier算法有MS（master-slave）、combining tree[12]、tournament[7,13]、MSC（Mellor&Scott’s combining tree）[14]、BST（binominal structure tree）[15]和2層樹形結構[16]。其中MS算法簡單，很多大數據平臺的同步模型都使用MS算法[1-2]，但是master節點容易成為全局的熱點。Combining tree的k叉樹結構、tournament的錦標賽結構和BST的二項樹結構等都能緩解一定的熱點問題。上述結構都是不同形狀的樹形結構，調整代價大，涉及到額外的同步、通信和存儲空間。

多層Barrier算法有 MLB（multi-layer barrier）[17]、TAB（tree-based all-to-all barrier）[18]和文獻[19]等。但是因為多層算法只是融合現有算法，其通信模式依然是固定的，且不易調整，同樣會出現斷路時效率大幅降低的問題。

此外，文獻[20]研究了上述Barrier算法在負載不均衡的情況下的效率。文獻[21]在共享內存結構下研究Barrier算法的效率。

3 DLCT Barrier算法

3.1 LCT通信模式

因為雙相Barrier算法消息復雜度低，比較適合在網絡中同步線程，所以本文在雙相Barrier算法的基礎上改進。本文采用的通信模式為二項樹結構。如圖2（a）所示，在LCT結構中，ID=x的節點的父節點為ID=x&(x-1)，比如節點6的父節點為6&(6-1)=4，相當于將子節點的最低非0位置0。根節點0的父節點為null。通信模式結構中相連的節點間需要通信。

Fig.2 Structures of LCT&BST圖2 LCT和BST的結構

本文給出通信模式的形式化定義，用一對映射G，R:{ID}→p({ID})分別表示節點x在Gather階段和Release階段的通信對象的集合，p({ID})表示節點集合的冪集（ID與節點一一對應）。在Gather階段每個節點需要與父節點通信，從而逐步將同步信息匯總到根節點，計算父節點的過程對應通信模式中的G映射：G(ID)={(ID-1)&ID}，相當于將二進制形式的ID的最低非0比特位置0。在Release階段每個節點需要與子節點通信，逐步廣播同步結束消息到葉子節點，計算孩子節點的過程對應R映射，R(ID)的計算見算法1，即將二進制形式的ID的最低非0位之后的比特位逐個置1。

算法1 R(ID)LCT Release階段的目標節點集合計算

通過引入節點編碼以簡化通信模式的調整：將網絡中各節點的位置映射到全局唯一的ID值，使其與LCT結構中相同ID的節點對應，用映射num:{(x，y)}→[0，N)表示。其中，(x，y)表示節點位置，N表示網絡節點個數。num映射用ID值將通信模式LCT結構中的節點與網絡節點聯系起來，網絡節點先通過num映射得到相應的ID，再通過LCT的G、R映射計算出在Gather和Release階段的通信對象。如在Gather階段，位置為(x，y)的非根節點需要發送同步消息給位置為num-1(G(num(x，y)))的節點，其中num-1為num的反函數。在節點編號的基礎上僅改變網絡節點的ID值就能達到調整通信模式的目的，具體調整過程在3.2節闡述。

LCT與同為二項樹的BST結構比較有兩點優勢：（1）簡化節點編碼；（2）易于更新鏈路集合。其中第（2）點在3.2節具體闡述。

LCT能簡化節點編碼：節點編碼傾向于將需要通信的兩個ID賦值給相互靠近的兩個物理節點以減小通信距離，提高算法效率。如圖2（a）、（b）所示，分別為LCT和BST的結構圖，容易看出LCT的子樹中的節點是連續編號的，而BST的編號是跳躍的，可知LCT結構中需要相互通信的節點編號相近。節點編碼時只需根據節點距離依次編碼，即可滿足減少通信距離的需求，此類編碼方式有S-order curve、Z-order curve[22]、Hilbert curve[23]等。本文采用的編碼方式就是S-order curve，其num映射為num(x，y)=x×size+y+(x%2)×(size-1-2y)，其中size為網格型網絡的長寬。用s-curve的編碼方式將圖2中虛線框內的節點映射到網絡節點時（參考圖3（a）或（c）），LCT結構中的節點12～15映射在一條直線上，而BST中的節點3、7、11、15卻分別在置于網絡中相距最遠的4個位置形成一個波浪形。在相同的簡單的節點編碼方式下LCT結構在網絡中的通信效率更高，即（在保證高效通信的情況下）LCT能夠簡化節點編碼。

3.2 異步調整算子(AAO）

調整通信模式即改變節點的通信對象，從而改變使用的鏈路集合，起到避開斷路的作用。通信模式調整主要有兩種方式，改變節點編碼num映射或者改變G、R映射。而改變G、R映射相當于改變邏輯上的樹型連接，調整方式復雜，代價大。本文采用改變num映射的方式調整通信模式。異步調整算子round(K)的作用是更新網絡節點的ID，即ID′=ID+KmodN，因為ID=num(x，y)，所以改變ID本質上即改變num映射：num′(x，y)=num(x，y)+KmodN。該調整過程僅對num映射進行模加運算，調整的計算代價很低。

Fig.3 Link set in use of BST&LCT before and after adjustment圖3 BST和LCT調整前后使用的鏈路集合

UQ的值域為[0，1]：當A=B時UQ=0，無更新量；當A?B=? 時UQ=1，更新量最大。

LCT易于更新鏈路集合：如圖3所示，分別為BST和LCT采用s-curve的方式映射到4×4的網絡中，并調用round(1)更新通信模式。圖中粗實線表示網絡使用的鏈路集合，可看出通過調整，LCT和BST使用的鏈路集合都發生變化。根據LCT結構（圖2）可知節點4、5之間需要通信，在圖3（c）中為（2,3）和（2,4）節點通信，調整之后如圖3（d）變為（1,4）和（2,4）節點通信，更換了使用的鏈路。LCT結構調整前后使用的鏈路集合的交集大小為7，并集大小為26，計算LCT的更新量UQ(LCT)=1-7/26=73.1%。同理根據圖3（a）、（b）計算BST調整之后的更新量UQ(BST)=18.2%。LCT的更新量顯著大于BST，即LCT更容易更新鏈路集合（在實驗4.2節會給出BST和LCT完整的更新量的比較，說明在整體上LCT結構的更新量大于BST，上述例子并非特例）。

異步調整過程在Release階段進行，其調整信息K值（round（K）的參數值）存放在同步消息結構中。同步消息結構如圖4所示：G/R標志該消息的類型：Gather和Release；content在不同類型消息中的含義不同：在Gather消息中，content保存消息經過的路徑的實際長度，該內容會被消息經過的每個節點更新，根節點根據Gather消息的content判斷是否存在斷路；在Release消息中，content表示調整算子的K值，收到Release消息的節點先轉發消息給子節點，然后根據K值改變num映射，調整結構。調整信息借助同步消息進行傳遞，無須增加額外的消息量，且每個節點獨立更新自己的num映射，異步調整結構。

本文定義了更新量UQ（update quantity）來量化AAO更新鏈路集合的效果，更新量越大說明結構越易于更新，從而越容易避開斷路。

定義1（更新量UQ）在AAO的作用下鏈路集合從A變為B，則更新量為：

Fig.4 Structure of synchronous message圖4 同步消息結構

此外，異步調整過程不會破壞同步過程的正確性。調整過程中只存在3種消息傳遞：舊節點給舊節點發送本次同步的Release消息，新節點給新節點發送下次同步的Gather消息，新節點給舊節點發送下一次的Gather消息。每個節點更新完num映射就結束本次同步過程，且如果節點未更新，它的子節點也一定未更新，所以不存在舊節點給新節點發送Release消息的情況。其中前兩種情況相當于通信模式固定時的同步消息傳送，不會破壞同步過程。在第3種情況中，因為舊節點處于本次同步過程的Release階段，只要保證在Release階段時本次的Gather消息已經清空，則下次的Gather消息與本次的Gather消息不會混在一起，隔離了兩次同步中的消息就能保證兩次同步過程正確。如何保證在Release階段Gather消息已清空會在3.3節解釋。

由調整過程可知，AAO有以下3個優點：（1）各節點異步調整num映射，不需要依賴額外的同步過程，或者額外的空間暫存新值；（2）斷路的判定信息以及調整值K存放在同步消息中，不會增加消息量；（3）每次更新通信模式僅僅對節點num進行模加，計算量極低。降低通信模式調整對同步算法效率的影響。

3.3 DLCT Barrier同步過程

DLCTBarrier同步過程分為3階段，分別為Gather、Release和調整階段。相比原來的雙相Barrier過程多了調整階段。算法2為DLCT算法的具體過程。步驟1、2，初始化當前節點的ID和子節點的數量（需要接收的Gather消息數量）。Gather階段：步驟3、4，節點等待接收所有子節點的Gather消息；步驟5，匯總子節點消息的路徑長度；步驟6，清空Gather消息；步驟7、8，發送Gather消息給父節點。注意這里需要先清空消息隊列再發送消息，確保節點不會在進入Release階段之后還存有本次的Gather消息。因為如果先發送消息給父節點，可能出現還未清空消息時，就收到父節的Release消息的情況。Release階段：步驟9、10，非根節點等待來自父節點的Release消息；步驟12，根節點匯總Gather消息，判斷是否存在較大影響的斷路，決定是否需要調整通信模式；步驟14，非根節點從Release消息中獲取K值；步驟15、16，發送Release消息給子節點。異步調整階段：步驟17、18，各節點根據K值調整通信模式；步驟19，最后結束同步過程，各節點恢復計算任務。

算法2DLCT Barrier同步過程

以4個節點的網絡為例，節點0的子節點為1、2，節點1的子節點為3。假設節點0、2之間的鏈路中斷，則在Gather階段根節點0收到所有子節點的消息之后，根據消息的跳數判斷網絡出現斷路情況，然后調用round(1)做出調整，并在Release階段將調整參數K=1通過Release消息傳遞給子節點。根節點0調整之后節點編號變為1（成為葉子節點），標記該節點為x，假設當其他3個節點還處于Release階段時，節點x已進入下一階段的同步過程，并發送Gather消息給節點0（原節點3），節點3在Release階段已清空Gather消息隊列，此時節點x給原節點3發送消息可以安全緩存到隊列中而不會與上一次的Gather消息混合，直到原節點3調整節點編號為0并進入下一次同步之后才會處理緩存的Gather消息，因此調整通信模式的過程是安全的。

4 實驗與分析

4.1 實驗設計

實驗在JADE[24]4.4.0平臺提供的通信基礎上搭建模擬的網格型網絡：每個節點都有唯一的位置信息(x，y)，并根據位置信息確定其鄰居節點（可以直接發送消息的節點），在發送消息給目標節點的過程中，先將消息發送給離目標節點最近的鄰居節點，如果接收到消息的節點非目標節點則繼續選取離目標節點最近的鄰居節點轉發消息。斷路情況通過刪除鄰居節點來實現，比如設定相鄰的a、b節點之間的鏈路中斷，則節點a刪除鄰居節點b，節點b刪除鄰居節點a。網絡層封裝消息的路由過程，保留send、receive接口供Barrier算法傳送同步消息。實驗采用一個簡單的同步測試程序測試各Barrier算法的效率，測試程序調用3次Barrier進行同步，每兩次同步之間sleep 0.5 s（無同步情況下的單個線程運行時間為1 s）。各Barrier算法都給同步測試程序提供統一的Barrier()接口用于各個節點的同步。

實驗選取現有的5種Barrier算法進行實驗，雙相算法采用MS、Tree、Tournament，分別代表不同的結構，其中MS為單層樹狀結構，Tree為最小生成樹結構，Tournament為錦標賽結構（混合二項樹與單層樹結構）。單相算法選取dissemination作為代表，因為該算法在單相算法中效率最高：A2A（all-to-all）算法消息量大，butterfly、pairwise exchange在節點數量非2的冪次方時效率驟降。多層算法由單相和雙相算法中效率最高的dissemination+Tree構成。在實驗過程中發現單純的DLCT算法擴展性不好，因此實驗采用了雙層算法ID1：DLCT+MS和ID2：DLCT+Tree。ID1和ID2的結構依然是樹狀結構，通信模式的調整過程只作用于DLCT層。

實驗結果有兩個指標分別為更新量UQ和同步程序運行時間。采用更新量來量化LCT結構在AAO調整下避開斷路的能力，更新量越大則越容易避開斷路。用同步程序運行時間來比較各Barrier算法的同步效率，因為用于測試Barrier算法效率的程序是相同的，程序的運行時間可以側面反映出Barrier算法的效率，程序運行時間越短則Barrier算法效率越高。此外，實驗設定了不同比例的斷路狀況來測試Barrier算法在斷路情況下的效率，并設定了不同的網絡規模，測試Barrier算法的拓展性。

4.2 LCT結構避開斷路的能力

為證明LCT避開斷路的能力，實驗在大小為4×4的網格型網絡上計算LCT的更新量。在16節點的網絡中，共有16種s-curve型的節點編號（確定了其中一個節點的編號就可以根據s-curve確定網絡中所有節點的編號），每種編號可以通過調用異步調整算子round(K)轉化成其他編號，一共有16×16種轉化。分別計算出這256種情況下的UQ(LCT)，其平均更新量為0.552 7，即平均每次調整結構都能更新一半的鏈路。

此外實驗比較了LCT和BST結構的更新量，計算BST在256種轉化下的相應的更新量UQ(BST)，取LCT與BST更新量的差值UQ(LCT)-UQ(BST)作直方圖，結果如圖5所示。當LCT的更新量大于BST時，豎條為正，出現在x軸上方，反之則出現在下方。由圖可知x軸上方的豎條比較密集，可見在絕大部分的轉化中LCT通信模式的更新量比BST大，從而可知LCT比BST更易更新鏈路。因為DLCT可通過雙層Barrier算法拓展，實驗只考慮算法在4×4大小的網絡中的更新量。

4.3 DLCT算法的拓展性

如圖6所示（a）、（b）、（c）分別為各Barrier算法在網絡鏈路完好、存在10%的網絡斷路和存在20%的網絡斷路的情況下，以及在不同網絡規模下（網絡節點數不同）的運行時間。

Fig.5 Update quantity of LCT&BST圖5 LCT和BST結構的更新量

除ID1、ID2和Tree外，其他算法的拓展性都比較差。Dissemination算法的消息量為NlbN，隨著網絡規模的增大，其消息量與其他算法的消息量的差值增大，雙層算法Dissemination+Tree有同樣的問題。Tournament和MS中的通信模式不契合網絡拓撲，導致通信距離比較長，網絡規模的增長，越發加劇了這種現象。ID1、ID2和Tree的通信模式比較契合網絡拓撲，其中Tree是依據實際網絡建立的最小生成樹，從圖6（a）可以看出無斷路情況下，隨著網絡規模的增大Tree算法的效率基本保持不變。DLCT在較大規模的網絡中的效率略低于Tree算法。網絡斷路使得每種算法的效率都有不同程度的降低，從圖6（b）、（c）可以看出在網絡斷路情況下，DLCT的斜率比Tree低，更適應斷路情況。

Fig.6 Delay of Barrier algorithms in different break rates of link圖6 Barrier算法在不同斷路率下的延時

4.4 DLCT在網絡斷路下的效率

從圖6可以看出雙層DLCT與Tree算法的效率比較高。實驗進一步比較斷路情況對DLCT與Tree的效率的影響。如圖7所示的橫向5組實驗分別是3種算法在不同網絡規模下的運行時間，每組中的3條豎線分別為對應算法在斷路率為[0%，50%]的網絡中運行時間的范圍，線上的黑點為算法在不同斷路率下對應的運行時間。可以看出兩種結構的DLCT的兩種算法ID和ID2都比Tree算法效率高，能達到30%到50%的效率提升。比較線段最低點（斷路率為0的情況）Tree算法跟DLCT算法的效率相差不大，但是在斷路情況下Tree算法效率急劇下降，圖7所示的Tree算法的線條長度最長便可說明該算法受斷路影響最大。本實驗說明了DLCT算法能在一定程度上提高Barrier算法在網絡斷路情況下的效率，從而表現得比其他算法優異。

Fig.7 Delay of DLCT&Tree in different break rates of link圖7 DLCT與Tree在不同斷路率下的延時

5 結束語

本文針對網絡斷路情況下同步算法效率急劇下降的問題，提出了DLCT Barrier算法，采用高效的LCT通信模式和低代價的AAO調整算子，用動態調整通信模式的方式避開網絡斷路提高算法效率。與現有的Barrier算法比較，DLCT在不同網絡斷路情況下算法效率提高30%到50%。

除了網格型網絡，DLCT還可以應用于其他網絡拓撲，如節點隨機分布的傳感網絡，根據節點距離依次編號(x，y)位置形成num映射表就能完成到傳感器網絡的應用。此外后續工作還可以通過對judge函數進行優化，更有效調整通信模式。