超越Hadoop的大数据分析之图形处理尺寸

本文翻译自《BIG DATA ANALYTICS BEYOND HADOOP》译者：许巧辉

另一个来自Google的重要工具，看起来超越了Hadoop MR——Pregel框架实现了图形计算（Malewicez et al.2010）。在Pregel中的计算是由一系列迭代组成的，被称为supersteps。图上的每个顶点都与一个用户定义的计算函数相关联；Pregel确保每个superstep在图的每条边上并发调用用户定义的计算函数。顶点可通过边发送消息，并且顶点间可交换值。这也是个全局同步——所有操作必须在用户定义的函数结束后才能继续。熟悉BSP的读者可以看出为什么Pregel是BSP优秀的例子——一组实体在用户定义的函数中使用全局锁并行计算，并且能够进行消息交换。

Apache Hama (Seo et al. 2010)相当于开源的Pregel，一种BSP的实现。Hama在HDFS和微软的Dryad引擎之上 实现了BSP。大概是因为他们不希望被认为他们与Hadoop的社区之间有所不同。但重要的是，BSP本质上是一种适合迭代计算的范例，而且Hama拥有CGD的并行实现，这是Hadoop不容易实现的。必须指出的是，Hama的BSP引擎是在MPI之上实现的，这是并行编程文学的鼻祖( www.mcs.anl.gov/research/projects/mpi/ )。Apache Giraph, Golden Orb, 还有Stanford GPS项目的灵感也来自Pregel。

GraphLab (Gonzalez et al. 2012)已经成为现代化图形处理的范例。GraphLab起源于华盛顿大学和卡内基梅隆大学（CMU）的学术项目。GraphLab提供跨集群节点处理图形的有用抽象。PowerGraph，GraphLab的后续版，使得它有效地处理自然图形或幂律图——这是有大量不良连接点和少量良好连接点的图。Twitter上关于页面排名和三角形计数问题的性能评估已验证GraphLab比其他方法更有效率。本书的重点主要是Giraph，GraphLab及其相关方面。

表1.1对各种范例的非功能特性进行了比较，如可扩展性、容错机制和已实现的算法。由此可推断出，尽管传统工具只工作在单个节点上，不可能做横向扩展，也有可能出现单点故障，近期重构方面的努力抢劫它们跨代迁移。值得注意的是，大多数图形处理范例并没有容错机制，然而Spark和Hadoop是其中提供容错机制的第三代工具。