《大数据技术原理与应用》

《《大数据技术原理与应用》》由会员分享，可在线阅读，更多相关《《大数据技术原理与应用》（46页珍藏版）》请在金锄头文库上搜索。

1、大数据技术原理与应用 厦门大学计算机科学系 林子雨 厦门大学计算机科学系 2016年版 林子雨林子雨 厦门大学计算机科学系厦门大学计算机科学系 E-mail: 主页：主页：http:/ 第九章第九章 图计算图计算 （PPT版本号：版本号：2016年年1月月29日版本）日版本） 大数据技术原理与应用大数据技术原理与应用 http:/ 温馨提示：编辑幻灯片母版，可以修改每页PPT的厦大校徽和底部文字 大数据技术原理与应用 厦门大学计算机科学系 林子雨 提纲 9.1 图计算简介图计算简介 9.2 Pregel简介简介 9.3 Pregel图计算模型图计算模型 9.4 Pregel的的C+ AP

2、I 9.5 Pregel的体系结构的体系结构 9.6 Pregel的应用实例的应用实例 9.7 Pregel和和MapReduce实现实现PageRank算算 法的对比法的对比 欢迎访问大数据技术原理与应用教材官方网站： http:/ 本PPT是如下教材的配套讲义： 21世纪高等教育计算机规划教材 大数据技术原理与应用 概念、存储、处理、分析与应用 （2015年6月第1版） 厦门大学 林子雨 编著，人民邮电出版社 ISBN:978-7-115-39287-9 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.1 图计算简介 9.1.1 传统图计算解决方案的不足之处 9.1.2 图计算通

3、用软件 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.1.1 传统图计算解决方案的不足之处 很多传统的图计算算法都存在以下几个典型问题： （1）常常表现出比较差的内存访问局部性； （2）针对单个顶点的处理工作过少； （3）计算过程中伴随着并行度的改变。 针对大型图（比如社交网络和网络图）的计算问题，可能的解决方案及 其不足之处具体如下： 为特定的图应用定制相应的分布式实现：通用性不好 基于现有的分布式计算平台进行图计算：在性能和易用性方面往往无法 达到最优 使用单机的图算法库：在可以解决的问题的规模方面具有很大的局限性 使用已有的并行图计算系统：对大规模分布式系统非常重要的一些方面

4、 （比如容错），无法提供较好的支持 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.1.2 图计算通用软件 一次BSP计算过程包括一系列全局超步（所谓的超步就是计算中的一次迭代）， 每个超步主要包括三个组件： 局部计算局部计算：每个参与的处理器都有自身的计算任务，它们只读取存储在本地内 存中的值，不同处理器的计算任务都是异步并且独立的 通讯通讯：处理器群相互交换数据，交换的形式是，由一方发起推送(put)和获取 (get)操作 栅栏同步栅栏同步(Barrier Synchronization)：当一个处理器遇到“路障”（或栅栏）， 会等到其他所有处理器完成它们的计算步骤；每一次同步也

5、是一个超步的完成 和下一个超步的开始。图9-1是一个超步的垂直结构图 处理器处理器局部计算局部计算通讯通讯栅栏同步栅栏同步图9-1 一个超步的垂直结构图 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.2 Pregel简介 Pregel是一种基于BSP模型实现的并行图处理系统 为了解决大型图的分布式计算问题，Pregel搭建了一套可扩展的、有容 错机制的平台，该平台提供了一套非常灵活的API，可以描述各种各样的 图计算 Pregel作为分布式图计算的计算框架，主要用于图遍历、最短路径、 PageRank计算等等 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.3 Prege

6、l图计算模型 9.3.1 有向图和顶点 9.3.2 顶点之间的消息传递 9.3.3 Pregel的计算过程 9.3.4 实例 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.3.1 有向图和顶点 Pregel计算模型以有向图作为输入，有向图的每个顶点都有一个String类型 的顶点ID，每个顶点都有一个可修改的用户自定义值与之关联，每条有向 边都和其源顶点关联，并记录了其目标顶点ID，边上有一个可修改的用户 自定义值与之关联 在每个超步S中，图中的所有顶点都会并行执行相同的用户自定义函数。 每个顶点可以接收前一个超步(S-1)中发送给它的消息，修改其自身及其出 射边的状态，并发送消息

