分布式系统和机器学习-文献阅读报告

摘要

我选择的20篇文章主要关注分布式系统，以及分布式系统在机器学习中的应用。分布式系统是计算机科学历史悠久的一个研究方向，设计一个分布式系统需要考虑许多方面的因素，例如进程的交互与通信协议、故障处理及容错机制、数据复制及一致性等。经过学界多年的研究，针对这些问题，已经有了比较好的解决方案。而在当下，机器学习正迅速发展，越来越多的数据以及规模越来越大的模型，都使得在分布式环境中训练机器学习模型成为一大主流趋势。如何针对机器学习应用设计分布式系统，从而加速机器学习应用的训练过程，成为现在研究的热潮。 2018年在斯坦福举行的全新学术会议SysML，就着眼于机器学习和系统这个交叉学科，使得这个领域受到越来越多的关注。通过这次的文献阅读，我们将会看到，适用于机器学习的分布式系统与传统的分布式系统有许多内在关联，但同时，机器学习应用的一些内在特点使其不同于传统的并行程序，如何针对机器学习应用的特点设计分布式系统，充满了新的挑战。

Abstract

The 20 articles I chose mainly focused on distributed system and its application in machine learning. Distributed system is a research field with a long history in computer science. Designing a distributed system requires consideration of many factors, such as process interaction and communication protocols, fault tolerance mechanisms, data replication, and data consistency. After years of research, there have been lots of good solutions to these problems. At the moment, machine learning is developing rapidly. More data and larger models have made the training of machine learning models in a distributed environment a mainstream. SysML, a new academic conference held at Stanford in 2018, focused on the interdisciplinary field of machine learning and systems, which has attracted more and more attention in this field. Through this literature reading, we will see that the distributed system for machine learning has many internal relations with the traditional distributed system, but at the same time, some inherent characteristics of machine learning applications make it different from traditional parallel programs. How to design a distributed system for machine learning applications is full of challenges.

我选择的20篇文章可以分为以下四类：

• 分布式系统领域的经典文章。这部分文章大多都已经入选ACM SIGOPS名人堂。SIGOPS名人堂奖是SIGOPS组织于2005年设立的奖项，每年都会评选几篇发表了10年以上，对系统领域产生了巨大影响的文章。我选择的文章包括Leslie Lamport关于分布式系统中的时间[19]以及Paxos协议[20]的两篇文章，以及MapReduce[1]、Spark[2]这样著名的工作和来自工业界三篇文章[16] [17] [18]；

• 著名的分布式机器学习系统。其中包含了Google的DistBelief[3]、Microsoft的Adam[4]、CMU的GraphLab[5]、Parameter Server[6]和一个CPU集群上的分布式框架[7]；

• 分布式机器学习算法的设计。其中包括并行的随机梯度下降算法[9]、中心化和去中心化算法的对比[13]以及Stale Synchronous Parallel算法[14]；

• 机器学习与系统结合的一些文章[8] [10] [11] [12] [15]。

分布式系统领域的经典文章

许多分布式系统领域的经典文章，其包含的思想可以对我们设计具体的分布式系统或算法起到指导作用。 本章节的内容包括MapReduce和Spark两大分布式编程框架，Google的Chubby锁服务，Microsoft的DryadLINQ分布式并行计算系统，Amazon的Dynamo分布式存储系统，以及Leslie Lamport对分布式系统时钟的经典论述和对Paxos协议的详细刻画。

MapReduce

MapReduce[1]是Google提出的针对大规模数据进行计算的编程框架。MapReduce对程序模型的抽象非常简单，将程序分为Map和Reduce两个阶段，Map要做的工作就是把数据转换成key-value的形式，而Reduce则会对Map输出的key-value进行聚合操作。每一个Map 和Reduce操作都可以运行在分布式集群中的任何一个节点上，而用户不需要考虑具体的任务分配细节。MapReduce通过隐藏编程框架背后复杂的并行化机制、容错机制、数据局部性优化和负载均衡等实现细节，仅仅向程序员提供一个简单明了的编程接口，使得编写大型分布式程序更加容易。程序员需要关心的只有Map和Reduce这两个函数功能的实现。

在MapReduce之前也有一些并行程序框架，但这些框架都只是在小规模集群上进行了实现，没有扩展到大规模集群，同时，MapReduce提供了一个带有容错功能的实现，而其他框架没有解决容错的问题。River是一个提供负载均衡的编程框架，其负载均衡是通过调度磁盘和网络带宽的占用，而MapReduce通过限制编程模型，从而可以更加容易地把任务划分为更细粒度的子任务，实现负载均衡。

