主题对照

图计算:切分、BSP 与迭代

以图为一等对象的计算怎么做:图为什么和存储耦合、点切与边切怎么权衡、顶点中心编程与消息传递、BSP 超级步与同步异步取舍、迭代代价与检查点,以及连通分量、二度关联这类图算法的落地方式。

30 张卡片 · 6 本书

本层 30 张卡片 · 含下级覆盖 30 张卡片

本主题的卡片

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

图数据强耦合

图的边让数据更新与邻居相关;幂律分布还可能把大量边集中到少数高阶节点。分片既要控制机器负载,也要减少迭代通信,局部性差的成本会被多轮计算放大。不是所有图都服从同一分布,不能仅按节点数平均分配就认定负载均衡。

查看卡片与原书出处

实时流计算系统设计与实现 · 第4章 数据处理

关联图谱表示实体关系

关联图谱用节点表示实体、用边表示实体间关系,可据此观察用户、设备、IP 等如何形成网络。流上的图谱特征还要限定时间窗口,例如“过去一周同设备注册的不同用户数”;不限定范围会把持续到来的历史关系无限累积。定义图谱指标时,应同时写清实体、边和时间范围。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

节点中心编程

为一个顶点定义读取信息、更新状态及向外传播的规则,系统反复调度这些局部规则来完成全图计算。分片、通信和恢复由框架承担。可读写哪些邻居对象、消息何时可见由具体模型规定,不能把所有节点中心框架的访问能力混为一谈。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

图编程模型与执行范型分开

节点中心和GAS规定应用如何表达一次更新;同步和异步规定更新何时可见、如何调度。相同局部算法可以配不同执行范型,仍需重新检查语义和停止条件。不能把GAS直接当同步协议,也不能因API像Pregel就推断内部运行方式相同。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

MR用按键聚集模拟图消息

Map按目标节点ID输出贡献,Shuffle把同一目标的贡献汇合,Reduce更新节点。邻接表也要传递或在其他结构中保留,下一轮才能继续发送。图14-7说明消息和图结构需区分,不能只输出分值而丢掉拓扑;省略跳转项的伪码不是完整PageRank。

查看卡片与原书出处

数据密集型应用系统设计 · 批处理

Pregel图批处理

