图计算系统发展简史（一）

图论起源于18世纪欧拉对哥尼斯堡七桥问题的研究，并经由众多数学家乃至计算机科学家不遗余力的发展成为了我们解决很多实际问题的强力武器。如今，基于图模型的数据分析方法已经应用在了互联网的很多场景：社交网络分析、网页排序、社区发现……在天体物理学、计算化学、生物信息学等自然科学领域，图也有广泛的应用。然而，随着图数据规模的不断扩大，在图上进行计算的效率也变得越发重要，并由此引发了学术界和工业界一轮又一轮围绕图计算系统展开的研究。

本文是一系列文章的第一篇，将简单地介绍在“图计算系统”这一概念提出前，我们需要处理大规模图数据时能够借助的一些方法和系统性解决方案。

早期的图计算框架

事实上，在大规模图数据上进行分析并不是一个最近才出现的需求。超大规模集成电路的设计、运输路线的规划、电力网络的仿真模拟等等，都需要将数据抽象成图的表示并用到各种面向图的分析算法。

在“图计算系统”的概念出现前，完成这类任务通常需要针对每个场景编写相应的专用程序。借助已有的程序库可以减少不少工作量，例如大名鼎鼎的Boost中包含的专门面向图计算的BGL（Boost Graph Library）和PBGL（Parallel Boost Graph Library）。BGL提供了用于表示图的数据结构以及一些常用的图分析算法；PBGL则扩展了BGL，在此之上基于MPI提供了并行/分布式计算的能力。CGMgraph与PBGL类似，基于MPI提供了一系列图分析算法的并行/分布式实现。

然而，早期的这些面向图计算的程序库缺乏对用户友好的编程模型，需要介入和管理的细节较多，上手难度较大。

通用大数据处理系统

Google发表于SOSP ‘03的GFS和OSDI ‘04的MapReduce两篇论文向大家展现了如何通过较为廉价的普通服务器集群进行大规模数据的管理和处理。基于这两篇论文的核心想法，Hadoop于2006年诞生，并一直以开源的模式发展至今。自此，“大数据”不再像以前那样高高在上，而我们也有了处理大规模图数据的原始武器：Hadoop。

尽管MapReduce的处理模型十分简洁易懂，但它并不适合图数据分析。这是由图分析算法的特点导致的：它们通常都是迭代式的计算过程，且每一轮计算涉及的数据会随着算法的进度不断发生变化。使用Hadoop实现图分析算法时，我们不得不反复地将中间结果序列化到磁盘，从而产生了不必要的开销。

事实上，凡是需要迭代式计算的场景如很多机器学习问题用到的算法都不适合用Hadoop来完成。Spark针对这一点，提出了将中间结果缓存到内存中的想法，尽可能地避免中间结果落地到外存上；通过用户自定义的划分方法，还可以极大地减少机器之间的通信。相比Hadoop，Spark能够在图数据的规模能够容纳到集群的内存中时获得显著的性能提升。

但是，Spark的RDD模型还是限制了它的发挥：Spark在计算过程中产生的RDD都是不可变（immutable）的，因此产生的大量中间结果依然会导致不必要的内存占用从而影响能够处理的图数据规模和图计算效率。

需要指出的是，尽管使用通用的大数据处理系统如Hadoop/Spark等进行图计算的效率较低，但它们在图数据分析的预处理/后处理等场景上依然有不可或缺的作用。

下篇预告

本系列的下一篇文章将介绍“图计算系统”领域的开山之作Pregel和各类衍生的开源系统，以及GraphLab团队的一系列工作。敬请期待！

本系列其他文章：