20210214
大数据 | 大数据基础--系统之大图计算框架
亲爱的读者朋友大家晚上好，前两篇文章讲了实时计算框架的理论知识和两个实例，这篇文章简单介绍一下大图计算框架，并以pregrel为例进行较为详细的分析。
什么是大图计算？
- 许多实际计算机问题会涉及到大型图
- MapReduce不适合图处理
- 并行处理需要多次迭代，这导致MapReduce的迭代，影响到了整体的性能
图算法的挑战
- 每个顶点的所需的计算量非常少
- 在执行过程中改变并行程度
动机
- 替代选择
- 为每个新算法创建分布式基础架构
- 分布式计算系统
- 同级间的通信开销
- 单计算机图数据库
- 扩展性差
- 其他并行图计算系统
- 没有容错机制
- 需要一个可扩展的分布式解决方案
实例--Pergel
- 可扩展和容错的平台
- API具有表达任意算法的灵活性
- 受批量同步并行模型启发
- 以顶点为中心的计算
大图计算任务的抽象
需要解决的问题
- 操作的数据形式和结构是什么？
- 应用程序可以对于数据做何种操作？
需要考虑的问题
- 适用的场景/数据是什么？
- 面向的软硬件环境是什么？
- 支撑程序程序之间的界面在哪里？
实例--Pergel
- 所有的计算任务被划分成一个一个的Superstep，superstep是并行结点计算对于每个结点
- 接受上一个superstep发出的消息
- 执行相同的用户定义函数
- 修改它的值或者其输出边的值
- 将消息送到其他点(由下一个superstep接受)
- 改变图的拓扑结构
- 没有额外工作要做时结束迭代
- 终止条件
- 所有顶点同时变为非活跃状态
- 没有信息传递
- 接受上一个superstep发出的消息
- 图并行模式
- 从相邻节点处获取信息
- 更新节点的属性
- 将信息传输给相邻节点
大图计算框架的API
需要解决的问题
- 程序员如何基于框架编写应用程序？
需要考虑的问题
- 面向什么样的程序员？
- 开发的效率？
- 程序的易读性？
- 程序的美感？
- 是否符合传统开发的习惯？
实例--Pergel
C++API，以 SSSP不动点类 为例
大图计算框架的系统架构
需要解决的问题
- 系统有哪些模块？
- 模块之间如何交互？
需要考虑的问题
- 有效配合硬件
- 扩展性高
- 效率高
- 扩展性好
- 开发容易
- 维护方便
- 升级简单
实例--Pergel
- Pregel系统也使用主/从模型
- 主节点
- 调度从节点
- 恢复从节点的错误
- 从节点
- 处理自己的任务
- 与其他从节点通信
- 主节点
- 持久化的数据位于分布式存储系统(如GFS或BigTable) 中
- 临时数据存储在本地磁盘中
大图计算框架的基本数据操作
需要解决的问题
- 包括哪些基本数据操作？
- 并行还是串行实现？
- 高效实现算法？
需要考虑的问题
- 有效支撑API
- 容易理解
- 扩展性高
- 效率高
实例--Pergel--聚合
- 从节点可以聚合它的节点报告的消息并整 合为一条消息发送
- 减少消息流量和硬盘占用
大图计算框架的流程生成
需要解决的问题
- 基本数据操作和用户自定义逻辑的步骤划分
- 基本数据操作和用户自定义逻辑的执行顺序
需要考虑的问题
- 可用性高
- 效率高
- 容易理解
- 容易支持调试工具
大图计算框架的流程调度
需要解决的问题
- 执行过程中如何执行操作？
需要考虑的问题
- 可扩展性高
- 效率高
实例--Pergel
- 程序的许多副本开始在机器集群上执行
- 主节点分割图并给每个从节点分配一个或多个部分
- 主节点还为每个从节点分配一个输入分区
- 每个从节点加载顶点并将它们标记为活动的
- 主节点指导每个从节点执行一个superstep
- 每个从节点循环其活动顶点并计算每个顶点
- 消息是异步发送的，但是在superstep结束之前送达
- 只要任何顶点处于活动状态，或者任何消息处于传输状态，就会重复此步骤
- 在计算停止后，主节点可以指示每个从节点保存各自部 分的图
大图计算框架的事务处理
需要解决的问题
- 如何保证执行的正确性
需要考虑的问题
- 结点出错怎么办？
- 分布式系统出现读脏写脏怎么办？
容错
- 检查点
- 主节点定期指示从节点将分区的状态保存到持久化存储中
- 例如：顶点数值，边数值，信息内容
- 主节点定期指示从节点将分区的状态保存到持久化存储中
- 错误检测
- 定时使用“ping”信息
- 恢复
- 主节点将图形分区重新分配给当前可用的从节点
- 所有工作人员都从最近可用的检查点重新加载分区状态
- 局部恢复
- 记录传出的信息
- 只涉及恢复分区
总结
以上就是大图计算框架的基本理论知识以及相应的知识结构，同时介绍了一个简单的例子pregrel，下次将会更进一步地介绍另一种实现graphX以及pregrel的一个高效实现pregrelix，敬请期待~