MapReduce对“掉队者”的处理如下：一旦一个Worker完成了它所有的计算任务，且没有新任务可以调度，Master就会把仍然还在别的Worker上计算的任务再次调度给空闲节点，这些任务叫做“备份任务”，一旦备份任务先完成，就把这个任务标记为完成，不再等待“掉队”的节点，避免掉队者拖慢整体任务的完成时间。

Spark

Spark[2]的提出，是为了解决MapReduce访存开销大的问题。因为MapReduce没有对分布式内存进行抽象，每次Map和Reduce计算完成后，会把结果写回分布式存储中，以供下次再使用，对于一些数据重用率比较高的程序，例如机器学习和图算法，包括PageRank, K-means 聚类和逻辑斯蒂回归等，以及交互式的数据挖掘任务，就会产生大量的网络传输和磁盘读写开销。

Spark的作者因此提出了Resilient Distributed Datasets（RDD），一种分布式内存抽象。RDD可以帮助程序员在大规模集群上实现in-memory的计算，通过把数据保存在内存中来提高运算效率，并保证容错性。Spark则是对RDD的一个具体实现。

RDD实现更高性能的核心是通过对数据的操作模式进行更多的限制来得到更高的效率，比如RDD只适用于粗粒度、批处理的数据，不能实现对任意位置数据的任意读写，但正因批处理，使得RDD在容错处理、故障恢复时更加高效。同时，RDD的数据是不可修改的，这使得处理掉队者的问题时也很简单，类似MapReduce，直接发起“备份任务”重新对掉队者的任务进行计算即可。

Chubby

接下来我阅读了几篇来自工业界的研究成果，其中包括Google的Chubby锁服务、Amazon的Dynamo分布式存储系统以及Microsoft的DryadLINQ。正如Google在介绍Chubby的文章中所说，这些工业界的学术成果，大多不含有令人耳目一新的设计，其使用的技巧基本都是学术界已有的成果，这些工作更偏重于工程实现，而非学术研究。但是阅读工业界的论文让我看到了如何解决实际部署系统时所遇到的在设计阶段没有设想到的问题，这是十分有意义的。

Chubby[16]是Google提出的分布式锁服务，其本质上是一个分布式的文件系统。服务调用者可以通过读写文件的方式实现加锁和释放锁。并且在Google的GFS中，Chubby还被用来选择master server，以及用于存储少量的元数据。Chubby的系统架构包括一个Chubby cell以及客户端的Chubby library。Chubby cell是一个分布式的文件系统，由多个server组成，客户端的Chubby library通过RPC与Chubby cell进行通信。在Chubby cell内部的多个server之间，通过一致性协议选择一个server作为master，只有master server会处理用户请求，其余server则用于数据备份。

作者使用了较多的篇幅分析之所以通过这样一个分布式锁服务来实现节点之间的一致性，而不是实现一个分布式一致性协议库的原因。因为通过这样的一个锁服务，可以更容易保持已有程序的结构以及数据传输的模式，不需要对程序本身进行过多的修改，并且在一致性协议中，往往要求节点要能存储和读取小规模的数据，Chubby本身就是文件系统，使得这一点更加容易。并且，分布式一致性算法往往通过一种选举机制来做决定，这要求系统中有比较多的可用节点，但通过锁服务，即使系统中只有一个节点，也能安全地推进程序的执行。同时，Chubby采用了粗粒度加锁，作者的考虑是，采用粗粒度的锁服务，不仅能减少Chubby cell的负载，同时也能更加容易地应对server的故障。而细粒度的锁服务，一旦server出现故障，将会造成大量进程阻塞，反而降低整个系统的性能。

Dynamo

Dynamo[18]是Amazon提出的分布式key-value存储服务。Dynamo从Amazon面临的实际问题出发，通过牺牲一定的一致性，实现了系统更高的可用性。在Dynamo之前，工业界的系统大多使用关系型数据库来存储信息，但Amazon发现在他们的应用场景中，关系型数据库复杂的query语句并不常用，大多数应用只会用到数据库的主键进行查询。因此Amazon提出了简单的key-value存储系统来满足大量的简单查询操作。

Dynamo通过一致性哈希算法将数据分布在不同的机器上。所有的机器组成一个哈希环，每个机器负责自己到下一个机器之间对应的哈希值。每当有数据要被存入，用其key值计算出一个哈希值，将这个数据的key-value对存入对应的机器，并将备份存入后续几个机器。除此之外，Dynamo也综合使用了大量的分布式系统中的技巧来提高系统的可用性和可扩展性：通过quorum算法以及去中心化的同步策略来保证备份之间的数据一致性，以及通过gossip算法来实现分布式的错误检测。

DyradLINQ

