Scaling Distributed Machine Learning with the Parameter Server——MIT6.824

发表于

Scaling Distributed Machine Learning with the Parameter Server

这篇论文提出了一种用于解决分布式机器学习问题的参数服务器框架。通过将数据和工作负载均匀地分布在所有工作节点上，服务器节点则用来维护全局共享的参数（即一些向量和矩阵）。这个框架能够很好地管理节点之间的异步数据通信，并保持了灵活的一致性、弹性可伸缩性和容错能力。

这是它的开源实现：https://github.com/dmlc/parameter_server

Introduction

分布式的优化和推理正成为解决大规模机器学习问题的先决条件，因为数据的增长和模型复杂，很难通过单机去快速解决这些问题。因此，如此大量的计算工作和数据都需要仔细的系统设计，

而这些复杂的模型需要在所有工作节点中进行全局共享，由于需要经常访问共享参数，因此这会带来三个挑战：

  • 访问参数需要大量的网络带宽；
  • 许多机器学习算法都是顺序执行的，如果同步和机器延迟成本很高，对性能影响很大；
  • 大规模的容错能力；因为机器学习任务通常在云环境中执行，而云环境不够稳定可靠；

Contributions

参数服务器（Parameter Server）在学术界和工业界已经有了一定的影响力。本文主要描述其第三代开源实现。其注重于分布式推理的实现，提供了5个关键功能：

  1. 高效的通信：使用了不会阻塞计算的异步通信模型；
  2. 灵活的一致性模型：较为宽松的一致性降低了同步成本和延迟；
  3. 弹性可伸缩行：主要是在运行时添加新节点，无需重启；
  4. 容错性和耐用性：秒级恢复故障机器，不会中断计算，并使用向量明确网络分区和故障行为；
  5. 计算更简单：全局共享的参数是向量和矩阵的形式；

Machine Learning

该论文因为要在非常大型的训练数据中证明参数服务器的有效性，因此介绍了两种广泛使用的机器学习技术。

Risk Minimization

risk minimization是机器学习中最直观的一个问题，大概意思就是对预测误差的衡量，即通过risk minimization的模型来预测自变量x的值y。训练数据量与模型大小的有着重要的联系，详细的模型可能提高了准确性，却导致过拟合，反之则可能是欠拟合。为了解决这个问题，则通过正则化来实现在模型复杂度和训练误差之间取得平衡，即最小化训练数据预测误差损失和惩罚模型复杂度的正则器。

虽然这两个对于机器学习算法的性能有着很重要的影响，但不是评估参数服务器的关键，因此这里采用了比较简单的算法，一种叫次梯度的分布式下降算法（ distributed subgradient descent）

在参数服务器中，训练数据分配到所有的worker，共同学习参数向量w。算法在每次迭代的时候，每个worker会独立地使用自己的训练数据来计算Δwi，这就是subgradient，参数向量w的移动方向，然后使用所有的subgradient来表示最终w的梯度。为了快速收敛，需要设计有效的学习率。算法如下所示

img

由于计算梯度的成本比较高，如果w的维度很高的话，计算将无法执行，因此每个worker都需要知道其训练数据所依赖的w的坐标范围，从而减少计算量。

论文的实验结果是，随着worker的增长，单机所需内存也在下降。如下图，对于100个worker，每个worker只需要使用参数的7.8％。拥有10,000名工人，这一比例降低到0.15％。

Generative Models

另一类主要的机器学习算法就是使用非监督算法来捕获数据的基础结构，具体不表，也是通过学习部分参数，然后进行聚合，但可能有点不同的是，有些算法不是使用的梯度下降，而是其它的比较方法。

Architecture

参数服务器可以同时运行多种算法，其将节点分为server group和好几个worker group。如下图所示，server group中的server节点负责维护全局共享的部分参数，而这些节点则通过相互通信完成参数迁移和复制，同时通过维护诸如节点状态和参数分配等原数据的一致性视图。

每个worker都运行一个应用程序，存储着部分的训练数据，worker之间是不能通讯的，只能与server节点交流，从而更新和检索参数。每个worker都有一个叫task scheduler的节点，负责为worker节点分配任务和监视进度。当有workers新增或移除节点·时，task scheduler负责重新分配未完成的任务。

参数服务器支持独立的参数名称空间，也允许多个worker group共享同一个名称空间。

(Key,Value) Vectors

节点之间的共享模型可以表示为一组键值对，并且假设所有的key都是有序的，例如损失函数最小化问题中，键值对是特征ID及其权重，对于LDA，则是单词ID和主题ID以及计数的组合。

Range Push and Pull

参数服务器中，worker与server的节点之间发送数据是通过推拉操作完成的，并且支持基于范围的推拉。worker将计算好的梯度push到server，然后worker从server读取新的参数。

1
2
w.push(R, dest) // 将key范围中w的所有现存项全部发往目的，这里的目的可以是特定节点，也可以是节点组
w.pull(R, dest) // 从目的位置读取key范围中w的所有现存项

User-Defined Functions on the Server

除了从worker聚合数据之外，server节点还可以执行用户自定义的功能，这里的好处是因为server节点往往具有共享参数更加完整更加新的的信息。

Asynchronous Tasks and Dependency

task是通过远程调用发出的，worker向server发出的消息是pull或者push其中一种，也可以是由调度程序发给任何节点的用户自定义功能。另外task可能包含任意数量的子task。

task是异步执行的，发出task之后，caller可以马上执行进一步的计算，caller仅在收到callee答复才能标记任务完成。默认情况下，callee并行执行任务，如果要实现序列化，则可以在task之间执行一个依赖关系。如下图就指示了三个迭代例子，其中10和11是独立的，但12依赖于11，因此callee在10中完成计算局部梯度之后可以立即开始11，但12则需要等到11的计算完成，返回数据之后才能开始。

