一周一论文（翻译）—— [PVLDB 12] Distributed GraphLab A Framework for Machine Learning 分布式机器学习图计算框架

不念不忘少年蓝@ 2022-05-22 02:36 183阅读 0赞

##  ##

## **摘要** ##

虽然高级别数据并行框架，像MapReduce，简化了大规模数据处理的设计和实现的系统，他们没有自然或有效地支持许多重要数据挖掘和机器学习算法并且导致学习系统效率低下。为了帮助填补这一重要空白，我们介绍了GraphLab框架，它自然表达异步的， 动态的，并行图计算，同时在共享内存设置上确保数据一致性和实现高度的并行性能。在本文中，我们扩展GraphLab框架到更具挑战性的分布式环境中，在保持健壮的数据一致性。

我们开发了基于图的扩展，用线性管道锁定和数据控制来减少网络拥塞和减弱网络延迟的影响。我们也介绍GraphLab容错，这个容错使用了经典的抽象Chandy-Lamport快照算法，并展示它如何能轻易利用实现的GraphLab抽象本身。最后，我们评估我们的分布式GraphLab框架，在Amazon EC2部署和展示1 - 2个数量级在Hadoop-based实现收益的性能。

## **1简介** ##

指数增长的机器学习和数据挖掘(MLDM，即Machine Learning and Data Mining)问题和日益成熟的MLDM技术，越来越需要一个能够在大型集群并行执行MLDM算法的系统。同时，云计算服务的可用性，比如Amazon EC2，提供按需获得可以负担的服务的承诺，这样就没有实质性的大规模计算和存储资源在前期投资上。不幸的是，设计、实施和调试分布式MLDM算法，需要充分利用云平台，可能是非常具有挑战性的。这些需要MLDM专家去解决竞争、死锁、分布式状态和通信协议等问题，同时提出复杂的数学模型和算法。

然而，大规模计算和存储资源的需求，推动许多人\[2、14、15，27，30，35\]去开发新的并行和分布式针对单个模型和应用程序的MLDM系统。这通常需要耗费大量的时间和多余的精力，减缓了不同研究领域的进展在反复解决相同的并行/分布式计算的问题上。因此， MLDM社区需要一个高级分布式抽象概念，异步的，动态的，并行图计算中发现许多MLDM应用程序而隐藏并行/分布式系统设计的复杂性。不幸的是，现有高级并行抽象(如MapReduce\[8、9\]，Dryad\[19\]和Pregel\[25\])不支持这些关键属性。为了帮助填补这一空白，我们引入了\[24\] GraphLab抽象， 在共享内存设置情况下实现异步的，动态的，并行图计算的目标。

在本文中，我们扩展了多核GraphLab系统来适用分布式环境和提供了一个分布式的正式描述执行模型。然后，我们探索几种方法来实现一个高效的、严格的满足一致性要求的分布式执行模型。为达到这一目标，我们用数据控制来减少网络拥塞和用线性分布式锁减轻网络延迟的影响。为解决数据本地化和入口的挑战，我们引入了原子图（atom），迅速把图结构数据放到分布式环境中。我们还对GraphLab框架添加容错通过调整经典的Chandy-Lamport\[6\]快照算法和证明如何简单在GraphLab系统实现。

我们进行一个全面的性能分析在优化的c++实现上，通过亚马逊弹性云计算服务(EC2)。结果表明，应用程序创建使用GraphLab可以等效Hadoop / MapReduce\[9\]实现和匹配的性能构造的MPI实现。我们的主要贡献有下面几个：:

•一个概要有关MLDM算法的常见属性以及现有的大型框架的局限性。(第2节)

•一个修改版本有关在分布式环境中GraphLab理论和执行模型。(第3节)

•两种截然不同的方法实现分布式执行模型(第4节):

染色引擎:使用图着色达到一致高效按顺序执行的静态表。

锁定引擎:使用管道线性分布式锁和隐藏延迟，支持动态优先执行

•通过两个快照的容错方案。(第4.3节)

•三个先进的机器学习算法在分布式GraphLab的高层实现。(第5节)

•一个广泛评估分布式GraphLab使用512处理器(64节点)EC2集群，包括比较Hadoop，Pregel，MPI的实现。(第5节)

## **2MLDM算法性能** ##

在本节中，我们描述了几个关键有效的属性有关大规模并行通过GraphLab解决的MLDM系统 \[24\]以及其他并行框架无法解决这些属性。这些属性和并行框架的概要在表1中可以找到。

**        图的结构计算**:许多在MLDM上最新进展都集中在依据数据的依赖关系建模上。通过数据依赖建模，我们能够提取更多的信号从非结构化的数据。例如，根据依赖关系的建模，类似于购物者允许我们做出产品推荐比孤立地对待顾客要更好。不幸的是，像MapReduce一样的数据并行\[9\]一般不适合通常需要更先进MLDM算法的依赖计算。虽然它通常是可能的映射算法与计算依赖MapReduce概念，由此产生的转换可以挑战和可能会引入大量的低效率。

