基于Spark的图计算框架 GraphX 入门介绍

╰半橙微兮° 2022-07-24 05:00 351阅读 0赞

# 基于Spark的图计算框架 GraphX 入门介绍 #

### GraphX原型论文 ###

[GraphX][]是 Spark中用于图(e.g., Web-Graphs and Social Networks)和图并行计算(e.g., PageRank and Collaborative Filtering)的API,可以认为是GraphLab(C++)和Pregel(C++)在Spark(Scala)上的重写及优化，跟其他分布式 图计算框架相比，GraphX最大的贡献是，在Spark之上提供一栈式数据解决方案，可以方便且高效地完成图计算的一整套流水作业。

[GraphX][GraphX 1]最先是伯克利AMPLAB的一个分布式图计算框架项目，后来整合到Spark中成为一个核心组件，这里的内容是基于论文

*  Xin, Reynold S., et al. "[GraphX: Unifying Data-Parallel and Graph-Parallel Analytics.][GraphX_ Unifying Data-Parallel and Graph-Parallel Analytics.]
 *  arXiv preprint arXiv:1402.2394 (2014). [ PPT][PPT]， [ Talk][Talk]，[Video][]
 *  [GitHub1][]
 *  [Hands-on Exercises][]

#### 图计算 ####

Graph来描述参数之间的关系，可以自然地做model partition/parallel，传统地用key-value存储参数的方式，可能会损失模型结构信息。  
![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX]

#### Graphx图处理流水线 ####

Graphx是Spark生态中的非常重要的组件，融合了图并行以及数据并行的优势，虽然在单纯的计算机段的性能相比不如GraphLab等计算框架，但是如果从整个图处理流水线的视角（图构建，图合并，最终结果的查询）看，那么性能就非常具有竞争性了。

![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 1]

![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 2]

#### 两种视图 ####

1.  GraphX通过引入\*\*Resilient Distributed Property Graph\*\*（一种点和边都带属性的有向多图）扩展了Spark RDD这种抽象数据结构，这种Property Graph拥有两种Table和Graph两种视图（及视图对应的一套API），而只有一份物理存储。![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 3]
2.  Table视图将图看成Vertex Property Table和Edge Property Table等的组合，这些Table继承了Spark RDD的API(fiter,map等)。![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 4]
3.  Graph视图上包括reverse/subgraph/mapV(E)/joinV(E)/mrTriplets等操作。结合pagerank和社交网络的实例看看mrTriplets（最复杂的一个API ）的用法。  
    ![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 5]  
    ![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 6]

#### 优化 ####

1.  **点分割**：graphx借鉴powerGraph，使用的是vertexcut(点分割)方式存储图。这种存储方式特点 是任何一条边只会出现在一台机器上，每个点有可能分布到不同的机器上。当点被分割到不同机器上时，是相同的镜像，但是有一个点作为主点(master), 其他的点作为虚点(ghost)，当点B的数据发生变化时,先更新点B的master的数据，然后将所有更新好的数据发送到B的ghost所在的所有机 器，更新B的ghost。这样做的好处是在边的存储上是没有冗余的，而且对于某个点与它的邻居的交互操作，只要满足交换律和结合律，比如求邻居权重的和， 求点的所有边的条数这样的操作，可以在不同的机器上并行进行，只要把每个机器上的结果进行汇总就可以了，网络开销也比较小。代价是每个点可能要存储多份， 更新点要有数据同步开销。
2.  **Routing Table**：vertex Table中的一个partition对应着Routing Table中的一个partition，Routing Table指示了一个vertex会涉及到哪些Edge Table partition。  
    ![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 7]
3.  **Caching for Iterative mrTriplets&Indexing Active Edges**：在迭代的后期，只有很少的点有更新，因此对没有更新的点使用local cached能够大幅降低通信所耗。  
    ![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 8]  
    ![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 9]
4.  **Join Elimination**：例如在PR计算中，一个点值的更新只跟邻居的值有关，而跟它本身的值无关，那么在mrTriplets计算中，就不需要Vertex Table和Edge Table的3-way join，而只需要2-way join。  
    ![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 10]此外，还有一些Index和Data Reuse的查询优化。

#### 性能 ####

