杜玉潔 王志剛 王 寧,2 劉芯亦 衣軍成 聶 婕 魏志強(qiáng) 谷 峪 于 戈

1（中國(guó)海洋大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 山東青島 266100）

2（密碼技術(shù)與信息安全教育部重點(diǎn)實(shí)驗(yàn)室（山東大學(xué)）山東青島 266237）

3（青島市大數(shù)據(jù)中心 山東青島 266071）

4（東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽(yáng) 110819）

作為計(jì)算機(jī)科學(xué)中一種重要的數(shù)據(jù)結(jié)構(gòu)，圖可以表示現(xiàn)實(shí)世界中各種元素間復(fù)雜的關(guān)系，例如互聯(lián)網(wǎng)中的社交網(wǎng)絡(luò)、生物學(xué)中的蛋白質(zhì)網(wǎng)絡(luò)等.隨著大數(shù)據(jù)時(shí)代的到來(lái)，圖數(shù)據(jù)的規(guī)模呈爆炸式增長(zhǎng)，截至2021 年1 月，F(xiàn)acebook 的月活躍用戶已超過(guò)28 億[1]，而用戶之間復(fù)雜的社交關(guān)系導(dǎo)致邊的規(guī)模更為龐大，這需要分布式處理框架提供可擴(kuò)展的存儲(chǔ)和計(jì)算能力[2].然而，圖數(shù)據(jù)的各種應(yīng)用分析通常需要進(jìn)行高頻迭代以逐步逼近最優(yōu)解，而迭代過(guò)程中需要以消息的形式交換頂點(diǎn)之間的中間計(jì)算結(jié)果.由于頂點(diǎn)可能分布于不同的分布式任務(wù)，這會(huì)產(chǎn)生大量的通信開(kāi)銷(xiāo).

常見(jiàn)的圖應(yīng)用分析既包括網(wǎng)頁(yè)排名計(jì)算Page-Rank 和單源最短路徑（single-source shortest path,SSSP）等簡(jiǎn)單算法，又包括社團(tuán)分類(lèi)SC（semi-cluster）[2]和復(fù)雜的多源最短路徑計(jì)算（multi-source shortest path,MSSP）[3]等復(fù)雜算法.其一條消息的結(jié)構(gòu)均包括目的頂點(diǎn)標(biāo)識(shí)符以及消息值，但簡(jiǎn)單算法的消息值僅需一個(gè)基本數(shù)據(jù)類(lèi)型即可表達(dá)，即單維消息值，如以浮點(diǎn)型數(shù)據(jù)表示PageRank 的網(wǎng)頁(yè)排名分?jǐn)?shù)或SSSP 的最短距離值；復(fù)雜算法則需要若干基本數(shù)據(jù)類(lèi)型聯(lián)合表達(dá)，即多維消息值，如以浮點(diǎn)型數(shù)組來(lái)表示MSSP中若干源頂點(diǎn)的最短距離值，以整型數(shù)集合表示SC中一個(gè)聚類(lèi)內(nèi)包含的實(shí)體等.面對(duì)海量圖數(shù)據(jù)的迭代處理作業(yè)，多維算法顯然會(huì)急劇增加消息通信開(kāi)銷(xiāo)，嚴(yán)重制約分布式計(jì)算的性能收益.

為提高計(jì)算和存儲(chǔ)的可擴(kuò)展性，大量分布式圖計(jì)算平臺(tái)已經(jīng)被開(kāi)發(fā)出來(lái)并從通用性、易用性、健壯性和性能提升等各個(gè)方面進(jìn)行了優(yōu)化、完善.其中關(guān)于通信優(yōu)化的技術(shù)主要包括圖劃分[2,4-6]以及給定劃分后的消息合并[2]與頂點(diǎn)備份機(jī)制[7].圖劃分作為一個(gè)NP 完全問(wèn)題[8]，難以在降低通信開(kāi)銷(xiāo)的解耦合和環(huán)節(jié)水桶效應(yīng)的負(fù)載均衡方面實(shí)現(xiàn)綜合最優(yōu).因此，如何在給定劃分結(jié)果的前提下進(jìn)行通信優(yōu)化，顯得格外重要.

現(xiàn)有分布式圖計(jì)算系統(tǒng)中的消息管理框架主要分為早期Pregel[2]與GPS[7]等系統(tǒng)采用的主動(dòng)推送機(jī)制（push）和PowerGraph[9]以及HGraph[10]等系統(tǒng)采用的新型按需拉取機(jī)制（pull）.已有的消息合并和頂點(diǎn)備份以及融合改進(jìn)技術(shù)[11]均在push 框架下完成.然而由于消息的目的頂點(diǎn)分布的局部性差，push 框架從機(jī)制上無(wú)法保證應(yīng)合并消息被完全合并，嚴(yán)重制約實(shí)際性能收益；反之，pull 框架極大改善了局部性，能夠保證應(yīng)合并消息被完全合并，可最大化消息合并收益.本文分析發(fā)現(xiàn)，對(duì)于PageRank 類(lèi)算法，pull框架下的消息合并與頂點(diǎn)備份，在理論上可產(chǎn)生相同的性能收益.然而，對(duì)于多維消息算法，如MSSP，即使對(duì)某個(gè)源頂點(diǎn)相關(guān)的單維度消息進(jìn)行了完全合并，不同源頂點(diǎn)所構(gòu)成的多維消息值依然較大；而對(duì)于SC 等算法，受計(jì)算邏輯正確性約束，僅能合并消息的目的頂點(diǎn)標(biāo)識(shí)符而不可合并消息值.因此，需在pull 框架下實(shí)現(xiàn)頂點(diǎn)備份機(jī)制，在保留非備份頂點(diǎn)消息合并（或僅合并目的頂點(diǎn)標(biāo)識(shí)符）收益的前提下，通過(guò)頂點(diǎn)備份進(jìn)一步優(yōu)化通信性能.

然而，現(xiàn)有頂點(diǎn)備份方法均在push 框架下開(kāi)發(fā)完成，其備份頂點(diǎn)值的同步策略依然采用push 方式，如果直接遷移到pull 框架下，會(huì)導(dǎo)致同一個(gè)迭代步中同時(shí)存在push 與pull 這2 種消息管理體制，破壞原有pull 框架的系統(tǒng)完整性與優(yōu)化設(shè)計(jì)，比如高效的容錯(cuò)管理以及較低的內(nèi)存資源消耗等特性.此外，備份機(jī)制雖然可帶來(lái)通信收益，但會(huì)導(dǎo)致邊數(shù)據(jù)在不同分布式任務(wù)之間進(jìn)行遷移，影響原圖劃分結(jié)果的負(fù)載均衡，加重分布式環(huán)境下水桶效應(yīng)導(dǎo)致的延遲開(kāi)銷(xiāo).因此如何選擇一個(gè)較好的備份控制閾值，對(duì)于獲取最優(yōu)的綜合性能至關(guān)重要.此外，對(duì)于MSSP類(lèi)支持合并的算法，遷移邊會(huì)破壞消息合并所依賴的圖結(jié)構(gòu)，降低合并收益，如何在合并收益與備份收益之間進(jìn)行均衡，是另外一個(gè)巨大挑戰(zhàn).

圍繞多維消息算法的通信優(yōu)化問(wèn)題，本文針對(duì)平衡合并收益與備份收益的挑戰(zhàn)，在新型pull 框架[10]下設(shè)計(jì)了輕量級(jí)頂點(diǎn)備份機(jī)制，采用按需同步備份頂點(diǎn)值和優(yōu)先級(jí)拉取消息等策略，使頂點(diǎn)備份與pull 框架完美兼容；設(shè)計(jì)代價(jià)收益模型以均衡通信收益與偏斜延遲的影響，可根據(jù)數(shù)據(jù)集相關(guān)的線下先驗(yàn)知識(shí)和應(yīng)用算法相關(guān)的線上實(shí)時(shí)信息，自動(dòng)計(jì)算最優(yōu)備份閾值，強(qiáng)化備份機(jī)制的實(shí)際性能收益并避免繁瑣的手工閾值測(cè)試與選擇操作；針對(duì)MSSP 類(lèi)可合并多維算法，從合并收益與備份收益2 個(gè)角度分析多源點(diǎn)并發(fā)數(shù)目的取值，以確保備份機(jī)制的性能收益.大量真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，傳統(tǒng)push備份機(jī)制的內(nèi)存開(kāi)銷(xiāo)均大于較本文提出的輕量級(jí)備份框架，最高可達(dá)15 倍；對(duì)比現(xiàn)有非備份的pull 框架，本文框架可實(shí)現(xiàn)高達(dá)53%的性能收益；而代價(jià)分析模型則可有效選擇較優(yōu)的備份閾值，實(shí)現(xiàn)與手動(dòng)調(diào)整相近的性能收益.

1 相關(guān)工作

通信開(kāi)銷(xiāo)一直是制約分布式圖處理性能提升的關(guān)鍵因素.本節(jié)總結(jié)了當(dāng)前主要的相關(guān)工作并闡述本文技術(shù)與它們的區(qū)別.

1）圖劃分優(yōu)化.高質(zhì)量的圖劃分算法旨在解耦圖數(shù)據(jù)以減少子圖間的關(guān)聯(lián)關(guān)系，進(jìn)而減少通信開(kāi)銷(xiāo)，同時(shí)確保各任務(wù)的負(fù)載均衡以減少并行計(jì)算的水桶效應(yīng)[12].然而，圖劃分問(wèn)題屬于NP 完全問(wèn)題[8].簡(jiǎn)單的Hash[2]和Range[10]劃分可分別保證頂點(diǎn)和邊數(shù)據(jù)的均衡分配，雖然頂點(diǎn)或邊的切割會(huì)引起較高的通信開(kāi)銷(xiāo)，但由于劃分速度快，已成為當(dāng)前主流的劃分機(jī)制.此外，多級(jí)層次劃分算法如Metis[6]，PaToH[13]，KaHIP[14]等通過(guò)反復(fù)迭代調(diào)整數(shù)據(jù)分配位置，可顯著降低通信開(kāi)銷(xiāo)，但執(zhí)行效率過(guò)低.而流式劃分[5]嘗試均衡通信優(yōu)化質(zhì)量和劃分執(zhí)行效率.本文的通信優(yōu)化機(jī)制是針對(duì)給定劃分后的子圖進(jìn)行2 次優(yōu)化，因此兼容上述圖劃分技術(shù).

2）消息傳遞優(yōu)化.除圖劃分外，在迭代計(jì)算過(guò)程中也存在很多通信優(yōu)化技術(shù).谷歌的Pregel 系統(tǒng)[2]首先針對(duì)多對(duì)1 結(jié)構(gòu)提出消息合并策略.Pregel 的開(kāi)源實(shí)現(xiàn)GPS 系統(tǒng)[7]則提出LALP 策略，對(duì)高出度頂點(diǎn)進(jìn)行邊遷移并備份源頂點(diǎn)；而以此為基礎(chǔ)，進(jìn)一步的工作探討了如何在備份遷移過(guò)程中保證負(fù)載均衡[14-16].Pregel+[11]在消息合并基礎(chǔ)上融合LALP，并增加邊遷移（即源頂點(diǎn)備份）閾值的討論，以在合并與備份之間進(jìn)行均衡.然而，上述系統(tǒng)均采用push 機(jī)制，這是由于目的頂點(diǎn)分布的局部性差，消息合并收益較低.不 同于push 框 架，PowerGraph[9]，CGraph[17]，HDRF[18]等框架在數(shù)據(jù)加載過(guò)程采用頂點(diǎn)分割策略，并設(shè)計(jì)了對(duì)應(yīng)的GAS（gather-apply-scatter）迭代計(jì)算框架，可同時(shí)支持圖算法和機(jī)器學(xué)習(xí)算法，其中Gather 即pull機(jī)制的核心部件.然而，頂點(diǎn)切分引入大量?jī)?nèi)存開(kāi)銷(xiāo)[19]，且GAS 計(jì)算頻繁觸發(fā)頂點(diǎn)之間的同步操作，開(kāi)銷(xiāo)較大.為此，PowerLyra[20]，GrapH[21]，L-PowerGraph[22]，LightGraph[23]等分別從頂點(diǎn)切分策略與頂點(diǎn)間消息傳遞方面進(jìn)行優(yōu)化.最近提出的HGraph 系統(tǒng)[10]則給出了以塊為單位進(jìn)行消息拉取的新型pull 框架，顯著改善了消息目的頂點(diǎn)分布的局部性，可實(shí)現(xiàn)完全徹底的消息合并，在不進(jìn)行頂點(diǎn)切分的前提下，針對(duì)值合并類(lèi)算法，其性能顯著優(yōu)于傳統(tǒng)pull 框架且在內(nèi)存消耗與容錯(cuò)控制方面均有較大優(yōu)勢(shì).然而，多維算法由于其消息值本身的字節(jié)規(guī)模較大，使得HGraph 在徹底合并消息（值或目的頂點(diǎn)ID）后，通信代價(jià)仍然較高，亟需通過(guò)頂點(diǎn)備份進(jìn)一步降低相關(guān)開(kāi)銷(xiāo).

近年來(lái)，基于特定硬件架構(gòu)的圖計(jì)算優(yōu)化問(wèn)題已經(jīng)成為另一個(gè)研究熱點(diǎn)[19,24]，但本文關(guān)注通用架構(gòu)下的通信優(yōu)化，不對(duì)硬件條件進(jìn)行特定假設(shè).

2 問(wèn)題定義

本節(jié)首先闡述分布式圖迭代計(jì)算的一般處理方式；然后根據(jù)消息數(shù)據(jù)的維度以及合并屬性對(duì)圖迭代算法進(jìn)行分類(lèi)，并著重介紹近些年提出的具有重要實(shí)用價(jià)值的多維消息類(lèi)算法；最后基于推送（push）和拉?。╬ull）這2種主流分布式消息管理框架，分析合并與備份對(duì)不同類(lèi)型圖算法的優(yōu)化效果.

2.1 分布式圖迭代計(jì)算