因此，图并行框架最近成为一个趋势，比如Pregel\[25\]和GraphLab\[24\] ，能够自然地表达计算依赖关系。这些框架采用以点为中心的模型，计算被定义在运行每个顶点的内核上。例如，Pregel批量同步消息传递抽象，通过消息传递进行顶点沟通。另一方面，GraphLab顺序共享内存框架，每个顶点可以读和写在相邻的顶点和边的数据。GraphLab运行状态是负责确保一致性的并行执行。因此， GraphLab通过释放用户集中在线性计算而不是并行移动的数据(例如，消息传递)，简化了设计和实现图并行算法。

**        异步迭代计算**:许多重要MLDM算法迭代更新大量的参数，因为潜在的图结构，参数更新(在顶点或边)取决于(通过图邻接结构) 其他参数的值。同步更新使用以前的时间步的参数值作为输入，更新所有参数(并行)，跟同步系统对比，异步系统使用最新更新的参数值作为输入。因此，异步系统为许多MLDM算法提供了便利。例如，线性系统(常见的许多MLDM算法)已被证明，通过异步计算，收敛会更快解决 \[4\]。此外，还有很多其他的情况下(比如置信传播\[13\]，期望最大化\[28\]，和随机优化\[35，34\])，异步的程序被经验性的显著表现同步过程。在图1(a)，我们演示如何异步的计算可以大大加快收敛网页排名PageRank。

同步计算会导致昂贵的性能损失，因为每个阶段的运行时是取决于最慢的机器。最慢的机器的表现不佳可能由多种因素引起:包括负载和网络失衡，硬件变化和多租户(关注云服务)。即使是在典型的集群设置里，每个计算节点也可以提供其他服务(如分布式文件系统)。在利用这些服务的失衡问题将导致大量的其他服务性能损失，如果使用同步计算的话。

此外，在复杂性上的转变和单个顶点内核的收敛在执行过程中可能产生额外的变化，即使是均匀分区图。举个例子，自然图形中遇到现实世界的应用——幂律分布图从而导致高度倾斜的运行时间，即使是随机分区\[36\]。此外，实际工作所需的每个顶点可能依赖于数据特定的方式(如局部收敛速度)。

虽然框架基于批量数据处理，如MapReduce \[9\]和Dryad \[19\]，没有被设计应用于迭代计算，最近的项目如Spark \[38\]扩展了MapReduce和其他数据并行框架的迭代设置。然而，这些框架仍然不支持异步计算。模块同步并行(BSP)框架如Pregel\[25\]， Piccolo \[33\]，BPGL\[16\]不自然地表达异步性。另一方面，共享内存GraphLab框架被设计成有效自然地表达对于常见的先进的MLDM算法的异步迭代。

**        动态计算**:在许多MLDM算法，迭代计算的收敛不对称。例如，在参数优化上，往往很快就会大量的参数在几个迭代中收敛，而其余的参数在许多迭代收敛中非常缓慢\[11,10\]。在图1(b)，我们绘制了需要收敛的PageRank的分布式更新的描述。令人惊讶的是，大多数所需的顶点一个更新，只有约3%的顶点需要超过10次以上更新。另外，优先计算可以进一步加速收敛(Zhang et al \[39\])各种各样的图算法包括PageRank。如果我们平等且经常更新所有参数，我们浪费大量时间在对已经有效收敛的参数的重复计算上。相反，通过早期计算在更具挑战性的参数，我们可以加速收敛。在图1(c)，我们实证证明动态调度在暴力的信息传播中(一个流行MLDM算法)如何加速收敛。

好几个最近的框架已经可以建立动态计算的表单。例如，Pregel\[25\]支持有限形式动态计算，通过允许一些顶点在每个超级步上跳过计算。另一些框架比如Pearce \[32\]和GraphLab允许用户自适应优化计算。虽然Pregel和GraphLab支持动态计算，只有GraphLab允许优先级以及从相邻的顶点拉取信息的自适应的能力 (详细信息见3.2节)。在本文中，我们简化一些原始GraphLab\[24\]中描述的调度需求，使有效的分布式FIFO和优先级调度。

**        可串行性**:通过确保所有并行执行的方式保证等价的顺序执行，可串行性消除了许多挑战，这些挑战与设计、实现和测试MLDM算法有关。此外，许多算法收敛更快，如果能保证可串行性，有些甚至需要保证可串行的正确性。例如，动态ALS(5.1节)是不稳定的当允许竞争时(图1(d))。Gibbs抽样，一个流行的MLDM算法，就需要可串行性统计的正确性。

![20180613130545358][]

一个执行序列化计算的框架消除了并发带来的复杂性，使MLDM专家集中在算法和模型设计上。在带有肮脏数据造成数据竞争的并发程序中调试数学代码是困难和费时的。令人惊讶的是，许多异步框架喜欢\[32\] 　　确保可串行性，或者像Piccolo \[33\]，只提供从数据竞争中恢复的基本机制。GraphLab支持范围广泛的一致性设置，允许一个程序选择需要正确性的一致性的级别。在第4节，我们描述了几个我们开发的在分布式配置下的可串行性技术。

