Chapter9-厦门大学-林子雨-大数据技术原理与应用-第九章-图计算44

《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]厦门大学计算机科学系2015年版林子雨厦门大学计算机科学系E-mail:[e-mail]主页：（PPT版本号：2015年6月第1.0版）《大数据技术原理与应用》：编辑幻灯片母版，可以修改每页PPT的厦大校徽和底部文字《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]提纲•9.1图计算简介•9.2Pregel简介•9.3Pregel图计算模型•9.4Pregel的C++API•9.5Pregel的体系结构•9.6Pregel的应用实例•9.7Pregel和MapReduce实现PageRank算法的对比欢迎访问《大数据技术原理与应用》教材官方网站：：21世纪高等教育计算机规划教材《大数据技术原理与应用——概念、存储、处理、分析与应用》（2015年6月第1版）厦门大学林子雨编著，人民邮电出版社ISBN:978-7-115-39287-9《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.1图计算简介•9.1.1传统图计算解决方案的不足之处•9.1.2图计算通用软件《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.1.1传统图计算解决方案的不足之处很多传统的图计算算法都存在以下几个典型问题：（1）常常表现出比较差的内存访问局部性；（2）针对单个顶点的处理工作过少；（3）计算过程中伴随着并行度的改变。针对大型图（比如社交网络和网络图）的计算问题，可能的解决方案及其不足之处具体如下：•为特定的图应用定制相应的分布式实现：通用性不好•基于现有的分布式计算平台进行图计算：在性能和易用性方面往往无法达到最优•使用单机的图算法库：在可以解决的问题的规模方面具有很大的局限性•使用已有的并行图计算系统：对大规模分布式系统非常重要的一些方面（比如容错），无法提供较好的支持《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.1.2图计算通用软件一次BSP计算过程包括一系列全局超步（所谓的超步就是计算中的一次迭代），每个超步主要包括三个组件：•局部计算：每个参与的处理器都有自身的计算任务，它们只读取存储在本地内存中的值，不同处理器的计算任务都是异步并且独立的•通讯：处理器群相互交换数据，交换的形式是，由一方发起推送(put)和获取(get)操作•栅栏同步(BarrierSynchronization)：当一个处理器遇到“路障”（或栅栏），会等到其他所有处理器完成它们的计算步骤；每一次同步也是一个超步的完成和下一个超步的开始。图9-1是一个超步的垂直结构图处理器局部计算通讯栅栏同步图9-1一个超步的垂直结构图《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.2Pregel简介•Pregel是一种基于BSP模型实现的并行图处理系统•为了解决大型图的分布式计算问题，Pregel搭建了一套可扩展的、有容错机制的平台，该平台提供了一套非常灵活的API，可以描述各种各样的图计算•Pregel作为分布式图计算的计算框架，主要用于图遍历、最短路径、PageRank计算等等《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.3Pregel图计算模型•9.3.1有向图和顶点•9.3.2顶点之间的消息传递•9.3.3Pregel的计算过程•9.3.4实例《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.3.1有向图和顶点•Pregel计算模型以有向图作为输入，有向图的每个顶点都有一个String类型的顶点ID，每个顶点都有一个可修改的用户自定义值与之关联，每条有向边都和其源顶点关联，并记录了其目标顶点ID，边上有一个可修改的用户自定义值与之关联•在每个超步S中，图中的所有顶点都会并行执行相同的用户自定义函数。每个顶点可以接收前一个超步(S-1)中发送给它的消息，修改其自身及其出射边的状态，并发送消息给其他顶点，甚至是修改整个图的拓扑结构。需要指出的是，在这种计算模式中，边并不是核心对象，在边上面不会运行相应的计算，只有顶点才会执行用户自定义函数进行相应计算《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.3.2顶点之间的消息传递Compute()值Compute()值Compute()值Compute()值消息图9-2纯消息传递模型图采用消息传递模型主要基于以下两个原因：（1）消息传递具有足够的表达能力，没有必要使用远程读取或共享内存的方式（2）有助于提升系统整体性能《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.3.3Pregel的计算过程活跃非活跃不需要执行进一步计算就设置为停机收到消息后被唤醒图9-3一个简单的状态机图•Pregel的计算过程是由一系列被称为“超步”的迭代组成的。在每个超步中，每个顶点上面都会并行执行用户自定义的函数，该函数描述了一个顶点V在一个超步S中需要执行的操作。该函数可以读取前一个超步(S-1)中其他顶点发送给顶点V的消息，执行相应计算后，修改顶点V及其出射边的状态，然后沿着顶点V的出射边发送消息给其他顶点，而且，一个消息可能经过多条边的传递后被发送到任意已知ID的目标顶点上去。这些消息将会在下一个超步(S+1)中被目标顶点接收，然后像上述过程一样开始下一个超步(S+1)的迭代过程•在Pregel计算过程中，一个算法什么时候可以结束，是由所有顶点的状态决定的，当图中所有的顶点都已经标识其自身达到“非活跃（inactive）”状态时，算法就可以停止运行《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.3.4实例3621超步06626超步16666超步26666超步3ABCD图9-4一个求最大值的Pregel计算过程图《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.4Pregel的C++APIPregel已经预先定义好一个基类——Vertex类：templatetypenameVertexValue,typenameEdgeValue,typenameMessageValueclassVertex{public:virtualvoidCompute(MessageIterator*msgs)=0;conststring&vertex_id()const;int64superstep()const;constVertexValue&GetValue();VertexValue*MutableValue();OutEdgeIteratorGetOutEdgeIterator();voidSendMessageTo(conststring&dest_vertex,constMessageValue&message);voidVoteToHalt();};•在Vetex类中，定义了三个值类型参数，分别表示顶点、边和消息。每一个顶点都有一个给定类型的值与之对应•编写Pregel程序时，需要继承Vertex类，并且覆写Vertex类的虚函数Compute()《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.4Pregel的C++API•9.4.1消息传递机制•9.4.2Combiner•9.4.3Aggregator•9.4.4拓扑改变•9.4.5输入和输出《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.4.1消息传递机制•顶点之间的通讯是借助于消息传递机制来实现的，每条消息都包含了消息值和需要到达的目标顶点ID。用户可以通过Vertex类的模板参数来设定消息值的数据类型•在一个超步S中，一个顶点可以发送任意数量的消息，这些消息将在下一个超步（S+1）中被其他顶点接收•一个顶点V通过与之关联的出射边向外发送消息，并且，消息要到达的目标顶点并不一定是与顶点V相邻的顶点，一个消息可以连续经过多条连通的边到达某个与顶点V不相邻的顶点U，U可以从接收的消息中获取到与其不相邻的顶点V的ID《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.4.2Combiner•Pregel计算框架在消息发出去之前，Combiner可以将发往同一个顶点的多个整型值进行求和得到一个值，只需向外发送这个“求和结果”，从而实现了由多个消息合并成一个消息，大大减少了传输和缓存的开销•在默认情况下，Pregel计算框架并不会开启Combiner功能，因为，通常很难找到一种对所有顶点的Compute()函数都合适的Combiner•当用户打算开启Combiner功能时，可以继承Combiner类并覆写虚函数Combine()•此外，通常只对那些满足交换律和结合律的操作才可以去开启Combiner功能，因为，Pregel计算框架无法保证哪些消息会被合并，也无法保证消息传递给Combine()的顺序和合并操作执行的顺序ACBD目标顶点值消息格式B2B3MaxCombinerB3A把值3发送给BC把值2发送给B经过MaxCombiner合并后只把值3通过网络发送给B机器M机器N图9-5Combiner应用的例子《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.4.3Aggregator•Aggregator提供了一种全局通信、监控和数据查看的机制•在一个超步S中，每一个顶点都可以向一个Aggregator提供一个数据，Pregel计算框架会对这些值进行聚合操作产生一个值，在下一个超步（S+1）中，图中的所有顶点都可以看见这个值•Aggregator的聚合功能，允许在整型和字符串类型上执行最大值、最小值、求和操作•Pregel计算框架预定义了一个Aggregator类，编写程序时需要继承这个类，并定义在第一次接收到输入值后如何初始化，以及如何将接收到的多个值最后聚合成一个值•为了保证得到正确的结果，Aggregator操作也应该满足交换律和结合律《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.4.4拓扑改变•Pregel计算框架允许用户在自定义函数Compute()中定义操作，修改图的拓扑结构，比如在图中增加（或删除）边或顶点•Pregel采用两种机制来解决这类冲突：局部有序和Handler•（1）局部有序：拓扑改变的请求是通过消息发送的，在执行一个超步时，所有的拓扑改变会在调用Compute()函数之前完成•（2）Handler：对于“局部无序”机制无法解决的那些操作冲突，就需要借助于用户自定义的Handler来解决，包括解决由于多个顶点删除请求或多个边增加请求（或删除请求）而造成的冲突《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.4.5输入和输出•在Pregel计算框架中，图的保存格式多种多样，包括文本文件、关系数据库或键值数据库等•在Pregel中，“从输入文件生成得到图结构”和“执行图计算”这两个过程是分离的，从而不会限制输入文件的格式•对于输出，Pregel也采用了灵活的方式，可以以多种方式进行输出《大数据技术原理与应用》厦门大学计算机科学系林子雨[e-mail]9.5Pregel的体系结构•9.5.1Pregel的执行过程•9.5.