TuX2：用于机器学习的分布式图计算

$Tu{X}^2$：用于机器学习的分布式图计算

$Tu{X}^2$: Distributed Graph Computation for Machine Learning 本文载于第14届USENIX网络系统设计与实现研讨会论文集（NSDI’17）

摘要

TUX2是一种新型的分布式图形引擎，它将图形计算和分布式机器学习联系起来。TUX2继承了优雅的图形计算模型、高效的图形布局和平衡的并行性的优点，可扩展到数十亿个边的图；我们将其扩展和优化用于分布式机器学习，以支持异构性、过时的同步并行模型和新的MEGA（Mini-batch、Exchange、GlobalSync和Apply）模型。

我们在TUX2开发了一套具有代表性的分布式机器学习算法，包括有监督学习和无监督学习。与分布式机器学习平台上的实现相比，在TUX2中编写这些算法只需要大约25%的代码：我们的图计算模型向开发人员隐藏了对数据布局、分区和并行性的详细管理。我们对TUX2进行了广泛的评估，使用了多达640亿条边的大型数据集，结果表明TUX2的性能比最先进的分布式图形引擎PowerGraph和PowerLyra高出一个数量级，同时击败了两个最先进的分布式机器学习系统至少48%。

引言

分布式图形引擎，例如Pregel [30]，PowerGraph [17]和PowerLyra [7]，都采用顶点程序抽象来表示大规模图形的迭代计算。图引擎有效地编码了图结构中的数据索引，以加快沿边的基于图遍历的数据访问，并支持优雅的图计算模型，例如Gather-Apply-Scatter（GAS），以简化编程。大量的研究[7、18、22、24、32、33、36、39、46、47]致力于通过数据布局，分区，调度和平衡并行性来开发高度可伸缩和高效的图形引擎。已经表明，对于简单的图算法（例如PageRank），分布式图形引擎可以处理到具有超过一万亿个边的图形[10，43，38]。

图形引擎（例如GraphLab [29]）的早期工作是由机器学习推动的，其基础是观察到许多机器学习问题可以用图自然有效地建模，并可以通过迭代收敛算法解决。但是，在图形引擎上的大多数后续工作都采用了简单的图形计算模型，该模型由基本的图形基准（例如PageRank）驱动。最终的图形引擎缺乏灵活性和其他关键功能，无法进行高效的分布式机器学习。

我们提出了TUX2，一个用图模型表示的机器学习算法的分布式图引擎。TUX2保留了图形计算的优点，同时也支持过时的同步并行（SSP）模型[20，11，42，13]，异构数据模型，以及用于高效分布式机器学习的新的MEGA（Minibatch，Exchange，GlobalSync，and Apply）图模型。我们使用代表性的分布式机器学习算法，包括矩阵因子分解（MF）、潜在Dirichlet分配（LDA）和块近端梯度（BlockPG），在具有多达640亿条边的合成和真实数据集上对32个机器（具有500多个物理核）的分布式集群上的TUX2的性能进行了评估，涵盖有监督和无监督学习。与最先进的分布式机器学习平台如Petuum[20,44]和Parameter Server[26]相比，TUX2中的图形模型显著减少了开发人员为算法编写的代码量（减少了73–83%）。它还支持基于自然图的优化，如顶点切割，以实现平衡的并行性。我们的评估表明，TUX2的性能优于最先进的图形引擎PowerGraph和PowerLyra一个数量级以上，这主要是因为我们的异构巨型图模型。由于一系列基于图的优化，TUX2还比Petuum和Parameter Server至少高出48%。

作为我们的主要贡献之一，TUX2在一个统一的模型中连接了两个基本上并行的研究线程，即图计算和基于参数服务器的分布式机器学习，这两个方面都是最先进的。TUX2在三个关键维度上显著扩展了图形引擎的功能：数据表示和数据模型、编程模型和执行调度。我们提出了一组具有代表性的机器学习算法，用于评估图引擎在机器学习应用中的应用，引导图引擎解决分布式机器学习的实际挑战，从而在实践中得到更广泛的应用。我们还通过对大规模实际工作负载的广泛评估，证明了分布式机器学习中图形计算模型在可编程性、可扩展性和效率方面的显著优势。
论文的其余部分安排如下。x2提供了图形计算和机器学习的概述，强调了它们之间的联系。x3描述了TUX2的设计。x4介绍了三种机器学习算法，详细介绍了它们在TUX2中的表达和实现；x5讨论了TUX2的实现和评估。我们在x6中讨论相关工作，在x7中总结。

