1. Pregel開發(fā)時(shí), 圖計(jì)算領(lǐng)域面對(duì)的問(wèn)題
- 分布式圖算法大部分是高度定制化的, 如果需要新的圖算法, 就需要從頭開始開發(fā), 實(shí)際上分布式圖算法自打有MPP就開始做了, 只不過(guò)通用的比較少.
- MapReduce可以解決部分圖挖掘問(wèn)題, 但是在MR的模型上直接跑Graph算法那, 性能和可用性都大打折扣, 達(dá)不到谷歌家的需求
- 單機(jī)版圖算法倒是不錯(cuò), 可惜neo4j這種東西面對(duì)谷歌的數(shù)據(jù)量就抓瞎.并沒(méi)有什么卵用
- 一些理論上的分布式圖計(jì)算引擎, 比如CGMGraph, Parallel BGraph沒(méi)法做fault tolerance. 這和分布式系統(tǒng)假設(shè)所有點(diǎn)都可以掛, 所有網(wǎng)絡(luò)都可以跑不通有矛盾. 并不能部署在工業(yè)界.
谷歌一氣之下, 在Valiant’s Bulk Synchronous Parallel Model的技術(shù)上做出了Pregel. 從算法理論到工業(yè)實(shí)現(xiàn)用了20年, 和cherry lock有一拼.
Leslie G. Valiant, A Bridging Model for Parallel
Computation. Comm. ACM 33(8), 1990, 103–111
2. 抽象模型概述
2.1 Supserstep
Pregel計(jì)算由一系列的被稱之為superstep的步驟組成, 它的輸入是一個(gè)有向圖, 所有的vertex必須是唯一的
在superstep的第N步, 會(huì)收取N-1步的信息, 計(jì)算, 更新?tīng)顟B(tài), 把信息按照邊向后發(fā)送, 等待第N+1步讀取.
2.2 計(jì)算模型的狀態(tài)機(jī)
superstep何時(shí)終止, 取決于所有節(jié)點(diǎn)的投票vote to halt的結(jié)果.
當(dāng)所有的點(diǎn)都不再收取信息時(shí), 就會(huì)終止.
在論文中介紹了一個(gè)非常簡(jiǎn)單的例子如上, 我們要想辦法在一個(gè)圖中找到value最大的vertex.
可以從圖中看到, 在每個(gè)supersetp
- 每個(gè)點(diǎn)比保存一個(gè)max(local_value, message_value)
- 如果沒(méi)有變化, 則vote to halt
- 如果有變化則把max value沿著邊發(fā)送
- 重復(fù)以上步驟, 直到所有verte vote to halt(變灰)
這樣我們就可以找到一個(gè)圖里的最大值, 而且可以看到這個(gè)過(guò)程可以是一串的map reduce過(guò)程, 在Map中所有點(diǎn)接收信息并比較, 在Reduce中產(chǎn)生vetex與vetex之間的信息轉(zhuǎn)移.
3 Pregel程序的執(zhí)行過(guò)程
一下過(guò)程基于google自己的底層框架, 換到spark+hbase上一樣說(shuō)的通
- 首先啟動(dòng)一個(gè)
master點(diǎn), 可以直接理解為spark里的driver, 用于管理整個(gè)程序的進(jìn)度. 所有的woker需要把自己注冊(cè)到這個(gè)master上. -
master負(fù)責(zé)把圖劃分為多個(gè)partition, 并指定每個(gè)worker需要負(fù)責(zé)的部分.worker需要對(duì)自己維護(hù)的這一部分graph執(zhí)行用戶寫的computer()操作, 并維護(hù)這一部分圖的狀態(tài). 每個(gè)worker都知道其它的任何一個(gè)worker維護(hù)的是哪部分graph, 這個(gè)問(wèn)master就好了.
1.master開始分發(fā)用戶的輸入, 如果worker觀察到用戶的input與自己維護(hù)的graph有關(guān), 則立即對(duì)這部分graph進(jìn)行修改和操作, 否則就把數(shù)據(jù)送到它該去的地方. 分發(fā)過(guò)程結(jié)束后, 這個(gè)分布式的圖已經(jīng)和用戶的input融合, 所有的vertex處于active狀態(tài) - 開始執(zhí)行superstep, 回到vote to halt的狀態(tài)到
master那里去 -
master觀察到所有的vertex都halt了, 運(yùn)行結(jié)束
4. Pregel下的圖算法
4.1 PageRank
class PageRankVertex
: public Vertex<double, void, double> {
public:
// 假設(shè)一共有v個(gè)節(jié)點(diǎn), 任何一個(gè)點(diǎn)初始的權(quán)重都是 1/v
virtual void Compute(MessageIterator* msgs) {
if (superstep() >= 1) {
double sum = 0;
for (; !msgs->Done(); msgs->Next())
sum += msgs->Value();
// 節(jié)點(diǎn)的權(quán)重調(diào)整如下, 引用它的網(wǎng)站越多, 它的權(quán)重越高, 引用它的網(wǎng)站約重要, 它的權(quán)重越高
*MutableValue() = 0.15 / NumVertices() + 0.85 * sum;
}
// 我們只進(jìn)行30層運(yùn)算
if (superstep() < 30) {
// 把這個(gè)vertex, 也就是網(wǎng)站的權(quán)重向所有它引用的網(wǎng)站進(jìn)行廣播
const int64 n = GetOutEdgeIterator().size();
SendMessageToAllNeighbors(GetValue() / n);
} else {
VoteToHalt();
}
}
};
4.2 Shortest Path
尋找source vertex和圖中任何一個(gè)其它點(diǎn)之間的最短路徑
一開始source vertex的距離是0, 其它任何一個(gè)點(diǎn)都是INF(無(wú)限), 然后source vertex開始廣播
之后每個(gè)superstep, 每個(gè)接收從鄰居那里來(lái)的message, 如果鄰居記錄的值加上邊長(zhǎng)比本地值小, 則修改記錄. 否則就vote for halt.
重復(fù)以上步驟直到所有的點(diǎn)都不動(dòng)了.
class ShortestPathVertex
:public Vertex<int, int, int> {
void Compute(MessageIterator* msgs) {
int mindist = IsSource(vertex_id()) ? 0 : INF;
for (; !msgs->Done(); msgs->Next())
mindist = min(mindist, msgs->Value());
if (mindist < GetValue()) {
*MutableValue() = mindist;
OutEdgeIterator iter = GetOutEdgeIterator();
for (; !iter.Done(); iter.Next())
SendMessageTo(iter.Target(),
mindist + iter.GetValue());
}
VoteToHalt();
}
};
class MinIntCombiner : public Combiner<int> {
virtual void Combine(MessageIterator* msgs) {
int mindist = INF;
for (; !msgs->Done(); msgs->Next())
mindist = min(mindist, msgs->Value());
Output("combined_source", mindist);
}
};
5. 待解決問(wèn)題
- 如果存在supernode, 會(huì)導(dǎo)致某一部分圖的計(jì)算量要遠(yuǎn)遠(yuǎn)大于其它部分, 而且這部分壓力會(huì)集中在一個(gè)機(jī)器上
- 因?yàn)槊總€(gè)superstep結(jié)束后, 才能進(jìn)行下一個(gè), 所以計(jì)算速度取決于最慢的那臺(tái)機(jī)器, 這對(duì)異構(gòu)系統(tǒng)不友好. 在新老機(jī)器混雜的集群里, 需要非常強(qiáng)大的資源管理系統(tǒng)協(xié)調(diào). 裸上一個(gè)yarn的默認(rèn)策略絕對(duì)會(huì)跪.
