图数据强耦合
图的边让数据更新与邻居相关;幂律分布还可能把大量边集中到少数高阶节点。分片既要控制机器负载,也要减少迭代通信,局部性差的成本会被多轮计算放大。不是所有图都服从同一分布,不能仅按节点数平均分配就认定负载均衡。
主题对照
以图为一等对象的计算怎么做:图为什么和存储耦合、点切与边切怎么权衡、顶点中心编程与消息传递、BSP 超级步与同步异步取舍、迭代代价与检查点,以及连通分量、二度关联这类图算法的落地方式。
图的边让数据更新与邻居相关;幂律分布还可能把大量边集中到少数高阶节点。分片既要控制机器负载,也要减少迭代通信,局部性差的成本会被多轮计算放大。不是所有图都服从同一分布,不能仅按节点数平均分配就认定负载均衡。
关联图谱用节点表示实体、用边表示实体间关系,可据此观察用户、设备、IP 等如何形成网络。流上的图谱特征还要限定时间窗口,例如“过去一周同设备注册的不同用户数”;不限定范围会把持续到来的历史关系无限累积。定义图谱指标时,应同时写清实体、边和时间范围。
为一个顶点定义读取信息、更新状态及向外传播的规则,系统反复调度这些局部规则来完成全图计算。分片、通信和恢复由框架承担。可读写哪些邻居对象、消息何时可见由具体模型规定,不能把所有节点中心框架的访问能力混为一谈。
节点中心和GAS规定应用如何表达一次更新;同步和异步规定更新何时可见、如何调度。相同局部算法可以配不同执行范型,仍需重新检查语义和停止条件。不能把GAS直接当同步协议,也不能因API像Pregel就推断内部运行方式相同。
Map按目标节点ID输出贡献,Shuffle把同一目标的贡献汇合,Reduce更新节点。邻接表也要传递或在其他结构中保留,下一轮才能继续发送。图14-7说明消息和图结构需区分,不能只输出分值而丢掉拓扑;省略跳转项的伪码不是完整PageRank。
许多图算法(如PageRank)的模式是”重复沿边传播信息,直到没有更多边要跟进或某个指标收敛”,这种迭代性质普通MapReduce表达不了——它只扫一遍数据,每轮迭代都要重新读取整个输入并产出全新输出,即便相比上一轮只有极小一部分图发生了变化。Pregel模型(也叫批量同步并行/BSP模型,Apache Giraph、Spark GraphX、Flink Gelly都实现了它)专门针对这种场景优化,核心是”像顶点一样思考”:每个顶点可以沿图的边向其他顶点发送消息,框架在每次迭代里为每个顶点调用一次函数,把上一轮所有发给它的消息一并递送——如果某部分图没收到消息,那部分就不必做任何工作。与MapReduce的关键区别是顶点状态能跨迭代保留,函数只需处理新到的消息,这有点像Actor模型,但通信以固定回合方式进行:框架保证上一轮发出的所有消息,一定在本轮送达。容错通过定期把所有顶点状态存档实现,一旦某节点故障导致内存状态丢失,最简单的做法是把整个计算回滚到最近的存档点重启(若算子确定性且消息有日志记录,也可以只恢复丢失的分区)。并行执行方面,顶点不需要知道自己运行在哪台物理机器上,图的分区完全由框架决定;但由于顶点间的通信开销往往很大,若图能放进单机内存或磁盘,单机(甚至单线程)算法反而经常比分布式Pregel更快。
结构图:
flowchart TD
A[第N轮迭代开始] --> B[框架递送第N-1轮发出的全部消息]
B --> C[对每个收到消息的顶点调用处理函数]
C --> D[顶点更新自身状态,可沿边发送新消息]
D --> E{是否满足终止条件: 无更多边可跟进或指标收敛}
E -->|否| F[框架存档全部顶点状态]
F --> A
E -->|是| G[计算完成,输出结果]
Pregel在超级步S处理上步消息、更新本地顶点并发送下步消息,所有工作节点完成该步后再推进。屏障提供清晰的可见性边界,也让拖尾工作影响全局。消息传输可在实现中异步进行,但应用语义仍是下一超级步接收。
结构图:
flowchart TD
A[接收S减1步消息] --> B[执行活跃顶点函数]
B --> C[生成S加1步消息]
C --> D[全局同步与终止检查]
D --> E[进入下一超级步]
BSP把执行划成多个超级步,每步依次进行本地计算、全局通信、屏障同步,然后进入下一步。局部计算使用本地可用数据,通信交换下一步需要的信息,屏障使各处理器在该步边界对齐。这是计算与通信的组织模型,不限定必须采用某一种机器学习算法。
BSP 把并行计算划成连续的 superstep,各进程在一阶段计算并交换消息,到栅栏处等待,所有参与者完成后才进入下一阶段。这适合需要上一轮结果的迭代过程;代价是慢进程会拖住整个阶段。发散:设计时要看阶段工作量是否均衡,而非只增加进程数。
doTaskBatch 一次发给多个工人并等待全体完成,调用简洁,也形成清晰的阶段屏障;但返回受最慢工人限制,快工人做完后可能空闲。逐个 doTask 并检查结果状态,可让先完成的工人马上接新任务,代价是调度者要自行跟踪在途结果与终止条件。选择取决于阶段同步要求和工人耗时差异。参见 [[工人槽位完成后再派新任务]]。
Gather收集邻边与邻点信息,Apply更新中心顶点,Scatter传播变化。拆分有助于把高阶节点邻边工作分散,Apply仍需统一决定顶点状态。收集运算必须满足所用并行合并语义;任意函数不能仅因被命名sum就安全重排。
结构图:
flowchart TD
A[邻边局部Gather] --> B[合并累积结果]
B --> C[中心Apply更新]
C --> D[Scatter传播变化]
D --> E[按变化激活后续顶点]
PowerGraph可让Gather、Apply、Scatter各阶段完成后再推进,用微屏障约束可见性;本轮激活节点在下轮调度。异步配置则允许较早利用更新。GAS接口与同步策略可分开选择,但消息、缓存和状态传播必须共同满足所选语义。
同步模型让本轮变化在规定边界后可见;异步模型允许后续调度较早使用新值。异步可能减少无效迭代和等待,也可能受顺序、竞争及资源冲突影响。是否收敛、是否等价于某个顺序执行需单独分析,不能保证异步一定更快或得到唯一结果。
MPI 是并行进程间消息通信的接口规范,发送和接收等操作让进程协作,但接口本身不替应用安排任务角色、阶段流转和资源调度。开发者可灵活组合通信,仍须自行设计这些上层机制。发散:选工具时要区分“能让进程传消息”和“已经提供完整作业编排”,避免把底层能力误当成应用框架。
Pregel主控分配分片、推动超级步和收集进度,Worker维护顶点与边、执行活跃计算并交换消息。主控不负责每个节点的业务运算。分工说明需要保存哪些管理状态,不能仅由一张主从图就断言完整系统没有主控恢复机制。
设超级步j中处理器i的本地计算时间为wᵢ,发送与接收的数据字数取大值为hᵢ,每数据字通信代价g,屏障代价l,则理想模型Tⱼ=maxᵢwᵢ+g·maxᵢhᵢ+l;总时间对超级步求和。书中单步公式图漏写g,应按同节文字补齐以保持量纲一致。该模型提示负载不均和通信热点会限制性能,不替代真实测量。
相邻BSP超级步之间有明确同步边界,可把这一时刻作为保存检查点的候选,恢复时从一致的计算进度继续。检查点仍须覆盖恢复所需的状态与消息,并处理存储失败;屏障只是提供边界,不会自动实现持久化,也不保证任意用户代码没有死锁。
链式MR每轮读写图状态、落盘中间结果并重新启动任务;很多迭代只改变少量值,这些重复成本会累积。驻留状态与专用消息通道可减少搬运,但需承担内存管理及恢复责任。MR可表达算法,表达可行与运行适合是不同判断。
本章Giraph把完整计算放入一个长驻Map-Only任务,状态留在内存,多轮消息通过专门网络传输,避免每步启动MR及Shuffle。复用Hadoop资源框架不意味着每个超级步都执行一次传统MapReduce。外存选项又是容量与I/O取舍。
GraphChi当前子图中,没有共同边的顶点可并行更新;存在共享边的顶点需避免同时修改同一状态。本章方案把有内部边的一组串行处理,是保守调度而非理论最大并行度。改进调度必须保留读写冲突保护,不能只增加线程。
二度好友推荐要从大量候选中选出少数结果:若平均每人有 100 个好友,理论上有约 10000 条二跳路径;排序可参考建交时间、交互密度、资料相似度和共同好友数。全量实时计算成本高,书中建议先离线计算,再通过更快更新或增量计算缩短结果延迟。
一度关联统计某实体直接相邻的不同实体数,在实时场景通常还限定时间窗口。比如一周内同设备注册的不同用户数,本质上是按设备分组后的 COUNT DISTINCT(user_id)。小规模时可用集合精确去重;取值很多时需权衡存储与近似计数误差。
二度关联先找目标节点的一度邻居,再取这些邻居各自的一度邻居并求并集,得到两跳范围内的节点集合。与只求邻居数量的一度关联不同,第二步需要知道中间邻居是谁,单靠去重计数的估计值无法继续扩展。因此高势图谱的二度计算会面临较大的中间集合状态。
同一人的不同标识通过等价边组成连通分量,选其中最小标识作为代表,即可把历史访问映射到统一身份。批处理迭代检查各节点邻域,把邻域连接逐步重写为指向较小代表;信息传播到稳定后,各分量形成共同代表。最小只是确定性选择规则,不意味着该标识在业务上更真实。
与[[等价关系会改写历史]]的联系:等价图连通分量把多个历史标识统一为一人。
无向等价关系若只存一次二元组,按第一个端点分组会漏掉节点出现在第二个位置的边。先为每条边生成两个方向,再按首端点分组,就能收齐每个节点的全部邻接信息。该转换是为后续聚合准备完整输入,不表示业务上发生了两次独立的身份关系。
与[[连通等价图统一身份]]的联系:双向化使每个节点能够收齐完整邻域用于身份传播。
身份归一化每轮输出下一轮的边集,并单独标出相对输入新生成的边。协调程序反复执行分布式步骤,直到新边集为空,表示在该转换规则下达到定点。判定依据是没有新进展,不能简单固定轮数;边的总数不变也不代表边的内容没有变化。
与[[连通等价图统一身份]]的联系:新增边为空定义身份图传播达到定点的可检查条件。
只有一个用户标识的人可能根本没有等价边,因而不在身份映射表中。访问事件连接映射表时要保留这些记录:若找到代表ID就替换,若映射缺失则沿用原ID。内连接会把这类有效访问静默丢弃,导致访客和浏览指标都偏低。
与[[连通等价图统一身份]]的联系:外连接让未进入等价图的标识仍保留原访问。
PageRank 示例把网页当前权重平均分给它指向的页面:A 指向 B、C 时,各收到 A 权重的一半;一个页面的新权重是所有指向它的页面贡献之和。反复用新权重计算下一轮,才能观察链接结构形成的排序。赌钱例子只是这一权重流动的类比。
分布式 PageRank 可让工人沿每条链接直接发送投票,再在目标节点聚合;也可由工人先统计本地贡献,交给工头统一合并。前者在链接很多时产生大量跨机消息,后者减少逐链接调用,但汇总节点要承担合并压力。选型要比较链接数量、部分结果大小与汇总容量。
书中的简化更新式在链接贡献之外加上 1−q:即使某页本轮没有收到链接投票,只要 q<1,它下一轮仍有正的基线权重。这缓解了示例中零值一路传播的问题。它并不等于已处理所有无出链页面;实现完整 PageRank 时仍须明确这类页面的权重去向。
点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。
来源书籍
书籍类型:未标注
424 张卡片
来源书籍
系统架构类
书籍类型:工程实践
清单覆盖 6/7
122 张卡片
来源书籍
分布式系统类
书籍类型:经典原理
类别清单尚未核对
173 张卡片
来源书籍
分布式系统类
书籍类型:工程实践
清单覆盖 2/6
97 张卡片
来源书籍
实时流计算系统类
书籍类型:未标注
清单覆盖 8/8
172 张卡片
来源书籍
分布式系统类
书籍类型:经典原理
类别清单尚未核对
194 张卡片
主题索引
比较批处理、流式、交互式查询、图计算、分布式机器学习与增量计算的计算模型与取舍。
与 2 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 1 张主题卡片存在结构化链接;来自相同书籍;属于相同分类