Giraph:Pregel 的 Hadoop 落地
Giraph 把 BSP/Pregel 的顶点程序放到 Hadoop 集群执行:输入从 HDFS 读、输出写回 HDFS,worker 各持一份顶点分区,每超步之间用 ZooKeeper 同步屏障收齐消息。
超步与消息账本
bsp 用例 18:路径图 4 顶点 3 边共 4 个超步(源点 + 3 层);用例 19、30:3 条边产生 3 条消息,消息数 = 边数。用例 23:星形图直径 1,2 超步收敛;用例 24:5 条边发 5 条消息。每超步活跃顶点只对本地分区执行程序,跨 worker 消息走网络,同步屏障保证下一超步看到全部上一超步消息。
收敛与算法复用
bsp 用例 20:无消息的活跃顶点计算后投票停止,收敛后 active=0;用例 25:aggregator 最后超步 = 1+2+3 = 6,把全局统计压缩为单一值。同一超步骨架承载多种算法:algo 用例 43 路径图 SSSP 距离 3、50 连通分量收敛到最小 id、54-55 三角计数全图 1 个三角形。
对齐卷一:MapReduce 之上的图轮次
MapReduce 一趟 map+shuffle+reduce 处理一批数据;Giraph 是它之上的多轮骨架,每超步等价一次带屏障的 reduce 同步。取舍:同步语义简单,但慢 worker 拖累全轮,ZooKeeper 协调与跨 worker 直连是工程重点。
验证
从卷十一实验包 解包,bsp 用例 16-18 验证 BFS 源点距离 0、末端距离 3、路径图 4 超步;用例 19、24、30 验证消息数 = 边数;用例 23 验证星形图 2 超步收敛;algo 用例 43、50、54-55 验证 SSSP、连通分量、三角计数在同一超步骨架上的收敛口径。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。