## **3Graphlab框架的组成部分** ##

GraphLab框架由三个主要部分组成，数据图，更新函数和同步操作。数据图(第3.1节)代表用户修改的程序状态，和提供用户定义的可变数据和稀疏编码的计算依赖关系（边）。更新函数(第3.2节)代表了用户在数据图上的计算和操作，通过在作用域上转换数据。最后，同步操作(第3.5节)同时维护全局变量。为了更全面的认识GraphLab框架在一个具体的问题上的应用，我们将PageRank算法\[31\]作为一个运行的例子。

示例1(PAGERANK)。PageRank算法递归定义网页的排名v:

![20180613130556828][]

依据权重wu，v的排名 R(u) 的页面 u 链接到 v作为随机跳到这个页面的概率。这个PageRank算法会收敛到一个值直到收敛的改变非常小为止。

### **3.1数据图** ###

GraphLab框架存储单向图的程序状态叫做数据图。数据图G =(V，E，D)是一个容器，用来管理我们用户定义的数据D。我们使用术语data引用模型参数，算法的状态，甚至统计数据。用户可以关联任意数据作为在图上的每个点和边。然而，如果GraphLab框架不是依赖在边的方向，我们也使用Du v表示数据在双向边。最后，图数据是可变的，D的数据结构是静态的，在执行过程中不能改变。

示例2(PAGERANK:例1)。数据图是直接的从网上获得的图，每个点对应一个网页，每个边代表一个链接。顶点数据Dv存储R(v)，当前估计的PageRank，和边的数据Wu，v表达单向的链接权重。

### **3.2更新函数** ###

计算方式被编码在GraphLab框架的更新函数中。一个更新函数是一个无状态的过程，这个过程修改一个顶点作用域内的数据和调度未来执行在其他顶点上的更新函数。一个顶点v的作用域(用Sv表示)是存储在v上的数据，以及数据存储的所有相邻点和相邻边(图2(a))。

GraphLab更新函数把一个点v和作用域Sv作为输入，并返回作用域内数据的新版本——顶点的集合T。

![20180613130610943][]

在执行更新函数后，在Sv上的修改数据会被写回到数据图。顶点集T的每个顶点u最终更新执行为函数f(u，Su)依据执行语义描述（在后面的3.3节）。

GraphLab允许用户定义更新功能，而不是采用消息传递或数据流模型\[19，25\],完全自由地来读和写任何相邻的点和边。这简化了用户代码并且消除了用户的移动数据的需求。通过控制所返回在T中的接着要执行的顶点，GraphLab更新函数可以有效地表达自适应计算。举个例子，一个更新函数可以选择返回(调度) 邻接的点，只有当这些点做出了对本地数据实质性改变。

有一个重要的区别在Pregel和GraphLab之间，动态计算是如何表达的。GraphLab从数据的移动中分离了未来计算的调度。作为结果，GraphLab更新函数可以访问数据在相邻的顶点，即使相邻顶点没有调用当前的更新。相反，Pregel更新函数通过消息初始化并且只能访问在消息中的数据，限制了所能表达的内容。例如，动态PageRank是很困难的表达在Pregel上， 计算给定页面PageRank值需要的所有相邻的PageRank值，即使所有相邻的页面最近的一些相邻的页面并没有改变。因此，发送数据 (PageRank值)给相邻的顶点的决定不能由发送顶点来做出(根据Pregel的要求)，但必须由接收顶点决定。GraphLab，自然表示了抽取模型，由于相邻顶点只负责调度和更新函数，可以直接读取相邻定点的值，即使他们没有改变顶点值。

示例3(PAGERANK:例1)。PageRank的更新函数计算了当前相邻顶点的加权和，和分配它作为当前顶点的排名。该算法自适应: 邻居被调度更新只有在当前顶点的值变化超过一个预定义的阈值。

![20180613130618328][]

### **3.3GraphLab执行模型** ###

GraphLab执行模型，提出了（在Alg.2）遵循简单的单回路的语义。GraphLab框架的输入包括数据图G =(V，E，D)， 一个更新函数，一个将被执行初始顶点集合。当有顶点在T，该算法选择(第1行)和执行(第2行) 顶点，添加任何新的顶点回到T(第3行)。重复的顶点被忽略。最后数据图和全局值在完成后返回给用户。

为了更有效的分布式执行，我们降低了执行共享内存GraphLab框架的要求，并且允许GraphLab运行时确定最佳的顶点执行顺序。例如，RemoveNext(T) 可以选择返回依照最小化网络沟通或延迟的顺序来执行顶点(见第4.2.2节)。唯一强加在GraphLab框架的要求是所有T中的顶点最终都要被执行。GraphLab框架允许用户指定优先级对在T中的顶点，所以许多MLDM应用程序从优先级受益。GraphLab运行时可能会使用这些优先级结合系统级目标来优化顶点的执行顺序。

![20180613130628157][]

### **3.4确保可串行性** ###