DryadLINQ[17]是Microsoft提出的用于在大规模数据和大规模分布式集群上进行高效计算的框架。其中，Dryad是一个分布式的数据并行程序执行框架，LINQ则是对Microsoft .NET语言的扩展，赋予了.NET语言query的特性。DryadLINQ能够自动地把通用编程语言下的命令式程序编译为能在大规模集群上执行的分布式程序。这个系统的目标是，让程序员只需要编写在单个计算机上执行的程序，让系统来处理并行、调度、分布式和容错的问题。

DryadLINQ的执行流程如下：用户编写.NET程序，创建DryadLINQ object，然后DryadLINQ会将程序编译为分布式的Dryad 执行计划（execution plan），将原程序拆分为多个子程序并生成相应的代码，每个子程序将运行在不一样的Dryad节点，接下来DryadLINQ唤起一个Dryad任务管理器，任务管理器将初始化任务的数据流图，并将任务调度到集群的服务器上，同时任务管理器提供了容错机制，会重新执行故障节点上的任务或者掉队者的任务。任务管理器也会根据用户定义的策略来动态调整任务图。DryadLINQ最大的优势在于，通过添加对任何一种编程语言的扩展，就能轻松实现对这种编程语言的程序的分布式计算，同时LINQ强大的静态数据类型使得对程序debug非常容易。

分布式系统中的时钟和事件顺序

Leslie Lamport是2013年图灵奖得主，他的许多工作对分布式系统领域有着非常重要的影响。这次文献阅读，我选择了他的两篇著名文章，分别对分布式系统中的时间以及Paxos协议进行了详细的阐述。

文章[19]显示定义了分布式系统中的偏序关系，然后引入逻辑时钟，逻辑时钟的提出是为了与现实世界的物理时钟进行区分，因为在计算机系统中，很多时候只要知道事件发生的先后关系即可，并不需要知道对应的物理时间，因此在多个节点之间进行时间同步时，只需要在事件发生的先后关系上进行同步，而不是在物理时间上进行同步。作者通过一个分布式算法来把偏序关系扩展到分布式系统中所有事件的全序关系，有了全序关系就能比较容易地解决分布式系统常常面临的复杂的同步问题。

然而仅仅有全序关系仍然可能出现一些“异常情况”，作者举的例子是用户A在一个互联网络发布一条消息，然后打电话给用户B，让用户B也发布一条消息，此时消息B有可能得到比消息A更小的时间戳。也就是说，全序关系并不能完全确定两个事件发生的绝对先后关系，因此作者引入了物理时钟，通过一定的限制条件，可以保证事件发生的绝对先后关系。

除此之外，这篇文章还给出了分布式系统的一个定义：

A system is distributed if the message transmission delay is not negligible compared to the time between events in a single process.

作者从消息传递延迟的角度对分布式系统下定义，抓住了分布式系统的核心特征。

兼职议会与Paxos协议

Lamport的另一篇文章： The Part-Time Parliament[20]，分析了Paxos小岛上的兼职议会系统，从而提出了一些新的思路来设计分布式系统。这篇文章的立足点在于，Paxos小岛上的议会系统与计算机中的分布式系统有很多可以对应上的特点。例如，Paxos的议会系统由很多个立法者组成，每个立法者相当于分布式系统中的一个进程，由于Paxos小岛上每个立法者都需要从事商业活动，因此只能兼职担任立法者，当立法者离开议会大厅，相当于一个进程发生故障。由于议会大厅比较吵，立法者之间不能通过“演讲”传递信息，只能通过消息员在立法者之间传递信息，这也对应了分布式系统中的点对点通信。每个立法者有一个自己的法令记录册，所有立法者必须保证每个法令记录册的一致性，这对应了分布式系统中的数据一致性。

这篇文章的绝大部分篇幅在讲解Paxos小岛上的议会是如何从一次通过一个法令的教会发展为一次通过多个法令的兼职议会，并对每一次议会的协议提供了理论上的一致性证明，以及对议会发展过程中遇到的问题和Paxos岛民的解决方案进行阐述，文章并没有对Paxos一致性协议本身进行阐述，但我们仍然能从Paxos岛民的经验中获得一些启示。例如，他们如何定义“大多数”立法者，这个概念，起初，他们通过重量来决定，后来基于立法者的参会历史为每个立法者赋予一个“虚拟重量”，这个思想其实跟我们对分布式节点定义权重或对操作系统进程定义优先级十分相似。起初Paxos立法者每次提出一条法令，为了通过这条法令需要与其他立法者发生好几次消息传输：首先需要知道其他立法者的上一次投票法令编号，然后发送开始投票信息，接收到其他立法者投票的信息后，还需要发送是否通过法令的结果信息。消息传输的开销十分巨大，后来他们精简了消息传输，例如一条消息包含好几条法令，并且合并上一轮的结果消息和下一轮的开始消息，大大减少了消息传递次数，这一点跟我们在分布式系统中对消息进行压缩以及合并发送的思想也十分相似。