Flexible Consistency

独立的任务虽然可以通过并行化CPU的使用，磁盘和网络带宽的方式提高系统效率，但也可能带来节点间数据不一致的问题，从而降低算法收敛速度，因此需要在系统效率和算法收敛速度之间进行取舍，但这里的权衡取舍又会依赖于以下几种因素：

  • 算法对数据不一致的敏感度；
  • 训练数据的特征相关性；
  • 硬件组件的容量差异；

参数服务器为算法设计人员提供了定义一致性模型的灵活性，下图就是通过任务依赖关系实现的三种不同模型：

img

Sequential：顺序执行所有任务，当前一个任务执行完成，才能启动下一个任务；

Eventual：所有任务同时执行，这只有在对延时敏感度很robust的算法中才会被使用；

Bounded Delay：就是前两种模型的折衷，即使用一个最大延时t，在t时刻之前完成前一个任务才能启动下一个任务。t=0就是Eventual，t=∞即Sequential；

另外，tasks之间的依赖关系可能是动态的，即可以根据系统情况来改变最大延时以平衡系统效率和优化算法的收敛性。

User-defined Filters

作为调度程序控制流的一个拓展，参数服务器支持用户自定义filter，以选择性地在节点之间同步各个键值对，从而更加细粒度地控制数据。这里的关键是，要明确优化算法本身拥有的跟参数有关的信息是什么。例如有些filter只会push自上次同步依赖变化超过阈值的item，有些则利用filterpush仅仅可能影响server权重的梯度。

Implementation

参数服务器使用一致性哈希来存储参数，并使用链式复制来备份内容，同时对基于key范围的通信进行了优化。

Vector Clock

参数服务器会将每个键值对与矢量时钟关联起来，该时钟会记录每个节点在该键值对上的时间，矢量时钟的一个好处就是可以用来跟踪聚合状态或者是拒绝重复发送数据。但矢量时钟的最初版需要O(mn)的空间来处理n个节点和m个参数，这样的成本太高了。

但由于参数服务器可以进行基于范围的通信模式，这样就会使得许多参数具有相同的时间戳，这样就可以将矢量时钟进行压缩。

一开始，所有的节点都共享一个range vector clock，覆盖了整个参数键空间，其最初的时间戳为0。每个range key都可以抽取子range，并最多创建3个新的矢量时钟，参考下面的算法，这样就可以大大降低参数数量：

Messages

节点可以将消息发送给耽搁节点或者是节点组，一条消息由key范围R中的键值对列表和相关范围的矢量时钟组成，这是参数服务器的基本通信格式，不仅用于共享参数，也会应用于任务。而对于任务，键值对则可能表示为（taskID，参数/返回值）。

参数服务器基本通信格式：[vc(R), (k1,v1), ..., (kp,vp)] kj ∈ R and j ∈ {1,...p}

由于机器学习问题往往需要高带宽，因此需要进行消息压缩：

  1. 如果迭代之间的训练数据保持不变，则可以要求接收节点缓存key列表，以后发送节点只需要发送该key的hash值即可。
  2. 由于键值对的value本身可能包含许多零项，另外用户定义的过滤器也可以将部分值归零，因此可以只发送非零的键值对即可。

Consistent Hashing

参数服务器将key的分区方式是通过将key和服务器节点ID插入到哈希环中，如下：

每个服务器节点管理一定的key范围，每个服务器节点都管理者它按逆时针方向到下一个节点之间的key range，这就是该key range的主节点。同样，每个节点都复制了按逆时针方向的k个节点的key range。另外为了改善平衡和提高恢复效率，物理服务器通过多个"虚拟服务器"在环中表示。例如k=2时，S1就会复制S2和S3管理的key range，这时S1就是这两个key range的slave

Replication and Consistency

Worker仅与该key range的master进行通信，在主server节点的修改和时间戳都需要复制到slave服务器。下面的左图就是这样的一个情况，

Worker1会push x到server1，server1执行完用户自定义函数后同步到slave server2，同步完成后，任务才算结束。

但简单的同步复制可能会使网络流量增加k倍，这对很多依赖于高网络带宽的机器学习应用是很致命的。因此参数服务器框架做了一个重要的优化：聚合后的复制，即servers先聚合从workers接收到的数据后再复制到slaves。如上右图所示，对于n个workers来说，复制带宽将会降低n倍。

Server Management

为了实现容错和动态扩展，参数服务器还必须支持添加和删除节点，为了方便起见，将会引入虚拟服务器。server 节点加入后，将会发生：

  1. server管理器为新节点分配一个key range以用作master节点。这可能会导致另一个key range分裂或者从某个终止节点中删除；
  2. 新加入的节点会获取k个key range，自身成为这些key range的slave；
  3. server管理器广播节点更改，接收方server将移除不属于自己管理的key range的数据，并将未完成的任务重新提交给新节点；

Worker Management

添加新的worker节点与添加server节点类似，但更简单：

  1. task调度器为新节点分配数据范围；
  2. 该节点从网络文件系统或者现有的工作程序中加载训练数据，接下来则是从server节点pull共享参数；
  3. task调度器广播修改，这可能会使部分workers释放部分训练数据；

当worker节点挂掉后，参数服务器提供了选项，用户可以自行控制恢复程序，这是因为：

  • 如果训练数据量巨大，则恢复worker节点可能比恢复server节点的成本更高；
  • 在优化过程中丢失少量训练数据通常只会对模型造成少许影响；

因此，算法设计者可能更喜欢继续操作而不替换失败的工作程序。