分布式图处理系统.pdf

数据库系统概论新技术篇 分布式图处理系统分布式图处理系统 An Introduction to Database System 提纲提纲 分布式图处理系统的必要性分布式图处理系统的必要性 谷歌的分布式图处理系统谷歌的分布式图处理系统Pregel 分布式图算法的实现举例分布式图算法的实现举例 An Introduction to Database System 提纲提纲 分布式图处理系统的必要性分布式图处理系统的必要性 谷歌的分布式图处理系统谷歌的分布式图处理系统Pregel 分布式图算法的实现举例分布式图算法的实现举例 An Introduction to Database System 分布式图处理系统的必要性分布式图处理系统的必要性 图的数据规模庞大图的数据规模庞大 An Introduction to Database System 分布式图处理系统的必要性分布式图处理系统的必要性 图的数据规模庞大图的数据规模庞大 社交网络社交网络 Facebook用户：用户：22亿用户，千亿规模的联系亿用户，千亿规模的联系 新浪微博：新浪微博：4亿多个用户，百亿规模的联系亿多个用户，百亿规模的联系 微信和微信和WeChat合并每后个月活跃用户数达合并每后个月活跃用户数达8.89亿亿 互联网互联网 截至截至2016年年12月，中国网页数量为月，中国网页数量为2360亿个亿个 An Introduction to Database System 集中式下图数据库的问题集中式下图数据库的问题 存不了：单机的存储能力有限存不了：单机的存储能力有限 算不出：即使是相对较为简单的最短路径发现操作算不出：即使是相对较为简单的最短路径发现操作 ，其计算时间复杂度是，其计算时间复杂度是O(n2)或或O(m + nlogn)，其，其 中中n是图中顶点的个数，是图中顶点的个数，m是边的数目是边的数目,图数据规模增图数据规模增 长导致算法代价迅速增加。更糟糕的是，很多图算长导致算法代价迅速增加。更糟糕的是，很多图算 法的计算时间复杂度与顶点或边的个数呈超线性关法的计算时间复杂度与顶点或边的个数呈超线性关 系系 An Introduction to Database System 分布式图处理系统的提出分布式图处理系统的提出 新的硬件和计算环境提供了可能性新的硬件和计算环境提供了可能性 CPU、GPU、大内存技术的发展、大内存技术的发展 云计算、大数据技术的出现云计算、大数据技术的出现 An Introduction to Database System 分布式图处理系统的兴起分布式图处理系统的兴起 2004 MapReduce 2010 Pregel 2010现在 Giraph、Trinity、GPS 、GraphX、Mizan、 Pregel+、GraphLab、 PowerGraph 采用整体同步同步并行计算（BSP）模型 ，以图顶点为中心的分布式计算框 架。优点：优点： 1. 消除了数据的重复加载 2. 构建以图顶点为计算中心、以消 息为驱动的编程模型，易于实现各 类图算法 主要问题：主要问题： 1. 数据重复载入 2. 木桶效应 迭代的图算法&一次迭代 一个MapReduce Job 主要问题：主要问题：木桶效应&过多 迭代次数和通信量 出发点：出发点：消除木桶效应 、减少迭代次数、减少 通信量、快速故障恢复 解决方案：解决方案：合理图数据 划分、动态数据迁移机 制、扩展以图顶点为计 算中心的编程模型、异 步迭代计算 An Introduction to Database System 提纲提纲 分布式图处理系统的必要性分布式图处理系统的必要性 谷歌的分布式图处理系统谷歌的分布式图处理系统Pregel 分布式图算法的实现举例分布式图算法的实现举例 An Introduction to Database System Pregel计算模型计算模型 Pregel是基于BSP（Bulk Synchronous Parallel，整体同步并行计算）模型实 现的分布式图处理系统 BSP模型的主要思想：一次BSP计算过程包含一个全局超步（Superstep）， 每一超步主要包括三个步骤：局部计算、通信、和屏障同步。 Barrier Synchronization Local Computation Processor1 Processor2 Processor3 Processor4 Processor5 Processor6 Communication An Introduction to Database System 局部计算（局部计算（Local computation） 1 5 2 4 3 Processor1 顶点值、上一个迭代收到的消息 输入 1 2 3 4 5 Processor1 执行Compute()函数 更新顶点值、发送其他顶点消息 An Introduction to Database System 顶点的状态顶点的状态 活跃与非活跃活跃与非活跃 Active Inactive Vote to halt Message received An Introduction to Database System 局部计算（局部计算（Local computation） 1 5 2 4 3 Processor1 1 2 3 4 5 顶点值、上一个迭代收到的消息 输入 Processor1 执行Compute()函数 更新顶点值、发送其他顶点消息 An Introduction to Database System 局部计算（局部计算（Local computation） 1 5 2 4 3 Processor1 1 2 3 4 5 顶点值、上一个迭代收到的消息 输入 Processor1 执行Compute()函数 更新顶点值、发送其他顶点消息 An Introduction to Database System 局部计算（局部计算（Local computation） 1 5 2 4 3 Processor1 1 2 3 4 5 顶点值、上一个迭代收到的消息 输入 Processor1 执行Compute()函数 更新顶点值、发送其他顶点消息 An Introduction to Database System 通信（Communication） Processor2 Processor1 Processor3 Processor4 Processor5 计算节点之间的消息通信 An Introduction to Database System 屏障同步屏障同步(Barrier Synchronization) Processor2 Processor1 Processor3 Processor4 Processor5 每个计算节点发送给其他的节点消息，都确保被对方收到 Barrier Synchronization An Introduction to Database System 在在BSP计算过程中超步迭代执行，直到图中所有顶计算过程中超步迭代执行，直到图中所有顶 点都被标识为“非活跃（点都被标识为“非活跃（inactive）”状态且没有消）”状态且没有消 息在传递。息在传递。 Active Inactive Vote to halt Message received An Introduction to Database System Pregel系统结构系统结构 Pregel采用主从式结构（采用主从式结构（Master/Worker） Master 任务分配任务分配 协调从节点（协调从节点（Worker）的计算和同步）的计算和同步 从节点的故障恢复从节点的故障恢复 Worker 任务计算任务计算 节点节点间通信间通信 数据存储在分布式文件系统中（例如数据存储在分布式文件系统中（例如HDFS） 临时数据存放在每个从节点的本地磁盘临时数据存放在每个从节点的本地磁盘 An Introduction to Database System Pregel系统结构（续）系统结构（续） Master进行图划分，每个进行图划分，每个 worker读取相应分片读取相应分片 Master协调协调worker的计算的计算 每个每个worker遍历其分片中包含的遍历其分片中包含的 顶点，执行顶点，执行compute函数函数 各各work之间消息通信；当前之间消息通信；当前 superstep的同步的同步 重复执行以上重复执行以上superstep，直到，直到 图中所有顶点都被标识为“非活图中所有顶点都被标识为“非活 跃（跃（inactive）”状态且没有消）”状态且没有消 息在传递息在传递 An Introduction to Database System Pregel系统结构（续）系统结构（续） Master 分布式文件系统（如HDFS） Worker inQoutQ Worker inQoutQ Worker inQoutQ 图数据载入 与写出，检 查点写出等 两个计算节点 间消息传递 全局同步等 Zookeeper An Introduction to Database System 提纲提纲 分布式图处理系统的必要性分布式图处理系统的必要性 谷歌的分布式图处理系统谷歌的分布式图处理系统Pregel 分布式图算法的实现举例分布式图算法的实现举例 An Introduction to Database System 在连通图中求最大值在连通图中求最大值 1 5 2 4 3 Superstep 0 1 2 3 4 5 5 4 5 1 2 4 5 3 5 5 4 5 1 5 2 4 3 5 5 5 5 4 Superstep 1 5 An Introduction to Database System 在连通图中求最大值在连通图中求最大值 1 5 2 4 3 5 5 4 4 5 5 5 5 4 5 Superstep 1 1 5 2 4 3 5 5 5 5 5 5 Superstep 2 1 5 2 4 3 5 5 5 5 5 Superstep 3 An Introduction to Database System Pregel的其他特性的其他特性 Combiners :发送消息，尤其是当目标顶点在另外一台机器时发送消息，尤其是当目标顶点在另外一台机器时 ，会产生一些通信开销。某些情况可以在用户的协助下降低这，会产生一些通信开销。某些情况可以在用户的协助下降低这 种开销。比方说，假如种开销。比方说，假如Compute() 收到许多的收到许多的int 值消息，而值消息，而 它仅仅关心的是这些值的和，而不是每一个它仅仅关心的是这些值的和，而不是每一个int的值，这种情况的值，这种情况 下，系统可以将发往同一个顶点的多个消息合并成一个消息，下，系统可以将发往同一个顶点的多个消息合并成一个消息， 该消息中仅包含它们的和值，这样就可以减少传输和缓存的开该消息中仅包含它们的和值，这样就可以减少传输和缓存的开 销销 Aggregators： 是一种提供全局通信，监控和数据查看的机制是一种提供全局通信，监控和数据查看的机制 。在一个超级步。在一个超级步S中，每一个顶点都可以向一个中，每一个顶点都可以向一个aggregator提提 供一个数据，系统会使用一种供一个数据，系统会使用一种reduce操作来负责聚合这些值，操作来负责聚合这些值， 而产生的值将会对所有的顶点在超级步而产生的值将会对所有的顶点在超级步S+1中可见。中可见。