许多图算法(如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[计算完成,输出结果]
查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

BSP超级步

Pregel在超级步S处理上步消息、更新本地顶点并发送下步消息,所有工作节点完成该步后再推进。屏障提供清晰的可见性边界,也让拖尾工作影响全局。消息传输可在实现中异步进行,但应用语义仍是下一超级步接收。

结构图:

flowchart TD
 A[接收S减1步消息] --> B[执行活跃顶点函数]
 B --> C[生成S加1步消息]
 C --> D[全局同步与终止检查]
 D --> E[进入下一超级步]
查看卡片与原书出处

大数据日知录_架构与算法 · 第15章 机器学习:范型与架构

BSP超级步分三阶段

BSP把执行划成多个超级步,每步依次进行本地计算、全局通信、屏障同步,然后进入下一步。局部计算使用本地可用数据,通信交换下一步需要的信息,屏障使各处理器在该步边界对齐。这是计算与通信的组织模型,不限定必须采用某一种机器学习算法。

查看卡片与原书出处

大规模分布式系统架构与设计实战 · 分布式并行计算的原理与实践

BSP用栅栏推进阶段

BSP 把并行计算划成连续的 superstep,各进程在一阶段计算并交换消息,到栅栏处等待,所有参与者完成后才进入下一阶段。这适合需要上一轮结果的迭代过程;代价是慢进程会拖住整个阶段。发散:设计时要看阶段工作量是否均衡,而非只增加进程数。

查看卡片与原书出处

大规模分布式系统架构与设计实战 · 分布式并行计算的原理与实践

批量屏障与逐个续派的取舍

doTaskBatch 一次发给多个工人并等待全体完成,调用简洁,也形成清晰的阶段屏障;但返回受最慢工人限制,快工人做完后可能空闲。逐个 doTask 并检查结果状态,可让先完成的工人马上接新任务,代价是调度者要自行跟踪在途结果与终止条件。选择取决于阶段同步要求和工人耗时差异。参见 [[工人槽位完成后再派新任务]]。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

GAS拆开节点

Gather收集邻边与邻点信息,Apply更新中心顶点,Scatter传播变化。拆分有助于把高阶节点邻边工作分散,Apply仍需统一决定顶点状态。收集运算必须满足所用并行合并语义;任意函数不能仅因被命名sum就安全重排。

结构图:

flowchart TD
 A[邻边局部Gather] --> B[合并累积结果]
 B --> C[中心Apply更新]
 C --> D[Scatter传播变化]
 D --> E[按变化激活后续顶点]
查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

微同步将GAS组合为超级步

PowerGraph可让Gather、Apply、Scatter各阶段完成后再推进,用微屏障约束可见性;本轮激活节点在下轮调度。异步配置则允许较早利用更新。GAS接口与同步策略可分开选择,但消息、缓存和状态传播必须共同满足所选语义。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

同步异步取舍

同步模型让本轮变化在规定边界后可见;异步模型允许后续调度较早使用新值。异步可能减少无效迭代和等待,也可能受顺序、竞争及资源冲突影响。是否收敛、是否等价于某个顺序执行需单独分析,不能保证异步一定更快或得到唯一结果。

查看卡片与原书出处

大规模分布式系统架构与设计实战 · 分布式并行计算的原理与实践

MPI定义进程通信接口

MPI 是并行进程间消息通信的接口规范,发送和接收等操作让进程协作,但接口本身不替应用安排任务角色、阶段流转和资源调度。开发者可灵活组合通信,仍须自行设计这些上层机制。发散:选工具时要区分“能让进程传消息”和“已经提供完整作业编排”,避免把底层能力误当成应用框架。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

主控调度与工作节点分工

Pregel主控分配分片、推动超级步和收集进度,Worker维护顶点与边、执行活跃计算并交换消息。主控不负责每个节点的业务运算。分工说明需要保存哪些管理状态,不能仅由一张主从图就断言完整系统没有主控恢复机制。

查看卡片与原书出处

大数据日知录_架构与算法 · 第15章 机器学习:范型与架构

BSP代价取决于最慢者

设超级步j中处理器i的本地计算时间为wᵢ,发送与接收的数据字数取大值为hᵢ,每数据字通信代价g,屏障代价l,则理想模型Tⱼ=maxᵢwᵢ+g·maxᵢhᵢ+l;总时间对超级步求和。书中单步公式图漏写g,应按同节文字补齐以保持量纲一致。该模型提示负载不均和通信热点会限制性能,不替代真实测量。

查看卡片与原书出处

大数据日知录_架构与算法 · 第15章 机器学习:范型与架构

超级步边界适合检查点

相邻BSP超级步之间有明确同步边界,可把这一时刻作为保存检查点的候选,恢复时从一致的计算进度继续。检查点仍须覆盖恢复所需的状态与消息,并处理存储失败;屏障只是提供边界,不会自动实现持久化,也不保证任意用户代码没有死锁。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

迭代图计算避免重复搬运状态

链式MR每轮读写图状态、落盘中间结果并重新启动任务;很多迭代只改变少量值,这些重复成本会累积。驻留状态与专用消息通道可减少搬运,但需承担内存管理及恢复责任。MR可表达算法,表达可行与运行适合是不同判断。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

长驻Map任务承载多轮图计算

本章Giraph把完整计算放入一个长驻Map-Only任务,状态留在内存,多轮消息通过专门网络传输,避免每步启动MR及Shuffle。复用Hadoop资源框架不意味着每个超级步都执行一次传统MapReduce。外存选项又是容量与I/O取舍。

查看卡片与原书出处

大数据日知录_架构与算法 · 第14章 图数据库:架构与算法

共享边限制子图更新并行

GraphChi当前子图中,没有共同边的顶点可并行更新;存在共享边的顶点需避免同时修改同一状态。本章方案把有内部边的一组串行处理,是保守调度而非理论最大并行度。改进调度必须保留读写冲突保护,不能只增加线程。

查看卡片与原书出处

大数据时代的IT架构设计 · 社交网络大数据挖掘与社会化推荐引擎的构建

二度好友排序权衡计算成本

二度好友推荐要从大量候选中选出少数结果:若平均每人有 100 个好友,理论上有约 10000 条二跳路径;排序可参考建交时间、交互密度、资料相似度和共同好友数。全量实时计算成本高,书中建议先离线计算,再通过更快更新或增量计算缩短结果延迟。

查看卡片与原书出处

实时流计算系统设计与实现 · 第4章 数据处理

一度关联是邻居去重计数

一度关联统计某实体直接相邻的不同实体数,在实时场景通常还限定时间窗口。比如一周内同设备注册的不同用户数,本质上是按设备分组后的 COUNT DISTINCT(user_id)。小规模时可用集合精确去重;取值很多时需权衡存储与近似计数误差。

查看卡片与原书出处

实时流计算系统设计与实现 · 第4章 数据处理

二度关联需要两步扩展

二度关联先找目标节点的一度邻居,再取这些邻居各自的一度邻居并求并集,得到两跳范围内的节点集合。与只求邻居数量的一度关联不同,第二步需要知道中间邻居是谁,单靠去重计数的估计值无法继续扩展。因此高势图谱的二度计算会面临较大的中间集合状态。

查看卡片与原书出处

大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法

连通等价图统一身份

同一人的不同标识通过等价边组成连通分量,选其中最小标识作为代表,即可把历史访问映射到统一身份。批处理迭代检查各节点邻域,把邻域连接逐步重写为指向较小代表;信息传播到稳定后,各分量形成共同代表。最小只是确定性选择规则,不意味着该标识在业务上更真实。

与[[等价关系会改写历史]]的联系:等价图连通分量把多个历史标识统一为一人。

查看卡片与原书出处

大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法

双向边收齐节点邻域

无向等价关系若只存一次二元组,按第一个端点分组会漏掉节点出现在第二个位置的边。先为每条边生成两个方向,再按首端点分组,就能收齐每个节点的全部邻接信息。该转换是为后续聚合准备完整输入,不表示业务上发生了两次独立的身份关系。

与[[连通等价图统一身份]]的联系:双向化使每个节点能够收齐完整邻域用于身份传播。

查看卡片与原书出处

大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法

无新边作为迭代终点

身份归一化每轮输出下一轮的边集,并单独标出相对输入新生成的边。协调程序反复执行分布式步骤,直到新边集为空,表示在该转换规则下达到定点。判定依据是没有新进展,不能简单固定轮数;边的总数不变也不代表边的内容没有变化。

与[[连通等价图统一身份]]的联系:新增边为空定义身份图传播达到定点的可检查条件。

查看卡片与原书出处

大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法

外连接保留孤立标识

只有一个用户标识的人可能根本没有等价边,因而不在身份映射表中。访问事件连接映射表时要保留这些记录:若找到代表ID就替换,若映射缺失则沿用原ID。内连接会把这类有效访问静默丢弃,导致访客和浏览指标都偏低。

与[[连通等价图统一身份]]的联系:外连接让未进入等价图的标识仍保留原访问。

查看卡片与原书出处

大规模分布式系统架构与设计实战 · 分布式并行计算的原理与实践

链接按出度分配权重

PageRank 示例把网页当前权重平均分给它指向的页面:A 指向 B、C 时,各收到 A 权重的一半;一个页面的新权重是所有指向它的页面贡献之和。反复用新权重计算下一轮,才能观察链接结构形成的排序。赌钱例子只是这一权重流动的类比。

查看卡片与原书出处

大规模分布式系统架构与设计实战 · 分布式并行计算的原理与实践

按链接消息或按页汇总

分布式 PageRank 可让工人沿每条链接直接发送投票,再在目标节点聚合;也可由工人先统计本地贡献,交给工头统一合并。前者在链接很多时产生大量跨机消息,后者减少逐链接调用,但汇总节点要承担合并压力。选型要比较链接数量、部分结果大小与汇总容量。

查看卡片与原书出处

大规模分布式系统架构与设计实战 · 分布式并行计算的原理与实践

基线项防止零值锁死

书中的简化更新式在链接贡献之外加上 1−q:即使某页本轮没有收到链接投票,只要 q<1,它下一轮仍有正的基线权重。这缓解了示例中零值一路传播的问题。它并不等于已处理所有无出链页面;实现完整 PageRank 时仍须明确这类页面的权重去向。

查看卡片与原书出处
辅助阅读:卢曼编号

按卢曼编号阅读

点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。

  • 展开或收起下级: 1779 图数据强耦合 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级
    • 1779.b 节点中心编程 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级
    • 展开或收起下级: 1779.c BSP超级步 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级
    • 展开或收起下级: 1779.d GAS拆开节点 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级
    • 1779.e 同步异步取舍 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:高级
    • 1779.j 图编程模型与执行范型分开 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级
    • 1779.k MR用按键聚集模拟图消息 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级
    • 1779.l 迭代图计算避免重复搬运状态 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级
    • 1779.p 长驻Map任务承载多轮图计算 主题成员 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级
  • 展开或收起下级: 1780 分布式ML瓶颈 路径上下文 大数据日知录_架构与算法 · 第15章 机器学习:范型与架构 理解等级:中级
    • 展开或收起下级: 1780.a 三种同步范型 路径上下文 大数据日知录_架构与算法 · 第15章 机器学习:范型与架构 理解等级:中级
      • 展开或收起下级: 1780.a.2 BSP超级步分三阶段 主题成员 大数据日知录_架构与算法 · 第15章 机器学习:范型与架构 理解等级:中级
        • 1780.a.2.a BSP代价取决于最慢者 主题成员 大数据日知录_架构与算法 · 第15章 机器学习:范型与架构 理解等级:中级
        • 1780.a.2.b 超级步边界适合检查点 主题成员 大数据日知录_架构与算法 · 第15章 机器学习:范型与架构 理解等级:中级
  • 展开或收起下级: 1787 规范化先于聚合 路径上下文 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法 理解等级:未标注
    • 展开或收起下级: 1787.b 等价关系会改写历史 路径上下文 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法 理解等级:未标注
      • 展开或收起下级: 1787.b.1 连通等价图统一身份 主题成员 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法 理解等级:中级
        • 1787.b.1.a 双向边收齐节点邻域 主题成员 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法 理解等级:中级
        • 1787.b.1.b 无新边作为迭代终点 主题成员 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法 理解等级:中级
        • 1787.b.1.c 外连接保留孤立标识 主题成员 大数据系统构建:可扩展实时数据系统构建原理与最佳实践 · 批处理层示例:架构和算法 理解等级:中级
  • 展开或收起下级: 2280 故障不同于失效 路径上下文 数据密集型应用系统设计 · 可靠性、可伸缩性、可维护性 理解等级:未标注
    • 展开或收起下级: 2280.q 服务批处理与流处理 路径上下文 数据密集型应用系统设计 · 批处理 理解等级:未标注
      • 2280.q.14 Pregel图批处理 主题成员 数据密集型应用系统设计 · 批处理 理解等级:未标注
  • 展开或收起下级: 3096 关联图谱表示实体关系 主题成员 实时流计算系统设计与实现 · 第4章 数据处理 理解等级:初级
  • 展开或收起下级: 5434 图分片按目标切源点排序 路径上下文 大数据日知录_架构与算法 · 第14章 图数据库:架构与算法 理解等级:中级

未编号或编号待整理

来源书籍

主题索引

大数据计算范式

比较批处理、流式、交互式查询、图计算、分布式机器学习与增量计算的计算模型与取舍。

298 张卡片 · 32 本书