思考题

• 流式计算与批量计算的区别
• 流式计算的关键要素
• 数据分发机制
• 图的切分方式
• BSP计算模式
• 图数据计算的并行思想

流式计算

• 数据流是一系列动态数据的集合体，例如网络数据包
• 数据流的特点
  • 微观上有独立的组成单元，宏观上呈现流的特点
  • 实时性
  • 随时间不断到来，具有一定的次序
  • 流处理的核心是一个管道或线路的拓扑结构设计
• 与批量计算相比
  • 实时计算、延时较少
  • 来一个处理一个
  • 数据驱动的计算请求
  • 推式获取计算结果，批量计算是拉式获取计算结果
• 主要挑战：处理速度要与数据到来速度匹配，保障数据的顺利流动，处理逻辑的表示
• 流式计算的分发策略
  • 随机分发，发牌式分发
  • 按特定值分发
  • 广播分发（每个包会分发给所有的节点）
• 分发策略的设计原则
  • 核心目的是为了解决节点处理压力问题
  • 将单一节点的处理压力分散到多个节点上
  • 关键是如何保证流经多个节点与流经一个节点的处理逻辑不变

• 流式计算技巧

  • 增加前序节点，在处理前对数据进行某种转换，前序节点可以起到限流、过滤和变换的作用
  • 增加功能相同的节点，随机分发，各节点的逻辑相同，仅需要保证数据流的均衡分配
  • 将处理功能分散，使用特定值分发，各节点负责处理的内容不同，把满足不同条件的内容分发到相应的节点上
  • 如果多个后续节点都需要同一个数据，可以设置一个专门的数据转发节点，使用广播分发发给这些后续节点
  • 某些节点可以作为同步节点，接收到来自多个上游的数据 后触发下一个步骤

    图数据计算

• 图计算的挑战：存在高纬度的节点，无法单机处理，并行化的核心就是如何拆分图

• 切分方法
  • 边切分：从点出发，寻找边和邻接点
  • 点切分：从边出发，加入所有端点
• 图本身分割存储、计算过程分布式并行、迭代
• BSP模式，Bulk Synchronous Parallel整体同步并行，纵向上是一个串行模式，横向上是并行模式，纵向上，每一个superstep之后都设置barrier，用来同步
• 最短路径的Dijkstra算法，分布式计算的关键
  • 0：白色，未被计算的节点，即未连通的节点，距离为MAX
  • 1：灰色，计算过程中节点
  • 2：黑色，已经完成最短路径计算的节点