结论

通过TUX2，我们提倡图计算和分布式机器学习的收敛性。TUX2不仅展示了这种融合的可行性，而且展示了这种融合的潜力，代表了朝这个方向迈出的关键一步。我们通过将重要的机器学习概念引入到图计算中，定义一个新的、灵活的图模型来有效地表达机器学习算法，并通过对典型机器学习算法的广泛评估来证明其优点。展望未来，TUX2将为图形计算和分布式机器学习的进一步研究提供共同的基础，允许更多的机器学习算法和优化在规模上容易且有效地表达和实现。

内容

1.机器学习图

在本节中，我们着重介绍将抽象化成图模型的好处，展示如何将大量的机器学习算法映射到图模型，并概述为什么现有的图引擎在表达性和效率上不足以支持这些算法。

图并行抽象 图并行抽象将数据建模为图G = {V，E}，其中V为顶点集，E为边集。提供了一个顶点程序P，以便在每个顶点v∈V上并行执行并与相邻实例P（u）交互，其中（u，v）∈E。该顶点程序通常维护与顶点关联的特定于应用程序的状态并带有边，在相邻顶点之间交换状态值，并在图形计算期间计算新值。它通常在迭代中进行，并且在使用批量同步并行（BSP）模型时，会在每次迭代结束时引入同步屏障。通过使用图模型来约束顶点程序的节点之间的交互，这种抽象使底层系统可以将数据索引编码为图结构，从而允许沿边进行快速数据访问。尽管顶点程序设计的实际形式可能有所不同，但许多现有的最先进的图形引擎都采用了这种并行的顶点程序方法。如PowerGraph [17]中所定义，顶点程序分为三个阶段：聚集，应用和分散。对于每个顶点u，聚集阶段通过可交换和关联的广义求和函数收集有关u的相邻顶点和边缘的信息。然后，此阶段的结果将在Apply阶段中使用，以更新u的状态。最后，分散阶段使用u的新状态更新其相邻边。

使用诸如GAS之类的图形模型，图形算法可以简洁地用三个函数表示，而不必担心管理数据布局和分区，或担心在多核和多台机器上安排并行执行。然后，图形引擎可以明智地优化数据布局以进行有效的图形数据访问，以减少跨核或跨服务器通信的方式对数据进行分区，并实现平衡的并行性以实现缩放和效率。例如，PowerGraph引入了顶点切割，以实现图形数据的均衡分区，即使对于幂律图，也可以提高可伸缩性。根据我们的经验，这些优化对于机器学习算法是有效的。此外，每个引擎只需实现一次即可，而无需为每个算法重复实现。

图的机器学习 机器学习广泛应用于网络搜索、推荐系统、文档分析和计算广告。这些算法通过训练由特征组成的数据样本来学习模型。机器学习的目标通常可以通过一个目标函数来表达，而目标函数的参数代表一个模型。这个目标函数捕捉学习模型的属性，例如在预测给定用户的搜索查询时用户单击广告的概率时所产生的错误。学习算法通常最小化目标函数来获得模型。它从初始模型开始，然后通过处理训练数据（可能多次）迭代地细化模型。

许多机器学习问题可以用图自然有效地建模，并用迭代收敛算法求解。例如，在推荐系统中经常使用的矩阵分解（MF）算法[16]可以建模为在二分用户-项目图上的计算，其中每个顶点对应于用户或项目，每条边对应于用户对项目的评分。另一个例子是，像LDA这样的主题建模算法在文档-单词图上执行操作，其中文档和单词是顶点。如果一个文档包含一个单词，那么它们之间就有一个边；该边上的数据是文档中该单词的主题。对于许多描述为稀疏矩阵计算的机器学习算法，计算通常可以很容易地转换为稀疏矩阵的图形表示。例如，在Logistic回归（LR）中，模型的参数保持在一个权重向量中，每个元素都是相应特征的权重。每个训练样本都是一个稀疏的特征向量，每个元素都是特定特征的值。整个训练样本集可以看作一个稀疏矩阵，其中一个维度是样本，另一个维度是特征。如果样本i包含特征j的值，则矩阵的元素（i，j）就是该值。因此，数据也可以建模为一个以样本和特征为顶点的图。权值是与特征顶点相关的数据，每个训练样本中的特征值是边上的数据。图1说明了如何用图形对MF和LR进行建模。