給定輸入的有向圖G=〈V,E〉,其中V為|V|個(gè)頂點(diǎn)的集合而E為|E|條邊的集合.E中每條有向邊e=〈vi,vj〉連接源頂點(diǎn)vi和目的頂點(diǎn)vj，其中vi是vj的入度鄰居/頂點(diǎn)，而vj是vi的出度鄰居/頂點(diǎn).圖以鄰接表形式存儲(chǔ)，每條鄰接表包含頂點(diǎn)vi和所有以vi為源頂點(diǎn)的出邊的目的頂點(diǎn).

分布式圖迭代計(jì)算系統(tǒng)在啟動(dòng)迭代計(jì)算之前，首先將G從初始存儲(chǔ)位置（如分布式文件存儲(chǔ)系統(tǒng)HDFS）并行加載到P個(gè)不同的分布式計(jì)算任務(wù)Ti上，每個(gè)任務(wù)負(fù)責(zé)處理一部分?jǐn)?shù)據(jù)，即子圖Gi=〈Vi,Ei〉,該過(guò)程即圖劃分；隨后各任務(wù)Ti對(duì)本地子圖Gi中的圖數(shù)據(jù)進(jìn)行迭代計(jì)算，計(jì)算過(guò)程中消息的生成、發(fā)送和接收處理都是按照出邊進(jìn)行的，相應(yīng)頂點(diǎn)循環(huán)執(zhí)行更新操作，每次循環(huán)即一個(gè)迭代步，迭代步之間通過(guò)全局同步路障來(lái)協(xié)調(diào)各個(gè)任務(wù)的處理進(jìn)度.第k個(gè)迭代步的具體操作包括：根據(jù)第k-1 步接收的消息更新頂點(diǎn)值，將更新后的頂點(diǎn)值以消息的形式沿著出邊發(fā)送給目的頂點(diǎn)，以便在第k+1 步執(zhí)行更新操作.如果頂點(diǎn)vi參加第k步迭代的更新計(jì)算，則稱vi在該迭代步是激活的，編程人員可根據(jù)需要設(shè)置激活標(biāo)記，以避免非激活頂點(diǎn)的無(wú)效計(jì)算.當(dāng)所有頂點(diǎn)均處于非激活狀態(tài)且系統(tǒng)中沒(méi)有新的消息生成時(shí)，算法收斂，迭代計(jì)算結(jié)束.

2.2 多維消息類(lèi)圖迭代算法

依據(jù)分布式圖算法在迭代計(jì)算過(guò)程中傳遞消息的不同維度特征和合并屬性，可對(duì)分布式圖算法進(jìn)行分類(lèi).具體分類(lèi)標(biāo)準(zhǔn)包括：1）一條消息數(shù)據(jù)的消息值可以由單個(gè)基本數(shù)據(jù)類(lèi)型獨(dú)自表達(dá)或多個(gè)基本數(shù)據(jù)類(lèi)型聯(lián)合表達(dá)，即單維與多維；2）發(fā)往同一個(gè)目的頂點(diǎn)的不同消息值是否允許被合并為一個(gè)值，即值合并和連接.表1 展示了常見(jiàn)分布式圖算法的分類(lèi)結(jié)果.下面以SSSP、標(biāo)簽廣播算法（label propagation algorithm，LPA）、MSSP 和SC 為例，分別按照2 種分類(lèi)標(biāo)準(zhǔn)對(duì)不同類(lèi)型算法的特征進(jìn)行闡述.

Table 1 Graph Algorithm Classification表1 圖算法分類(lèi)

SSSP 算法的目標(biāo)是發(fā)現(xiàn)給定源頂點(diǎn)到圖中其他所有頂點(diǎn)之間的最短距離.迭代初始階段，源頂點(diǎn)將頂點(diǎn)值（即距離值）初始化為0 并根據(jù)出邊的距離權(quán)重生成消息值發(fā)送給出度頂點(diǎn)，而其余所有頂點(diǎn)均將頂點(diǎn)值設(shè)置為無(wú)窮大.隨后，每步迭代過(guò)程中，收到上一步消息的頂點(diǎn)被激活并從入度鄰居的消息值和自身頂點(diǎn)值中選擇最小的值進(jìn)行值更新，而如果頂點(diǎn)值發(fā)生了更新，則沿出邊生成新消息并發(fā)送給出度鄰居.每條消息msg=〈ID,msgValue〉，其結(jié)構(gòu)僅包括一個(gè)int 型的目的頂點(diǎn)ID和double 型距離值msgValue,屬單維消息.此外，算法邏輯僅關(guān)心最短距離值，所以如果沿2 條或多條目的頂點(diǎn)相同的出邊如e13=〈v1,v3〉和e23=〈v2,v3〉,分別生成具有不同消息值的消息如msg13=〈3,0.1〉和msg23=〈3,0.5〉,則可合并為一條消息msg=〈3,min{0.1,0.5}=0.1〉以節(jié)省通信開(kāi)銷(xiāo).

LPA 是一種快速社團(tuán)發(fā)現(xiàn)算法，其將每個(gè)頂點(diǎn)賦值一個(gè)社團(tuán)標(biāo)簽并初始化為頂點(diǎn)ID,隨后迭代更新標(biāo)簽值為其入度鄰居標(biāo)簽值中出現(xiàn)次數(shù)最多者.由于頂點(diǎn)更新依賴所有入度鄰居的標(biāo)簽值分布，所以每步迭代中每個(gè)頂點(diǎn)均參與更新且沿出邊向所有出度鄰居廣播自己的標(biāo)簽值，即全激活.與SSSP 相比，其消息結(jié)構(gòu)相同，即目的頂點(diǎn)ID和int 型的標(biāo)簽值，屬于單維消息；但不同之處是，由于需要根據(jù)標(biāo)簽頻數(shù)分布進(jìn)行更新，所有消息值不可合并，僅可連接，即如有msg13=〈3,2〉和msg23=〈3,2〉，僅可連接消息值為msg=〈3,[2,2]〉以合并（共享）目的頂點(diǎn)ID進(jìn)而節(jié)省通信開(kāi)銷(xiāo).

MSSP 是SSSP 的一種常見(jiàn)多源點(diǎn)擴(kuò)展.高級(jí)圖挖掘與分析算法通常需要衡量圖中所有頂點(diǎn)對(duì)之間的最短距離，而通過(guò)串行提交不同源頂點(diǎn)的SSSP 作業(yè)，會(huì)造成圖的反復(fù)遍歷，效率低下.一種高效的解決方案是根據(jù)集群的計(jì)算與存儲(chǔ)能力，在一個(gè)圖遍歷作業(yè)內(nèi)并發(fā)計(jì)算多個(gè)源頂點(diǎn)的最短距離分布，即MSSP.假設(shè)并發(fā)源頂點(diǎn)個(gè)數(shù)為m，則此時(shí)每個(gè)頂點(diǎn)值由一個(gè)double 型數(shù)據(jù)擴(kuò)展為長(zhǎng)度為m的double 數(shù)組；對(duì)應(yīng)地，消息值也擴(kuò)展為double 數(shù)組.例如，當(dāng)m=3時(shí)，可有msg13=〈3,[0.1,0.4,0.2]〉和msg23=〈3,[0.5,0.3,0.1]〉,此時(shí)雖然對(duì)應(yīng)源頂點(diǎn)的消息值可合并，但合并后的消息值仍是一個(gè)長(zhǎng)度為3 的數(shù)組，即msg=〈3,[0.1,0.3,0.1]〉,故屬于可合并、多維消息類(lèi)算法.其他單源點(diǎn)遍歷算法如PPR 和BFS 均有類(lèi)似的多源擴(kuò)展.

SC 是谷歌開(kāi)源圖處理系統(tǒng)Pregel 中內(nèi)置的一種半聚類(lèi)算法，即允許一個(gè)頂點(diǎn)記錄自己所屬的多個(gè)聚類(lèi)并打分排序.迭代初始，每個(gè)頂點(diǎn)將自身初始化為一個(gè)聚類(lèi)并發(fā)送給出度鄰居.在每個(gè)迭代步，所有頂點(diǎn)均激活，根據(jù)入度鄰居所屬的聚類(lèi)分布更新自己所屬聚類(lèi)，并繼續(xù)廣播.算法傳播的消息是描述頂點(diǎn)所在的聚類(lèi)（即頂點(diǎn)集合），需要多個(gè)基本數(shù)據(jù)類(lèi)型進(jìn)行聯(lián)合表達(dá)，屬于多維消息結(jié)構(gòu)；且由于需要聚類(lèi)分布信息，故消息值不可合并.延續(xù)上例，可有消息msg13=〈3,（1）|0.6,（2,5）|0.3〉和msg23=〈3,（2,5）|0.3〉,即頂點(diǎn)v1可歸屬于包含頂點(diǎn)v1的聚類(lèi)（1）和包含頂點(diǎn)v2與v5的聚類(lèi)（2,5）,分?jǐn)?shù)分別為0.6 和0.3,而v2則以0.3 的分?jǐn)?shù)歸屬于聚類(lèi)（2,5）.與LPA 類(lèi)似，2 條消息因?qū)?yīng)的目的頂點(diǎn)相同故可以合并發(fā)送，但消息值僅可連接，即以msg=〈3,[（1）|0.6,（2,5）|0.3,（2,5）|0.3]〉的形式進(jìn)行發(fā)送.

綜上，對(duì)于單維值可合并類(lèi)算法，如果可以保證應(yīng)合并的消息被全部合并，可極大緩解通信壓力；對(duì)單維值連接類(lèi)算法，由于消息值不可合并，每個(gè)迭代步中總的消息值規(guī)模最多可達(dá)到出邊的數(shù)量級(jí)，即|E|，但由于每個(gè)消息值的字節(jié)數(shù)較少，故通信壓力仍可以接受；反之，對(duì)于多維消息類(lèi)算法，其單條消息值的規(guī)模取決于聯(lián)合表達(dá)所用的基本數(shù)據(jù)類(lèi)型的數(shù)目，即維度，如MSSP 算法中的并發(fā)源頂點(diǎn)數(shù)目和SC 算法中描述聚類(lèi)特征的基本數(shù)據(jù)類(lèi)型集合規(guī)模.在相同的輸入圖規(guī)模下，多維算法顯然會(huì)產(chǎn)生較大的通信壓力.而當(dāng)消息值不可合并時(shí)，通信代價(jià)更會(huì)急劇增大.而根據(jù)已有測(cè)試結(jié)果，在分布式圖算法處理過(guò)程中，即使對(duì)于單維消息類(lèi)算法，任務(wù)間通信引入的時(shí)間開(kāi)銷(xiāo)約占總執(zhí)行時(shí)間的50%以上[3].因此亟需針對(duì)多維消息圖迭代算法設(shè)計(jì)通信優(yōu)化技術(shù)，以提升分布式計(jì)算效益.

2.3 消息合并與源頂點(diǎn)備份收益分析

分布式通信問(wèn)題可以通過(guò)提升圖劃分質(zhì)量加以改善，即在保證負(fù)載均衡的前提下盡量減少子圖之間的邊耦合依賴程度.然而，圖劃分是一個(gè)傳統(tǒng)的NP 完全問(wèn)題[8]，難以在合理時(shí)間內(nèi)獲得高質(zhì)量劃分結(jié)果.因此，對(duì)已有劃分后的子圖進(jìn)行后續(xù)通信優(yōu)化就顯得尤為重要.目前的優(yōu)化方法主要分為2 類(lèi)：消息合并和頂點(diǎn)備份.下面結(jié)合push 和pull 這2 種消息傳輸方式分析2 種優(yōu)化方法產(chǎn)生的效益，以突出本文研究的必要性.

2.3.1 push 與pull 消息傳輸方式對(duì)比

迭代過(guò)程中消息的生成與傳送方式可分為兩大類(lèi)設(shè)計(jì)，分別為push 和pull.在迭代步k，push 在頂點(diǎn)更新時(shí)直接遍歷所有出邊并主動(dòng)推送消息給所有目的頂點(diǎn)；而pull 僅完成頂點(diǎn)更新、不發(fā)送消息.在迭代步k+1，push 可確保目的頂點(diǎn)所需消息均已接收并儲(chǔ)備在本地，可直接使用；而pull 需要根據(jù)邊的依賴關(guān)系從對(duì)應(yīng)源頂點(diǎn)處按需拉取消息數(shù)據(jù).2 種消息管理框架各有優(yōu)缺點(diǎn)，push 在一個(gè)迭代步中，僅需遍歷一次頂點(diǎn)即可完成頂點(diǎn)值更新和新消息生成，但由于頂點(diǎn)之間邊關(guān)系的自由分布，一個(gè)頂點(diǎn)的出邊所指向的目的頂點(diǎn)的分布具有較差的局部性，即主動(dòng)推送的消息數(shù)據(jù)所指向的目的頂點(diǎn)的局部性差，且該部分消息直到下一個(gè)迭代步才被使用，因此需要在發(fā)送端和接收端設(shè)置大量消息管理緩存，需較多的內(nèi)存資源；pull 由于消息按需生成且消息均指向欲更新頂點(diǎn)值的目的頂點(diǎn)，故局部性良好，且接收的消息可直接被目的頂點(diǎn)處理，無(wú)需緩存，極大節(jié)省了內(nèi)存資源，但不同目的頂點(diǎn)的更新會(huì)導(dǎo)致其共享的源頂點(diǎn)被隨機(jī)掃描讀取多次.

2.3.2 消息合并