GraphLab框架提供了一个丰富的序列化模型，这个模型通过允许多个处理器上对相似的图执行相同的循环操作，可以同时删除和操作不同的顶点的方式实现自动转换为并行执行。为了保留顺序执行的语义，我们必须确保重叠计算并不是同时运行的。我们介绍几个一致性模型，允许运行时优化并行执行，同时保持可串行性。

GraphLab运行时确保序列化执行。一个序列化执行意味着存在一个类似的串行执行的更新函数的调度，并且更新函数在数据图上产生相同的值。通过确保可串行性， GraphLab简化了在分布式计算环境下有关高异步的动态计算的演算。

一个实现可串行性的简单方法是确保同时执行的更新函数作用域不重叠。在\[24\]我们称之为完全一致性模型(见图2(b))。然而，完全一致性同时限制了潜在的并行性，执行更新函数必须至少两个顶点(见图2(c))。然而，对于许多机器学习算法，更新功能不需要完整的读/写访问所有的数据作用域的权限。例如，PageRank更新只需要读访问边和相邻的顶点的权限。为了提供更大的并行性，同时保留可串行性，GraphLab 定义了边一致性模型。边一致性模型确保每个更新函数独占读写访问顶点和相邻的边，但只读访问相邻的点（图2(b))。因此，边缘一致性模型也在不断增加并行性，通过允许更新函数使用少量重叠作用域来安全并行运行(见图2(c))。最后，点一致性模型允许并行运行，所有更新功能提供最大的并行性。

### **3.5同步操作和全局值** ###

在许多MLDM算法中，需要保证全局统计的数据存储在数据图上。例如，许多统计推断算法要求跟踪全局收敛性的评估值。为了解决这种需求，GraphLab框架定义了全局值，这个值通过更新函数读，但都使用同步操作写。类似于Pregel的聚集值，同步操作是一个关联交换的和:

![20180613130635650][]

在所有的范围定义图。与Pregel不同的是，同步操作引入了一个终结阶段， Finalize (·)，来支持任务，如标准化，在MLDM算法中相当常见。与Pregel的聚合值在超级步后运行相比，GraphLab的同步操作能够连续运行在保持更新的全局值的背景上。

由于每个更新函数可以访问全局值，确保同步操作的可串行性对更新函数是费资源的，一般会需要同步和停止所有计算。正如GraphLab有多个一致性水平更新函数，我们同样提供一致和不一致的同步计算的选择。

## **4．分布式GRAPHLAB设计** ##

在本节中，我们扩展了共享内存系统GraphLab框架的设计到更具挑战性的分布式的环境，并且讨论实现这一目标所需的技术。分布式设计的概述被展示在图5(a)。由于固有的随机内存访问模仿了常见的动态异步图算法，我们关注分布式内存设定，整个图的需求和所有驻留在RAM中的程序状态。我们的分布式实现是用c++写的，扩展了原始开源共享内存GraphLab的实现。

### **4.1分布式数据图** ###

有效地实现分布环境的数据图需要平衡计算、通信和存储。因此，我们需要构建平衡数据的分区图，保证最小化的边的数量介于机器之间。因为云环境可以使用不同预算和性能要求的集群，我们必须能够迅速加载数据图在不同大小的云部署上。为了解决这些挑战，我们开发了一个可以在任意的集群大小有效负载平衡的基于双相分块的图表示法。

![20180613130647290][]

数据图使用指定作用域的方法被初始化为覆盖分区 (如平面嵌入)，或者通过使用一个分布式图分区探索式(如ParMetis\[21\]，随机散列)分成k个部分，这k个部分远远大于机器的数量。每一个部分，称为一个原子，在分布式存储系统中存储作为一个单独的文件(如HDFS，Amazon S3)。每个原子文件是一个简单的二进制压缩图，包含生成加点和加边的命令。此外，每个原子存储关于虚拟点的信息: 与分区边界相邻的顶点和边的集合。这k个原子连接的结构和文件位置存储为一个原子索引文件中，作为与k 个顶点(对应原子)和边通过连接原子的编码的标签图。

分布载荷是通过物理机器的数量执行一个快速平衡分区的标签图。每台机器然后构造其本地图，通过从每个原子的分配的记录来回放。回放过程还实例化的在内存中的本地分区虚拟点。虚拟点在网络上被用作缓存。缓存一致性被安排使用一个简单版本控制系统，消除了不变或常量数据的传播(如边的权重)。

两级分区技术允许相同的图分区计算可以被不同数量的机器重用，而不需要一个完整的实现步骤。两级分区方案的质量研究超出了本文的范围，但使用图表的简单实验获得\[23\]性能与直接分区。

### **4.2分布式GraphLab引擎** ###

分布式GraphLab引擎模拟执行模型(定义在3.3节)，并负责执行更新功能和同步操作，维护调度顶点集T，并对适当的一致性模型确保可串行性(参见3.4节)。在3.3节，已经讨论了精确的顺序T中顶点到实现以及如何影响性能和表现力。为了评估权衡我们建立的低开销染色引擎，这个引擎部分异步地执行T集合，更富有表现力的锁定引擎是完全异步的，支持顶点的优先事项。

