大规模机器学习框架的四重境界（下）

接《大规模机器学习框架的四重境界（上）》

3.2同步协议

本节假设读者已经对随机梯度优化算法比较熟悉，如果不熟悉的同学请参考吴恩达经典课程机器学习中对SGD的介绍，或者我之前多次推荐过的书籍《最优化导论》。

我们先看一个单机算法的运行过程，假设一个模型的参数切分成三个分片k1，k2，k3；比如你可以假设是一个逻辑回归算法的权重向量被分成三段。我们将训练样本集合也切分成三个分片s1，s2，s3；在单机运行的情况下，我们假设运行的序列是（k1，s1）、（k2，s1）、（k3、s1）、（k1、s2）、（k2、s2）、（k3、s2）。。。看明白了吗？就是假设先用s1中的样本一次对参数分片k1、k2、k3进行训练，然后换s2；这就是典型的单机运行的情况，而我们知道这样的运行序列最后算法会收敛。

现在我们开始并行化，假设k1、k2、k3分布在三个server node上，s1、s2、s3分布在三个worker上，这时候如果我们还要保持之前的计算顺序，则会变成怎样？work1计算的时候，work2和worker3只能等待，同样worker2计算的时候，worker1和work3都得等待，以此类推；可以看出这样的并行化并没有提升性能；但是也算简单解决了超大规模模型的存储问题。

为了解决性能的问题，业界开始探索这里的一致性模型，最先出来的版本是前面提到的[11]中的ASP模式，就是完全不顾worker之间的顺序，每个worker按照自己的节奏走，跑完一个迭代就update，然后继续，这应该是大规模机器学习中的freestyle了，如图所示

ASP的优势是最大限度利用了集群的计算能力，所有的worker所在的机器都不用等待，但缺点也显而易见，除了少数几个模型，比如LDA，ASP协议可能导致模型无法收敛。也就是SGD彻底跑飞了，梯度不知道飞到哪里去了。

在ASP之后提出了另一种相对极端的同步协议BSP，spark用的就是这种方式，如图所示

每个worker都必须在同一个迭代运行，只有一个迭代任务所有的worker都完成了，才会进行一次worker和server之间的同步和分片更新。这个算法和严格一直的算法非常类似，区别仅仅在于单机版本的batch size在BSP的时候变成了有所有worker的单个batch size求和得到的总的butch size替换。毫无疑问，BSP的模式和单机串行因为仅仅是batch size的区别，所以在模型收敛性上是完全一样的。同时，因为每个worker在一个周期内是可以并行计算的，所以有了一定的并行能力。

以此协议为基础的spark在很长时间内成为机器学习领域实际的霸主，不是没有理由的。此种协议的缺陷之处在于，整个worker group的性能由其中最慢的worker决定；这个worker一般称为straggler。读过GFS文章的同学应该都知道straggler的存在是非常普遍的现象。

能否将ASP和BSP做一下折中呢？答案当然是可以的，这就是目前我认为最好的同步协议SSP；SSP的思路其实很简单，既然ASP是允许不同worker之间的迭代次数间隔任意大，而BSP则只允许为0，那我是否可以取一个常数s？如图所示

不同的worker之间允许有迭代的间隔，但这个间隔数不允许超出一个指定的数值s，图中s=3.

SSP协议的详细介绍参见[14]，CMU的大拿Eric Xing在其中详细介绍了SSP的定义，以及其收敛性的保证。理论推导证明常数s不等于无穷大的情况下，算法一定可以在若干次迭代以后进入收敛状态。其实在Eric提出理论证明之前，工业界已经这么尝试过了：）

顺便提一句，考察分布式算法的性能，一般会分为statistical performance和hard performance来看。前者指不同的同步协议导致算法收敛需要的迭代次数的多少，后者是单次迭代所对应的耗时。两者的关系和precision\recall关系类似，就不赘述了。有了SSP，BSP就可以通过指定s=0而得到。而ASP同样可以通过制定s=∞来达到。

3.3核心技术