1.  GraphX整体上比GraphLab慢2-3倍，有两方面的原因：1）GraphX跑在JVM上，没有C++快是显然的 2)GraphLab不受Spark框架的限制，可以通过Threads来共享内存，而GraphX就算在同一台机器上都有communication cost，“GraphX have to go through the full network stack even communicating between patrition on the same machine.”  
    ![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 11]
2.  GraphX在超大规模数据下，Runtime的增长比GraphLab要慢，scalability要好一些。
3.  从整个图计算Pipeline来说，GraphX的总体Runtime少于GraphLab+Spark。  
    ![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 12]

#### 社交网络实验 ####

[Graph Analytics With GraphX][]

[GraphX Programming Guide][]

#### 代码量 ####

![基于Spark的图计算框架 GraphX 入门介绍][Spark_ GraphX 13]

#### 杂谈 ####

1.  GraphX论文的作者Joseph Gonzalez在今年ICML上做了关于大规模机器学习系统对比的[报告][Link 1]
2.  Spark的GraphX是从表到图、允许图与表的交互，GraphLab也认识到表对图的重要性，在其Python包GraphLab Create里提供[SFrame][]， 即基于表的图表示，该图表示数据存在于HDFS，S3或直接从URL读取，支持Tb级的数据（虽然不大，比PyData和R强），提供基于表的 groupby aggregation/joins/user defined transformations/append等API, 功能和语法类似于pandas- and R- dataframes。

#### 参考 ####

*  [关于图计算和graphx的一些思考][graphx]

[GraphX]: http://spark.apache.org/graphx/
[GraphX 1]: https://amplab.cs.berkeley.edu/projects/graphx/
[GraphX_ Unifying Data-Parallel and Graph-Parallel Analytics.]: https://amplab.cs.berkeley.edu/wp-content/uploads/2014/02/graphx.pdf
[PPT]: https://amplab.cs.berkeley.edu/wp-content/uploads/2014/02/graphx@strata2014_final.pptx
[Talk]: http://www.meetup.com/spark-users/events/169857492/
[Video]: http://www.youtube.com/watch?v=MY0NkZY_tJw&list=L-x35fyliRwiP3YteXbnhk0QGOtYLBT3a
[GitHub1]: http://amplab.github.io/graphx/
[Hands-on Exercises]: http://ampcamp.berkeley.edu/4/exercises/graph-analytics-with-graphx.html#the-map-reduce-triplets-operator
[Spark_ GraphX]: /images/20220722/36a34346e306486e8ed874fede3adaf5.png
[Spark_ GraphX 1]: /images/20220722/ddf30b7e65514a69bc735c5ad287d61c.png
[Spark_ GraphX 2]: /images/20220722/da104ae27cec40ca8688a9c6382e43b6.png
[Spark_ GraphX 3]: /images/20220722/68ebee935e8e45e1af47b0bd60d67736.png
[Spark_ GraphX 4]: /images/20220722/a743498d52df4a0fa776dbd104ecdc33.png
[Spark_ GraphX 5]: /images/20220722/9060366d0dba43f7b48951149e7767bf.png
[Spark_ GraphX 6]: /images/20220722/6a1dc12125e04ee3a728eda2cb4b238e.png
[Spark_ GraphX 7]: /images/20220722/a60d8512e47342599eec0930f89dfb8e.png
[Spark_ GraphX 8]: /images/20220722/ce0a2b1f51054d038e5074c71832648c.png
[Spark_ GraphX 9]: /images/20220722/971453ea185b4f5aa9f1637076ce44f7.png
[Spark_ GraphX 10]: /images/20220722/478070dc45904fb6bd1e77430bc73b7b.png
[Spark_ GraphX 11]: /images/20220722/ce1578d7e2a84a0ca102a7574f632269.png
[Spark_ GraphX 12]: /images/20220722/3484104611594b94bd56d37b24e0b72b.png
[Graph Analytics With GraphX]: http://ampcamp.berkeley.edu/4/exercises/graph-analytics-with-graphx.html
[GraphX Programming Guide]: http://spark.apache.org/docs/1.0.0/graphx-programming-guide.html
[Spark_ GraphX 13]: /images/20220722/2501a036e322432cb30fe948e4993a04.png
[Link 1]: http://www.eecs.berkeley.edu/%7Ejegonzal/talks/icml14_sysml.pdf
[SFrame]: http://graphlab.com/products/create/tutorials.html
[graphx]: http://rdc.taobao.org/?p=1927