差距 即使可以将这些机器学习算法植入图模型中，我们仍会观察到当前图引擎中的空白，从而无法自然有效地支持它们。这些差距涉及数据模型，编程模型和执行计划。

数据模型：标准图模型假设一组同构的顶点，但是对机器学习问题建模的图通常自然会具有不同类型的顶点，它们扮演着不同的角色（例如，用户顶点和项目顶点）。异构感知的数据模型和布局对性能至关重要。

编程模型：对于机器学习计算，图形计算的迭代可能涉及不同类型的顶点之间的多轮传播，而不是简单的一系列GAS阶段。标准GAS模型无法有效表达这种计算模式。对于LR就是这种情况，首先将特征顶点的数据（权重）传播到样本顶点以计算目标函数，然后将梯度传播回特征顶点以更新权重。在GAS中实施此流程将不必要地需要两个连续的GAS阶段，并且有两个障碍。

执行调度：机器学习框架已从Stale同步并行（SSP）模型中受益，SSP模型是一种宽松的一致性模型，具有一定的陈旧性，可以改善并行性。这是因为机器学习算法通常会根据目标函数描述收敛到“良好”解决方案的过程，并且收敛过程本身对于变化和松弛具有鲁棒性，可以利用这些变化和松弛来提高效率和并行度。小型批处理是另一个重要的调度概念，通常用于随机梯度下降（SGD）中，其中一小批样本被一起处理以提高效率，但代价是迭代次数较慢。最小批量大小是这些算法的重要参数，需要进行调整以找到最佳平衡。图形引擎通常在单个顶点[29]上运行，或在整个图形[30]上定义“迭代”或批处理，而小批处理提供介于两者之间的附加灵活性。

因此，TUX2支持并优化数据模型中的异构性，倡导一种新的图形模型，该模型允许灵活地组合阶段，并在执行调度中支持SSP和小型批处理。

2.TUX2设计

TUX2旨在保留图引擎的优势，同时扩展其数据模型，编程模型和调度方法，以服务于分布式机器学习。

TUX2使用顶点切割方法，其中（高度）顶点的边集可以分为多个分区，每个分区都维护该顶点的副本。这些副本之一称为主副本。它维护顶点数据的主版本。所有其余的副本称为镜像，每个副本都维护本地缓存的副本。我们采用了“顶点切割”，因为事实证明它可以有效地处理幂律图，并且可以自然地连接到参数服务器模型[26，11]：所有顶点数据的主版本都可以视为（分布式）全局状态存储在参数服务器中。在每个分区中，TUX2在单独的数组中维护顶点和边。边数组中的边按源顶点分组。每个顶点都有一个索引，该索引给出了其边集在边数组中的偏移量。每个边包含信息，例如包含目标顶点的分区的ID和该顶点在相应顶点数组中的索引。该图形数据结构针对遍历进行了优化，并使用查找表胜过了顶点索引。

每个分区由一个进程管理，该进程在逻辑上既充当工作角色，枚举分区中的顶点并沿边传播顶点数据，又充当服务器角色，以同步镜像顶点及其对应的主节点之间的状态。在进程内部，TUX2使用多个线程进行并行化，并将分区的服务器角色和工作角色分配给同一线程。然后，每个线程负责枚举镜像顶点的子集以进行本地计算，并维护该进程拥有的分区中主顶点子集的状态。图2显示了如何在TUX2中对数据进行分区，存储和分配给执行角色。

异构数据布局

传统图引擎仅假设同构图，而TUX2在数据布局的多个维度（包括顶点类型和分区方法）中支持异构性。它甚至支持主顶点和镜像顶点数据类型之间的异构性。在我们的评估（x5.2）中，对异构性的支持转化为显着的性能提升（40％）。