當(dāng)某個(gè)任務(wù)上的多個(gè)源頂點(diǎn)均需要向同一個(gè)目的頂點(diǎn)發(fā)送消息時(shí)（多對(duì)1 結(jié)構(gòu)），如果消息值可合并，顯然可以在消息發(fā)送之前進(jìn)行合并（如2.2 節(jié)的SSSP 算法），以減少通信開(kāi)銷(xiāo).然而，在push 方式下，考慮到消息的目的頂點(diǎn)分布的局部性較差而發(fā)送端緩存又是有限的，因此能夠在緩存中參與合并的消息比例較少，即無(wú)法保證徹底的消息合并，導(dǎo)致通信收益降低，甚至難以抵消合并所引入的管理開(kāi)銷(xiāo).如圖1（a）所示，假設(shè)發(fā)送端緩存容量為2 條消息，可保證頂點(diǎn)v1與v2發(fā)往目的頂點(diǎn)d1與d2的消息被合并；但當(dāng)v2繼續(xù)往d3發(fā)送消息時(shí)，由于緩存已滿，需將發(fā)往d1與d2的消息清空；最后v3往d2發(fā)送消息，但因緩存清空，該消息無(wú)法與v1與v2生成的消息合并，即應(yīng)合并消息無(wú)法保證被徹底、完全地合并.相反地，在pull 方式下[5]，如圖1（b）所示，目的頂點(diǎn)按照2 為單位進(jìn)行分塊，然后以塊為單位拉取所需消息.第1個(gè)塊中，消息均發(fā)往d1與d2，局部性優(yōu)異，在緩存為2 的前提下，可被完全合并；之后第2 個(gè)塊啟動(dòng)拉取操作.此外，這種按塊拉取的方式，可保證同一個(gè)塊內(nèi)的目的頂點(diǎn)僅掃描1 次對(duì)應(yīng)的源頂點(diǎn)，降低源頂點(diǎn)的隨機(jī)讀取次數(shù).需要注意的是：這里的消息合并是泛化概念，即對(duì)于2.2 節(jié)中值合并類(lèi)算法，可實(shí)現(xiàn)目的頂點(diǎn)ID與消息值合并；而對(duì)值連接類(lèi)算法，僅可實(shí)現(xiàn)目的頂點(diǎn)ID的合并，其通信收益仍在，但效果減弱.

Fig.1 Illustration of message combination and vertex replication圖1 消息合并與頂點(diǎn)備份圖示

2.3.3 頂點(diǎn)備份

當(dāng)某個(gè)頂點(diǎn)的出度較高以至于其在若干任務(wù)上均有大量的目的頂點(diǎn)（1 對(duì)多結(jié)構(gòu)），可以將出邊遷移至目的頂點(diǎn)所在任務(wù)并對(duì)源頂點(diǎn)進(jìn)行備份，從而將遷移邊所對(duì)應(yīng)的網(wǎng)絡(luò)消息轉(zhuǎn)換為目的頂點(diǎn)所在任務(wù)的本地消息，同時(shí)增加了同步備份頂點(diǎn)值的網(wǎng)絡(luò)開(kāi)銷(xiāo).如圖1（c）所示，源頂點(diǎn)備份主要在傳統(tǒng)的push 框架下實(shí)現(xiàn)，如GPS[7]和Pregel+[11].當(dāng)頂點(diǎn)更新后，同步備份頂點(diǎn)的值，而備份頂點(diǎn)收到同步值之后立即沿遷移邊生成本地消息.同步值與本地消息均采用push 方式管理.考慮到遷移邊的消息不再由源頂點(diǎn)所在任務(wù)生成，這會(huì)影響消息合并的機(jī)率.因此，對(duì)于消息合并類(lèi)算法，Pregel+[11]設(shè)計(jì)了合并優(yōu)先的備份機(jī)制，即只有當(dāng)目的頂點(diǎn)的入度為1 時(shí)，其對(duì)應(yīng)的源頂點(diǎn)才可能被備份（此時(shí)無(wú)其他源頂點(diǎn)指向該目的頂點(diǎn)，故不會(huì)損失合并收益），以兼顧合并與備份的收益.Pregel+[11]在非完全合并的push 框架下取得了較好的通信壓縮效果；但在新型pull 框架下，由于徹底合并已經(jīng)極大壓縮了通信規(guī)模，根據(jù)我們的實(shí)測(cè)結(jié)果，如表2 所示，雖然滿足備份約束的頂點(diǎn)比例較高，但備份僅帶來(lái)1%～7%的微弱壓縮效果，而實(shí)際性能收益可以忽略.表2 所示的4 個(gè)真實(shí)圖數(shù)據(jù)集，包括互聯(lián)網(wǎng)領(lǐng)域的Web 圖數(shù)據(jù)集Uk2014tpd（UK）、Wikipedia（Wiki）和Eu2015host（EU），以及社交網(wǎng)絡(luò)領(lǐng)域的常用圖數(shù)據(jù)集LiveJournal（LiveJ）.

Table 2 Replicate Effect of Pregel+Under Thorough Combination表2 Pregel+在徹底合并下的備份效果 %

2.3.4 分析

對(duì)比消息合并和頂點(diǎn)備份機(jī)制可發(fā)現(xiàn)，對(duì)于合并類(lèi)消息算法如SSSP,在以塊為中心的pull 框架下，其完全徹底合并消息的特點(diǎn)特別適合多對(duì)1 結(jié)構(gòu)，合并后僅需發(fā)送一條消息.本質(zhì)上，可以看作目的頂點(diǎn)在源頂點(diǎn)所在任務(wù)上的備份過(guò)程（如圖1（b）所示），最終的網(wǎng)絡(luò)通信代價(jià)取決于目的頂點(diǎn)的備份規(guī)模；另一方面，現(xiàn)有頂點(diǎn)備份適用于1 對(duì)多結(jié)構(gòu)，僅有備份頂點(diǎn)的同步會(huì)引入網(wǎng)絡(luò)開(kāi)銷(xiāo)，通信代價(jià)取決于源頂點(diǎn)備份規(guī)模（如圖1（c）所示）.因此，無(wú)論是對(duì)目的頂點(diǎn)還是對(duì)源頂點(diǎn)進(jìn)行備份，備份后的通信規(guī)模都是由備份頂點(diǎn)的數(shù)量決定的.注意到PowerGraph[9]提供了關(guān)于求解頂點(diǎn)v在P個(gè)任務(wù)上備份頂點(diǎn)數(shù)的期望公式：其中d為頂點(diǎn)v的出度或入度，V是頂點(diǎn)集，|V|是頂點(diǎn)集中頂點(diǎn)個(gè)數(shù)，|V|與冪律偏斜指數(shù) α和Zipf 分布的歸一化常數(shù)直接相關(guān).其中，消息合并關(guān)心的目的頂點(diǎn)備份規(guī)模依賴入度偏斜，而源頂點(diǎn)備份規(guī)模則依賴出度偏斜.圖2 分析了本文所用真實(shí)數(shù)據(jù)集的出入度偏斜指數(shù)，可以看出兩者近似相等.因此，不同于傳統(tǒng)push 框架下的非完全合并，對(duì)于值合并類(lèi)算法，pull 框架下的消息完全合可帶來(lái)與源頂點(diǎn)備份相近的通信收益；即使對(duì)于值連接類(lèi)算法，pull 框架的優(yōu)異合并效果依然可以在目的頂點(diǎn)合并方面帶來(lái)性能收益.

Fig.2 The skewness of the in/out degree distribution for different datasets圖2 各數(shù)據(jù)集的出/入度偏斜指數(shù)

特別地，對(duì)于MSSP 類(lèi)圖遍歷算法，頂點(diǎn)值是逐步收斂的.在第k步迭代中，同一目的頂點(diǎn)所對(duì)應(yīng)的多個(gè)源頂點(diǎn)中可能有頂點(diǎn)值已經(jīng)達(dá)到收斂而停止更新，該部分頂點(diǎn)自然不會(huì)生成新消息.這種算法邏輯層面的部分收斂現(xiàn)象顯然會(huì)減少參與合并的消息規(guī)模，削弱多對(duì)1 結(jié)構(gòu)產(chǎn)生的合并收益.相反地，頂點(diǎn)備份依賴1 對(duì)多結(jié)構(gòu).對(duì)于某個(gè)頂點(diǎn)而言，只要其尚未收斂，則需要繼續(xù)沿出邊廣播消息，頂點(diǎn)備份可繼續(xù)正常工作，不受頂點(diǎn)收斂的影響.這會(huì)在兩者之間產(chǎn)生通信收益差，且差值與消息值維度成正比，即MSSP類(lèi)算法并發(fā)源頂點(diǎn)個(gè)數(shù)越多，2 種機(jī)制的通信收益差距越大.基于上述分析以及 pull 方法極低的內(nèi)存消耗特別適合大規(guī)模圖數(shù)據(jù)處理，本文因此致力于在以塊為中心的pull 框架下，針對(duì)多維消息算法，通過(guò)源頂點(diǎn)備份機(jī)制進(jìn)一步優(yōu)化消息值的傳輸開(kāi)銷(xiāo).

考慮到源頂點(diǎn)備份會(huì)破壞原有圖劃分的均衡負(fù)載分布，且現(xiàn)有源頂點(diǎn)備份機(jī)制均在push 框架下設(shè)計(jì)，難以兼容新型pull 框架，因此需要重新設(shè)計(jì)備份機(jī)制并仔細(xì)分析備份閾值，以實(shí)現(xiàn)功能性和性能優(yōu)化方面的統(tǒng)一.

3 輕量級(jí)頂點(diǎn)備份框架

由于大部分算法的基本工作流程是頂點(diǎn)更新與邊消息傳遞，而圖中邊的規(guī)模遠(yuǎn)大于頂點(diǎn)規(guī)模，故工作負(fù)載與邊密切相關(guān).因此，本文假設(shè)采用簡(jiǎn)單快速的Range 劃分以保證劃分后各任務(wù)間的出邊數(shù)目均衡，然后通過(guò)對(duì)消息傳遞模型的改進(jìn)降低網(wǎng)絡(luò)通信量，以實(shí)現(xiàn)圖處理性能的整體提升.然而，已有消息傳遞模型的改進(jìn)主要是基于非完全合并的push 環(huán)境下進(jìn)行的.為實(shí)現(xiàn)通信開(kāi)銷(xiāo)的進(jìn)一步壓縮，本文在完全合并的pull 環(huán)境下，即HGraph[10]系統(tǒng)上設(shè)計(jì)新的輕量級(jí)頂點(diǎn)備份機(jī)制，以改善多維消息算法的消息值傳輸效率.

輕量級(jí)頂點(diǎn)備份的核心是，在pull 系統(tǒng)下，備份點(diǎn)的相關(guān)操作也采用pull 方式實(shí)現(xiàn)；通過(guò)只使用一種pull 管理方式，避免了傳統(tǒng)push 頂點(diǎn)備份機(jī)制在pull方式下內(nèi)存開(kāi)銷(xiāo)大與容錯(cuò)負(fù)載重的問(wèn)題，程序設(shè)計(jì)簡(jiǎn)潔、易維護(hù).本節(jié)首先總結(jié)push 備份在pull 框架下的缺點(diǎn)，然后介紹輕量級(jí)備份的按需同步和優(yōu)先級(jí)消息拉取技術(shù)，最后對(duì)比本文備份框架與PowerLyra的混合備份技術(shù)，突出本文備份的輕量級(jí)特點(diǎn).

3.1 push 頂點(diǎn)備份與pull 消息管理框架的兼容性

根據(jù)2.3 節(jié)中對(duì)消息合并與頂點(diǎn)備份的收益分析可知，在完全合并的pull 框架下，兩者對(duì)值合并類(lèi)算法的通信壓縮效果相近.但針對(duì)多維算法，在保證完全合并（目的頂點(diǎn)ID合并、消息值合并）的前提下，可針對(duì)部分高出度頂點(diǎn)進(jìn)行邊遷移與源頂點(diǎn)備份，以進(jìn)一步優(yōu)化通信開(kāi)銷(xiāo).然而，目前源頂點(diǎn)備份對(duì)通信的改進(jìn)都是在push 框架下實(shí)現(xiàn)的，備份頂點(diǎn)的同步以及遷移邊的消息生成方式，均采用push 主動(dòng)推送方式，如果直接在pull 框架下實(shí)現(xiàn)，會(huì)導(dǎo)致每個(gè)迭代步內(nèi)同時(shí)存在非備份頂點(diǎn)的pull 操作以及備份頂點(diǎn)的push 操作，帶來(lái)2 個(gè)缺點(diǎn)：

1）容錯(cuò)管理復(fù)雜且效率低.容錯(cuò)控制對(duì)圖迭代計(jì)算至關(guān)重要，可在部分任務(wù)發(fā)生故障時(shí)避免其他任務(wù)回滾、重新計(jì)算.目前的容錯(cuò)機(jī)制主要采用檢查點(diǎn)回滾的方式進(jìn)行故障恢復(fù).為避免非故障任務(wù)的重新計(jì)算，需要不斷記錄每個(gè)任務(wù)的消息輸出，以便故障任務(wù)在重新計(jì)算時(shí)使用.大量的消息記錄，尤其是多維算法的大消息值特性，會(huì)嚴(yán)重影響正常迭代的計(jì)算效率.在push 方式下，由于消息是主動(dòng)生成并發(fā)送出去，無(wú)法對(duì)此進(jìn)行優(yōu)化；而pull 方式允許消息按需生成，故可按需生成故障任務(wù)恢復(fù)過(guò)程中所需的消息，不必主動(dòng)記錄.當(dāng)故障節(jié)點(diǎn)需要入度鄰居的消息來(lái)更新頂點(diǎn)值時(shí)，僅需沿入邊向入度鄰居發(fā)送拉取請(qǐng)求，而非故障任務(wù)上的頂點(diǎn)只需記錄對(duì)應(yīng)迭代步的頂點(diǎn)值以響應(yīng)消息請(qǐng)求即可.由于頂點(diǎn)的規(guī)模遠(yuǎn)低于消息規(guī)模，記錄頂點(diǎn)值對(duì)正常迭代計(jì)算的影響很小.然而，一旦pull 與push 混合執(zhí)行，則仍需要對(duì)push 方式下的頂點(diǎn)同步值以及根據(jù)遷移邊生成的消息進(jìn)行記錄，既增加了容錯(cuò)管理的復(fù)雜性，也增大了容錯(cuò)開(kāi)銷(xiāo).