除了参数服务器的架构、同步协议之外，本节再对其他技术做一个简要的介绍，详细的了解请直接阅读沐帅的博士论文和相关发表的论文。

热备、冷备技术：为了防止server node挂掉，导致任务中断，可以采用两个技术，一个是对参数分片进行热备，每个分片存储在三个不同的server node中，以master-slave的形式存活。如果master挂掉，可以快速从slave获取并重启相关task。

除了热备，还可以定时写入checkpoint文件到分布式文件系统来对参数分片及其状态进行备份。进一步保证其安全性。

Server node管理：可以使用一致性哈希技术来解决server node的加入和退出问题，如图所示

当有server node加入或退出的时候，server manager负责对参数进行重新分片或者合并。注意在对参数进行分片管理的情况下，一个分片只需要一把锁，这大大提升了系统的性能，也是参数服务器可以实用的一个关键点。

4. 大规模机器学习的四重境界

到这里可以回到我们的标题了，大规模机器学习的四重境界到底是什么呢？

这四重境界的划分是作者个人阅读总结的一种想法，并不是业界标准，仅供大家参考。

境界1：参数可单机存储和更新

此种境界较为简单，但仍可以使用参数服务器，通过数据并行来加速模型的训练。

境界2：参数不可单机存储，可以单机更新

此种情况对应的是一些简单模型，比如sparse logistic regression；当feature的数量突破百亿的时候，LR的权重参数不太可能在一台机器上完全存下，此时必须使用参数服务器架构对模型参数进行分片。但是注意一点，SGD的更新公式

w’=w-α

，其中

可以分开到单个维度进行计算，但是单个维度的w i =f(w)x i

这里的f(w)表示是全部参数w的一个函数，具体推倒比较简单，这里篇幅所限就不赘述了。只是想说明worker在计算梯度的时候可能需要使用到上一轮迭代的所有参数。

而我们之所以对参数进行分片就是因为我们无法将所有参数存放到一台机器，现在单个worker有需要使用所有的参数才能计算某个参数分片的梯度，这不是矛盾吗？可能吗？

答案是可能的，因为单个样本的feature具有很高的稀疏性（sparseness）。例如一个百亿feature的模型，单个训练样本往往只在其中很小一部分feature上有取值，其他都为0（假设feature取值都已经离散化了）。因此计算f(w)的时候可以只拉取不为0的feature对应的那部分w即可。有文章统计一般这个级别的系统，稀疏性往往在0.1%（or 0.01%，记得不是很准，大致这样）以下。这样的稀疏性，可以让单机没有任何阻碍的计算f(w)。

目前公司开源的angel和AILab正在做的系统都处于这个境界。而原生spark还没有达到这个境界，只能在中小规模的圈子里厮混。Angel改造的基于Angel的Spark则达到了这个境界。

境界3：参数不可单机存储，不可单机更新，但无需模型并行

境界3顺延境界2二来，当百亿级feature且feature比较稠密的时候，就需要计算框架进入到这层境界了，此时单个worker的能力有限，无法完整加载一个样本，也无法完整计算f(w)。怎么办呢？其实很简单，学过线性代数的都知道，矩阵可以分块。向量是最简单的矩阵，自然可以切成一段一段的来计算。只是调度器需要支持算符分段而已了。

境界4：参数不可单机存储，不可单机更新，需要模型并行

进入到这个层次的计算框架，可以算是世界一流了。可以处理超大规模的神经网络。这也是最典型的应用场景。此时不仅模型的参数不能单机存储，而且同一个迭代内，模型参数之间还有强的依赖关系，可以参见姐夫对distbelief的介绍里的模型切分。

此时首先需要增加一个coordinator组件来进行模型并行的concurrent控制。同时参数服务器框架需要支持namespace切分，coordinator将依赖关系通过namespace来进行表示。

一般参数间的依赖关系因模型而已，所以较难抽象出通用的coordinator来，而必须以某种形式通过脚本parser来生产整个计算任务的DAG图，然后通过DAG调度器来完成。对这个问题的介绍可以参考Erix Xing的分享[5]。