我们强调对二部图的优化，因为许多机器学习问题自然会映射到具有两个不相交的顶点集的二部图，例如MF中的用户和项，LR中的特征和样本，等等。因此，两组顶点通常具有不同的属性。例如，对于LR，只有特征顶点包含权重字段，而只有样本顶点包含目标标签字段。而且，在像BlockPG [27]这样的LR变体中，特征顶点也保留了额外的历史信息。因此，TUX2允许用户定义不同的顶点类型，并将不同类型的顶点放置在单独的数组中。这导致紧凑的数据表示，从而提高了计算期间的数据局部性。此外，不同的顶点类型可能具有极大不同的程度。例如，在用户项目图中，项目顶点可以链接到成千上万的用户，但是用户顶点通常仅链接到数十个项目。

TUX2使用PowerLyra[7]和BiGraph[8]中提出的二部图感知划分算法，因此只有高阶顶点具有镜像版本。

在二部图中，TUX2可以通过只扫描一种类型的顶点来枚举所有边。选择要枚举的类型有时会对性能产生重大影响。只要TUX2能够识别出具有更新的镜像集以与主镜像同步，那么以小批量的方式扫描顶点往往会导致更有效的同步步骤，因为这些顶点是连续放置在一个数组中的。相反，如果TUX2在一个小批量中扫描没有镜像的顶点，那么在扫描过程中为其他顶点类型更新的镜像将被分散，因此定位成本更高。因此，TUX2允许用户指定在计算期间要枚举的顶点集。

图3以用户项图上的MF为例说明了TUX2如何组织二分图的顶点数据。由于用户顶点的阶数通常要小得多，因此只有项目顶点通过顶点切割分割来分割。因此，服务器角色中的主顶点数组仅包含项顶点，而worker角色仅管理用户顶点。这样，就不需要用户顶点的镜像副本，也不需要分布式同步。在worker角色中，项和用户顶点的镜像存储在两个单独的数组中。

该图还显示了在小批量中扫描项目顶点的好处。如图3（a）所示，这将导致更新后的镜像顶点连续地位于项目顶点数组中。因此，TUX2只需重新扫描该数组的相应范围，就可以很容易地识别它们以进行主镜像同步。相反，在小批量中扫描用户顶点需要额外的索引结构来标识镜像更新。这是因为它们分散在项目顶点数组中，如图3（b）所示。这样的索引结构会带来额外的开销。

另一种异构性来自于对顶点的主副本和镜像副本执行的不同计算，这可能需要不同的数据结构来提高同步效率。例如，BlockPG算法在一个小批量中访问和更新一个特征块的权重，而在样本顶点计算的目标函数可能依赖于不在该块中的特征的权重。这就产生了镜像上的辅助特征顶点属性，记录特征权重的历史增量，以增量计算目标函数的值。但是，主机上不需要这个delta属性，因此在同步期间不需要交换。类似地，主顶点还保留一些镜像上不需要的额外属性。因此，TUX2允许用户为同一顶点的主副本和镜像副本定义不同的数据结构。

使用SSP调度

TUX2支持Stale Synchronous Parallel（SSP）模型[11]，具有有限的过时性和小批量。SSP基于每时钟工作的概念，其中一个时钟对应于由一组并发任务执行的小批量的迭代。迭代批处理可以看作是每次迭代使用所有输入数据的一种特殊情况。SSP引入了一个显式slack参数，它在时钟中指定任务的全局共享状态视图的过时程度。因此，时差决定了任何任务都可以比最慢的任务提前多远。如果slack为s，那么在时钟t的任务可以保证看到从时钟1到t-s-1的所有更新，并且可以看到从时钟t-s到t-1的更新。图4演示了一个slack为1的SSP执行。

TUX2在指定大小的小批量上执行每个迭代。每个工作线程首先选择一组顶点或边作为当前要执行的小批处理。在小批量执行完成后，TUX2通常通过继续枚举顶点或边数组的连续段，为下一个小批量获取另一组顶点或边。TUX2支持小批量粒度的SSP。它跟踪每个小批量迭代的进度，以便能够计算时钟。如果所有工作线程上相应的小批量已完成（包括主服务器和镜像之间的同步），并且生成的更新已应用于状态并反映在状态中，则工作线程认为时钟t已完成。一个worker只有在知道t-s-1之前的所有时钟都已完成时，才能在时钟t执行任务，其中s是允许的时差。