2）多緩存高內(nèi)存消耗.使用push 方式進(jìn)行消息發(fā)送時(shí)，需要在發(fā)送端針對(duì)每一個(gè)分布式任務(wù)設(shè)置一個(gè)雙緩存結(jié)構(gòu)，以便其中一個(gè)緩存溢出、進(jìn)行消息發(fā)送時(shí)，另一個(gè)緩存可繼續(xù)接收消息、不阻塞頂點(diǎn)的計(jì)算更新；在接收端，由于消息對(duì)應(yīng)的目的頂點(diǎn)的局部性差且無(wú)法預(yù)知其到達(dá)時(shí)間，需要根據(jù)目的頂點(diǎn)的分塊信息、消息源頂點(diǎn)所在的任務(wù)等設(shè)置多個(gè)緩存區(qū)，以避免針對(duì)同一個(gè)目的頂點(diǎn)的消息進(jìn)行整理時(shí)導(dǎo)致頻繁的加鎖開(kāi)銷(xiāo).在多維消息類(lèi)算法中，由于頂點(diǎn)值以及據(jù)此生成的消息值的規(guī)模巨大，發(fā)送端與接收端的多緩存設(shè)置給內(nèi)存造成巨大壓力.而在pull 系統(tǒng)中，消息按需生成且生成之后被立即消耗，因此根據(jù)需要更新的目的頂點(diǎn)的規(guī)模預(yù)估消息規(guī)模設(shè)置緩存即可，避免了繁雜的多緩存結(jié)構(gòu)，節(jié)省了內(nèi)存開(kāi)銷(xiāo).同理，當(dāng)pull 與push 混合時(shí)，為正確、高效運(yùn)行push 機(jī)制，需要配備多個(gè)緩存結(jié)構(gòu)，增大了內(nèi)存開(kāi)銷(xiāo).因此，需要設(shè)計(jì)與pull 機(jī)制相兼容的頂點(diǎn)備份框架，在實(shí)現(xiàn)輕量級(jí)程序框架設(shè)計(jì)的同時(shí)，可以實(shí)現(xiàn)容錯(cuò)和內(nèi)存管理的簡(jiǎn)潔與高效.

3.2 基于按需同步的備份更新策略

鑒于push 備份與pull 框架的沖突點(diǎn)是由備份點(diǎn)的同步方式以及遷移邊的消息生成方式所導(dǎo)致的，因此需要將這2 種方式改為pull 方式，以實(shí)現(xiàn)系統(tǒng)兼容.本節(jié)重點(diǎn)介紹基于按需同步的拉取式頂點(diǎn)備份機(jī)制.

3.2.1 按需同步框架設(shè)計(jì)

執(zhí)行頂點(diǎn)備份后，每個(gè)迭代步中頂點(diǎn)值計(jì)算更新所需的消息來(lái)源于2 個(gè)部分：1）所有任務(wù)上非備份頂點(diǎn)發(fā)送的非備份消息值；2）備份到本地的頂點(diǎn)根據(jù)遷移出邊發(fā)送的本地備份消息值.當(dāng)目的頂點(diǎn)塊欲執(zhí)行更新操作時(shí)，針對(duì)非備份消息值，直接以塊為單位向所有任務(wù)發(fā)送拉取請(qǐng)求，而各任務(wù)接收請(qǐng)求后，直接掃描本任務(wù)內(nèi)指向該請(qǐng)求塊內(nèi)所有目的頂點(diǎn)的出邊，生成所需消息并在發(fā)送端執(zhí)行徹底合并后發(fā)送給請(qǐng)求端（即目的頂點(diǎn)塊所在的任務(wù)），該過(guò)程可由現(xiàn)有pull 機(jī)制直接完成；而針對(duì)本地備份消息值，在按需同步策略下，某個(gè)頂點(diǎn)值被更新后，不會(huì)主動(dòng)推送消息以同步其備份頂點(diǎn)值，因此應(yīng)先同步其備份值，然后生成本地備份消息.具體地，在同步備份頂點(diǎn)值時(shí)，仍然以目的頂點(diǎn)塊為單位向所有任務(wù)廣播同步請(qǐng)求，而各任務(wù)收到請(qǐng)求后，檢索本地頂點(diǎn)是否有指向該請(qǐng)求塊內(nèi)目的頂點(diǎn)的遷移出邊（即是否有備份），如是，則響應(yīng)同步請(qǐng)求，將頂點(diǎn)值發(fā)送到請(qǐng)求端，然后根據(jù)同步后的備份頂點(diǎn)值生成本地備份消息.進(jìn)一步地，為實(shí)現(xiàn)按需生成本地備份消息的目標(biāo)，需將備份的源頂點(diǎn)和遷移的出邊以鄰接表的形式分塊存儲(chǔ)，即每個(gè)遷移過(guò)來(lái)的鄰接表按照目的頂點(diǎn)所在的塊對(duì)遷移邊進(jìn)行分割存儲(chǔ).如是，當(dāng)目的頂點(diǎn)所在的塊欲執(zhí)行更新操作而拉取消息時(shí)，僅需讀取每個(gè)遷移鄰接表中對(duì)應(yīng)該塊的部分出邊即可生成所需消息，從而避免push 方式下的多種緩存設(shè)置，降低內(nèi)存消耗.

3.2.2 2 階段同步響應(yīng)優(yōu)化

在同步響應(yīng)過(guò)程中，各任務(wù)的檢索操作需要遍歷所有出邊，時(shí)間復(fù)雜度較高.此外，某個(gè)源頂點(diǎn)的出邊可能指向任務(wù)Ti上不同塊內(nèi)的目的頂點(diǎn).當(dāng)任務(wù)Ti上不同塊內(nèi)的目的頂點(diǎn)發(fā)送同步請(qǐng)求時(shí)，該源頂點(diǎn)所在的任務(wù)需進(jìn)行多次檢索以及響應(yīng)操作，造成備份頂點(diǎn)值的冗余同步，浪費(fèi)計(jì)算和網(wǎng)絡(luò)資源.為提高同步效率，本文設(shè)計(jì)了基于字典的2 階段同步響應(yīng)機(jī)制.具體地，每個(gè)任務(wù)在內(nèi)存中維護(hù)同步響應(yīng)字典，即如果某個(gè)頂點(diǎn)在某個(gè)任務(wù)上存在備份，則在字典中添加該條記錄，且標(biāo)記該備份值在當(dāng)前迭代步是否已經(jīng)被同步.根據(jù)2 階段同步響應(yīng)機(jī)制，當(dāng)某個(gè)目的頂點(diǎn)塊欲向任務(wù)Ti發(fā)送同步請(qǐng)求時(shí)，其首先查驗(yàn)本地是否存在來(lái)自于Ti的遷移邊，如果沒(méi)有，顯然無(wú)備份頂點(diǎn)，無(wú)需發(fā)送請(qǐng)求；如存在，則正常發(fā)送請(qǐng)求.任務(wù)Ti收到請(qǐng)求后，首先查驗(yàn)響應(yīng)字典，如果指向請(qǐng)求端所在任務(wù)存在備份點(diǎn)且所有備份點(diǎn)均已被同步，則不再響應(yīng)，返回值為空；否則，根據(jù)字典中尚未標(biāo)記同步的頂點(diǎn)查找頂點(diǎn)值以響應(yīng)同步備份頂點(diǎn)值并更新字典內(nèi)容.2 階段同步機(jī)制顯然可以根據(jù)字典信息避免冗余同步，提高響應(yīng)效率.

3.2.3 實(shí)例演示

圖3 展示了按需同步策略下數(shù)據(jù)存儲(chǔ)和管理方式的一個(gè)實(shí)例.該實(shí)例包含20 個(gè)頂點(diǎn)（圖3 中頂點(diǎn)編號(hào)直接以數(shù)字形式呈現(xiàn)），分布于2 個(gè)分布式任務(wù)T1與T2.以T1為例，本地圖數(shù)據(jù)包含頂點(diǎn)v1至v10及其鄰接表，具體分為2 個(gè)塊，分別包含頂點(diǎn)v1至v6和v7至v10.對(duì)應(yīng)地，出邊按照目的頂點(diǎn)的分塊信息按列分割存儲(chǔ).如v1的出邊指向4 個(gè)目的頂點(diǎn)，其中目的頂點(diǎn)v2和v3屬于同一個(gè)頂點(diǎn)塊，故對(duì)應(yīng)出邊被存儲(chǔ)到同一列中；同理，v7和v18分別屬于不同頂點(diǎn)塊，故對(duì)應(yīng)出邊被存儲(chǔ)在另外2 列中.特別地，v6，v7，v10分別有邊遷移到任務(wù)T2,即在T2上存在備份.以為v6例，其出邊〈v6,v13〉和〈v6,v15〉被遷移到T2并按照目的頂點(diǎn)的分塊信息進(jìn)行按列分割存儲(chǔ)，而遷移之后，T1的響應(yīng)字典中應(yīng)添加1 條v6指向T2的記錄.在第k步迭代中，假設(shè)T2上的頂點(diǎn)塊v11至v15欲更新頂點(diǎn)值，則分2 步拉取所需消息：1）本地備份消息，即首先檢查本地是否有來(lái)自T1的遷移邊，如有，則向T2發(fā)送同步請(qǐng)求，而T1收到請(qǐng)求后，首先檢查字典中T1對(duì)應(yīng)的列是否均為1，否則，如有且字典中對(duì)應(yīng)值為0（如此處的v6與v7），則應(yīng)封裝對(duì)應(yīng)頂點(diǎn)值進(jìn)行響應(yīng)并將字典中的值更新為1（此處即v6與v7在T2列的值），而T2收到同步值之后根據(jù)遷移邊按需生成本地備份消息；2）非備份消息，可按照原有pull 框架設(shè)計(jì)，發(fā)送消息拉取請(qǐng)求并通過(guò)掃描對(duì)應(yīng)列的出邊信息生成消息并返回給T2.當(dāng)頂點(diǎn)塊v16至v20被調(diào)度更新時(shí)，可重復(fù)此過(guò)程，但需要注意的是，v16的更新依賴于v7的消息，但v7的頂點(diǎn)值已經(jīng)被同步（即T1中字典的對(duì)應(yīng)值為1），故該值不會(huì)被再次返回，以避免冗余同步，減少網(wǎng)絡(luò)通信開(kāi)銷(xiāo).

Fig.3 The data storage and management methods of on-demand synchronization update strategy圖3 按需同步更新策略的數(shù)據(jù)存儲(chǔ)和管理方式

3.3 基于優(yōu)先級(jí)拉取的并發(fā)消息生成

在按需同步備份更新策略下，頂點(diǎn)更新所依賴的消息包括備份消息和非備份消息.為獲取這2 類(lèi)消息，直觀的解決方案是并發(fā)發(fā)送備份值同步請(qǐng)求和非備份消息請(qǐng)求（詳見(jiàn)圖3 示例）.然而，這種方案的弊端是頂點(diǎn)同步值和非備份消息值的同時(shí)傳輸會(huì)增大瞬時(shí)通信負(fù)載，造成網(wǎng)絡(luò)擁堵；而在目的任務(wù)接收到響應(yīng)的備份頂點(diǎn)同步值和非備份消息值后，迭代計(jì)算的負(fù)載重心轉(zhuǎn)為備份消息的本地生成以及目的頂點(diǎn)更新，均不涉及網(wǎng)絡(luò)通信，導(dǎo)致網(wǎng)絡(luò)資源空閑.本節(jié)介紹基于優(yōu)先級(jí)拉取的并發(fā)消息生成策略，通過(guò)備份頂點(diǎn)值和非備份消息值的錯(cuò)峰拉取，提高網(wǎng)絡(luò)資源使用效率.

3.3.1 優(yōu)先級(jí)錯(cuò)峰拉取

基于優(yōu)先級(jí)錯(cuò)峰拉取和并發(fā)拉取的區(qū)別在于，前者優(yōu)先拉取備份頂點(diǎn)的同步值，然后拉取非備份消息且同時(shí)啟動(dòng)本地備份消息的生成與合并處理工作，最后待所有需要的消息準(zhǔn)備完畢后，進(jìn)行目的頂點(diǎn)的計(jì)算更新.該方案的優(yōu)點(diǎn)是不同優(yōu)先級(jí)的拉取請(qǐng)求錯(cuò)峰響應(yīng)，消息在網(wǎng)絡(luò)中的傳輸壓力減小，且減少了空閑等待狀態(tài)，充分利用網(wǎng)絡(luò)通信帶寬.

3.3.2 優(yōu)先級(jí)動(dòng)態(tài)調(diào)整

給定一個(gè)目的頂點(diǎn)塊，由于響應(yīng)字典的存在以及算法本身消息規(guī)模的動(dòng)態(tài)變化，會(huì)導(dǎo)致需要拉取的備份頂點(diǎn)同步值以及非備份消息值的規(guī)模動(dòng)態(tài)變化.直觀地，當(dāng)兩者的規(guī)模較低時(shí)，優(yōu)先級(jí)錯(cuò)峰拉取可能導(dǎo)致兩者各自均無(wú)法充分利用通信帶寬，降低網(wǎng)絡(luò)資源使用效率.式（2）和式（3）分別描述了并發(fā)拉取和優(yōu)先級(jí)拉取的性能度量方法.

