利用大数据技术进行图处理

处理非常大型的图对象一直都是个挑战，但最近大数据技术的进步却让这一工作变得更具实践性。作为纽约市的一家专注于跨设备内容分发的创业公司， Tapad 利用大数据技术处理 TB 级的数据，并已将图处理作为其商业模型的核心业务。

像 Facebook 和 Twitter 这样的社交网络，其数据天生就适合于图表示法。而对这方面属性不太明显的数据，我们也可以用图对象来表示，比如 Tapad 的设备图。Tapad 的联合创始人兼 CTO， Dag Liodden ，解释了为什么对设备使用图表示法很有意义：

“Tapad 采用面向图的方式对设备间的关系进行建模。在设备图中，我们把匿名标示符（如 cookie ID）表示为节点并且追踪这些节点的市场信息。节点间的边则结合使用测定数据、概率统计模型以及机器学习技术计分或加权重。我们将‘设备’的概念定义为一个起始设备或节点（比如说某个浏览器的 cookie ID）和由该起点出发的、在一组可定制边约束下能达到的节点集合（比如说一个 Tablet 和一个 Connected TV 的 cookie ID）。相对于单个节点仅有的聚合信息，实际的图结构使我们能够在动态平衡数据准确度和规模方面更具灵活性，而且还能更容易地运用新的边推理模型来对图进行扩充。”

用合适的工具完成合适的工作很重要，这个道理同样适用于图处理：对于通过传统工作负载就能处理的图对象，我们就没必要使用大数据技术。正如 Dag 所说：

“‘大数据’对我而言就像个门槛，跨过之后你就不能再使用少数通用的、现成的工具来存储和分析数据了，而是要依据具体的用例对不同的技术加以取舍。随着软硬件解决方案的进步和成熟，这些阈值每年都在变动，而我们所处理的数据集的大小以及所进行的分析的复杂程度亦是如此。”

对 Facebook 来说，这个阈值达到了几 PB 级，详情可参阅他们在 2013 纽约 ACM SIGMOD 大会上的报告。对 Tapad 而言，图对象的数据量虽然较小，但依然不可能用传统的方法来处理：

“全美的图对象当前有大约 11 亿个节点，它们代表着移动电话、平板、笔记本、游戏终端以及电视机。其中有些节点是临时的，比如因为浏览器使用非持久的 cookie，导致节点缺少数据而没有边缘。非临时节点平均有大概 5 个边缘和约 500 个离散的信息片段与其相关联，如行为分段。实时图数据量达到了几 TB 级，而且我们还要跨多个数据中心每秒对其进行几十万次的读取、写入操作。图对象的更新实现了跨地域相互复制，每个数据中心由配备了 20TB Flash SSD 存储和 2TB RAM 的服务器来支撑。”

近几年涌现出很多处理大型图对象的技术，尤其是 2013 年，我们看到了几个新成员加入到该生态系统中。有两类系统值得考虑：

• 针对 OLTP 工作负载，能够快速低延迟访问小部分图数据的图数据库。
• 针对 OLAP 工作负载，能够对图对象中的大部分数据进行批处理的图处理引擎。

知名的图数据库已经很多了，但最近仍冒出了几个标新立异的项目。 Neo4j 算是最老牌、最成熟的图数据库之一，但因不支持分片而依然存在可伸缩性的问题。另一个相当年轻，却在2013 年非常流行的数据库便是 Titan 。作为后端无关的图数据库，它支持 HBase 和 Cassandra 的可伸缩架构，并且如 2013 年的一篇博文所报道的，它在内部使用了一套优化的顶点和边表示法以使其能处理几十亿个边对象。

但你不必非要使用图特定数据库，更通用的可伸缩的 NoSQL 数据库也是有效的解决方案。基于 Google BigTable 并在 2011 年开源的 Apache Accumulo 就是一个通用数据库的例子，它的数据记录很灵活，所以也适合存储大型图对象，同时还可以用来存储含有类型化的边和权重的图对象， 2013 年发布的一份技术报告表明 NSA 也在使用它。Cassandra 或者 Aerospike 则是另一种数据库，它们能通过适当的数据模型，用边、顶点和权重给图对象高效地建模。Facebook 也构建了自己的解决方案，他们在被称为 Tao 的系统中使用了 MySQL 和 Memcache 组合，并正在使用这一方案为其用户提供社区图服务。据 Dag 所说，Tapad 在其设备图的设计过程中也运用了同样的哲学：

“将实时的图对象保存在键值对存储中可以支持快速的遍历和更新。我们就是把图的快照周期性地存进 HDFS，然后从中提取它们进行高级图处理并用其他数据流来扩充，之后再把结果回填至‘实时图’。虽然使用图特定的数据库会有一些优势，但以我们目前的设置，既可以在键值对存储中极快且简单地遍历图对象，还可在 Hadoop 上慢速但非常灵活地进行遍历和分析操作，对我们来说它工作的很好，至少现在如此。”

和存储于数据库中的图对象一样 ，可大规模进行的操作也只是局限于查找和小范围的遍历。至于在图对象中进行更加复杂的分析，就需要分布式的批处理框架。为了达到最佳性能， GraphLab 框架使用了 Message Passing Interaface(MPI) 模型来调整并运行基于 HDFS 数据的复杂算法。而新近的框架如 Apache Giraph 和 Apache Hama 则基于 Bulk Synchronous Paralle(BSP) 范式，该范式是由 Google 的 Pregel 项目推广开的。而生态系统中最新的项目便是 GraphX 和 Faunus 。GraphX 项目运行于 2013 年才问世的 Spark 之上，而 Faunnus 则通过用 Hadoop 运行 MapReduce 作业的方式来处理 Titan 数据库中图对象。Tapad 正在运用这些新技术处理其离线图数据。按照 Dag 所说：

“目前，我们主要的图处理框架虽是 Apache Giraph，但我们也在尝试 Saprk GraphX 和 GraphLab。所有这些架构还都很年轻，学习曲线也颇为陡峭，而且全都有自己的优缺点及注意事项。举个例子，Giraph 和 GraphX 由于能很好地支持我们的 Hadoop 架构所以很方便，但 GraphLab 却完全是因为其性能而更吸引我们。”

有些项目正试图提供统一的架构以支持 OLTP 和 OLAP 查询。来自 Lab41 的 Dendrite 就是这样一个项目，它利用基于 Titan 的 GraphLab 进行存储、处理，并用 AngularJS 实现可视化。因为这个非常年轻的项目在 2014 年年初才公开，所以社群反响有限，但是它试着顾及到所有用例，这应该有助于它的普及。

参考英文原文： Graph Processing Using Big Data Technologies

感谢孙镜涛对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ）或者腾讯微博（ @InfoQ ）关注我们，并与我们的编辑和其他读者朋友交流。