TUX2中的MEGA模型

TUX2引入了一个新的基于阶段的MEGA模型，其中每个阶段都是对一组顶点及其图形边缘的计算。每个阶段都有用户定义的函数（UDF），可将其应用到在此阶段访问的顶点或边上。 TUX2支持四种类型的阶段：Mini-batch，Exchange，GlobalSync和Apply（因此称为MEGA）。它允许用户构造任意的阶段序列。该引擎负责在每个阶段中调度UDF在多个内核和/或机器上的并行执行。

MEGA模型保留了GAS模型的简单性，同时引入了额外的灵活性以解决GAS模型在支持机器学习算法方面的不足。例如，在诸如MF和LDA之类的算法中，处理边涉及更新两个顶点。这需要两个GAS阶段，但可以在我们的模型的一个Exchange阶段中完成。对于LR，在两个方向上的顶点数据传播都应跟随一个Apply阶段，但是没有Scatter阶段是必需的。在MEGA模型中可以避免这种情况，因为MEGA允许任意阶段顺序。接下来，我们将详细介绍不同类型的阶段。

Exchange：此阶段枚举一组顶点的边，采用具有以下签名的UDF：

Exchange（Du，au，D（u，v），a（u，v），Dv，av，t）

Exchange（）在每个枚举的边上执行。 Du和Dv分别是顶点u和v的数据。 D（u，v）是与边（u，v）关联的数据。 au，av和a（u，v）是顶点和边缘数据的相应累积增量，t是与每个工作线程相关联的用户定义的共享上下文，并在整个计算执行期间维护。所有这些参数都允许在此UDF中进行更新。用户可以使用它为顶点和边生成新的累积增量，或直接更新其状态。给定顶点切割图的位置，Exchange（）只能更新顶点的镜像版本数据（即本地状态）。用户还可以使用t来计算和存储一些特定于算法的非图形上下文数据，这些数据可以通过全局聚集来共享。默认情况下，未指定用于枚举的顶点受顶点级别的锁保护，但是TUX2还允许用户为某些应用程序实现自己的无锁语义[14、21、37]。该阶段比GAS模型中的“收集” /“分散”阶段更加灵活，因为它不暗示或不强制沿边的顶点数据传播方向，并且可以更新同一UDF中两个顶点的状态。从而提高了LDA和MF等算法的效率。

Apply：此阶段枚举一组顶点并同步其主版本和镜像版本。 对于每个顶点，主服务器从镜像中累积增量，调用Apply（Du，au，t）更新其全局状态，然后更新镜像上的状态。 为了支持主服务器和镜像服务器之间的异构性，TUX2允许用户为需要同步的顶点的全局状态定义基类VertexDataSync。 母版和镜像可以定义不同的子类，每个子类都继承自基类，以包含其他信息。 引擎仅在主顶点和镜像顶点之间同步VertexDataSync中的数据。

GlobalSync：此阶段负责跨工作线程同步上下文t和/或跨一组顶点聚合数据。 此阶段有三个UDF：

ti + 1←Aggregate（Dv，ti）

tl←Combine（ti，tj）

ti+1←Apply（ti）

Aggregate（）将顶点间的数据聚合到工作程序上下文t中。 Combine（）将跨工作程序的上下文t聚合到一个特殊的工作程序中，该工作程序为不同的时钟维护上下文t的多个版本以支持SSP。 Apply（）最终确定全局汇总的t（例如，用于重新缩放）。 执行Apply（）之后，最终的汇总t将同步回所有工作进程。 如果未提供Aggregate（）函数，则此阶段将仅在工作进程之间聚合并同步上下文t。

Mini-Batch：这是一个包含其他stage序列的复合stage；它定义了为每个Mini-Batch迭代执行的stage。MiniBatch根据每个小批量中要枚举的顶点或边的数量定义小批量大小，如果是二部图，则定义要枚举哪种类型的顶点（参见x4中的示例）。

今天的文章TuX2：用于机器学习的分布式图计算分享到此就结束了，感谢您的阅读。