無(wú)論采用何種拉取策略，具體工作負(fù)載均包括拉取非備份消息值的開(kāi)銷(xiāo) φmsg和拉取本地備份消息的開(kāi)銷(xiāo)，而后者可細(xì)分為同步備份頂點(diǎn)值開(kāi)銷(xiāo) φsyn和本地備份消息生成開(kāi)銷(xiāo) φpro.對(duì)于并發(fā)拉取，由于2 種拉取請(qǐng)求同時(shí)發(fā)送、同時(shí)響應(yīng)，故其性能指標(biāo) φcon取決于 φmsg與 φsyn+φpro中的較大值，而考慮到同時(shí)請(qǐng)求產(chǎn)生的網(wǎng)絡(luò)擁堵，應(yīng)添加懲罰因子 λ(λ ≥1);對(duì)于優(yōu)先級(jí)拉取，同步請(qǐng)求被優(yōu)先發(fā)送，而后并行執(zhí)行備份消息的拉取以及本地備份消息的生成，故其性 φpri能應(yīng)在 φsyn的 基礎(chǔ)上累加后兩者的最大值，即當(dāng) λ較低，比如 λ=1時(shí)，顯然有 φcon＜φpri,即并發(fā)拉取優(yōu)于優(yōu)先級(jí)拉?。环粗?，當(dāng) λ較高，即備份頂點(diǎn)值和非備份消息值規(guī)模較大而導(dǎo)致網(wǎng)絡(luò)擁塞程度加劇時(shí)，優(yōu)先級(jí)拉取優(yōu)于并發(fā)拉取.在實(shí)際運(yùn)行圖迭代計(jì)算時(shí)，可根據(jù)算法的執(zhí)行進(jìn)度和網(wǎng)絡(luò)瞬時(shí)狀態(tài)，實(shí)時(shí)計(jì)算 φcon與 φpri的 對(duì)比結(jié)果進(jìn)而選擇 決定是否將同步請(qǐng)求的優(yōu)先級(jí)升高.具體地，對(duì)于需要同步的備份頂點(diǎn)值的規(guī)模，可在請(qǐng)求發(fā)起端（如圖3 中的任務(wù)T2）記錄當(dāng)前迭代步已經(jīng)完成同步的備份頂點(diǎn)，當(dāng)啟動(dòng)一個(gè)新的目的頂點(diǎn)塊的更新時(shí)，可先分析本地遷移邊以確定需要同步的備份頂點(diǎn)數(shù)目，然后對(duì)比已經(jīng)完成同步的備份頂點(diǎn)，以估算同步開(kāi)銷(xiāo)；同理，可根據(jù)本地遷移邊規(guī)模估算本地備份消息的生成開(kāi)銷(xiāo)；對(duì)于非備份消息的規(guī)模，因該類(lèi)消息由其他所有任務(wù)生成，相關(guān)統(tǒng)計(jì)信息無(wú)法在本地獲取，故可在迭代計(jì)算過(guò)程中，通過(guò)記錄上一個(gè)迭代步中獲取的消息規(guī)模來(lái)估算本步的消息規(guī)模[28]；而對(duì)于 λ,可通過(guò)測(cè)試給定集群在不同擁塞程度下的通信延遲并記錄整理為先驗(yàn)知識(shí)，直接帶入公式進(jìn)行對(duì)比分析.

3.4 頂點(diǎn)備份方式討論

圖劃分是分布式圖計(jì)算的基礎(chǔ)，而劃分技術(shù)可分為邊割與點(diǎn)割兩大類(lèi).邊割的核心是以頂點(diǎn)為中心進(jìn)行圖劃分，即將頂點(diǎn)分配到各計(jì)算任務(wù)；如果一條邊的2 個(gè)頂點(diǎn)位于不同任務(wù)，則該邊成為切割邊，在迭代計(jì)算過(guò)程中會(huì)引入通信開(kāi)銷(xiāo)；因此在頂點(diǎn)分配時(shí)應(yīng)考慮切割邊的規(guī)模以優(yōu)化通信開(kāi)銷(xiāo)，Pregel 等系統(tǒng)均以邊割方式運(yùn)行圖算法[11].點(diǎn)割的核心是以邊為中心完成圖劃分，即將邊分配到各計(jì)算任務(wù)；如果同一個(gè)頂點(diǎn)關(guān)聯(lián)的2 條邊位于不同任務(wù)，則該頂點(diǎn)被切分，且多個(gè)切分點(diǎn)中會(huì)隨機(jī)選擇一個(gè)作為主控頂點(diǎn)master 而其余作為切分后的從節(jié)點(diǎn)mirror 存在，在迭代計(jì)算過(guò)程中的通信僅發(fā)生在master 與mirror之間.顯然，邊分配的過(guò)程應(yīng)盡量減少頂點(diǎn)被切分的概率.PowerGraph 等系統(tǒng)以點(diǎn)割方式運(yùn)行圖計(jì)算[9].

本文的頂點(diǎn)備份是在邊割基礎(chǔ)上進(jìn)行的通信優(yōu)化.給定邊割的圖劃分結(jié)果，也即頂點(diǎn)在任務(wù)間的分布已經(jīng)確定，備份機(jī)制將對(duì)每個(gè)頂點(diǎn)v（master）的出邊進(jìn)行解析，通過(guò)分析其目的頂點(diǎn)在任務(wù)間的分布來(lái)評(píng)估后續(xù)計(jì)算過(guò)程中的通信開(kāi)銷(xiāo)；如果v與任務(wù)Ti間的通信過(guò)高（即指向Ti中頂點(diǎn)的出邊數(shù)目超過(guò)閾值θ），則將v中對(duì)應(yīng)的邊定向遷移到Ti中并在Ti進(jìn)行v的備份（mirror）.

基于以上描述，本文備份框架與點(diǎn)割方案中，雖然頂點(diǎn)均存在master 與mirror 的功能角色之分，但在備份的主動(dòng)性和方向性方面存在區(qū)別.

1）備份的主動(dòng)性.在基于邊割的頂點(diǎn)備份優(yōu)化框架中，由于頂點(diǎn)（master）分布已經(jīng)確定，可精確分析“頂點(diǎn)—任務(wù)”之間的通信開(kāi)銷(xiāo)并主動(dòng)決定是否進(jìn)行出邊遷移與頂點(diǎn)備份；而點(diǎn)割方案中，采用啟發(fā)式規(guī)則來(lái)指導(dǎo)邊的分配并在分配過(guò)程中直接（被動(dòng)）完成頂點(diǎn)切分（以及master 和mirror 的界定），由于邊分配是動(dòng)態(tài)完成的，系統(tǒng)無(wú)法主動(dòng)分析通信收益以決定是否進(jìn)行頂點(diǎn)切分.

2）備份的方向性.在基于邊割的頂點(diǎn)備份框架中，由于頂點(diǎn)備份是因遷移出邊而引起的，故備份的頂點(diǎn)均作為邊的起始點(diǎn)而存在，也即僅將高出度頂點(diǎn)v（master）切分為若干備份頂點(diǎn)（mirror），當(dāng)v（master）向其出度鄰居廣播消息時(shí)，可先通過(guò)網(wǎng)絡(luò)將v（master）的值同步到備份頂點(diǎn)（mirror）再由備份頂點(diǎn)進(jìn)行局部廣播，即將消息傳遞給目的頂點(diǎn)，從而優(yōu)化通信開(kāi)銷(xiāo)；而在點(diǎn)割方案中，為保證同一個(gè)任務(wù)上的子圖完整性，備份頂點(diǎn)（mirror）既可能作為邊的起始點(diǎn)存在，也可能作為邊的終止點(diǎn)存在，邊的起始點(diǎn)可將發(fā)往頂點(diǎn)v的消息首先在其各任務(wù)的mirror 上進(jìn)行局部計(jì)算以減輕v（master）的處理壓力（如PageRank 算法中，可基于mirror 進(jìn)行消息的局部累加和操作），邊的終止點(diǎn)可減少v（master）向其出度鄰居廣播消息時(shí)的通信開(kāi)銷(xiāo).

下面分析本文舍棄點(diǎn)割，轉(zhuǎn)而基于邊割機(jī)制設(shè)計(jì)頂點(diǎn)備份優(yōu)化機(jī)制的原因.

1）從備份的方向性角度.針對(duì)本文關(guān)注的多維消息類(lèi)算法，消息值通常不滿足累加特性，即無(wú)法將多個(gè)消息值通過(guò)計(jì)算合并為一個(gè)消息值（如PageRank中的累加求和，以及最短路徑計(jì)算中的最小值計(jì)算），而只能將消息值進(jìn)行簡(jiǎn)單串聯(lián)連接（即本文表1 中的值連接類(lèi)算法），此時(shí)點(diǎn)割機(jī)制中，作為起始點(diǎn)存在的mirror 不但失去“先局部計(jì)算以減輕v（master）處理壓力”的意義，反而引入了mirror 的存儲(chǔ)開(kāi)銷(xiāo)與維護(hù)開(kāi)銷(xiāo).另一方面，本文相關(guān)技術(shù)基于以塊為中心的pull 框架實(shí)現(xiàn)，其基礎(chǔ)框架可保證各頂點(diǎn)發(fā)送的消息在發(fā)送端實(shí)現(xiàn)“能合并盡合并”[10]，故即使針對(duì)單維值可合并的多維算法（如MSSP），可以Combine 合并的方式在發(fā)送端實(shí)現(xiàn)消息的局部合并，且僅在運(yùn)行時(shí)使用，無(wú)需始終維護(hù)mirror.

2）從備份的主動(dòng)性角度.基于邊割的頂點(diǎn)備份可保證被備份的頂點(diǎn)均可帶來(lái)通信收益，而點(diǎn)割機(jī)制由于邊分配的動(dòng)態(tài)性，無(wú)法保證備份的通信收益.此處，注意到PowerLyra[20]基于PowerGraph 的點(diǎn)割進(jìn)行了混合備份優(yōu)化（hybrid-cut），即通過(guò)閾值設(shè)定，僅針對(duì)高度頂點(diǎn)進(jìn)行點(diǎn)割而對(duì)于低度頂點(diǎn)保持邊割.這與本文對(duì)高度頂點(diǎn)進(jìn)行切分，以最大化減少網(wǎng)絡(luò)通信開(kāi)銷(xiāo)的目的是一致的.然而，本文是在邊割基礎(chǔ)上完成頂點(diǎn)備份，而PowerLyra 是在點(diǎn)割基礎(chǔ)上進(jìn)行優(yōu)化.顯然，兩者在備份方向性的2 個(gè)角度存在區(qū)別.具體地，從頂層設(shè)計(jì)層面，本文和PowerLyra 均針對(duì)高度頂點(diǎn)進(jìn)行切分，這必然涉及到“高度”的衡量標(biāo)準(zhǔn)，即備份閾值θ.從實(shí)現(xiàn)層面，本文的 θ作用于頂點(diǎn)v指向任務(wù)Ti上目的頂點(diǎn)的出邊規(guī)模，而非PowerLyra 中作用于v的全部出邊（即出度）.由于出邊規(guī)模超過(guò)閾值即會(huì)產(chǎn)生備份，考慮到高出度頂點(diǎn)指向某個(gè)具體任務(wù)的出邊也可能較少，顯然本文的作用域更為精確，可確保通信收益.其次，PowerLyra 并未給出閾值θ的推薦方式，僅以多次重復(fù)實(shí)驗(yàn)的手工方式選擇較優(yōu)閾值；而本文在第4 節(jié)分析了遷移導(dǎo)致的負(fù)載偏斜代價(jià)與通信收益，可基于統(tǒng)計(jì)信息給出推薦的最優(yōu)閾值并在5.4 節(jié)通過(guò)大量實(shí)驗(yàn)驗(yàn)證了相關(guān)方案的可行性.

下面通過(guò)實(shí)例分析，展現(xiàn)本文備份機(jī)制的輕量級(jí)特點(diǎn).假設(shè)分布式任務(wù)的數(shù)目為3，圖4 給出了一個(gè)包含6 個(gè)頂點(diǎn)、9 條邊的示例圖在PowerLyra 和本文輕量級(jí)備份框架下的備份情況分析.設(shè)定備份閾值θ=3，PowerLyra 以邊表的方式并行加載輸入圖并根據(jù)邊的源頂點(diǎn)的Hash 值，即Ti=hash（exy.x-1）%3，決定該邊的分配位置.然后統(tǒng)計(jì)各頂點(diǎn)的出度，如果出度值大于等于3，則認(rèn)定為高度頂點(diǎn)，則按照該頂點(diǎn)關(guān)聯(lián)出邊的目的頂點(diǎn)重新分配出邊，即Ti=hash（exy.y-1）%3.這里頂點(diǎn)v1被判定為高度頂點(diǎn)，其出邊e12與e15被遷移到任務(wù)T2，而e13被遷移到任務(wù)T3.最后按照備份方向性的討論，完成頂點(diǎn)備份，即T1中 的v3，T2中 的v1以 及T3中 的v1與v2.然 而，T2中的v1顯然無(wú)法進(jìn)行通信優(yōu)化，因?yàn)関1在該任務(wù)上僅有一個(gè)目的頂點(diǎn)，備份與否并不能優(yōu)化通信規(guī)模.這是由于點(diǎn)割方案無(wú)法主動(dòng)控制頂點(diǎn)切分而導(dǎo)致的現(xiàn)象.相反地，本文輕量級(jí)備份以鄰接表作為輸入，并利用Range 劃分按照字節(jié)規(guī)模均衡分割、并行加載.而對(duì)于高度頂點(diǎn)的界定，采用“頂點(diǎn)—任務(wù)”模式進(jìn)行主動(dòng)界定.此處，只有頂點(diǎn)v1向任務(wù)T2進(jìn)行邊e12，e13，e14的遷移并備份v1，因?yàn)関1指向T2的出邊數(shù)目大于等于閾值θ，從而保證通信收益.注意到在本文備份機(jī)制下，出邊被遷移后，任務(wù)T2的負(fù)載加重，而其中的偏斜程度與閾值的設(shè)定相關(guān).第4 節(jié)將詳細(xì)討論閾值的設(shè)定問(wèn)題.

綜上，基于本文關(guān)注的多維消息算法的巨大內(nèi)存開(kāi)銷(xiāo)，以及以塊為中心的、最新的pull 系統(tǒng)框架，考慮到點(diǎn)割的維護(hù)開(kāi)銷(xiāo)和通信收益的不確定性，本文基于邊割的圖劃分技術(shù)，通過(guò)頂點(diǎn)備份進(jìn)行通信再優(yōu)化.故本文備份機(jī)制的輕量級(jí)特點(diǎn)，可總結(jié)為4 點(diǎn)：1）優(yōu)化的pull 同步方式可顯著減少備份頂點(diǎn)同步過(guò)程中的內(nèi)存開(kāi)銷(xiāo)并與普通消息的pull 方式統(tǒng)一，便于系統(tǒng)級(jí)優(yōu)化（如容錯(cuò)控制）；2）僅按照出邊方向進(jìn)行頂點(diǎn)備份，減少備份開(kāi)銷(xiāo)；3）通過(guò)精確控制備份閾值的作用范圍，避免無(wú)效的冗余備份，保證通信收益；4）提供備份閾值的自動(dòng)優(yōu)化計(jì)算模型，避免頻繁手動(dòng)測(cè)試的閾值選擇方式.