文章最后用短短的篇幅介绍了Paxos议会和计算机领域的状态机以及三阶段提交协议的关联，我觉得Paxos议会所包含的分布式系统设计思想还有更多的内容可以深入分析。

著名的分布式机器学习系统

这一部分的文章主要是利用传统分布式领域的思想来构建用于机器学习应用的大规模分布式系统。其中许多工作都来自产业界，已经被实际部署并验证其性能。我将从这几个分布式系统被提出的时间顺序来依次分析。

GraphLab

CMU于2010年提出了GraphLab[5]。GraphLab是针对通用机器学习算法提出的高性能并行计算框架，通过利用机器学习算法中的稀疏结构和常见的计算模式，大大提升了机器学习算法的并行计算性能。

GraphLab主要由四部分组成：① 数据模型。GraphLab将计算任务抽象为一个有向数据图，以及一个共享数据表；② 用户定义的计算。包括update function和sync mechanism，分别对应MapReduce中的Map和Reduce。但跟MapReduce不同的是，update function可以访问并修改计算图中的信息，而且sync mechanism可以和update function并行执行；③ 数据一致性。包括三个程度的数据一致性，分别是full consistency, edge consistency 和 vertex consistency，用户可以根据应用的具体需要进行选择；④ 调度器。GraphLab针对不同的算法选择不同的调度器，并且允许用户自定义新的调度算法。

GraphLab相对于已有的分布式计算框架的优势是，可以表达有计算依赖的算法，MapReduce没有提供对迭代式算法的支持，无法实现这一点。并且MapReduce针对大型的数据中心的应用进行了非常多的优化，当我们把MapReduce应用到小型的集群或者多处理器的系统，这些优化的性能开销就变得非常大，GraphLab则显得更加轻量级。除此之外，在一些框架中，并行计算被表示为有向无环图，然而有向无环图不能表示迭代式的算法，因为图结构依赖于迭代的次数。另一种Systolic抽象，是扩展版的有向无环图，可以表达迭代式算法，但是不能表达大多数机器学习算法中的参数更新调度。

DistBelief

Google于2012年提出了DistBelief[3]，这是TensorFlow的前身。由于GraphLab是针对通用机器学习算法提出的框架，并没有对神经网络的结构进行分析和优化，DistBelief填补了这一空缺。DistBelief虽然是针对大型神经网络的训练框架，但也能训练中等规模神经网络和任何基于梯度更新的机器学习算法。

这篇文章最大的亮点在于根据神经网络的性质，提出了两个分布式算法，从而提高了分布式神经网络的计算效率。

Downpour SGD：把数据分成几个部分，每个部分上运行模型的一个复制。模型的每个复制通过一个中心化的参数服务器交换参数更新。同时这个中心化的参数服务器是分片化的，由很多个机器组成，每个机器管理一部分的参数。因此这个算法中的异步性存在于两个层面：模型的每个复制是异步、独立运行的，参数服务器的每个分片是独立、异步更新的。这样的异步SGD也比同步SGD更容易处理分布式集群的故障问题。

Sandblaster L-BFGS：批量训练的算法。一个协调进程负责在参数服务器和工作节点之间调度协调，避免模型在训练时与参数服务器产生大量的传输开销。同时也解决了“掉队者”问题，通过把一个批量的工作分成更细的粒度分发给工作节点，在某台机器空闲时调度给它新的任务，这样性能好的机器就能执行更多的任务，在一个批量的任务快结束时，协调进程还会分发剩余任务的多个副本，接收最快返回的结果。这一点与MapReduce的处理机制类似。同时Sandblaster L-BFGS只需要在每个批量的任务开始前获取一次数据，结束时回传数据，比起Downpour SGD，对带宽的要求更低。

Adam

在2014年的OSDI上，Microsoft和CMU分别提出了一个大规模分布式神经网络训练框架。两篇文章都在前人的工作上针对应用场景中的具体问题，做了大量的细节优化，从而提高分布式神经网络训练的速度。

Microsoft提出了Adam[4]，通过整个系统的协同设计，优化并平衡了计算与数据传输。同时，重构了跨节点的计算，从而减少了传输开销。并且，他们开发了机器学习训练过程中对不一致性的容忍程度，从而提高了训练的性能和扩展性。

Adam整个架构包括3部分：快速的数据供应、模型训练过程的优化、全局的参数服务器。他们的工作主要关注各个环节的计算和数据传输的优化。

