1. 布景
自从google宣布闻名的GFS、MR、BigTable三篇paper今后，互联网正式迎来了大数据年代。大数据的显着特点是大，哪里都大的大。本篇首要针对volume大的数据时，运用机器学习来进行数据处理进程中遇到的架构方面的问题做一个体系的整理。
有了GFS咱们有才干堆集海量的数据样本，比方在线广告的曝光和点击数据，天然具有正负样本的特性，累积一两个月往往就能轻松获得百亿、千亿级的练习样本。这样海量的样本怎样存储?用什么样的模型能够学习海量样本中有用的pattern?这些问题不止是工程问题，也值得每个做算法的同学去深化考虑。
1.1简略模型or杂乱模型
在深度学习概念提出之前，算法工程师手头能用的东西其实并不多，就LR、SVM、感知机等聊聊可数、相对固定的若干个模型和算法，那时分要处理一个实践的问题，算法工程师更多的作业首要是在特征工程方面。而特征工程自身并没有很体系化的辅导理论(至少现在没有看到相关的体系介绍的书本)，所以许多时分特征的结构技法显得斑驳陆离，是否有用也取决于问题自身、数据样本、模型以及命运。
在特征工程作为算法工程师首要作业内容的时分，结构新特征的测验往往很大部分都不能在实践作业中work。据我了解，国内几家大公司在特征结构方面的成功率在后期一般不会超越20%。也便是80%的新结构特征往往并没什么正向提高作用。假如给这种办法起一个姓名的话，大概是简略模型+杂乱特征;简略模型说的是算法比方LR、SVM自身并不服务，参数和表达才干根本呈现一种线性联系，易于了解。杂乱特征则是指特征工程方面不断测验运用各种奇技淫巧结构的或许有用、或许没用的特征，这部分特征的结构办法或许会有各种trick，比方窗口滑动、离散化、归一化、开方、平方、笛卡尔积、多重笛卡尔积等等;趁便提一句，由于特征工程自身并没有特别体系的理论和总结，所以初入行的同学想要结构特征就需求多读paper，特别是和自己事务场景相同或相似的场景的paper，从里边学习作者剖析、了解数据的办法以及对应的结构特征的技法;一朝一夕，有望构成自己的常识体系。
深度学习概念提出今后，人们发现经过深度神经网络能够进行必定程度的体现学习(representation learning)，例如在图画范畴，经过CNN提取图画feature并在此根底上进行分类的办法，一举打破了之前算法的天花板，并且是以极大的距离打破。这给一切算法工程师带来了新的思路，已然深度学习自身有提取特征的才干，干嘛还要苦哈哈的自己去做人工特征规划呢?
深度学习尽管必定程度上缓解了特征工程的压力，但这儿要着重两点：1.缓解并不等于完全处理，除了图画这种特定范畴，在个性化引荐等范畴，深度学习现在还没有完全获得肯定的优势;究其原因，或许仍是数据自身内涵结构的问题，使得在其他范畴现在还没有发现相似图画+CNN这样的完美CP。2.深度学习在缓解特征工程的一同，也带来了模型杂乱、不行解说的问题。算法工程师在网络结构规划方面相同要花许多心思来提高作用。归纳起来，深度学习代表的简略特征+杂乱模型是处理实践问题的另一种办法。
两种方式孰优孰劣还难有结论，以点击率猜测为例，在核算广告范畴往往以海量特征+LR为干流，依据VC维理论，LR的表达才干和特征个数成正比，因而海量的feature也完全能够使LR具有满足的描绘才干。而在个性化引荐范畴，深度学习刚刚萌发，现在google play选用了WDL的结构[1]，youtube选用了两层DNN的结构[2]。
不管是那种方式，当模型满足巨大的时分，都会呈现模型参数一台机器无法寄存的状况。比方百亿级feature的LR对应的权重w有好几十个G，这在许多单机上存储都是困难的，大规划神经网络则更杂乱，不只难以单机存储，并且参数和参数之间还有逻辑上的强依靠;要对超大规划的模型进行练习势必要借用散布式体系的技法，本文首要是体系总结这方面的一些思路。
1.2 数据并行vs模型并行
数据并行和模型并行是了解大规划机器学习结构的根底概念，其缘起未深究，榜首次看到是在姐夫(Jeff Dean)的blog里，其时仓促一瞥，以为自己懂了。多年今后，再次开端调研这个问题的时分才想起长者的经历，年轻人啊，仍是图样，图森破。假如你和我相同从前疏忽过这个概念，今日不放温习一下。
这两个概念在[3]中沐帅从前给出了一个十分直观而经典的解说，惋惜不知道什么原因，当我想引用时却发现现已被删除了。我在这儿简略介绍下这个比方：假如要修两栋楼，有一个工程队，怎样操作?榜首个计划是将人分红两组，别离盖楼，改好了就装饰;第二种做法是一组人盖楼，等榜首栋楼盖好，另一组装饰榜首栋，然后榜首组持续盖第二栋楼，改完今后等装饰队装饰第二栋楼。咋一看，第二种办法好像并行度并不高，但榜首种计划需求每个工程人员都具有“盖楼”和“装饰”两种才干，而第二个计划只需求每个人具有其间一种才干即可。榜首个计划和数据并行相似，第二个计划则道出了模型并行的精华。
数据并行了解起来比较简略，当样本比较多的时分，为了运用一切样原本练习模型，咱们无妨把数据散布到不同的机器上，然后每台机器都来对模型参数进行迭代，如下图所示
图片取材于tensorflow的paper[4]，图中ABC代表三台不同的机器，上面存储着不同的样本，模型P在各台机器上核算对应的增量，然后在参数存储的机器上进行汇总和更新，这便是数据并行。先疏忽synchronous，这是同步机制相关的概念，在第三节会有专门介绍。
数据并行概念简略，并且不依靠于详细的模型，因而数据并行机制能够作为结构的一种根底功用，对一切算法都收效。与之不同的是，模型并行由于参数间存在依靠联系(其实数据并行参数更新也或许会依靠一切的参数，但差异在于往往是依靠于上一个迭代的全量参数。而模型并行往往是同一个迭代内的参数之间有强依靠联系，比方DNN网络的不同层之间的参数依照BP算法构成的先后依靠)，无法类比数据并行这样直接将模型参数分片而损坏其依靠联系，所以模型并行不只要对模型分片，一同需求调度器来操控参数间的依靠联系。而每个模型的依靠联系往往并不同，所以模型并行的调度器因模型而异，较难做到完全通用。关于这个问题，CMU的Erix Xing在[5]中有所介绍，感兴趣的能够参阅。
模型并行的问题界说能够参阅姐夫的[6]，这篇paper也是tensorflow的前身相关的总结，其间图
解说了模型并行的物理图景，当一个超大神经网络无法存储在一台机器上时，咱们能够切开网络存到不同的机器上，可是为了坚持不同参数分片之间的一来，如图中粗黑线的部分，则需求在不同的机器之间进行concurrent操控;同一个机器内部的参数依靠，即途中细黑线部分在机器内即可完结操控。
黑线部分怎样有用操控呢?如下图所示
在将模型切分到不同机器今后，咱们将参数和样本一同在不同机器间流通，途中ABC代表模型的不同部分的参数;假定C依靠B，B依靠A，机器1上得到A的一个迭代后，将A和必要的样本信息一同传到机器2，机器2依据A和样本对P2更新得到，以此类推;当机器2核算B的时分，机器1能够打开A的第二个迭代的核算。了解CPU流水线操作的同学必定感到了解，是的，模型并行是经过数据流水线来完结并行的。想想那个盖楼的第二种计划，就能了解模型并行的精华了。
上图则是对操控模型参数依靠的调度器的一个示意图，实践结构中一般都会用DAG(有向无环图)调度技能来完结相似功用，未深化研讨，今后有时机再弥补阐明。
了解了数据并行和模型并行对后边参数服务器的了解至关重要，但现在让我先荡开一笔，简略介绍下并行核算结构的一些布景信息。
2. 并行算法演进2.1MapReduce道路
从函数式编程中的遭到启示，google发布了MapReduce[7]的散布式核算方
式;经过将使命切分红多个叠加的Map+Reduce使命，来完结杂乱的核算使命，示意图如下
MapReduce的首要问题有两个，一是原语的语义过于初级，直接运用其来写杂乱算法，开发量比较大;另一个问题是依靠于磁盘进行数据传递，功用跟不上事务需求。
为了处理MapReduce的两个问题，Matei在[8]中提出了一种新的数据结构RDD，并构建了Spark结构。Spark结构在MR语义之上封装了DAG调度器，极大降低了算法运用的门槛。较长时间内spark简直能够说是大规划机器学习的代表，直至后来沐帅的参数服务器进一步开辟了大规划机器学习的范畴今后，spark才暴露出一点点缺乏。如下图
从图中能够看出，spark结构以Driver为中心，使命调度和参数汇总都在driver，而driver是单机结构，所以spark的瓶颈十分显着，就在Driver这儿。当模型规划大到一台机器存不下的时分，Spark就无法正常运转了。所以从今日的眼光来看，Spark只能称为一个中等规划的机器学习结构。剧透一句，公司开源的Angel经过修正Driver的底层协议将Spark扩展到了一个高一层的境地。后边还会再详细介绍这部分。
MapReduce不只仅一个结构，仍是一种思维，google开创性的作业为咱们找到了大数据剖析的一个可行方向，时至今日，仍不过期。仅仅逐步从事务层下沉究竟层语义应该处于的结构基层。
2.2MPI技能
沐帅在[9]中对MPI的远景做了扼要介绍;和Spark不同，MPI是相似socket
的一种体系同学API，仅仅支撑了音讯播送等功用。由于对MPI研讨不深化，这儿简略介绍下有点和缺点吧;有点是体系支撑，功用刚刚;缺点也比较多，一是和MR相同由于原语过于初级，用MPI写算法，往往代码量比较大。另一方面是根据MPI的集群，假如某个使命失利，往往需求重启整个集群，而MPI集群的使命成功率并不高。阿里在[10]中给出了下图：
从图中能够看出，MPI作业失利的几率挨近五成。MPI也并不是完全没有可取之处，正如沐帅所说，在超算集群上仍是有场景的。关于工业届依靠于云核算、依靠于commodity核算机来说，则显得性价比不够高。当然假如在参数服务器的结构下，对单组worker再运用MPI未尝不是个好的测验，[10]的鲲鹏体系正式这么规划的。
3. 参数服务器演进
3.1前史演进
沐帅在[12]中将参数服务器的前史区分为三个阶段，榜首代参数服务器萌发
于沐帅的导师Smola的[11]，如下图所示：
这个作业中仅仅引进memcached来寄存key-value数据，不同的处理进程并行对其进行处理。[13]中也有相似的主意，第二代参数服务器叫application-specific参数服务器，首要针对特定运用而开发，其间最典型的代表应该是tensorflow的前身[6]。
第三代参数服务器，也便是通用参数服务器结构是由百度少帅李沐正式提出的，和前两代不同，第三代参数服务器从规划上便是作为一个通用大规划机器学习结构来定位的。要脱节详细运用、算法的捆绑，做一个通用的大规划机器学习结构，首要就要界说好结构的功用;而所谓结构，往往便是把许多重复的、琐碎的、做了一次就不想再来第2次的脏活、累活进行杰出而高雅的封装，让运用结构的人能够只重视与自己的中心逻辑。第三代参数服务器要对那些功用进行封装呢?沐帅总结了这几点，我照搬如下：
1)高效的网络通信：由于不管是模型仍是样本都十分巨大，因而对网络通信的高效支撑以及高配的网络设备都是大规划机器学习体系不行短少的;
2)灵敏的一致性模型：不同的一致性模型其实是在模型收敛速度和集群核算量之间做tradeoff;要了解这个概念需求对模型功用的点评做些剖析，暂时留到下节再介绍。
3)弹性可扩展：清楚明了
4)容灾容错：大规划集群协作进行核算使命的时分，呈现Straggler或许机器毛病对错常常见的事，因而体系规划自身就要考虑到应对;没有毛病的时分，也或许由于对使命时效性要求的改变而随时更改集群的机器装备。这也需求结构能在不影响使命的状况下能做到机器的热插拔。
5)易用性：首要针对运用结构进行算法调优的工程师而言，明显，一个难用的结构是没有生命力的。
在正式介绍第三代参数服务器的首要技能之前，先从另一个视点来看下大规划机器学习结构的演进
这张图能够看出，在参数服务器出来之前，人们现已做了多方面的并行测验，不过往往仅仅针对某个特定算法或特定范畴，比方YahooLDA是针对LDA算法的。当模型参数打破十亿今后，则能够看出参数服务器一统江湖，再无敌手。
首要咱们看看第三代参数服务器的根本架构
上图的resourcemanager能够先放一放，由于实践体系中这部分往往是复用现有的资源办理体系，比方yarn或许mesos;底下的training data毋庸置疑的需求相似GFS的散布式文件体系的支撑;剩余的部分便是参数服务器的中心组件了。
图中画了一个servergroup和三个worker group;实践运用中往往也是相似，server group用一个，而worker group按需装备;server manager是server group中的办理节点，一般不会有什么逻辑，只要当有server node参加或退出的时分，为了坚持一致性哈希而做一些调整。
Worker group中的task schedule则是一个简略的使命和谐器，一个详细使命运转的时分，task schedule担任告诉每个worker加载自己对应的数据，然后去server node上拉取一个要更新的参数分片，用本地数据样本核算参数分片对应的改变量，然后同步给server node;server node在收到本机担任的参数分片对应的一切worker的更新后，对参数分片做一次update。
如图所示，不同的worker一同并行运算的时分，或许由于网络、机器装备等外界原因，导致不同的worker的进展是不相同的，怎样操控worker的同步机制是一个比较重要的课题。详见下节分化。
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散布在三个servernode上，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和serve人之间的同步和分片更新。这个算法和严厉一向的算法十分相似，差异仅仅在于单机版别的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不等于无穷大的状况下，算法必定能够在若干次迭代今后进入收敛状况。
趁便提一句，调查散布式算法的功用，一般会分为statistical performance和hard performance来看。前者指不同的同步协议导致算法收敛需求的迭代次数的多少，后者是单次迭代所对应的耗时。两者的联系和precisionrecall联系相似，就不赘述了。有了SSP，BSP就能够经过指定s=0而得到。而ASP相同能够经过拟定s=∞来到达。
3.3中心技能
除了参数服务器的架构、同步协议之外，本节再对其他技能做一个扼要的介绍，详细的了解请直接阅览沐帅的博士论文和相关宣布的论文。
热备、冷备技能：为了避免servernode挂掉，导致使命中止，能够选用两个技能，一个是对参数分片进行热备，每个分片存储在三个不同的server node中，以master-slave的方式存活。假如master挂掉，能够快速从slave获取并重启相关task。
除了热备，还能够守时写入checkpoint文件到散布式文件体系来对参数分片及其状况进行备份。进一步确保其安全性。
Servernode办理：能够运用一致性哈希技能来处理server node的参加和退出问题，如图所示
当有server node参加或退出的时分，servermanager担任对参数进行从头分片或许兼并。留意在对参数进行分片办理的状况下，一个分片只需求一把锁，这大大提高了体系的功用，也是参数服务器能够有用的一个要害点。
4. 大规划机器学习的四重境地
到这儿能够回到咱们的标题了，大规划机器学习的四重境地究竟是什么呢?
这四重境地的区分是作者个人阅览总结的一种主意，并不是业界规范，仅供咱们参阅。
境地1：参数可单机存储和更新
此种境地较为简略，但仍能够运用参数服务器，经过数据并行来加快模型的练习。
境地2：参数不行单机存储，能够单机更新
此种状况对应的是一些简略模型，比方sparse logistic regression;当feature的数量打破百亿的时分，LR的权重参数不太或许在一台机器上完全存下，此刻有必要运用参数服务器架构对模型参数进行分片。可是留意一点，SGD的更新公式
w’=w-α，其间能够分开到单个维度进行核算，可是单个维度的wi=f(w)xi
这儿的f(w)表明是悉数参数w的一个函数，详细推倒比较简略，这儿篇幅所限就不赘述了。仅仅想阐明worker在核算梯度的时分或许需求运用到上一轮迭代的一切参数。
而咱们之所以对参数进行分片便是由于咱们无法将一切参数寄存到一台机器，现在单个worker有需求运用一切的参数才干核算某个参数分片的梯度，这不是对立吗?或许吗?
答案是或许的，由于单个样本的feature具有很高的稀少性(sparseness)。例如一个百亿feature的模型，单个练习样本往往只在其间很小一部分feature上有取值，其他都为0(假定feature取值都现已离散化了)。因而核算f(w)的时分能够只拉取不为0的feature对应的那部分w即可。有文章核算一般这个等级的体系，稀少性往往在0.1%(or 0.01%，记住不是很准，大致这样)一下。这样的系数性，能够让单机没有任何阻止的核算f(w)。
现在公司开源的angel等体系都处于这个境地。而原生spark还没有到达这个境地，只能在中小规划的圈子里鬼混。
境地3：参数不行单机存储，不行单机更新，但无需模型并行
境地3顺延境地2二来，当百亿级feature且feature比较稠密的时分，就需求核算结构进入到这层境地了，此刻单个worker的才干有限，无法完好加载一个样本，也无法完好核算f(w)。怎样办呢?其实很简略，学过线性代数的都知道，矩阵能够分块。向量是最简略的矩阵，天然能够切成一段一段的来核算。仅仅调度器需求支撑算符分段罢了了。
境地4：参数不行单机存储，不行单机更新，需求模型并行
进入到这个层次的核算结构，能够算是国际一流了。能够处理超大规划的神经网络。这也是最典型的运用场景。此刻不只模型的参数不能单机存储，并且同一个迭代内，模型参数之间还有强的依靠联系，能够拜见姐夫对distbelief的介绍里的模型切分。
此刻首要需求添加一个coordinator组件来进行模型并行的concurrent操控。而一般参数间的一来联系因模型罢了，所以较难笼统出通用的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的实力，肯定是能够做到第四重境地的，之所以没有曝光，或许是根据其他商业意图的考量，比方运用他们的云核算服务。
5. 其他
5.1资源办理
本文没有涉及到的部分是资源办理，大规划机器学习结构布置的集群往往
资源耗费也比较大，需求专门的资源办理东西来保护。这方面yarn和mesos都是佼佼者，细节这儿也就不介绍了。
5.2设备
除了资源办理东西，自身布置大规划机器学习集群自身对硬件也仍是有些要
求的，尽办理论上来说，一切commodity机器都能够用来建立这类集群，可是考虑到功用，咱们主张尽量用高内存的机器+万兆及以上的网卡。没有超快速的网卡，玩参数传递和样本加载估量会比较苦逼。
6. 结语
从后台转算法以来，长时间沉浸于算法推理的论文无法自拔，对自己之前的后
台工程才干逐渐小看起来，觉得工程对算法的协助不大。直到最近一个要害，需求做一个这方面的调研，才豁然发现，之前的工程经历对我了解大规划机器学习结构十分有用，公然如李宗盛所说，人生每一步路，都不是白走的。
在一个月左右的调研中，脑子每天都充满这各种疑问和困惑，从前深夜4点醒来，考虑同步机制而再也睡不着，爽性起来躲卫生间看书，而那天我一点多才睡。当脑子里有放不下的问题的时分，整个人会处于一种十分兴奋的状况，除非完全想清楚这个问题，不然失眠是必定的，上一次这种状况现已是许多年前了。好在最终我总算理清了这方面的一切要害细节。以此，记之。Carbonzhang于2017年8月26日清晨!
称谢
感谢wills、janwang、joey、roberty、suzi等同学一同评论，特别感谢burness在TF方面的深沉造就和调研。由于自己水平所限，讹夺不免，别的还有相当多的细节由于篇幅约束并未逐个打开，仅仅是从较高笼统层面上简述了下大规划机器学习结构的要害思路，其他如分片向量锁、通信协议、时钟逻辑、DAG调度器、资源调度模块等均为打开来讲，期望今后有时机能补上。