4 自適應(yīng)性能優(yōu)化模型

本文基于Range 劃分完成邊割，而Range 方法將輸入圖（由頂點(diǎn)和出邊組成）的數(shù)據(jù)規(guī)模進(jìn)行均等切分，可保證各計(jì)算節(jié)點(diǎn)負(fù)載（即頂點(diǎn)和出邊的數(shù)量之和）的均衡性.在此基礎(chǔ)上，頂點(diǎn)備份框架在圖劃分階段額外引入各任務(wù)間頂點(diǎn)的備份和出邊的遷入遷出等操作.考慮到真實(shí)圖的度分布通常有冪律偏斜特點(diǎn)，備份頂點(diǎn)在各任務(wù)間的分布也具有偏斜，且每個(gè)任務(wù)遷移邊的規(guī)模不盡相同，這顯然破壞了原Range劃分的負(fù)載均衡.故本文設(shè)計(jì)的框架對(duì)負(fù)載均衡方面沒(méi)有改善，大部分情況下甚至?xí)又刎?fù)載偏斜.

Fig.4 Comparison of hybrid-cut and lightweight vertex replication圖4 混合切分與輕量級(jí)頂點(diǎn)備份的對(duì)比

在頂點(diǎn)備份機(jī)制中，位于任務(wù)Ti上的頂點(diǎn)v是否需要在任務(wù)Tj上進(jìn)行備份，取決于其出邊是否被遷移.直觀地，如果v的鄰接表中存在大量指向Tj上目的頂點(diǎn)的出邊，則邊遷移可顯著降低通信代價(jià)，但同時(shí)也會(huì)引起Ti與Tj的負(fù)載變化進(jìn)而影響性能.因此，需要根據(jù)通信收益和負(fù)載影響綜合考慮，設(shè)定出邊遷移閾值θ,當(dāng)指向Tj的出邊數(shù)目超過(guò) θ時(shí)，證明通信收益可抵消負(fù)載變化影響，允許遷移，否則禁止遷移.顯然 θ的設(shè)定對(duì)備份機(jī)制的實(shí)際性能收益至關(guān)重要.在實(shí)際應(yīng)用場(chǎng)景，可通過(guò)多次運(yùn)行迭代算法手動(dòng)尋找最優(yōu)閾值，但這會(huì)浪費(fèi)大量計(jì)算資源，可操作性較差.一種理想的方式是給出 θ相關(guān)的性能函數(shù)，然后自動(dòng)分析最優(yōu)閾值以指導(dǎo)實(shí)際算法的運(yùn)行.本節(jié)重點(diǎn)介紹一種基于線下先驗(yàn)知識(shí)與線上實(shí)時(shí)信息相結(jié)合的閾值計(jì)算模型，其中4.1 節(jié)介紹預(yù)測(cè)函數(shù)，而4.2節(jié)介紹重要參數(shù)的線下與線上獲取方式.

4.1 出邊遷移閾值優(yōu)化預(yù)測(cè)函數(shù)

輕量級(jí)頂點(diǎn)備份框架的性能預(yù)測(cè)指標(biāo)要綜合考慮頂點(diǎn)備份后的通信凈收益和備份前后各任務(wù)負(fù)載均衡程度變化導(dǎo)致的水桶效應(yīng)影響.給定遷移閾值θ,式（4）給出了性能預(yù)測(cè)函數(shù)的邏輯結(jié)構(gòu)，其中 φcom表示頂點(diǎn)備份后的通信凈收益，而φl(shuí)oad代表備份前后各任務(wù)的負(fù)載均衡變化引起的水桶效應(yīng)影響.

對(duì)于通信凈收益 φcom,由第3 節(jié)可知，頂點(diǎn)備份在產(chǎn)生消息通信收益的同時(shí)，會(huì)引入備份頂點(diǎn)值的同步開(kāi)銷(xiāo).其中，消息通信收益取決于頂點(diǎn)備份所產(chǎn)生遷移的出邊數(shù)量（E上面的橫杠表示備份）以及沿出邊發(fā)送的消息字節(jié)大小 ηmsg，而同步開(kāi)銷(xiāo)則取決于備份頂點(diǎn)的數(shù)量和被同步的頂點(diǎn)值字節(jié)大小從字節(jié)規(guī)模角度給出了通信的凈收益.需要注意的是，分布式網(wǎng)絡(luò)通信的基本流程是首先在發(fā)送端進(jìn)行數(shù)據(jù)序列化，然后將序列化后的數(shù)據(jù)通過(guò)網(wǎng)絡(luò)傳輸?shù)浇邮斩耍邮斩诉M(jìn)行反序列化操作之后即可得到可用數(shù)據(jù).因此，在得到消息總規(guī)模和同步數(shù)據(jù)總規(guī)模后，可根據(jù)網(wǎng)絡(luò)傳輸速率Snet和接收端、發(fā)送端的序列化、反序列化速率Sio來(lái)計(jì)算凈性能收益 φcom：

其中，P代表共同參與計(jì)算的分布式任務(wù)數(shù)目，式（5）等號(hào)右邊第1 項(xiàng)為分布式環(huán)境下的凈性能收益；序列化和反序列化需要在發(fā)送端和接收端分別執(zhí)行，因此需要將字節(jié)規(guī)模乘以系數(shù)2.

對(duì)于負(fù)載均衡變化導(dǎo)致的水桶效應(yīng)影響 φl(shuí)oad,考慮到某個(gè)任務(wù)Ti在向其他任務(wù)遷移出邊的同時(shí)，也在接收其他任務(wù)遷入的邊數(shù)據(jù).這種遷入遷出會(huì)打破既有圖劃分結(jié)果的均衡性，進(jìn)而影響負(fù)載偏斜程度，導(dǎo)致水桶效應(yīng)延遲發(fā)生變化.分布式環(huán)境下，系統(tǒng)處理性能取決于負(fù)載最重的任務(wù)，因此可用備份前后最重負(fù)載的差值作為衡量指標(biāo).若備份后的負(fù)載均衡狀況優(yōu)于備份前，則負(fù)載指標(biāo)的計(jì)算結(jié)果為正，對(duì)處理性能起正向加速作用；反之，則會(huì)降低系統(tǒng)處理速度.φl(shuí)oad的計(jì)算方式為

其中 1 ≤i≤P，1 ≤j≤P，|Vi|和 |Ei|分別表示計(jì)算任務(wù)Ti上分配的子圖Gi的頂點(diǎn)數(shù)和邊數(shù)，而分別表示備份到任務(wù)Tj上的頂點(diǎn)數(shù)和由頂點(diǎn)備份導(dǎo)致的出邊遷入遷出變化數(shù).此外，無(wú)論是本地頂點(diǎn)還是備份頂點(diǎn)，在計(jì)算更新或同步更新時(shí)，會(huì)產(chǎn)生計(jì)算負(fù)載，因此分別加入調(diào)節(jié)因子 α 和 β以調(diào)節(jié)其相對(duì)于邊操作的負(fù)載.其中，α的值取決于頂點(diǎn)的計(jì)算更新以及遍歷參與計(jì)算更新的接收消息的復(fù)雜度；β的值取決于備份頂點(diǎn)的同步更新.顯然，α 和 β的值由算法和數(shù)據(jù)集共同確定.最后，Stpt為系統(tǒng)吞吐效率，可在給定集群上通過(guò)運(yùn)行標(biāo)準(zhǔn)測(cè)試程序獲得.

4.2 關(guān)鍵預(yù)測(cè)參數(shù)的獲取

根據(jù)式（4）～（6）,當(dāng) φ為正值時(shí)可提高計(jì)算效率，而 φ的預(yù)測(cè)值主要取決于4 類(lèi)參數(shù)：1）遷移與備份相關(guān)類(lèi)參數(shù)，具體包括備份頂點(diǎn)數(shù),遷移邊數(shù),和圖劃分結(jié)束后各任務(wù)的子圖分布 |Vi|與 |Ei|,其中 |Vi|與 |Ei|的取值依賴具體的圖數(shù)據(jù)集拓?fù)浣Y(jié)構(gòu)以及分布式任務(wù)數(shù)目P,而備份與遷移參數(shù)還與備份閾值 θ密切相關(guān)；2）應(yīng)用算法類(lèi)相關(guān)參數(shù)，主要包括 ηval，ηmsg,其取值由應(yīng)用層面的圖迭代算法決定；3）硬件配置類(lèi)參數(shù)，即Snet,Sio，Stpt,可通過(guò)在給定集群上運(yùn)行標(biāo)準(zhǔn)測(cè)試程序獲得；4）權(quán)重調(diào)節(jié)因子 α 和 β,可通過(guò)分析應(yīng)用算法復(fù)雜度與圖數(shù)據(jù)集的平均出入度計(jì)算得到.在上述4 類(lèi)參數(shù)中，第3 類(lèi)屬于固定常量，只要集群的硬件配置不變，無(wú)需反復(fù)測(cè)試，較易獲取和維護(hù)；第2 類(lèi)和第4 類(lèi)與具體的應(yīng)用算法和數(shù)據(jù)集相關(guān)，需要根據(jù)用戶提交的作業(yè)程序?qū)崟r(shí)分析，屬于較易獲取的線上實(shí)時(shí)參數(shù)；第1 類(lèi)因涉及圖拓?fù)浣Y(jié)構(gòu)以及關(guān)鍵變量θ,難以通過(guò)直觀的理論分析進(jìn)行準(zhǔn)確估計(jì)，因此本節(jié)對(duì)第1 類(lèi)參數(shù)的獲取進(jìn)行詳細(xì)討論.

雖然第1 類(lèi)參數(shù)難以理論評(píng)估，但注意到其只與數(shù)據(jù)集和集群任務(wù)配置相關(guān)，而與具體的應(yīng)用算法無(wú)關(guān).考慮到具體領(lǐng)域的圖應(yīng)用通常是根據(jù)指定的數(shù)據(jù)集進(jìn)行多方位的挖掘分析，如社交網(wǎng)絡(luò)公司對(duì)其運(yùn)營(yíng)的社交網(wǎng)絡(luò)圖進(jìn)行社團(tuán)聚類(lèi)、廣告推薦以及成員影響力評(píng)估等多種業(yè)務(wù)分析，論文檢索系統(tǒng)對(duì)學(xué)術(shù)研究網(wǎng)絡(luò)進(jìn)行合作研究團(tuán)隊(duì)識(shí)別、新研究領(lǐng)域發(fā)現(xiàn)以及學(xué)界泰斗與新星挖掘等業(yè)務(wù)分析.這表明，針對(duì)一個(gè)數(shù)據(jù)集，通常會(huì)從不同角度進(jìn)行不同類(lèi)別的應(yīng)用分析，即多次在同一個(gè)數(shù)據(jù)集上運(yùn)行不同算法.因此，可對(duì)給定的數(shù)據(jù)集和任務(wù)數(shù)目配置，通過(guò)線下變換 θ值統(tǒng)計(jì)不同任務(wù)上的第1 類(lèi)參數(shù)值并保存為先驗(yàn)知識(shí).當(dāng)需要在指定數(shù)據(jù)集上運(yùn)行某種算法時(shí)，可依據(jù)先驗(yàn)知識(shí)和算法相關(guān)的實(shí)時(shí)信息，立即計(jì)算出較優(yōu)的備份閾值，指導(dǎo)輕量級(jí)備份框架的運(yùn)行.

在參數(shù)提取階段，僅需統(tǒng)計(jì)各任務(wù)的備份頂點(diǎn)數(shù)目以及遷移邊交換情況，而無(wú)需進(jìn)行具體的迭代計(jì)算.因此可直接利用分布式圖處理系統(tǒng)的數(shù)據(jù)加載流程進(jìn)行邏輯數(shù)據(jù)統(tǒng)計(jì)，而不必進(jìn)行實(shí)際的物理遷移與頂點(diǎn)備份操作，以節(jié)省參數(shù)提取開(kāi)銷(xiāo).邏輯統(tǒng)計(jì)的另一個(gè)優(yōu)勢(shì)是，可同時(shí)分析多個(gè) θ取值下的參數(shù)數(shù)值，避免針對(duì)每個(gè)閾值取值進(jìn)行一次參數(shù)提取，進(jìn)一步壓低提取開(kāi)銷(xiāo).下面通過(guò)算法1 介紹第1 類(lèi)參數(shù)的具體提取過(guò)程.

算法1.備份頂點(diǎn)和遷移邊數(shù)目統(tǒng)計(jì).

算法1 展示了P個(gè)分布式任務(wù)中某個(gè)任務(wù)Ti的運(yùn)行流程.該任務(wù)對(duì)給定的劃分子圖Gi,分析各種備份閾值 Θ={θ1,θ2,…}下的頂點(diǎn)備份與遷移邊數(shù)目等統(tǒng)計(jì)信息.具體地，通過(guò)遍歷Gi中的每條鄰接表記錄，統(tǒng)計(jì)其出邊所指向的目的頂點(diǎn)在P個(gè)任務(wù)之間的分布頻數(shù)并記錄在數(shù)組dstTid中（行⑥～⑨）；之后分析不同閾值設(shè)定下如 θj,是否向?qū)?yīng)的任務(wù)如Tk進(jìn)行出邊遷移以及頂點(diǎn)備份，如是，將該統(tǒng)計(jì)信息記錄在各閾值下備份頂點(diǎn)數(shù)以及遷出出邊數(shù)的分布矩陣Mi與Ni的第（j,k）位置（行⑩～?）.需要注意的是，此處僅統(tǒng)計(jì)分布信息，而無(wú)需對(duì)邊進(jìn)行實(shí)際物理遷移（行?），因此算法1 的運(yùn)行效率較高.

5 實(shí)驗(yàn)結(jié)果與分析

5.1 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