#### **4.2.1染色引擎准备** ####

一个来实现一个可序列化的并行执行相关的任务(图中表示为顶点)的典型技术是构建一个顶点着色，每个顶点分配一个颜色，这样没有相邻的顶点共享相同的颜色。给定一个数据图的顶点着色情况，我们可以通过同步执行顶点集合T中相同颜色的所有顶点，然后继续下一个颜色，来满足边缘一致性模型。 我们使用术语染色步，在类比的超级步 BSP模型中，描述在单独的颜色和沟通所有的变化的情况下，更新所有的顶点的过程。同步操作就可以安全地运行染色步。

我们可以仅通过改变顶点的颜色，满足其他一致性模型。完整的一致性模型是满意的通过构造一个二阶顶点着色(即没有顶点分享相同的颜色在任何两个邻居的之间)。顶点的一致性模型是通过设定所有顶点为相同的颜色来实现的。而最优图着色是NP难题，一个合理的高质量着色使用启发式方法图形着色可以快速构建(如贪心的着色)。此外，许多MLDM问题生成带有琐碎的颜色的图表。例如，许多优化问题在MLDM自然表达为双边(two-colorable)图表，而基于模板模型的程序可以很容易的使用模板\[12\]。

在染色引擎运行同步的染色步时，虚拟点和虚拟边的改变是异步通信。因此，染色引擎有效地在每个染色步使用网络带宽和处理器时间。然而，我们必须确保所有的修改在改变到下一个颜色之前能够被连接起来，因此我们需要一个在染色步之间的完整的通信界限。

#### **4.2.2分布式锁引擎** ####

当染色引擎满足分布式GraphLab框架（第3节），它不提供足够的调度灵活性为许多有趣的应用程序。此外，它是以图着色的可用性为先决条件，这可能并非总是有效的。为了克服这些限制，我们介绍扩展了用于共享内存引擎的技术的分布式互斥锁引擎。

我们通过实现分布式互斥读写锁关联每个顶点。不同的一致性模型可以使用不同的锁协议实现。顶点　　的一致性是通过获取每个请求中心顶点作用域的写锁来完成的。边一致性是通过在中央顶点获取写锁，在相邻的顶点获取读锁。最后，完全一致性是通过获取中央顶点和相邻顶点的写锁来实现。通过依照有顺序的规范秩序的方式获取锁而避免死锁。我们依照顶点id的机器id来引用(所有者(v)，v)，因为这允许在一个远程的机器的所有锁可以被请求通过单个消息。

因为图是分区的，我们限制每台机器只能更新本地顶点。虚拟顶点/边更新直接访问内存所有信息的范围。每个工作线程在每台机器上评估中所描述的回路（Alg.3），直到调度器是空的。终止评估使用分布式一致算法\[26\]。

由于远程锁获取和数据同步的延迟，在（Alg。3）朴素的实现将表现不佳。因此我们依靠几个技术来降低延迟和隐藏它的影响\[17\]。首先，虚拟点系统提供缓存功能，消除了没有改变的远程数据传输或等待的需要。第二，所有的锁请求和同步调用是线性的，允许每台机器同时请求锁和数据，然后评估作用域已经准备好了的更新函数。

![20180613130656345][]

**        线式锁定和预读**:每台机器维护线性的拥有锁请求的顶点，但是没有得到执行的。完成的锁获取和数据同步的顶点执行离开线性管道和工作线程。本地的调度程序确保管道总是满足使用的。管线式锁定引擎的回路概述被展示在(Alg.4)。

为了实现流水线系统，常规的读写锁不能被使用在将停止的争用管道线程的数据上。因此，我们实现了一个非阻塞的通过回调操作的读写锁变种。锁请求和获取一个回调指针，这就叫做请求被实现。这些回调指针被链接成一个分布式扩展传递理论，这个理论在机器间的锁请求被批准。既然锁请求依从之前的描述的顺序（线性），无死锁操作就能被保证。为了进一步减少延迟，在每台机器完成其本地锁后，数据同步锁应该立即执行。

![20180613130704488][]

例4。为了获得一个分布式边一致的作用域下的一个顶点v，这个顶点在机器2上，虚拟点在机器1和5上，系统首先发送一个消息到机器1，获取机器1上的边一致性的作用域(在v写锁，在邻接点读锁)。一旦锁被请求了，消息被传递到机器2，再次获得本地边一致作用域。最后，在返回主机信号完成之前，消息发送到机器5。

评估分布式管线（管道线性）系统的性能， 我们构建了一个三维网格的300×300×300 = 27，000，000个顶点。每个顶点26个连接(直接相邻的顶点沿轴方向，以及所有对角线)， 生产超过3.75亿的边缘。图使用Metis \[21\]被分成512个原子。我们表示图作为二进制Markov随机文件\[13\]和评估运行10次迭代的置信传播\[13\]，从不同长度100至10000的管道，EC2集群计算实例的数量(cc1.4xlarge)4机(32个处理器)到16机(128个处理器)。我们看到在（图3(a)）分布式锁系统提供了强有力的、几乎线性，可伸缩性的性能。我们在图3(b) 通过增加的管道长度来评估管道系统的有效性。我们发现增加长度从100到1000导致运行时减少三倍。