在模型训练部分，他们使用了模型并行的机制，对整个神经网络进行垂直划分，他们表示这样划分模型会最小化机器间的数据传输。同时在每个机器内部，使用多线程共享权重进行训练，这一点类似数据并行，但不同于数据并行，因为多线程共享了相同的权重参数，并且通过NUMA- aware allocations来减少多线程访存的冲突。并且，他们让多个线程异步地、无锁地更新权重，这可能引入冲突、可能会更新到较老的权重，但因为神经网络是有弹性的，因此并不会极大程度上影响最终效果。他们还划分模型使其可以被放进L3 cache从而提高了访存带宽。对于掉队者，他们的处理是，对每个epoch当75%的数据处理完毕，就认为这个epoch计算完成，不再等待掉队者的计算结果，实验表明这可以加速计算过程20%并且不会影响模型精度。同时，他们还根据神经网络不同层的特点，设计了与参数服务器更新参数的不同机制，对于卷积层，由于参数量不大，可以每处理k张图片后就把参数更新发到参数服务器，对于全连接层，由于参数量巨大，可以发送梯度向量而不是参数本身，从而减少了数据传输量。

Parameter Server

CMU的工作[6]则更关注参数服务器的设计。他们的框架主要有5大特点：①高效的数据传输。他们使用了一个异步的数据传输模型，针对了机器学习问题进行优化，减少了数据传输的开销和带宽的占用。由于机器学习是迭代式的算法，每次迭代，需要传输的key-value 对基本是一致的，因此接收节点可以保存key list，下次发送节点不再发送key list，而只需要发送一个key list的哈希值。同时，value中可能包含大量的0，可以对消息进行压缩后再发送。② 灵活的一致性模型。他们的框架允许用户针对不同的算法选择不同的一致性模型。还允许用户自定义规则来针对某个具体的key-value对有选择性地同步。例如，只有当某个参数的改变值超过了某个临界值才进行同步。③ 有弹性的可扩展性。新的节点可以随时加入，不需要重启整个框架。④ 容错和耐用性。从机器宕机后恢复的时间很短，并且不会影响计算过程。每个工作节点组有个调度节点，针对节点的删除和加入，会调整对任务的调度。⑤易用性。全局共享参数的数据结构是向量和矩阵，这样的数据结构使得很容易应用高效的、多线程的加速库。对数据还采用了批处理的方法，即对一整个向量或矩阵的一整行进行更新，避免了过多的数据传输开销。

CHAOS

除此之外，我还看到了一篇2019年发表的文章CHAOS[7]，这篇文章是针对CPU集群设计的神经网络训练框架。目前大量的研究都是选择GPU来作为神经网络训练的加速卡，很少有人用CPU来训练大规模的神经网络。这篇文章的关注点其实不在于“分布式”，而在于“并行”，因为文中主要研究了神经网络在CPU上训练时的线程级并行和SIMD并行。这篇文章所采用的线程级并行与分布式训练环境中的工作节点间的并行类似。线程间是数据并行，每个线程独立地从数据集中取数据完成前向计算和后向更新。

CHAOS的全称是Controlled Hogwild with Arbitrary Order of Synchronization。Hogwild是一种异步更新的算法，Controlled Hogwild是指，每次迭代所计算出的参数更新，在本地（当前线程）立即更新，之后再与其他worker（线程）共享更新。每个worker并不等待其他worker发送的更新信息。Arbitrary Order of Synchronization是指，不进行明确的全局更新，可见其实这篇文章的核心思路就是利用神经网络对错误的容忍程度来加速其训练过程。与其他工作不同的是，这篇文章还提出了一个性能模型，用来预测不同卷积网络结构在不同epoch数量和线程数量下的性能。

小结

纵观以上这几个大规模神经网络的训练框架，我最大的感受是，没有特别让人印象深刻的设计，都是针对实际应用场景进行针对性的优化，并且优化的思想大多来自分布式系统领域已有的工作，但他们能够把这些细节的优化协调统一成一个完整的框架，这其中的难度也不容小觑，这就是他们的工作最大的意义。

分布式机器学习训练算法

在机器学习应用中，最常用的训练算法就是随机梯度下降（SGD），为了提高随机梯度下降算法的性能，以及让它适用于分布式的训练环境，许多学者针对这个简单的算法提出了针对分布式环境的改进。这个部分的三篇文章包含大量的理论证明，我将略去不做分析，主要分析他们在将算法扩展到分布式环境时的考虑与取舍。

并行的SGD算法