本文在支持完全合并的HGraph 系統(tǒng)上實(shí)現(xiàn)了輕量級(jí)頂點(diǎn)備份框架，可同時(shí)支持消息完全合并以及源頂點(diǎn)備份，在繼承HGraph 系統(tǒng)優(yōu)勢(shì)的前提下，實(shí)現(xiàn)備份機(jī)制的內(nèi)存優(yōu)化和通信性能提升.為便于區(qū)分，實(shí)現(xiàn)輕量級(jí)按需備份的系統(tǒng)被稱之為L(zhǎng)Graph（light-weight graph）.實(shí)驗(yàn)設(shè)計(jì)方面，首先在不同數(shù)據(jù)集上對(duì)比輕量級(jí)頂點(diǎn)備份與傳統(tǒng)push 備份的內(nèi)存使用占比（5.2 節(jié)），然后給出輕量級(jí)頂點(diǎn)備份與HGraph原系統(tǒng)的性能對(duì)比與分析（5.3 節(jié)），最后驗(yàn)證自適應(yīng)性能優(yōu)化模型的預(yù)測(cè)分析結(jié)果以及備份過(guò)程對(duì)性能的影響（5.4 節(jié)）.應(yīng)用算 法選取 表1 中多維算法MSSP,SC,SA，分別作為合并類(lèi)和連接類(lèi)的代表.其中MSSP 與SC 的算法邏輯已在2.2 節(jié)中介紹.而SA算法是基于LPA 設(shè)計(jì)完成的廣告?zhèn)鞑ツM算法，即每個(gè)頂點(diǎn)維護(hù)自己感興趣的廣告標(biāo)簽列表，迭代開(kāi)始后，各頂點(diǎn)根據(jù)入度鄰居的廣告喜好分布對(duì)自己的廣告列表進(jìn)行更新并廣播給出度鄰居，其消息值不可合并且消息值需要使用多個(gè)int 數(shù)據(jù)來(lái)表征廣告標(biāo)簽.當(dāng)涉及運(yùn)行時(shí)間分析時(shí)，由于SC 與SA 算法在每步迭代中所有頂點(diǎn)均激活并向所有出度鄰居廣播消息，各步的負(fù)載相同，故除非特殊聲明，否則僅匯報(bào)一個(gè)迭代步的運(yùn)行時(shí)間；而對(duì)于MSSP，各步激活頂點(diǎn)規(guī)模動(dòng)態(tài)變化，導(dǎo)致負(fù)載也不盡相同，因此匯報(bào)整個(gè)算法收斂的總迭代計(jì)算時(shí)間.

實(shí)驗(yàn)集群由5 臺(tái)小型服務(wù)器組成，包括4 個(gè)計(jì)算節(jié)點(diǎn)和1 個(gè)主控節(jié)點(diǎn)，節(jié)點(diǎn)配備千兆網(wǎng)卡并使用千兆交換機(jī)互聯(lián)，實(shí)測(cè)網(wǎng)絡(luò)傳輸性能為89 MBps①網(wǎng)絡(luò)性能測(cè)試使用iperf-2.0.5 工具.主控節(jié)點(diǎn)配置Intel i9-10900K，3.7 GHz 的10 核CPU,1 TB固態(tài)硬盤(pán)，64 GB 內(nèi)存；每個(gè)計(jì)算節(jié)點(diǎn)配置Intel 至強(qiáng)E3-2224，3.5 GHz 的4 核CPU,1 TB 機(jī)械硬盤(pán)，32 GB內(nèi)存.實(shí)驗(yàn)使用4 個(gè)真實(shí)圖數(shù)據(jù)集，各數(shù)據(jù)集的具體信息描述如表3 所示.

Table 3 Description of Real Datasets表3 真實(shí)數(shù)據(jù)集描述

實(shí)驗(yàn)參數(shù)設(shè)定方面主要涉及閾值優(yōu)化模型，其中網(wǎng)絡(luò)通信與序列化/反序列化速率為Snet=89 MBps,Sio=507 MBps,平均負(fù) 載吞吐率為Stpt=42 MBps；另一方面，負(fù)載權(quán)重調(diào)節(jié)因子 α=(μin·ηmsg)/Supd,β=(μout·ηval)/Supd，其中 μin與 μout分別為對(duì)應(yīng)數(shù)據(jù)集的平均入度與平均出度，Supd為頂點(diǎn)更新/同步的CPU 處理速度，實(shí)測(cè)值為1533MBps.最后，對(duì)于MSSP 類(lèi)算法的并發(fā)源頂點(diǎn)數(shù)目設(shè)置，考慮到其合并與備份的通信收益之差與并發(fā)粒度成正比，同時(shí)在真實(shí)應(yīng)用環(huán)境下通常在硬件允許的前提下采用較大的并發(fā)粒度以提高圖遍歷共享收益，故在UK 和LiveJ 數(shù)據(jù)集上將并發(fā)粒度直接設(shè)置為平均出入度值；而對(duì)較為稠密的高出入度圖Wiki 和EU，將并發(fā)源頂點(diǎn)數(shù)目設(shè)置為平均出入度的2 倍，以強(qiáng)化通信收益.

5.2 備份頂點(diǎn)同步模式對(duì)比

本節(jié)在4 個(gè)真實(shí)數(shù)據(jù)集上對(duì)比了傳統(tǒng)push 同步頂點(diǎn)備份方式與按需同步頂點(diǎn)備份方式的內(nèi)存使用占比情況（即push 同步的內(nèi)存消耗/按需同步的內(nèi)存消耗）和同步性能，以證明按需同步頂點(diǎn)備份方式在減少內(nèi)存資源消耗方面的同時(shí)還可以保證相近的同步性能.表4 和 表5 分別展 示了連 接（SC）和合并（MSSP）類(lèi)多維消息算法的對(duì)比結(jié)果.由于按塊拉取框架的消息按需生成，因此不同的頂點(diǎn)分塊數(shù)目決定了按需生成消息的規(guī)模.故測(cè)試過(guò)程中，通過(guò)將每個(gè)任務(wù)上的頂點(diǎn)分塊數(shù)目由2 增加到64，觀察2 種同步方式的內(nèi)存消耗變化.

Table 4 Memory Usage of Concatenation Algorithms表4 值連接類(lèi)算法內(nèi)存使用情況

Table 5 Memory Usage of Combination Algorithms表5 值合并類(lèi)算法內(nèi)存使用情況

在2 類(lèi)算法中，按需同步的備份方式均表現(xiàn)出更低的內(nèi)存使用情況（對(duì)比值均大于1）.這是因?yàn)榘葱柰絺浞莘绞焦?jié)省了發(fā)送端和接收端的多緩存以及本地消息接收緩存設(shè)置.隨著每個(gè)任務(wù)上的頂點(diǎn)分塊數(shù)的增加，每塊內(nèi)部的頂點(diǎn)規(guī)模下降，其接收的消息規(guī)模也隨之成比例下降，導(dǎo)致按需生成的消息規(guī)模降低，內(nèi)存消耗減少；與此同時(shí)，push 同步方式的發(fā)送與接收端緩存，只受任務(wù)數(shù)目的影響，不隨頂點(diǎn)分塊的變化而改變.因此，隨著塊規(guī)模的增大，在不同數(shù)據(jù)集和算法的所有組合測(cè)試案例中，兩者的內(nèi)存消耗對(duì)比值均呈現(xiàn)增加趨勢(shì).此外，對(duì)于MSSP，因不同數(shù)據(jù)集下其并發(fā)源頂點(diǎn)數(shù)量的不同，每條消息的大小也會(huì)發(fā)生變化，導(dǎo)致不同數(shù)據(jù)集下內(nèi)存收益表現(xiàn)出較大的差異性.特別地，EU 數(shù)據(jù)集上的MSSP算法并發(fā)源頂點(diǎn)數(shù)量最多，需要消耗大量?jī)?nèi)存，故在頂點(diǎn)分塊為64 時(shí)2 種方案的內(nèi)存消耗對(duì)比最為明顯，此時(shí)push 同步的內(nèi)存消耗規(guī)模約是本文方法的15 倍.因此，對(duì)于消息規(guī)模巨大的多維消息類(lèi)算法，采用本文的按需同步方式可有效降低消息傳遞的規(guī)模，從而減少系統(tǒng)的內(nèi)存資源消耗.

在同步性能分析方面，由于備份頂點(diǎn)的同步操作與正常消息值的交換操作緊密耦合，難以剝離出同步操作的精確時(shí)間開(kāi)銷(xiāo).考慮到同步方式的不同，僅影響同步性能而不會(huì)影響正常消息的操作效率以及頂點(diǎn)更新效率，此處采用控制變量法，即設(shè)定其他參數(shù)均一致而僅變化備份頂點(diǎn)的同步方式，然后通過(guò)匯報(bào)迭代計(jì)算過(guò)程的運(yùn)行時(shí)間來(lái)反映不同同步方式的性能影響.如表6 所示，通過(guò)手動(dòng)測(cè)試不同備份閾值下LGraph 的運(yùn)行時(shí)間來(lái)確定最優(yōu)閾值，然后以最優(yōu)閾值作為輸入，測(cè)試不同同步方式下的運(yùn)行時(shí)間.這里，npull 是未采用3.3 節(jié)中優(yōu)先級(jí)技術(shù)的拉取操作方案而pull 是集成優(yōu)先級(jí)技術(shù)的方案.雖然pull方式涉及同步請(qǐng)求發(fā)送環(huán)節(jié)，但受益于同步字典的冗余消除剪枝作用以及優(yōu)先級(jí)調(diào)度，其同步效率與push 方式幾近相同（延遲率 ＜2%）.綜合表4～6 可知，本文的pull 同步方式在不影響同步效率的前提下可顯著優(yōu)化內(nèi)存使用開(kāi)銷(xiāo)，從而提升系統(tǒng)在數(shù)據(jù)處理容量方面的擴(kuò)展性.

5.3 備份性能分析

本節(jié)分別在4 個(gè)真實(shí)數(shù)據(jù)集上運(yùn)行3 種多維消息類(lèi)算法，通過(guò)手動(dòng)測(cè)試不同備份閾值下LGraph 的運(yùn)行時(shí)間并選擇與最優(yōu)閾值下的性能與無(wú)備份機(jī)制的HGraph 進(jìn)行對(duì)比，以展現(xiàn)輕量級(jí)備份框架的最佳性能收益.由于算法和數(shù)據(jù)集本身存在的復(fù)雜性和冪律偏斜特性，每組實(shí)驗(yàn)的實(shí)際收益各不相同，圖5～7 分別展示了對(duì)比效果.

Table 6 Comparison of Synchronizing Running Time for Replicated Vertices with pull and push表6 pull 與push 方式下備份頂點(diǎn)的同步運(yùn)行時(shí)間對(duì)比 s

Fig.5 Running time of SC algorithm on different data sets圖5 SC 算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間

Fig.6 Running time of SA algorithm on different data sets圖6 SA 算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間

Fig.7 Running time of MSSP algorithm on different data sets圖7 MSSP 算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間

在算法和數(shù)據(jù)集的各種組合中，LGraph 的計(jì)算時(shí)間始終低于HGraph.特別地，對(duì)于連接類(lèi)算法SC和SA，由于其只能合并目的頂點(diǎn)ID，消息合并收益對(duì)整體性能提升并不敏感.換言之，通信性能的優(yōu)化主要依靠頂點(diǎn)備份.此時(shí)通過(guò)選擇較好的備份閾值，可以顯著提升整體性能，如SA 算法在Wiki 數(shù)據(jù)集上可以達(dá)到53%的性能提升.對(duì)于可合并類(lèi)算法MSSP，在UK 和LiveJ 數(shù)據(jù)集上，可實(shí)現(xiàn)24%和21%的性能提升；而對(duì)數(shù)據(jù)集Wiki 和EU，由于并發(fā)源頂點(diǎn)數(shù)目增大，此時(shí)性能收益可分別達(dá)到31%和33%.

針對(duì)各數(shù)據(jù)集上的不同算法，圖8 和圖9 分別匯報(bào)了最優(yōu)備份閾值對(duì)負(fù)載和通信的影響，即4.1 節(jié)中分析的因負(fù)載偏斜導(dǎo)致的水桶效應(yīng) φl(shuí)oad以及因備份帶來(lái)的通信收益 φcom.需要注意的是，實(shí)際運(yùn)行圖計(jì)算作業(yè)時(shí)，水桶效應(yīng)和通信收益同時(shí)發(fā)生，兩者對(duì)運(yùn)行時(shí)間的影響緊密耦合，無(wú)法精確測(cè)量各自的實(shí)際影響.故此處匯報(bào)的 φl(shuí)oad與 φcom均為量化后的理論估算的運(yùn)行時(shí)間（單位為s），以展示備份后的負(fù)載偏斜代價(jià)和通信收益，進(jìn)而理解本文技術(shù)可加速圖計(jì)算過(guò)程的原理.

圖8 中，頂點(diǎn)備份對(duì)負(fù)載變化的影響是指計(jì)算過(guò)程中水桶效應(yīng)拖慢的系統(tǒng)運(yùn)行時(shí)間.LGraph 備份后的負(fù)載指標(biāo)計(jì)算結(jié)果均為負(fù)，即備份后的負(fù)載均衡情況劣于備份前，對(duì)加速圖計(jì)算過(guò)程起反向作用.根據(jù)式（6），負(fù)載變化與拓?fù)浣Y(jié)構(gòu)和消息維度規(guī)模密切相關(guān).從拓?fù)浣Y(jié)構(gòu)角度來(lái)看，Wiki 數(shù)據(jù)集由于出/入度偏斜指數(shù)相差較大，頂點(diǎn)的備份和邊的遷入遷出對(duì)其負(fù)載影響較大；而EU 數(shù)據(jù)集的高出/入度頂點(diǎn)較多且在各任務(wù)間的分布較為均衡，故備份對(duì)負(fù)載變化的影響較小.從消息維度角度來(lái)看，MSSP 由于并發(fā)源頂點(diǎn)數(shù)目多，導(dǎo)致消息和頂點(diǎn)值的字節(jié)數(shù)均大于其余2 個(gè)算法，因此其負(fù)載變化幅度通常是最大的.特別地，在LiveJ 數(shù)據(jù)集上，MSSP 算法的負(fù)載變化遠(yuǎn)小于SA 算法.這是由于算法特性導(dǎo)致兩者的備份閾值不同.根據(jù)表7，MSSP 的備份閾值遠(yuǎn)高于SA，導(dǎo)致MSSP 參與遷移的邊以及備份的頂點(diǎn)規(guī)模均較少，故負(fù)載變化較少.

