第1章　引言

1.1　大规模图计算

随着计算机技术的不断发展，其应用范围逐渐推广到人类生产生活的方方面面。当前被计算机系统产生或者收集到的数据的规模正在飞速增长，这些大规模的数据无疑对现代计算机系统的大规模数据存储、管理和分析处理的能力形成了极其尖锐的挑战。为了应对这一挑战，以谷歌和微软为代表的各大公司以及诸多的学术界团队提出了一系列的大数据处理系统^[1-5]。这些系统通过横向以及纵向扩展的方式极大地提升了数据处理系统的处理效率，扩展了它们所能承载的最大数据规模。

作为大数据中重要的一类，大规模图数据的管理与分析是近来备受重视的一个热点话题。举例来说，近来发展迅猛的各类社交网络产生了一个个规模巨大的图数据集。根据一项近期的统计结果^[6]，Facebook公司所维护的社交网络拥有将近20亿的用户。如果以图的模型进行建模，其结果将会拥有近20亿个点（代表各个用户）以及更高数量级的边（用于描述用户间的关系）。支持在这样规模的图上进行高效地查询和分析的需求无疑是现有系统所需应对的一项重要挑战。同时，由于图这一数据结构的灵活性，许多原本通过稀疏矩阵等其他数据结构进行建模的问题往往也都可以转化成图计算的形式。因此，正如将在3.2节中详细描述的，诸如协同过滤等在内的很多机器学习和数据挖掘算法也都被认为是涵盖在图计算系统的处理范围之内的。这一现象极大地拓展了图计算的应用范围，因此也间接地提升了图计算系统的重要性。

鉴于大规模图数据的普遍存在以及对其进行分析处理的实际需求，众多商业公司和学术团队设计和提出了一系列的大规模图计算系统^[1-4]。与传统的数据并行类大数据处理系统（如MapReduce^[7]，Spark^[8]等）不同，这些专用图计算系统专门针对图这一数据结构本身的特点进行了优化，从而避免了传统通用系统在图这一类数据间具有复杂联系的数据上可扩展性不好的问题。经过最近数年的发展，目前的大规模图计算系统已经具有极高的可扩展性。Facebook公司研究人员通过将Giraph^[9]系统横向扩展到数百台计算机上，成功地对包含数十亿条边的超大规模图数据集进行了处理。与此同时，由于点程序（vertex program）等简单有效的编程接口的提出，程序员们可以非常简单地进行图计算的编程，而无需考虑网络通讯、外存访问等复杂问题。往往系统可以几乎完全自动地将用户编写的单机单进程程序扩展到多核乃至多机环境下，甚至可以自动地进行单点容错。由此可见，在可扩展性和易用性等方面目前已有的研究已经取得了非常良好的结果。也正是因为这样的原因，目前图计算系统已经被部署在众多的商业公司之中，用于支撑它们的多种关键业务^[6]。