文章[9]首次提出并行的SGD算法。其主要思路是将SGD与MapReduce结合起来，假设有k台机器，先将所有的数据分成k份，将每份数据放到一台对应的机器上。对应于MapReduce的Map过程的是，每台机器独立地在本地数据上进行随机梯度下降的计算过程，对应于Reduce过程的是，将k台机器的权重取平均，得到最终的权重。这篇文章还对这一算法的正确性提出了理论证明。这个算法的核心思想在于，通过把数据存在每个机器的本地，大大减少了I/O开销和数据传输开销，只需要在最后交换模型的参数信息。因此非常适合用MapReduce来实现。

这篇文章也跟另一种思路进行了对比，另一种思路是将问题划分为多个子问题，每个工作节点对一个子问题进行计算，最终将多个子问题的解进行平均，这个做法能极大程度减少数据传输，但从理论上分析，这种算法得到的结果会存在比较大的方差，影响最终结果的准确性。

Stale Synchronous Parallel算法

文章[14]提出了Stale Synchronous Parallel (SSP)算法，其核心思想就是利用“过期”的参数版本。对SSP算法的一个简单解释如下：假设有P个worker，每个worker都能对一个共享的变量x做更新，每个worker更新的周期是固定的，称为clock。每个worker都有自己的clock，且只会在一个clock结束时对共享变量进行更新。最新的更新不一定会立刻被其他worker看到，也就是说，当一个worker尝试去读取共享变量x的值时，读到的是过期的更新。根据这个观察，worker可以直接从本地cache读取共享变量，不需要等待从参数服务器获取共享变量最新的值。通过用户给定一个staleness 临界值，SSP模型能够最大化每个worker用在有效计算上的时间，并且提供了正确性的保证。

在这篇文章之前已有的算法包括BSP（Bulk Synchronous Parallel）和完全异步更新的算法。作者通过证明表示，SSP能比这两种算法都达到更快的收敛。并且，SSP不会像完全异步更新的算法那样产生大量的访存冲突，从而带来性能下降。

中心化与去中心化算法的对比

中心化的SGD算法往往会包括一个参数服务器，由参数服务器担任所有计算节点的中介，统一收集所有计算节点的梯度值并计算参数更新，再发送给所有计算节点。去中心化的SGD算法则依赖于类似all-reduce的操作在节点之间交换参数更新。

文章[13]从理论上分析、对比了中心化SGD和去中心化SGD。这篇文章指出，使用中心化还是去中心化SGD，取决于很多因素，包括：网络拓扑、带宽、延迟、参数更新频率、容错机制等等。但大部分人都有一种观点，认为去中心化SGD只是在不能使用中心化SGD的情况下的一种妥协，其性能不如中心化SGD，这篇文章指出在某些情况下去中心化算法能达到比中心化算法更好的性能。作者从理论上分析了去中心化算法的可扩展性，发现当更多的节点可用时，去中心化算法可以实现近似线性加速。并且作者在多种机器学习框架和网络上进行了实验，发现去中心化算法在低带宽和高延迟的情况下，能实现相比中心化算法10倍的加速。

机器学习与系统结合的文章

这一部分主要包括几篇不能被分到前几类的文章，它们也基本属于机器学习和系统相结合的工作。

利用GPU实现加速

文章[8]发表于2009年，可能是最早提出用GPU来训练机器学习模型的文章之一。当时大多数工作都还停留于在CPU上训练机器学习模型，并且NVIDIA的生态也还不完善，没有cuDNN这样的针对GPU平台的算法加速库。因此，这篇文章提出用GPU来训练机器学习模型就显得很有前瞻性。这篇文章用到的例子是深度置信网络（DBN）和稀疏编码问题。作者表示，只要使用足够多的训练数据，比较简单的模型也能得到比复杂模型更好的效果。因此提出使用GPU在大规模数据集上训练简单模型来提高模型的精度，同时加速训练过程。

GPU往往有数百个处理单元，并且峰值访存带宽也高于CPU。GPU能并发计算数千个线程，并且调度开销非常小，这样的属性使其很适合作为一个通用的并行计算框架。然而GPU虽然有着非常好的并行特性，但却无法像CPU那样执行通用处理器的程序，因此，这篇文章对机器学习算法进行了一定程度上的重新设计，使其更适合在GPU上运行。

这篇文章的核心思想在于，对于机器学习应用，把所有的参数存在GPU的global memory中，能极大减少数据传输的开销。而训练数据往往不能存在global memory中，但可以按chunk进行分组，减少传输的次数。并且，在当时，已有工作尝试用MapReduce来实现分布式的机器学习算法，但这样的工作也只开发到了数据并行这个级别，而GPU提供的两个层级的架构，可以在block层面用数据并行，而thread层面使用更细粒度的并行。

利用MapReduce实现可扩展性