![20180613130712393][]

### **4.3容错** ###

我们为GraphLab框架引入容错分布式，使用一个分布式检查点机制。在一个事件发生失败后，系统从最后一个检查点恢复过来。我们评估两个策略去构建分布式快照:一个同步的方法——暂停所有计算当构造快照，和一个异步方法——逐步构造快照没有暂停执行。

同步快照通过暂停更新功能来执行，冲洗所有的沟通渠道，然后从最后次快照保存所有修改数据。变化都写在分布式文件系统日志文件里，可以用来在任何以前的快照上重新启动执行。

不幸的是，同步快照暴露了GraphLab引擎一样效率低下的同步计算 (第2节) GraphLab试图解决的。因此我们设计了一个完全异步的基于Chandy-Lamport\[6\] 替代快照。对于使用GraphLab框架，我们设计并实现了的一种Chandy-Lamport的变体，专门为GraphLab 数据图和执行模型定制的快照。由此产生的算法(Alg。5)表示为一个更新功能和保证一致的快照，在下列所示:

•边缘一致性是用于所有更新功能，

•在作用域未锁之前完成调度，

•其他更新函数比更新快照优先，

![20180613130722424][]

对GraphLab引擎实现最小的改变。正确性的证明遵循自然的原始证据在\[6\]中，机器和渠道取而代之的是顶点与边和消息对应作用域的修改。

同步和异步快照都在固定的间隔启动。启动的时间间隔必须平衡构建检查点和从失败的检查点恢复的花费。Young et al. \[37\]派生一个一阶近似最优检查点间隔：

![20180613130730978][]

当T（checkpoint）是构建检查点的时间和T（MTBF）集群的平均故障间隔时间。例如，使用一个集群的64台机器，每台机器平均1年，一个检查点2分钟时间导致最优检查点间隔是3小时。因此，对于部署考虑在我们的实验中，即使把T（MTBF）悲观的假设，导致检查点间隔，远远超过我们的实验和事实上的运行时也超过了Hadoop实验运行时。这引入了在Hadoop强大的容错问题。更好的表现可以通过平衡容错性能成本实现对工作的重新启动。

**        评价**: 对前一节中的相同的网片问题，我们评估快照的性能算法，16个机器上运行(128处理器)。我们配置实现问题的一个快照第二次迭代。在图4(a)，我们标记随时间更新完成的数量。同步快照和异步快照的效果可以清楚地被观察到:同步快照停止执行，而异步的快照只减慢执行。

当系统性能的变化加剧同步操作的成本的时候，异步快照在多租户的设定的好处更加明显。我们模拟了Amazon EC2在快照开始了15秒后停止的一个过程。在图4(b)，我们再次标记随时间更新完成的数量后，我们观察到异步快照是受模拟故障的影响最小(只有3秒添加到运行时)，而同步快照经历一个完整的运行时增加到15秒。

![20180613130742459][]

### **4.4系统设计** ###

![20180613130754168][]

在图5中(a)，我们提供GraphLab系统的高级概述。用户首先在一个分布式文件系统(DFS)构建原子图表示。如果使用hash分区，构造过程是Map-Reduceable过程，执行对每个顶点和边map，每个reduce聚集一个原子文件。原子格式允许将来的改变，通过附加图数据，而不会再操作所有数据。

图5(b)提供了一个高水平的概述GraphLab锁定引擎的实现。一个集群上GraphLab启动时，每台机器上执行GraphLab程序的一个实例。GraphLab过程是同步的，并且使用一个自定义异步基于TCP / IP的RPC协议直接沟通。第一个进程是一个额外的责任主/监控机器。

主进程在启动时会根据原子序列计算原子的位置，所有进程执行一个被指派给他们的原子进行并行加载。每个流程负责管理分区的本地图存储的分布式图，并提供分布式锁。一个缓存用于提供对远程图数据的访问。

每个进程也包含一个调度程序，管理已经分配给进程的顶点。在运行时，每台机器的当地调度器将顶点放入预取管道，收集所需的数据和顶点的锁执行。一旦所有数据和锁已经获得，顶点操作由一个工作线程池完成。顶点调度被分散到每个机器，管理本地顶点的调度和转发请求远程顶点的调度。最后，一个分布式共识算法\[26\]用于确认所有调度器是否为空。由于分布式运行时的对称设计，没有集中的瓶颈。

## 5.CONCLUSIONS AND FUTRUE WORK  ##

