下面我们看一下图计算的简单示例:

Spark入门(1-5)Spark统一了TableView和GraphView-LMLPHP

从图我们可以看出, 拿到Wikipedia的文档后,我们可以:

1、Wikipedia的文档 -- > table视图 -- >分析Hyperlinks超链接 -- > PageRank分析,

2、Wikipedia的文档 -- > table视图 -- >分析Term-Doc Graph  -- > LDA  -- > WordTopics

3、Wikipedia的文档 -- >Editor Graph  -- > Community , 这个过程可以称之为Triangle Computation,这是计算三角形的一个算法,基于此,会发现一个社区,

从上面的分析中我们可以发现图计算有很多的做法和算法,同时也发现图和表格可以做互相的转换,不过并非所有的图计算框架都支持图与表格的互相转换。

Spark GraphX的优势在于能够把表格和图进行互相转换,这一点可以带来非常多的优势,

现在很多框架也在渐渐的往这方面发展,例如GraphLib已经实现了可以读取Graph中的Data,也可以读取Table中的Data,也可以读取Text总的data即文本中的内容等,

与此同时Spark GraphX基于Spark也为GraphX增添了额外的很多优势,例如和mllib、Spark SQL协作等。

当今图计算领域对图的计算大多数只考虑邻居节点的计算,也就是说一个节点计算的时候只会考虑其邻居节点,对于非邻居节点是不关心的,如下图所示:

Spark入门(1-5)Spark统一了TableView和GraphView-LMLPHP

目前基于图的并行计算框架已经有很多,比如来自Google的Pregel、来自Apache开源的图计算框架Giraph,以及我们最为著名的GraphLab,当然也包含HAMA,其中Pregel、HAMA、Giraph都是非常类似的,都是基于BSP模型,

BSP模型实现了SuperStep即超步,BSP首先进行本地计算,然后进行全局的通信,然后进行全局的Barrier;

BSP最大的好处是编程简单,而其问题在于一些情况下BSP运算的性能非常差,

因为我们有一个全局Barrier的存在,所以系统速度取决于最慢的计算,也就把木桶原理体现无遗,

另外一方面,很多现实生活中的网络是符合幂律分布的,也就是定点、边等分布式很不均匀,所以在这种情况下BSP的木桶原理导致了性能问题会得到很大的放大,

对这个问题的解决,以GraphLab为例,使用了一种异步的概念而没有全部的Barrier;

最后,不得不提的一点是在Spark Graphx中可以用极为简洁的代码非常方便的使用Pregel的API。

基于图的计算框架的共同特点是抽象出了一批API来简化基于图的编程,这往往比一般的data-parellel系统的性能高出很多倍。

传统的图计算,往往需要不同的系统支持不同的View,

例如在Table View这种视图下可能需要Spark的支持或者Hadoop的支持,

而在Graph View这种视图下可能需要Pregel或者GraphLab的支持,

也就是把图和表分别在不同的系统中进行拉练处理,如下图所示:

Spark入门(1-5)Spark统一了TableView和GraphView-LMLPHP

上面所描述的图计算处理方式是传统的计算方式,当然现在除了Spark GraphX之外的图计算框架也在考虑这个问题;

不同系统带来的问题是之一是需要学习、部署和管理不同的系统,

例如要同时学习、部署和管理Hadoop、Hive、Spark、Giraph、GraphLab等:

Spark入门(1-5)Spark统一了TableView和GraphView-LMLPHP

大家都知道“Detail is evil”,如果我们能够用更少的框架解决更多的问题那是更好的。

其实最关键的问题还是效率问题,因为在不同的转换中间每步都要落地的话,数据转换和复制带来的开销也非常大,包括序列化带来的开销,同时中间结果和相应的结构无法重用,特别是一些结构性的东西,

譬如说顶点或者边的结构一直没有变,这种情况下结构内部的Structure是不需要改变的,而如果每次都重新构建的话,就算不变也无法重用,这回导致非常差的性能:

Spark入门(1-5)Spark统一了TableView和GraphView-LMLPHP

解决方案就是Spark GraphX,GarphX实现了Unified Representation,GraphX统一了Table View和Graph View,基于Spark可以非常轻松的做pipeline的操作:

Spark入门(1-5)Spark统一了TableView和GraphView-LMLPHP

如果和Spark SQL结合,我们可以用SQL语句来进行ETL,然后放入GraphX来处理,是非常方便的。

在Spark GraphX中的Graph其实是Property Graph,也就是说图的每个顶点和边都是有属性的,如下图所示:

Spark入门(1-5)Spark统一了TableView和GraphView-LMLPHP

例如为3的顶点的名称为rxin,是学生stu.,5这个顶点是franlin,是一个prof.,5到3表明5是3的Advisor,上图中蓝色的表示的是相应顶点的Property,而黄色橙黄色部分表示的边的Property,边和顶点都是有ID的,对于顶点而言有自身的ID,而对于边来说有SourceID和DestinationID,即对于边而言会有两个ID来表达从哪个顶点出发到哪个顶点结束,来表明边的方向,这就是Property Graph的表示方法;如果把Property反映到表上的话,例如我们在Vertex Table中Id为的3的Property就是(rxin, student),而在Edge Table中3到7表明的边的Property是Collaborator的关系,2到5是Colleague的关系;更为重要的是Property Graph和Table之间是可以相互转换的,在GraphX中所有操作的基础是table operator和graph operator,,其继承自Spark中的RDD,都是针对集合进行操作。

05-11 11:08