Spark2.1.0入门:图计算简介

大数据技术原理与应用

【版权声明】博客内容由厦门大学数据库实验室拥有版权,未经允许,请勿转载!
[返回Spark教程首页]

在实际应用中,存在许多图计算问题,如最短路径、集群、网页排名、最小切割、连通分支等。图计算算法的性能直接关系到应用问题解决的高效性,尤其对于大型图(如社交网络和网络图)而言,更是如此。

图是由很多个节点(vertex)构成的,节点之间通过边(edge)进行连接。图在网络科学中被称为网络。实际应用中,有很多图结构数据:
* 计算机网络:由许多节点(计算机或者路由器)以及节点之间的边(网线)构成的网络;
* 城市的道路系统:由节点(路口)和边(道路)构成的图;
* 微信的社交网络:由节点(个人或公众号)和边(关注或点赞)构成的图;
* 淘宝的交易网络:由节点(个人或商品)和边(购买或收藏)构成的图;
* 网页的链接网络,由节点(网页)和边(链接)构成的图。

图处理技术

图处理技术包括图数据库、图数据查询、图数据分析和图数据可视化。

图数据库:Neo4j、Titan、OrientDB、DEX和InfiniteGraph等基于遍历算法的、实时的图数据库;
图数据查询:对图数据库中的内容进行查询;
图数据分析:Google Pregel、Spark GraphX、GraphLab等图计算软件。传统的数据分析方法侧重于事物本身,即实体,例如银行交易、资产注册等等。而图数据不仅关注事物,还关注事物之间的联系。例如,如果在通话记录中发现张三曾打电话给李四,就可以将张三和李四关联起来,这种关联关系提供了与两者相关的有价值的信息,这样的信息是不可能仅从两者单纯的个体数据中获取的。
图数据可视化:OLTP风格的图数据库或者OLAP风格的图数据分析系统(或称为图计算软件),都可以应用图数据库可视化技术。需要注意的是,图可视化与关系数据可视化之间有很大的差异,关系数据可视化的目标是对数据取得直观的了解,而图数据可视化的目标在于对数据或算法进行调试。

通常,在进行大规模图数据分析时,都会组合使用图数据库(比如Neo4j)和图计算软件(比如Spark Gtaph X)。如果只是简单地存储实体之间的关系,那么,只要使用图数据库即可,不需要使用图计算软件。业界的一个发展趋势是,会出现可以同时处理OLAP和OLTP类型应用的图系统,也就是说,在图数据库与图计算框架之间的紧密集成,或者通过Neo4j这样的图数据库与Spark GraphX这样的图处理系统间的无缝互操作来实现,或者在将来某一天这些功能会出现在同一产品中。

图计算软件

目前典型的图计算软件(比如Google Pregel),都是基于BSP模型实现的分布式并行图处理系统。BSP是由哈佛大学Viliant和牛津大学Bill Mc Coll提出的并行计算模型,全称为“整体同步并行计算模型”(Bulk Synchronous Parallel Computing Model,BSP模型),又名“大同步模型”。创始人希望BSP模型像冯•诺依曼体系结构那样,架起计算机程序语言和体系结构间的桥梁,故又称为“桥模型”。一个BSP模型由大量通过网络相互连接的处理器组成,每个处理器都有快速的本地内存和不同的计算线程,一次BSP计算过程包括一系列全局超步(超步就是指计算中的一次迭代),每个超步主要包括3个组件。
• 局部计算。每个参与的处理器都有自身的计算任务,它们只读取存储在本地内存中的值,不同处理器的计算任务都是异步并且独立的。
• 通信。处理器群相互交换数据,交换的形式是,由一方发起推送(put)和获取(get)操作。
• 栅栏同步(Barrier Synchronization)。当一个处理器遇到“路障”(或栅栏),会等其他所有处理器完成它们的计算步骤;每一次同步也是一个超步的完成和下一个超步的开始。图1是一个超步的垂直结构图。

谷歌公司在2003年到2004年公布了关于GFS、MapReduce和BigTable的3篇技术论文,成为后来云计算和Hadoop项目的重要基石。如今,谷歌在后Hadoop时代的新“三驾马车”——Caffeine、Dremel和Pregel,再一次影响着全球大数据技术的发展潮流。Caffeine主要为谷歌网络搜索引擎提供支持,使谷歌能够更迅速地添加新的链接(包括新闻报道以及博客文章等)到自身大规模的网站索引系统中。Dremel是一种可扩展的、交互式的实时查询系统,用于只读嵌套数据的分析。通过结合多级树状执行过程和列式数据结构,它能做到几秒内完成对万亿张表的聚合查询。系统可以扩展到成千上万的CPU上,满足谷歌上万用户操作PB级的数据,并且可以在2秒~3秒钟完成PB级别数据的查询。Pregel是一种基于BSP模型实现的并行图处理系统。为了解决大型图的分布式计算问题,Pregel搭建了一套可扩展的、有容错机制的平台,该平台提供了一套非常灵活的API,可以描述各种各样的图计算。Pregel作为分布式图计算的计算框架,主要用于图遍历、最短路径、PageRank计算等。

子雨大数据之Spark入门
扫一扫访问本博客