《大规模分布式计算深入解析》3.3 aggregator、combiner 与收敛判定

aggregator 汇总全局、combiner 合并同目标消息不改发送账本;星形图 2 超步收敛。

aggregator、combiner 与收敛判定

同步超步模型附带三件优化/判定工具:aggregator 看全局、combiner 省带宽、投票停止判收敛。

aggregator:全局汇总

aggregator 每超步把各顶点局部值归约为一个全局值,供下一超步读取。bsp 用例 25:aggregator 最后超步 = 1+2+3 = 6——每超步累加,账本可核算。

combiner:同目标消息合并

combiner 在发送端把发往同一顶点的多条消息合并成一条,不改变发送账本。用例 27a:顶点 0 发 5.0、顶点 1 发 3.0,目标收 5.0(取最大值);27b:原始消息仍计 2 条;27c:目标顶点只收到合并后的 1 条。省的是网络带宽,不是算法语义。

收敛判定

用例 22:一条边只发一条消息。用例 23:星形图直径 1,2 超步收敛。用例 24:星形图 5 条边 5 条消息。所有顶点投票停止、无新消息即收敛;自循环消息会让超步被上限截断(用例 29)。

验证

从卷十一实验包 解包,运行 Java 账本:bsp 用例 22-24 验证一条边一条消息、星形图直径 1 两超步收敛、5 条边 5 条消息;用例 27 验证 combiner 合并为最大值 5.0 且不改发送账本;用例 25 验证 aggregator 账本 6。

一手资料

卷十一目录 · 系列导读与实验

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析》15.3 落地:从 Neo4j 到自研图引擎
  2. 《大规模分布式计算深入解析·图计算与图数据库内核》 · 目录与学习路径(45 篇)
  3. 《大规模分布式计算深入解析》15.2 十一卷主线:从切分到图