TuX²：面向机器学习的分布式图计算系统

2017 年 4 月 10 日 微软研究院AI头条

当下，机器学习的技术成果已经深入到了我们生活中的各个方面。从网页检索系统，到电影书籍推荐系统、广告展示系统……这些看似隐形却又存在感十足的技术无一不得到了机器学习的支撑。可以这么说：没有计算机技术的发展，就不会有这些智能服务的高效便捷。

从理论到应用并非一步之遥

在人们计算体验改善的过程中，算法的进步自然功不可没。例如，话题模型（topic-modeling）、点击率预测（click-through prediction）等一系列算法的出现与不断优化，使得例如推荐系统等信息服务的质量逐步提高。但是，在海量的数据规模上，要应用这些算法以解决问题，仅有理论是远远不够的。我们显然不能指望单台计算机运行串行程序来维持当今互联网级别的计算和服务。而随着数据内容的增长和用户量的剧增，更多的信息也使得我们面临的挑战愈加严峻。因此为了不断应对新时期信息处理规模的需要，从科学研究到工程实践，分布式计算的相关理论都得到了长足的发展，多个分布式系统先后涌现。它们将规模庞大的计算机联合起来，从而有效地解决大规模的计算问题。其中，图计算系统就是其中一只重要的分支，从Pregel到GraphLab再到PowerGraph，她们解决的问题范围逐步增大，性能也不断提升。

从图的视角看问题

而介绍图计算系统，首先我们会问：什么是图呢？图（Graph），将信息中的实体，以及实体之间的关系，分别抽象表达成为顶点以及顶点间的边这样的结构数据。图计算系统就是主要针对图结构数据处理的系统，并在这样的数据上进行针对性优化的高效计算。

我们处理机器学习的问题时，为什么会考虑到用图计算系统呢？

首先，从其本质上来讲，我们机器学习中需要处理的很多信息是由实体和关系构成的。例如：用户和电影就是实体，他们之间的喜好构成了实体间的关系；搜索查询和商品也是实体，他们之间的点击率构成了实体间的关系……

下图表示了如何将逻辑回归（LR: Logistic Regression）计算抽象成图计算。其中的绿色和黄色顶点分别表示样本（sample）和特征（feature），而联结它们的蓝色边则是 “样本具有特征” 关系。样本点上具有标签y，特征上具有权重w，而LR的目的就是希望通过回归计算不断更新各个w，从而得到适合该模型的权重w，以便通过此模型为只具有特征关系的样本预测标签。

将逻辑回归抽象成图计算

其次，这样的抽象会使我们有机会更有效地处理。图计算系统已经在处理这样的图数据的长期实践中积累了大量的经验。图计算系统可以利用图结构的特性，有效地进行数据存储和调度执行。譬如，我们可以通过基于图的划分方法将数据更平均的分发给多台机器，让他们并行执行，保证各机器的负载均衡，并且可以根据图的结构信息来更好的安排数据的存放以改进计算时的数据局部性，从而带来更高的性能。

TuX²

诸如PageRank这样的应用，传统的图计算系统已经可以很高效地处理了。用户可以利用系统提供的编程模型接口实现相应算法的逻辑，然后将数据灌入系统运行即可。然而，许多常用的机器学习应用并不能直接采用传统的例如PowerGraph这样的系统。这是因为，与传统的图计算应用相比，许多机器学习应用处理数据有着不同于传统图算法的模式。例如小分批（mini-batch）和延时同步并行（SSP: Stale Synchronous Parallel）。前者需要按照指定的批量为单位处理数据，而后者是一种区别于传统的图计算中纯同步/纯异步当中的一种同步方式。这都需要对传统图计算系统进行重新设计，从而支持相应的功能。而这些重新设计的挑战在某种意义上也是机会——我们可以利用这些机器学习应用共同的内在属性，从而提高算法的执行效率。

因此，基于分布式图计算系统的经验和机器学习应用的理解，我们提出了分布式机器学习系统——图学习TuX²（Tu Xue Xi）。TuX²作为一个全新的分布式图引擎，致力于融合图计算和分布式机器学习系统。TuX²继承了传统图计算系统中的优势：简洁的计算模型，高效的数据排布，均衡的负载分配以及超过10亿条边的规模处理能力；并对于分布式机器学习进行了大幅扩展和优化，以支持异质性、延时同步并行（Stale Synchronous Parallel），并提出了一种新的编程模型——MEGA（Mini-batch, Exchange, GlobalSync, Apply）。

性能

我们在TuX²上实现了一系列具有代表性的分布式机器学习算法，涵盖了监督学习和非监督学习。通过与机器学习系统的对比，我们发现实现相同的算法，TuX²只需要约25%的代码量，因为我们的图计算模型从开发者手中接管了很多琐碎的处理细节，包括数据排布、数据划分和并行。在640亿条边的大规模数据上的多个实验结果充分表明，相比于目前最先进的图计算系统PowerGraph和PowerLyra，TuX²具有一个量级上的性能优势，并且与参测的两个目前最先进的分布式机器学习系统相比，实现了至少48%的性能提升。

相关论文

本文所介绍的工作发表于会议14th USENIX Symposium on Networked Systems Design and Implementation （NSDI 2017）: TuX²: Distributed Graph Computation for Machine Learning》Wencong Xiao, Jilong Xue, Youshan Miao, Cheng Chen, and Ming Wu, Wei Li, Lidong Zhou。（请点击阅读原文或将网址复制至浏览器中打开即可查看：https://www.usenix.org/conference/nsdi17/technical-sessions/presentation/xiao）

关于微软亚洲研究院系统组

微软亚洲研究院系统组从事计算机系统领域重大课题的基础性研究，在分布式系统、存储系统、云计算、网络、及计算机语言等方面均有理论与实践经验丰富的专家。自成立以来，系统组一直致力于设计、开发、分析、优化大规模分布式系统，其中一些系统已经在微软产品中应用，支持各种在线服务。系统组成员在此过程中收获了宝贵的第一手实践经验，而这些经验更进一步激发了一系列新的研究项目，并在计算机系统及相关领域的顶级会议上收获丰富成果。微软亚洲研究院系统组多项工作发表于OSDI、SOSP、NSDI、EuroSys、SoCC、USENIX ATC等一系列高水平学术会议上。

你也许还想看：