最近MLDM研究的进展已经强调，在大规模MLDM问题中稀疏计算依赖性，异步计算，动态调度和可串行化。 我们描述了最近的分布式抽象如何不能支持所有三个关键属性。 为了解决这些属性，我们引入了Distributed GraphLab，一种图形并行分布式框架，它针对MLDM应用的这些重要属性。分布式GraphLab通过改进执行模型，放宽调度需求以及引入新的分布式数据图，执行引擎和容错系统，将共享内存GraphLab抽象扩展到分布式设置。

我们设计了一个基于两阶段分区方案的分布式数据图形格式，该格式允许在可变大小的集群部署中实现高效的负载平衡和分布式入口。我们设计了两个GraphLab引擎：部分同步并假定存在图着色的一个色引擎，以及完全异步的锁引擎，支持通用图结构，并依赖于一种基于图形的新型流水线锁定系统来隐藏网络潜伏。 最后，我们引入了两种容错机制：基于Chandy-Lamport快照的同步快照算法和完全异步快照算法，可以使用常规GraphLab基元表示。

我们使用C++实现分布式GraphLab，并使用真实数据在三种最先进的MLDM算法上对其进行评估。评估是在Amazon EC2上使用64台HPC机器中的512个处理器执行的。 我们证明Distributed GraphLab的性能比Hadoop高出20-60倍，并且与定制的MPI实现相竞争。 我们比较了PageRank，LoopyBP和ALS的BSP（Pregel）实现，并展示了如何支持动态异步计算可显着提高收敛性。

未来的工作包括扩展抽象和运行时，以支持图形数据库中动态演化的图形和外部存储。这些功能将使Distributed GraphLab能够连续存储和处理在许多真实世界的应用程序（例如社交网络和推荐系统）中常见的时间演进数据。最后，我们认为动态异步图并行计算将成为大规模机器学习和数据挖掘系统的关键组件，因此对这些技术的理论和应用的深入研究将有助于定义新兴的大学学习领域。

参考文献

\[1\] R. Angles and C. Gutierrez. Survey of graph database models.*ACM Comput.Surv.*, 40(1):1:1–1:39,2008.

\[2\] A. Asuncion, P. Smyth, and M. Welling. Asynchronous distributedlearning of topic models. In *NIPS*, pages 81–88.2008.

\[3\] D. Batra, A. Kowdle, D. Parikh, L. Jiebo, and C. Tsuhan.iCoseg:Interactive co-segmentation with intelligent scribble guidance. In *CVPR*, pages 3169 –3176, 2010.

\[4\] D. P. Bertsekas and J. N. Tsitsiklis. *Parallel and distributed computation:numerical methods*. Prentice-Hall, Inc., 1989.

\[5\] A. Carlson, J. Betteridge, B. Kisiel, B. Settles, E. R. H. Jr.,and T.M. Mitchell. Toward an architecture for never-ending language learning. In *AAAI*, 2010.

\[6\] K. M. Chandy and L. Lamport. Distributed snapshots:determining globalstates of distributed systems. *ACM Trans.Comput. Syst.*, 3(1):63–75, 1985.

\[7\] R. Chen, X. Weng, B. He, and M. Yang. Large graph processing in thecloud. In *SIGMOD*, pages 1123–1126, 2010.

\[8\] C.-T. Chu, S. K. Kim, Y.-A. Lin, Y. Yu, G. Bradski, A. Y. Ng,and K.Olukotun. Map-reduce for machine learning on multicore. In *NIPS*, pages 281–288. 2006.

\[9\] J. Dean and S. Ghemawat. Mapreduce: simplified data processing onlarge clusters. In *OSDI*, 2004.

\[10\] B. Efron, T. Hastie, I. M. Johnstone, and R. Tibshirani. Least angleregression. *Annals ofStatistics*, 32(2):407–499,2004.

\[11\] G. Elidan, I. McGraw, and D. Koller. Residual Belief Propagation:Informed scheduling for asynchronous message passing. In *UAI*, pages 165–173, 2006.

\[12\] J. Gonzalez, Y. Low, A. Gretton, and C. Guestrin. Parallel gibbssampling: From colored fields to thin junction trees. In *AISTATS*, volume 15, pages 324–332, 2011.

\[13\] J. Gonzalez, Y. Low, and C. Guestrin. Residual splash for optimallyparallelizing belief propagation. In *AISTATS*,volume 5, pages 177–184, 2009.

\[14\] J. Gonzalez, Y. Low, C. Guestrin, and D. O’Hallaron.Distributed parallelinference on large factor graphs. In *UAI*,2009.

\[15\] H. Graf, E. Cosatto, L. Bottou, I. Dourdanovic, and V.Vapnik.Parallel support vector machines: The cascade SVM. In *NIPS*,pages 521–528, 2004.

\[16\] D. Gregor and A. Lumsdaine. The parallel BGL: A generic library fordistributed graph computations. *POOSC*, 2005.

\[17\] A. Gupta, J. Hennessy, K. Gharachorloo, T. Mowry, and W.-D.Weber.Comparative evaluation of latency reducing and tolerating techniques. *SIGARCHComput. Archit. News*,19(3):254–263, 1991.

\[18\] B. Hindman, A. Konwinski, M. Zaharia, and I. Stoica. A commonsubstrate for cluster computing. In *HotCloud*, 2009.

