目的
在分布式圖計算中的圖分割方法一文中介紹了分布式圖計算中的頂點分割方法來對圖數據來進行分割,從而使得一個數據量巨大的圖,能夠在不同的分布式計算節(jié)點中進行平行計算。
但是當圖數據被分割后進入不同計算節(jié)點進行計算的時候,由于在不同節(jié)點中對于同一個節(jié)點有可能有多個副本磨淌,這個節(jié)點副本之間如何進行數據交換協(xié)同也成為了一個難題,于是GAS模型就被提出來解決這個難題凿渊。
圖計算頂點切割
GAS模型
GAS模型主要分為3個階段:Gather Apply Scatter
GAS模型
Gather階段
Gather階段的主要工作主要發(fā)生在各個計算節(jié)點梁只,搜集這個計算節(jié)點圖數據中某個頂點的相鄰邊和頂點的數據進行計算(例如在PageRank算法中計算某個頂點相鄰的頂點的數量)。
Apply階段
Apply階段的主要工作是將各個節(jié)點計算得到的數據(例如在PageRank算法中各計算節(jié)點計算出來的同一節(jié)點的相鄰節(jié)點數)統(tǒng)一發(fā)送到某一個計算節(jié)點埃脏,由這個計算節(jié)點對圖節(jié)點的數據進行匯總求和計算搪锣,這樣就得到這個圖頂點的所有相鄰節(jié)點總數。
Scatter階段
Scatter階段的主要工作是將中心計算節(jié)點計算的圖頂點的所有相鄰節(jié)點總數發(fā)送更新給各個計算節(jié)點中剂癌,這些收到更新信息的節(jié)點將會更新本計算節(jié)點中與這個圖頂點相鄰的頂點以及邊的相關數據淤翔。
總結
通過GAS模型的不同階段的配合翰绊,很完美的解決分布式圖計算中的節(jié)點副本之間如何進行數據交換協(xié)同難題佩谷。