7、给其他顶点，甚至是修改整个图的拓扑结构。需 要指出的是，在这种计算模式中，边并不是核心对象，在边上面不会运行 相应的计算，只有顶点才会执行用户自定义函数进行相应计算 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.3.2 顶点之间的消息传递 ComputeCompute()() 值ComputeCompute()() 值ComputeCompute()() 值ComputeCompute()() 值消息图9-2 纯消息传递模型图 采用消息传递模型主要基于以下两个原因： （1）消息传递具有足够的表达能力，没有必要使用远程读取或共享内存的方式 （2）有助于提升系统整体性能 大数据技术原理

8、与应用 厦门大学计算机科学系 林子雨 9.3.3 Pregel的计算过程 活跃活跃非活跃非活跃不需要执行进一步 计算就设置为停机收到消息后被唤醒图9-3 一个简单的状态机图 Pregel的计算过程是由一系列被称为“超步”的迭代组成的。在每个超步中， 每个顶点上面都会并行执行用户自定义的函数，该函数描述了一个顶点V在一个 超步S中需要执行的操作。该函数可以读取前一个超步(S-1)中其他顶点发送给顶 点V的消息，执行相应计算后，修改顶点V及其出射边的状态，然后沿着顶点V的 出射边发送消息给其他顶点，而且，一个消息可能经过多条边的传递后被发送到 任意已知ID的目标顶点上去。这些消息将会在下一个超步

9、(S+1)中被目标顶点接 收，然后像上述过程一样开始下一个超步(S+1)的迭代过程 在Pregel计算过程中，一个算法什么时候可以结束，是由所有顶点的状态决定 的，当图中所有的顶点都已经标识其自身达到“非活跃（inactive）”状态时， 算法就可以停止运行 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.3.4 实例 3 36 62 21 1超步超步0 06 66 62 26 6超步超步1 16 66 66 66 6超步超步2 26 66 66 66 6超步超步3 3ABCD图9-4 一个求最大值的Pregel计算过程图 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.4

10、 Pregel的C+ API Pregel已经预先定义好一个基类Vertex类： template class Vertex public: virtual void Compute(MessageIterator* msgs) = 0; const string int64 superstep() const; const VertexValue VertexValue* MutableValue(); OutEdgeIterator GetOutEdgeIterator(); void SendMessageTo(const string void VoteToHalt(); ; 在Vet

11、ex类中，定义了三个值类型参数，分别表示顶点、边和消息。每一个顶点都 有一个给定类型的值与之对应 编写Pregel程序时，需要继承Vertex类，并且覆写Vertex类的虚函数Compute() 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.4 Pregel的C+ API 9.4.1 消息传递机制 9.4.2 Combiner 9.4.3 Aggregator 9.4.4 拓扑改变 9.4.5 输入和输出 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.4.1 消息传递机制 顶点之间的通讯是借助于消息传递机制来实现的，每条消息都包含了 消息值和需要到达的目标顶点ID。用户

12、可以通过Vertex类的模板参数 来设定消息值的数据类型 在一个超步S中，一个顶点可以发送任意数量的消息，这些消息将在 下一个超步（S+1）中被其他顶点接收 一个顶点V通过与之关联的出射边向外发送消息，并且，消息要到达 的目标顶点并不一定是与顶点V相邻的顶点，一个消息可以连续经过 多条连通的边到达某个与顶点V不相邻的顶点U，U可以从接收的消息 中获取到与其不相邻的顶点V的ID 大数据技术原理与应用 厦门大学计算机科学系 林子雨 9.4.2 Combiner Pregel计算框架在消息发出去之前，Combiner可以将发往同一个顶点 的多个整型值进行求和得到一个值，只需向外发送这个“求和结果” ，从而实现了由多个消息合并成一个消息，大大减少了传输和缓存的 开销 在默认