1. 和上一代有哪些區(qū)別?
GraphLab主要并發(fā)解決計算問題, 但是對于highly skewed power-law degree
distributions 解決的不太好, 這一點在上一代的基礎(chǔ)上進一步嘗試解決嚴重的數(shù)據(jù)偏斜.
論文地址: http://www.cs.princeton.edu/courses/archive/fall13/cos518/papers/powergraph.pdf
- 為了應對這個情況, 把
update操作變成GatherApplyScatter三個步驟 - 進一步優(yōu)化切分, 把切分從edge cut 變成 vertex cut, 讓熱點存在于多個機器上, 每個機器保存這個熱點的一部分關(guān)聯(lián)edge以分散數(shù)據(jù)壓力
2. 計算模型GAS
- Gather
用戶定義一個操作⊕,這個操作必須滿足交換律和結(jié)合律
針對某個vertex u, 它所有關(guān)聯(lián)的edge和vertex的data搜集到一起執(zhí)行這個操作.
在有向圖里這里只會計算入度的邊
Gather
-
Apply
把上一步計算的結(jié)果進行匯總, 然后把匯總結(jié)果∑更新到執(zhí)行的vertex
Apply Scatter
根據(jù)執(zhí)行中心點vertex在apply之后的值去更新和它關(guān)聯(lián)的所有edge的值
在有向圖里這里只會計算出度的邊
我讀論文說是更新edge的值, 國內(nèi)好多技術(shù)博客說是更新edge和vertex的值, 我對自己的閱讀能力產(chǎn)生了深深的懷疑...不過都不影響后續(xù)講GraphX, 那邊是直接有代碼的
Scatter
interface GASVertexProgram(u) {
// Run on gather_nbrs(u)
gather(Du, D(u,v), Dv) → Accum
sum(Accum left, Accum right) → Accum
apply(Du,Accum) → Du
// Run on scatter_nbrs(u)
scatter(Du ,D(u,v),Dv) → (D(u,v), Accum)
}
partition切割模型
看完上面的介紹后, 立馬產(chǎn)生一個問題就是Gather和Apply為啥是分開的, 算完之后直接更新上去不就行了么?
答案是, Gather過程不一定是在一個機器上運算的, 上文提到Power Graph是在Vertex處切割, 這意味著一個Vertex可能被切到多臺機器上分別計算, 然后再匯總到一起!
按vertex切割
如上圖所示, 在vertex切割的情況下, 我們在綠色的點上執(zhí)行
Gather操作后, 實際上CPU1上的進程和CPU2上的進程各持有了一部分數(shù)據(jù), 這個時候想要執(zhí)行Apply就需要兩個進程通信后匯總結(jié)果, 然后分別更新綠色點的值.
在實際切分中有兩種切分策略 Random切分 和 Greedy切分, 感興趣的可以看論文附送的Slide里面用動圖講了Greedy的策略:
- A(v): set of machines that vertex v spans.
- Case 1: If A(u) ∩ A(v) != ?, then the edge should be assigned to a
machine in the intersection. - Case 2: If A(u)∩A(v) = ?, then the edge should be assigned to one
of the machines from the vertex with the most unassigned edges. - Case 3: If only one of the two vertices has been assigned, then
choose a machine from the assigned vertex. - Case 4: If A(u) = A(v) = ?, then assign the edge to the least
loaded machine