Fig.8 Analysis on workload variation due to vertex replication圖8 頂點(diǎn)備份對(duì)負(fù)載變化的影響分析

Fig.9 Analysis on communication net benefit variation due to vertex replication圖9 頂點(diǎn)備份對(duì)通信凈收益變化的影響分析

Table 7 Comparison of Performance Improvement Between Actual and Predicted Optimal Replication Thresholds表7 實(shí)際與預(yù)測(cè)最優(yōu)備份閾值的性能提升對(duì)比

頂點(diǎn)備份對(duì)通信收益變化的影響是指計(jì)算過(guò)程中頂點(diǎn)備份加快的系統(tǒng)運(yùn)行時(shí)間，以備份后產(chǎn)生的消息通信收益與引入備份頂點(diǎn)值的同步開(kāi)銷(xiāo)之差作為最終的通信收益指標(biāo)，圖9 展示了各算法的通信收益.對(duì)比圖8 和圖9 可以發(fā)現(xiàn)，不同算法在各數(shù)據(jù)集上的負(fù)載變化與通信收益趨勢(shì)一致，即高負(fù)載偏斜會(huì)帶來(lái)較大的通信收益.其中，對(duì)于LiveJ 數(shù)據(jù)集上的MSSP 與SA 算法，由于MSSP 算法備份閾值較高，導(dǎo)致遷移邊的規(guī)模降低，故通信收益較少.綜合來(lái)看，通信收益與負(fù)載代價(jià)之差的變化位于3.64～63.26 s 之間，即輕量級(jí)頂點(diǎn)備份框架即使引起負(fù)載偏斜，仍能提高圖處理的整體性能.

5.4 自適應(yīng)性能優(yōu)化模型分析

本組實(shí)驗(yàn)主要驗(yàn)證備份閾值優(yōu)化模型的有效性以及所產(chǎn)生的額外開(kāi)銷(xiāo).

1）模型有效性.自適應(yīng)優(yōu)化模型的有效性可通過(guò)2 個(gè)方面進(jìn)行驗(yàn)證，即公式 φl(shuí)oad與 φcom對(duì)負(fù)載偏斜和通信收益估算的準(zhǔn)確性以及最優(yōu)閾值選擇的準(zhǔn)確性.φl(shuí)oad的驗(yàn)證方式為，通過(guò)在4 個(gè)數(shù)據(jù)集上運(yùn)行SC，SA，MSSP 算法，首先手動(dòng)詳細(xì)測(cè)試了不同備份閾值下LGraph 的實(shí)際表現(xiàn)；對(duì)應(yīng)地，為便于對(duì)比，將備份閾值優(yōu)化模型的輸出結(jié)果（即 φl(shuí)oad與 φcom理論估算值）累加上無(wú)備份的HGraph 的運(yùn)行結(jié)果，從而對(duì)備份框架的性能進(jìn)行理論評(píng)估.φcom則通過(guò)對(duì)比手動(dòng)選擇的最優(yōu)閾值與自適應(yīng)模型計(jì)算的最優(yōu)閾值及其對(duì)應(yīng)的LGraph 性能來(lái)驗(yàn)證.

圖10 展示了φl(shuí)oad與φcom的估算準(zhǔn)確性驗(yàn)證.隨著閾值的增加，算法在不同數(shù)據(jù)集上的運(yùn)行時(shí)間一般呈先下降后上升趨勢(shì)，并最終達(dá)到甚至超過(guò)無(wú)備份的HGraph 運(yùn)行時(shí)間.算法整體運(yùn)行時(shí)間的變化，是通信收益與負(fù)載偏斜延遲之間相互作用的結(jié)果.前期，隨著閾值增大，參與備份的頂點(diǎn)（以及遷移的出邊）規(guī)模減少，導(dǎo)致通信收益降低，但同時(shí)負(fù)載偏斜程度也急劇下降，因此綜合性能收益為正；后期，隨著閾值持續(xù)增大，通信收益的損失遠(yuǎn)大于負(fù)載偏斜的緩解，導(dǎo)致綜合性能收益為負(fù)，總運(yùn)行時(shí)間呈持續(xù)上趨勢(shì).注意到在大部分情況下，當(dāng)閾值超過(guò)500 時(shí)，由于指向某一目的任務(wù)的最大出度超過(guò)500 的頂點(diǎn)數(shù)量極少，頂點(diǎn)備份產(chǎn)生的通信收益趨于0，LGraph的實(shí)際迭代性能在此時(shí)與HGraph 相當(dāng).特別地，對(duì)于EU 數(shù)據(jù)集上的SC 算法（圖10（d））和MSSP 算法（圖10（l）），由于高出度頂點(diǎn)較多，當(dāng)閾值增大時(shí)，仍有大量出邊被遷移，但任務(wù)間的負(fù)載分布卻更為偏斜，導(dǎo)致通信收益無(wú)法抵消負(fù)載延遲開(kāi)銷(xiāo)，使得LGraph實(shí)際性能甚至不如HGraph.此時(shí)的閾值分析模型雖不能很好地?cái)M合實(shí)際性能表現(xiàn)，但也可以預(yù)測(cè)出整體運(yùn)行時(shí)間呈現(xiàn)上升趨勢(shì)，從而指導(dǎo)編程人員避免選擇較大的閾值.整體來(lái)看，圖10（a）～（l）表明自適應(yīng)閾值分析模型可較好地?cái)M合實(shí)際運(yùn)行時(shí)間的變化趨勢(shì)，為最優(yōu)備份閾值選擇的準(zhǔn)確性提供了保證.

表7 對(duì)比了實(shí)際手工測(cè)試得到的最優(yōu)閾值與分析模型計(jì)算得到的最優(yōu)閾值，以驗(yàn)證最優(yōu)閾值自動(dòng)選擇的準(zhǔn)確性.表7 同時(shí)匯報(bào)了累加數(shù)據(jù)加載與劃分開(kāi)銷(xiāo)后頂點(diǎn)備份對(duì)整個(gè)作業(yè)運(yùn)行時(shí)間的優(yōu)化效果，即“性能提升”斜杠后面的內(nèi)容.顯然，閾值分析模型在UK 數(shù)據(jù)集上的SC 與MSSP 算法、LiveJ 數(shù)據(jù)集上的SA 算法、Wiki 數(shù)據(jù)集上的SC 與MSSP 算法均可以找到或近似找到最優(yōu)閾值；對(duì)于LiveJ 數(shù)據(jù)集上的SC 與MSSP 算法、Wiki 上的SA 算法和EU 上的SA算法，自動(dòng)計(jì)算的最優(yōu)閾值與實(shí)測(cè)值相差較大，這是由于收益與延遲開(kāi)銷(xiāo)的博弈接近臨界值，對(duì)各種參數(shù)的取值較為敏感，難以準(zhǔn)確預(yù)測(cè)，但也因此導(dǎo)致最優(yōu)閾值周?chē)男阅茏兓容^?。ㄒ?jiàn)圖10（b）（j）與圖（g）（h）），故即使閾值選擇偏差較大，實(shí)際的性能收益仍然接近手動(dòng)選擇的最優(yōu)值.

Fig.10 The actual and predicted performance under different replication thresholds圖10 不同備份閾值下的實(shí)際和預(yù)測(cè)性能

需要注意的是，對(duì)于整個(gè)作業(yè)的運(yùn)行時(shí)間問(wèn)題，SC 與SA 算法均采用10 步迭代計(jì)算的時(shí)間之和.考慮到頂點(diǎn)備份過(guò)程內(nèi)嵌于數(shù)據(jù)加載與劃分階段，因此，啟動(dòng)頂點(diǎn)備份功能后，系統(tǒng)的加載與劃分階段會(huì)引入額外的出邊遷移開(kāi)銷(xiāo).對(duì)比“性能提升”斜杠兩邊的內(nèi)容可以看到，即使備份機(jī)制在加載劃分階段引入了額外遷移開(kāi)銷(xiāo)，但由于后續(xù)迭代過(guò)程中產(chǎn)生了巨大的通信收益，前者對(duì)綜合性能提升百分比的影響十分微小.以影響最大的Wiki-SA 組合為例，在手工測(cè)試的最優(yōu)閾值下，性能提升比例由53%下降到47.5%,僅產(chǎn)生了5.5%的影響；而在自適應(yīng)閾值分析模型下，性能提升比例也僅有3%的差距，其綜合性能收益仍然十分可觀.

2）模型開(kāi)銷(xiāo).自適應(yīng)性能優(yōu)化模型的開(kāi)銷(xiāo)來(lái)源于預(yù)測(cè)所需參數(shù)的獲取，也即算法1 展示的第1 類(lèi)參數(shù)的獲取過(guò)程.該過(guò)程的核心操作，是在給定的分布式任務(wù)數(shù)和數(shù)據(jù)集額外運(yùn)行一次數(shù)據(jù)加載，并在加載過(guò)程中根據(jù)給定的候選閾值數(shù)組對(duì)不同閾值下的頂點(diǎn)分布以及出邊遷移情況進(jìn)行參數(shù)值統(tǒng)計(jì).圖11 展示了不同閾值粒度（即候選閾值數(shù)組長(zhǎng)度）下的加載時(shí)間開(kāi)銷(xiāo).圖12～14 對(duì)應(yīng)列出了3 種不同算法在不同粒度下閾值選擇的準(zhǔn)確率.令 θs為模型選擇的最優(yōu)閾值，而 θ*為表7 中匯報(bào)的、通過(guò)多次手工調(diào)試所得的最優(yōu)閾值.選擇準(zhǔn)確性的計(jì)算方式為 |θs-θ*|/θ*.結(jié)果顯示，輸入閾值數(shù)組的粒度與自適應(yīng)性能優(yōu)化模型的統(tǒng)計(jì)開(kāi)銷(xiāo)成反比，與最優(yōu)閾值選擇的準(zhǔn)確性成正比.閾值粒度越細(xì)化，解析的參數(shù)越多，優(yōu)化模型對(duì)最優(yōu)閾值的預(yù)測(cè)結(jié)果越精細(xì)，利于找到最優(yōu)閾值；反之，最優(yōu)閾值的選擇偏差增大，但參數(shù)統(tǒng)計(jì)操作減少，加載延遲降低.

Fig.11 Latency analysis of loading data under different threshold granularities圖11 不同閾值粒度下的數(shù)據(jù)加載延遲分析

Fig.12 Accuracy analysis of selecting the optimal threshold under different threshold granularities for SC圖12 SC 在不同閾值粒度下的最優(yōu)閾值選擇準(zhǔn)確率分析

Fig.13 Accuracy analysis of selecting the optimal threshold under different threshold granularities for SA圖13 SA 在不同閾值粒度下的最優(yōu)閾值選擇準(zhǔn)確率分析

Fig.14 Accuracy analysis of selecting the optimal threshold under different threshold granularities for MSSP圖14 MSSP 在不同閾值粒度下的最優(yōu)閾值選擇準(zhǔn)確率分析

綜合考慮加載延遲和選擇準(zhǔn)確性，本文以2000為閾值運(yùn)行優(yōu)化模型，以1.12～1.64 倍的延遲獲得較高的選擇準(zhǔn)確率.此外，考慮到同一個(gè)數(shù)據(jù)集上的不同應(yīng)用作業(yè)可共享參數(shù)統(tǒng)計(jì)結(jié)果，故該加載過(guò)程可視為離線操作，其開(kāi)銷(xiāo)不計(jì)入實(shí)時(shí)的作業(yè)處理時(shí)間.

6 結(jié)論

通信開(kāi)銷(xiāo)一直是制約分布式圖處理性能提升的關(guān)鍵因素.本文從內(nèi)存和迭代性能上對(duì)現(xiàn)有HGraph系統(tǒng)進(jìn)行了改進(jìn).具體地，本文首先對(duì)圖算法進(jìn)行分類(lèi)，指出多維消息類(lèi)算法對(duì)通信和內(nèi)存的緊迫性要求，并以此為基礎(chǔ)在徹底合并系統(tǒng)上引入輕量級(jí)頂點(diǎn)備份框架，對(duì)系統(tǒng)的內(nèi)存開(kāi)銷(xiāo)進(jìn)行優(yōu)化.其次，提出了自適應(yīng)性能優(yōu)化模型，對(duì)頂點(diǎn)參與備份或合并進(jìn)行定量分析，并對(duì)出邊偏移閾值進(jìn)行優(yōu)化.大量真實(shí)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果表明，輕量級(jí)頂點(diǎn)備份框架在內(nèi)存和執(zhí)行時(shí)間方面，均優(yōu)于目前最新的處理平臺(tái)HGraph，自適應(yīng)性能優(yōu)化模型對(duì)最優(yōu)備份閾值的選擇也表現(xiàn)出很好的適應(yīng)性.

作者貢獻(xiàn)聲明：杜玉潔參與算法構(gòu)思并負(fù)責(zé)完成實(shí)驗(yàn)方案與論文初稿撰寫(xiě)；王志剛提出了完整的算法框架并修改完成論文終稿；王寧參與了論文的審閱與格式校正；劉芯亦協(xié)助完成了相關(guān)工作調(diào)研與實(shí)驗(yàn)數(shù)據(jù)整理；衣軍成完成了實(shí)驗(yàn)數(shù)據(jù)集的收集與格式變換；聶婕與魏志強(qiáng)對(duì)論文內(nèi)容的邏輯布局進(jìn)行了指導(dǎo)；谷峪與于戈對(duì)備份閾值的計(jì)算方式提出了指導(dǎo)意見(jiàn)并協(xié)助修改論文.