\[19\] M. Isard, M. Budiu, Y. Yu, A. Birrell, and D. Fetterly.Dryad:distributed data-parallel programs from sequential building blocks. In *EuroSys*, pages 59–72, 2007.

\[20\] U. Kang, C. E. Tsourakakis, and C. Faloutsos. Pegasus: A peta-scalegraph mining system implementation and observations. In *ICDM*, pages 229 –238, 2009.

\[21\] G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregulargraphs. *J. ParallelDistrib. Comput.*,48(1):96–129, 1998.

\[22\] S. Lattanzi, B. Moseley, S. Suri, and S. Vassilvitskii. Filtering:amethod for solving graph problems in mapreduce. In *SPAA*,pages 85–94, 2011.

\[23\] J. Leskovec. Stanford large network datasetcollection.http://snap.stanford.edu/data/index.html, 2011.

\[24\] Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M.Hellerstein. Graphlab: A new parallel framework for machine learning. In *UAI*, pages 340–349, 2010.

\[25\] G. Malewicz, M. H. Austern, A. J. Bik, J. Dehnert, I. Horn, N.Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing.In *SIGMOD*, pages 135–146, 2010.

\[26\] J. Misra. Detecting termination of distributed computations usingmarkers. In *PODC*, pages 290–294, 1983.

\[27\] R. Nallapati, W. Cohen, and J. Lafferty. Parallelized variational EMfor latent Dirichlet allocation: An experimental evaluation of speed andscalability. In *ICDM Workshops*, pages 349–354, 2007.

\[28\] R. Neal and G. Hinton. A view of the EM algorithm that justifiesincremental, sparse, and other variants. In *Learning in graphical models*, pages 355–368. 1998.

\[29\] Neo4j. http://neo4j.org, 2011.

\[30\] D. Newman, A. Asuncion, P. Smyth, and M. Welling.Distributedinference for latent dirichlet allocation. In *NIPS*,pages 1081–1088, 2007.

\[31\] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citationranking: Bringing order to the web. Technical Report 1999-66, Stanford InfoLab,1999.

\[32\] R. Pearce, M. Gokhale, and N. Amato. Multithreaded Asynchronous GraphTraversal for In-Memory and Semi-External Memory. In *SC*, pages 1–11, 2010.

\[33\] R. Power and J. Li. Piccolo: building fast, distributed programs withpartitioned tables. In *OSDI*, 2010.

\[34\] A. G. Siapas. *Criticality and parallelism in combinatorial optimization*. PhD thesis, Massachusetts InstituteofTechnology, 1996.

\[35\] A. J. Smola and S. Narayanamurthy. An Architecture for Parallel TopicModels. *PVLDB*, 3(1):703–710, 2010.

\[36\] S. Suri and S. Vassilvitskii. Counting triangles and the curse of thelast reducer. In *WWW*, pages 607–614,2011.

\[37\] J. W. Young. A first order approximation to the optimum checkpointinterval. *Commun. ACM*, 17:530–531, 1974.

\[38\] M. Zaharia, M. Chowdhury, M. Franklin, S. Shenker, and I. Stoica.Spark: cluster computing with working sets. In *HotCloud*, 2010.

\[39\] Y. Zhang, Q. Gao, L. Gao, and C. Wang. Priter: a distributed frameworkfor prioritized iterative computations. In *SOCC*, pages 13:1–13:14, 2011.

\[40\] Y. Zhou, D. Wilkinson, R. Schreiber, and R. Pan. Large-scale parallelcollaborative filtering for the netflix prize. In *AAIM*,pages 337–348, 2008.

[20180613130545358]: /images/20220522/b26c61a2083e4f19bb2db47d4ccabe77.png
[20180613130556828]: /images/20220522/94e475590a83485186e5108c50356dc8.png
[20180613130610943]: /images/20220522/67188262245d4d27bd34de9f43307b1a.png
[20180613130618328]: /images/20220522/dae7744dfd964b37b4994b47ecf5f49e.png
[20180613130628157]: /images/20220522/1f81ef15947c419e8f4032fcd824b5ec.png
[20180613130635650]: /images/20220522/9fe5ce170ada4e86b8dbbfc662ad1130.png
[20180613130647290]: /images/20220522/ca821c419d3f44b3a9e7584c54e6eebd.png
[20180613130656345]: /images/20220522/62f07807ac1a47c496016f41346db0f7.png
[20180613130704488]: /images/20220522/066cb70d82484597842a68423bb968b7.png
[20180613130712393]: /images/20220522/c03cf46aa3fa40e3bbe3d82e417a6867.png
[20180613130722424]: /images/20220522/6948d3a580354cc58b7c73e77aa089d2.png
[20180613130730978]: /images/20220522/f5459b2ceb424f7c99ccad254369155d.png
[20180613130742459]: /images/20220522/c6ce1285af834ed48edebdb4b5b37c67.png
[20180613130754168]: /images/20220522/7ef19b70d057450e8e704370d51046b4.png