文章[10]认为，大量的研究工作都使用GPU作为加速卡，但使用GPU很难实现可扩展性，因为GPU的内存有限，而使用MapReduce来并行，就可以利用MapReduce框架内在拥有的数据带宽，实现可扩展性。这篇文章提出了使用MapReduce来训练深度置信网络（DBN）的一种实现。

基于MapReduce框架设计分布式的DBN训练算法，核心在于设计一个Map函数和Reduce函数，以及恰当的key-value对。由于DBN是由多个有限玻尔兹曼机（RBM）堆叠组成的，这篇文章对DBN的训练，包括了对多个RBM的分布式预训练，以及对整个DBN的分布式反向传播训练算法。对每个RBM进行分布式训练时，每个epoch都有一组Map节点，每个Map节点负责一部分数据，计算出参数的更新值后通过key-values发送给reduce节点，再由reduce节点执行参数的更新过程。对DBN的训练也是类似的，Map执行前向计算过程，Reduce执行反向更新过程。这篇文章可以看做是将MapReduce在机器学习场景的一次具体应用，将具体问题和已有框架相结合，没有太多的创新点。

对神经网络的细粒度划分

文章[11]关注的问题是对卷积神经网络进行细粒度的划分，从而提高卷积网络的可扩展性。在此之前，大多数卷积网络主要关注小型的图片输入，例如ImageNet中的每个图片大小为224x224x3，很多网络因此针对这个量级的图片而设计，在进行并行训练时也都基本采用了数据并行，每个计算节点保存一部分数据。但逐渐出现了一些比较大的图片集，使得数据并行不那么有效了，因为单张图片比较大，如果采用数据并行，每个计算节点能保存的数据量就比较小，从而无法实现比较大的batch size 的训练。因此这篇文章提出对卷积网络中的节点进行空间划分，即每个节点处理模型输入数据在空间维度一部分，对于图片数据，就是处理图片的一个子区域。

除此之外，这篇文章还提出了对卷积网络运行时间进行建模的方案，并且将寻找网络最优划分的问题转化为一个图问题，利用启发式规则对每个卷积层生成一些候选划分方式，再使用性能模型对每种划分方式进行时间预测，最后使用图算法寻找最短路径的方式，找到网络的最佳划分方案。

对GPU程序访存模式的研究

文章[12] 指出越来越多的计算任务在多GPU节点上进行，为了能充分利用GPU之间的低延迟和高带宽，程序员往往需要对程序进行精细的划分，充分考虑负载平衡，边界条件以及设备间同步等等问题。这篇文章提出了MAPS-Multi，一个自动的多GPU划分框架，可以根据任务访存的模式把任务划分到多个GPU上。这篇文章在真实应用，例如机器学习上，实现了接近线性的加速比。这篇文章提出了对GPU上的任务其输入和输出访存模式的不同分类，然后实现了一个框架，可以根据这些访存模式，对GPU 核函数进行自动的划分，以及边界值的交换，使得程序员不需要关注底层的细节，在多GPU环境下的编程更加简单。

层级化的参数服务器以及对深度学习性能指标的分析

文章[15] 提出了一个基于参数服务器的分布式深度学习框架，Rudra。并且通过在这个框架中一系列的实验，系统地分析了深度学习问题中两大重要因素，运行时间和模型准确率之间的权衡。分析了同步策略, 陈旧的参数更新, 批大小, 学习率,以及工作节点数量对这两个因素的影响。这篇文章提出了一种动态调整学习率的方式，可以实现模型更快的收敛，提出了一种新的同步机制，可以减少梯度过期对模型准确率的影响，并且文章指出，当工作节点数量增加时，为了保持模型的准确率，要减少minibatch size。

除此之外，这篇文章提出的层级化参数服务器结构Rudra-adv，也十分新颖。通过将参数服务器组织为树狀层级结构，可以减少数据传输开销。为了进一步减少数据传输开销，作者又提出了Rudra-adv* ,直接在所有的训练节点之内构造这个层级化的参数服务器，进一步利用了训练节点之间的连接和带宽。

总结

纵观这20篇文章，我的感受是，分布式系统领域那些许多年前被提出的算法，至今仍然在影响着学术界和工业界对系统的设计。例如在Chubby的设计中，Chubby cell内部的server之间仍然是使用类似Paxos的一致性协议来选举Master server。例如Paxos小岛上那种压缩信息量和减少消息传递次数的思想，仍然能在Adam和CMU的机器学习框架中看到。