Tensorflow

目前业界比较知名的深度学习框架有Caffee、MXNet、Torch、Keras、Theano等，但目前最炙手可热的应该是google发布的Tensorflow。这里单独拿出来稍微分解下。

前面不少图片引自此文，从TF的论文来看，TF框架本身是支持模型并行和数据并行的，内置了一个参数服务器模块，但从开源版本所曝光的API来看，TF无法用来10B级别feature的稀疏LR模型。原因是已经曝光的API只支持在神经网络的不同层和层间进行参数切分，而超大规模LR可以看做一个神经单元，TF不支持单个神经单元参数切分到多个参数服务器node上。

当然，以google的实力，绝对是可以做到第四重境界的，之所以没有曝光，可能是基于其他商业目的的考量，比如使用他们的云计算服务。

综上，个人认为如果能做到第四重境界，目前可以说的上是世界一流的大规模机器学习框架。仅从沐帅的ppt里看他曾经达到过，google内部应该也是没有问题的。第三重境界应该是国内一流，第二充应该是国内前列吧。

5. 其他

5.1 资源管理

本文没有涉及到的部分是资源管理，大规模机器学习框架部署的集群往往

资源消耗也比较大，需要专门的资源管理工具来维护。这方面yarn和mesos都是佼佼者，细节这里也就不介绍了。

5.2 设备

除了资源管理工具，本身部署大规模机器学习集群本身对硬件也还是有些要

求的，虽然理论上来说，所有commodity机器都可以用来搭建这类集群，但是考虑到性能，我们建议尽量用高内存的机器+万兆及以上的网卡。没有超快速的网卡，玩参数传递和样本加载估计会比较苦逼。

6. 结语

从后台转算法以来，长期沉浸于算法推理的论文无法自拔，对自己之前的后台工程能力渐渐轻视起来，觉得工程对算法的帮助不大。直到最近一个契机，需要做一个这方面的调研，才豁然发现，之前的工程经验对我理解大规模机器学习框架非常有用，果然如李宗盛所说，人生每一步路，都不是白走的。

在一个月左右的调研中，脑子每天都充斥这各种疑问和困惑，曾经半夜4点醒来，思考同步机制而再也睡不着，干脆起来躲卫生间看书，而那天我一点多才睡。当脑子里有放不下的问题的时候，整个人会处于一种非常亢奋的状态，除非彻底想清楚这个问题，否则失眠是必然的，上一次这种状态已经是很多年前了。好在最后我总算理清了这方面的所有关键细节。以此，记之。Carbonzhang于2017年8月26日凌晨！

致谢

感谢wills、janwang、joey、roberty、suzi等同学一起讨论，特别感谢burness在TF方面的深厚造诣和调研。因为本人水平所限，错漏难免，另外还有相当多的细节因为篇幅限制并未一一展开，仅仅是从较高抽象层面上简述了下大规模机器学习框架的关键思路，其他如分片向量锁、通信协议、时钟逻辑、DAG调度器、资源调度模块等均为展开来讲，希望以后有机会能补上。

引用

1. Wide & Deep Learning for Recommender Systems
2. Deep Neural Networks for YouTube Recommendations
3. https://www.zhihu.com/question/53851014
4. TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems
5. http://www.jianshu.com/p/00736aa21dc8
6. Large Scale Distributed Deep Networks
7. MapReduce: Simplified Data Processing on Large Clusters
8. Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
9. https://www.zhihu.com/question/55119470
10. KunPeng: Parameter Server based Distributed Learning Systems and Its Applications in Alibaba and Ant Financial
11. An Architecture for Parallel Topic Models
12. Scaling Distributed Machine Learning with the Parameter Server
13. Piccolo: Building fast, distributed pro- grams with partitioned tables 

14. More Effective Distributed ML via a Stale Synchronous Parallel Parameter Server
15. Angel-A Flexible and Powerful Parameter Server；黄明ppt