PDF《主讲教师：林子雨 http://www.cs.xmu.edu.cn/》

厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.

cs.xmu.edu.cn/linziyu

1 /

33 获取教材和讲义 PPT 等各种课程资料请访问 http://dblab.xmu.edu.cn/node/422 =课程教材由林子雨老师根据网络资料编著= 厦门大学计算机科学系教师 林子雨 编著 http://www.cs.xmu.edu.cn/linziyu

2013 年9月厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.cs.xmu.edu.cn/linziyu

2 /

33 前言 本教程由厦门大学计算机科学系教师林子雨编著, 可以作为计算机专业研究生课程 《大 数据技术基础》的辅助教材. 本教程的主要内容包括:大数据概述、大数据处理模型、大数据关键技术、大数据时代 面临的新挑战、NoSQL 数据库、云数据库、Google Spanner、Hadoop、HDFS、HBase、 MapReduce、Zookeeper、流计算、图计算和 Google Dremel 等. 本教程是林子雨通过大量阅读、收集、整理各种资料后精心制作的学习材料,与广大数 据库爱好者共享.教程中的内容大部分来自网络资料和书籍,一部分是自己撰写.对于自写 内容,林子雨老师拥有著作权. 本教程 PDF 文档及其全套教学 PPT 可以通过网络免费下载和使用(下载地址: http://dblab.xmu.edu.cn/node/422) . 教程中可能存在一些问题, 欢迎读者提出宝贵意见和建议! 本教程已经应用于厦门大学计算机科学系研究生课程《大数据技术基础》 ,欢迎访问

2013 班级网站 http://dblab.xmu.edu.cn/node/423. 林子雨的 E-mail 是:ziyulin@xmu.edu.cn. 林子雨的个人主页是:http://www.cs.xmu.edu.cn/linziyu. 林子雨于厦门大学海韵园

2013 年9月厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.cs.xmu.edu.cn/linziyu

3 /

33 第9章图计算 厦门大学计算机科学系教师 林子雨 编著 个人主页:http://www.cs.xmu.edu.cn/linziyu 课程

网址:http://dblab.xmu.edu.cn/node/422

2013 年9月厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.cs.xmu.edu.cn/linziyu

4 /

33 第9章图计算 随着大数据时代的到来,图的规模越来越大,有的甚至有数十亿的顶点和数千亿的边, 这就给高速地处理图数据带来了挑战. 一台机器已经不能存放所有需要计算的数据了, 所以 需要一个分布式的计算环境. 而已有的图计算框架和图算法库不能很好地满足计算需求, 因此,新的图计算框架应运而生. 本章内容首先简单介绍了图计算,然后详细介绍了当前热门的 Google 图计算框架 Pregel,包括 Pregel 图计算模型、Pregel 中的 C++ API、Pregel 的执行过程和 Pregel 的算法 实现,内容要点如下: ? 图计算简介 ? Google Pregel 简介 ? Google Pregel 图计算模型 ? Pregel 的C++ API ? Pregel 模型的基本体系结构 ? Pregel 模型的应用实例 ? 改进的图计算模型 9.1 图计算简介 在实际应用中,存在许多图计算问题,比如最短路径、集群、网页排名、最小切割、连 通分支等等.图计算算法的性能,直接关系到应用问题解决的高效性,尤其对于大型图(比 如社交网络和网络图) 而言, 更是如此. 下面我们首先指出传统图计算解决方案的不足之处, 然后介绍两大类通用图计算软件. 9.1.1 传统图计算解决方案的不足之处 在很长一段时间内, 都缺少一个可扩展的通用系统来解决大型图的计算问题. 很多传统 的图计算算法都存在以下几个典型问题: (1)常常表现出比较差的内存访问局部性;

(2)针 厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.cs.xmu.edu.cn/linziyu

5 /

33 对单个顶点的处理工作过少;

(3)计算过程中伴随着并行度的改变. 针对大型图(比如社交网络和网络图)的计算问题,可能的解决方案及其不足之处具体 如下: ? 为特定的图应用定制相应的分布式实现. 不足之处是, 在面对新的图算法或者

图表 示方式时,就需要做大量的重复实现,不通用. ? 基于现有的分布式计算平台进行图计算.但是,在这种情况下,它们往往并不适于 做图处理.比如,MapReduce 就是一个对许多大规模计算问题都非常合适的计算 框架.有时,它也被用来对大规模图对象进行挖掘,但是,通常在性能和易用性上 都不是最优的. 尽管这种对数据处理的基本模式经过扩展, 已经可以使用方便的聚 合以及类似于 SQL 的查询方式,但是,这些扩展对于图算法这种更适合用消息传 递模型的问题来说,通常并不理想. ? 使用单机的图算法库.比如 BGL、LEAD、NetworkX、JDSL、Standford GraphBase 和FGL 等等;

但是,这种方式对可以解决的问题的规模提出了很大的限制. ? 使用已有的并行图计算系统.Parallel BGL 和CGMgraph 这些库实现了很多并行图 算法,但是,并没有解决对大规模分布式系统中来说非常重要的容错等一些问题. 9.1.2 图计算通用软件 正是因为传统的图计算解决方案无法解决大型图的计算问题, 因此, 就需要设计能够用 来解决这些问题的通用图计算软件. 针对大型图的计算, 目前通用的图处理软件主要包括两 种:第一种主要是基于遍历算法和实时的图数据库,如Neo4j 、OrientDB、DEX 和InfiniteGraph.第二种则是以图顶点为中心的消息传递批处理的并行引擎,如Hama、Golden Orb、Giraph 和Pregel. 第一种图处理软件,基本都基于 Tinkerpop 的图基础框架,Tinkerpop 项目关系如图 9-1 所示. 厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.cs.xmu.edu.cn/linziyu

6 /

33 图9-1 Tinkerpop 项目关系图 下面具体介绍一下 TinkerPop 框架的各层功能: ? Blueprints:是一组针对属性图数据模型的接口、实现、测试套件,它和 JDBC 类似, 但是,它是基于图数据库的.就其本身而言,它提供了一组通用的接口,允许开发 者对其图数据库后台即插即用.另外,在Blueprints 上编写的软件可以运行于所有 的Blueprints 开启的图数据库.在Tinkerpop 的图基础框架中,Blueprints 为其他几 层提供基础技术服务. ? Pipes:是一个应用流程图的数据流框架.一个流程图由很多通过 通信边 相连 的pipe 顶点组成.一个 pipe 实现了一个简单的计算步骤,它可以和其他的 pipe 相 组合,一起产生一个更大的计算.这样的数据流图允许拆分、合并、循环和输入输 出数据的相互转换.伴随着主 Pipe 的分布,会产生大量的 Pipe 类.只要了解了每 个Pipe 的实现,就可以直接使用 Pipe 框架. ? Gremlin:是一种图遍历语言,可以用于图的查询、分析和处理.它工作在那些执 行Blueprints 性能图数据模型的图数据库和框架上.Gremlin 是能用于各种 JVM 语 言的一种图遍历.Gremlin 的布局为 Java 和Groovy 提供了支持. ? Frames:把Blueprints 图映射为一组相互关联的域对象集.Frames 中经常使用 InvocationHandler、Porxy 类和 Annotations,使开发者可以用一个特殊的 Java 接口 来构造一个图元素 (顶点或边) . 通过 Frames, 非常容易确认图中数据各自的图解, 对应哪一个带有注释的 Java 接口. ? Furnace:是能启用 Blueprints 图的一个算法包.在图理论和分析的历史进程中开发 厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.cs.xmu.edu.cn/linziyu

7 /

33 了很多的图算法.这些算法中的大多数是为无标号的、单一关系的图而设计的. Furnace 的目的就是在单一关系图算法中揭示属性图 (像属性化图或多关系图) . 另外,Furnace 提供了针对不同图计算场景,各种图算法的优化实现,像单机图和分 布图. ? Rexster:是一个图服务器,通过 REST 和一个被称为 RexPro 的二进制协议展现任意 的Blueprints 图.HTTP 网页服务器提供了标准的低层 GET、POST、PUT 和DELETE 方法,一个灵活的、像开发一个外部服务器(如通过 Gremlin 的特殊图查询)一样 允许插件法的扩展模型, 用Gremlin 编写的服务器端存储程序和一个基于浏览器的 接口――Dog House.Rexster Console 使对 Rexster 服务器中的配置图的远程脚本评 估成为可能.Rexster Kibbles 是由 TinkerPop 提供的各种 Rexster 服务器的扩展集. 第二种图处理软件,则主要是基于 BSP 模型所实现的并行图处理包.BSP 是由哈佛大 学Viliant 和牛津大学 Bill McColl 提出的并行计算模型,全称为 整体同步并行计算模 型 (Bulk Synchronous Parallel Computing Model,简称 BSP 模型),又名 大同步模型 .创始人 希望 BSP 模型像冯・ 诺伊曼体系结构那样,架起计算机程序语言和体系结构间的桥梁,故又 称作 桥模型 (Bridge Model).一个 BSP 模型由大量相互关联的处理器所组成,它们之间形 成了一个通信网络.每个处理器都有快速的本地内存和不同的计算线程.一次 BSP 计算过 程包括一系列全局超步,所谓的超步就是计算中的一次迭代.每个超步主要包括三个组件: ? 并发计算: 每个参与的处理器都有自身的计算任务, 它们只读取存储在本地内存的 值,这些计算都是异步并且独立的;

? 通讯:处理器群相互交换数据,交换的形式是,由一方发起推送(put)和获取(get) 操作;

? 栅栏同步(Barrier synchronisation): 当一个处理器遇到 路障 ,会等到其他所有处 理器完成它们的计算步骤;

每一次同步也是一个超步的完成和下一个超步的开始;

图9-2 是一个超步的垂直结构图. 厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.cs.xmu.edu.cn/linziyu

8 /

33 图9-2 一个超步的垂直结构图 9.2 Google Pregel 简介 Pregel就是一种基于BSP模型所实现的并行图处理包.为了解决大型图的分布式计算问 题,Pregel搭建了一套可扩展的、有容错机制的平台,该平台提供了一套非常灵活的API, 可以描述各种各样的图计算.Pregel是一个用于分布式图计算的计算框架,主要用于图遍历 (BFS) 、最短路径(SSSP) 、PageRank计算等等.共享内存的运行库有很多,但是,对于 Google来说,一台机器早已经放不下需要计算的数据了,所以,需要分布式这样一个计算环 境. 没有Pregel之前,你可以选择用MapReduce来做,但是效率很低.图算法如果用 MapReduce实现,需要一系列的MapReduce的调用.从一个阶段到下一个阶段,它需要传递 整个图的状态,会产生大量不必要的序列化和反序列化开销.而Pregel使用超步简化了这个 过程.下面我们以一个实例来阐述采用Pregel和MapReduce来执行图计算的区别. 实例:PageRank算法在Pregel和MapReduce中的实现. PageRank 算法作为 Google 的网页链接排名算法,具体公式如下: 对于任意一个链接,其PR值为链入到该链接的源链接的PR值对该链接的贡献和(分母 厦门大学计算机科学系研究生课程 《大数据技术基础》 主讲教师:林子雨 http://www.cs.xmu.edu.cn/linziyu

9 /

33 Ni为第i个源链接的链出度) . Pregel是Google提出的专门为图计算所设计的计算模型,主要来源于BSP并行计算模型 的启发.要用Pregel计算模型实现PageRank算法,也就是将网页排名算法映射到图计算中, 这其实是很自然的,因为,网络链接是一个连通图. 图9-3 一个连通图 图9-3就是四个网页(A,B,C,D)互相链入链出组成的........