当然，对系统设计的权衡也在随着具体场景的变化逐渐发生改变，Lamport在论文中详细刻画了系统的全序关系以及逻辑时钟，研究如何确保分布式系统的一致性，而机器学习领域的研究者对一致性逐渐没有那么苛求，他们发现，容忍一定程度的不一致性反而能带来性能的提升。又比如，在MapReduce这样传统的框架中，为了解决掉队者的问题，他们会把掉队者的任务再次调度给其他节点，力争在保证程序正确性的前提下提高性能，而机器学习科学家们对掉队的节点也没有那么苛责了，他们直接放弃那些掉队节点的结果，发现也能在不损失模型精度的前提下提高性能。

总的来说，我认为，要进行系统领域的研究，吃透这些经典论文的思想是一个前提条件，分布式系统中许多共通的特点可以使我们在设计一个系统时更快地解决那些前人已经分析透彻的问题，而着眼于具体应用场景的特点，设计因地制宜和与时俱进的策略。

参考文献

[1] Dean, Jeffrey & Ghemawat, Sanjay. (2004). MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM. 51. 137-150. 10.1145/1327452.1327492.
[2] Zaharia, M. , Chowdhury, M. , Das, T. , Dave, A. , & Stoica, I. . (2012). Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association.
[3] J. Dean et al. 2012. Large scale distributed deep networks. In Proceedings of the 25th International Conference on Neural Information Processing Systems (NIPS’12), vol. 1. 1223–1231.
[4] T. Chilimbi, Y. Suzue, J. Apacible, and K. Kalyanaraman. 2014. Project adam: Building an efficient and scalable deep learning training system. In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation. 571–582.
[5] Yucheng Low, Joseph Gonzalez, Aapo Kyrola, Danny Bickson, Carlos Guestrin, and Joseph Hellerstein. 2010. GraphLab: a new framework for parallel machine learning. In Proceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence (UAI’10). AUAI Press, Arlington, Virginia, USA, 340–349.
[6] M. Li et al. 2014. Scaling distributed machine learning with the parameter server. In Proceedings of the 11th USENIX Conference on Operating Systems Design and Implementation (OSDI’14). 583–598.
[7] A. Viebke, S. Memeti, S. Pllana, and A. Abraham. 2019. CHAOS: A parallelization scheme for training convolutional neural networks on Intel Xeon Phi. The Journal of Supercomputing 75, 1 (Jan. 2019), 197–227.
[8] R. Raina, A. Madhavan, and A. Y. Ng. 2009. Large-scale deep unsupervised learning using graphics processors. In Proceedings of the 26th Annual International Conference on Machine Learning (ICML’09). 873–880.
[9] M. A. Zinkevich, M. Weimer, A. Smola, and L. Li. 2010. Parallelized stochastic gradient descent. In Proceedings of the 23rd International Conference on Neural Information Processing Systems, vol. 2. 2595–2603.
[10] K. Zhang and X. W. Chen. 2014. Large-scale deep belief nets with MapReduce. IEEE Access 2 (2014), 395–403.
[11] N. Dryden et al. 2019. Improving strong-scaling of CNN training by exploiting finer-grained parallelism. In Proceedings of the 33rd IEEE Int:l Parallel & Distributed Processing Symposium (IPDPS’19).
[12] T. Ben-Nun, E. Levy, A. Barak, and E. Rubin. 2015. Memory access patterns: The missing piece of the multi-GPU puzzle. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’15). 19:1–19:12.
[13] X. Lian et al. 2017. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems 30. MIT Press, 5336–5346.
[14] Q. Ho et al. 2013. More effective distributed ML via a stale synchronous parallel parameter server. In Proceedings of the 26th International Conference on Neural Information Processing Systems, vol. 1 (NIPS’13). 1223–1231.
[15] S. Gupta, W. Zhang, and F. Wang. 2016. Model accuracy and runtime tradeoff in distributed deep learning: A systematic study. In Proceedings of the IEEE 16th International Conference on Data Mining (ICDM’16). 171–180.
[16] Burrows, M. (2006, November). The Chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th symposium on Operating systems design and implementation (pp. 335-350).
[17] Fetterly, Y. Y. M. I. D., Budiu, M., Erlingsson, Ú., & Currey, P. K. G. J. (2009). DryadLINQ: A system for general-purpose distributed data-parallel computing using a high-level language. Proc. LSDS-IR, 8.
[18] DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., … & Vogels, W. (2007). Dynamo: amazon’s highly available key-value store. ACM SIGOPS operating systems review, 41(6), 205-220.
[19] Lamport, L. (2019). Time, clocks, and the ordering of events in a distributed system. In Concurrency: the Works of Leslie Lamport (pp. 179-196).
[20] Lamport, L. (2019). The part-time parliament. In Concurrency: the Works of Leslie Lamport (pp. 277-317).