[源代码分析] 深度学习主要参数网络服务器ps-lite 之(1) —– PostOffice

0x00 引言

主要参数网络服务器是深度学习训炼一种方式，是为了更好地处理分布式系统深度学习难题的一个程序编写架构，其关键包含服务端，手机客户端和生产调度器，与别的方式对比，主要参数网络服务器把实体模型主要参数储存和升级提高为关键部件，而且应用多种多样方式 提升了解决工作能力。

文中是主要参数网络服务器系列产品第一篇，详细介绍ps-lite的总体方案设计和基本控制模块 Postoffice。
l

0x01 概述

1.1 主要参数网络服务器是啥

假如做一个对比，主要参数网络服务器是深度学习行业的分布式系统内存数据库，其功效是储存实体模型和升级实体模型。

大家一起来看看深度学习的好多个流程，这种流程持续周而复始。

1. 提前准备数据信息：训炼过程取得权重值 weight 和数据信息（data label）；
2. 前向测算：训炼过程应用数据信息开展前向测算，获得 loss = f(weight, data & label)；
3. 反方向求导：根据对 loss 反方向求导，获得导函数 grad = b(loss, weight, data & label)；
4. 升级权重值：weight -= grad * lr；
5. 赶到1，开展下一次迭代更新；

假如应用主要参数网络服务器训炼，我们可以把以上流程相匹配以下：

1. 主要参数下达：主要参数网络服务器服务器端 将 weight 发送给 每一个worker（或是worker自主获取），worker便是主要参数网络服务器Client端;
2. 并行处理：每一个worker 各自进行自身的测算（包含前向测算和反方向求导）;
3. grad 搜集：主要参数网络服务器服务器端 从每一个 Worker 处获得 grad，进行合并（或是worker自主消息推送）；
4. 升级权重值：主要参数网络服务器服务器端 自主将 grad 运用到 weight 上;
5. 赶到1，开展下一次迭代更新；

实际如下图：

          FP/BP     --------   Gather/Sum                                       FP/BP             -------     Gather/Sum
       ----------> | grad 1  ------                                      ----------------------> |grad 2  ----------- 
      |             --------       |                                    |                         -------            |
 ----- ----                        v                      -------------- -------------------                         v
|          |                    --- ----------   Update  |                                  |                  ------ -----  Update    ------------------ 
| weight 1 |                   | total grad 1  ---------> weight 2 = weight 1 - total grad 1|                 |total grad 2 --------> |weight 2 = ...... |
|          |                    --- ----------           |                                  |                  ------ -----            ------------------ 
 ----- ----                        ^                      -------------- -------------------                         ^
      |   FP/BP     --------       |                                    |       FP/BP             -------            |
       ----------> | grad 2  ------                                      ----------------------> |grad 2  ----------- 
                    --------   Gather/Sum                                                         -------     Gather/Sum

手机上以下：

因而我们可以计算出主要参数网络服务器当中每个控制模块的功效：

• 服务端（Server ）：储放深度学习实体模型主要参数，接受手机客户端推送的梯度方向，进行合并，对当地实体模型主要参数开展升级。
• 手机客户端（Client 或是 Worker）：
  • 从服务端获得当今全新的主要参数；
  • 应用训炼数据信息和从全新主要参数测算获得估计值，依据损失函数来测算有关训炼主要参数的梯度方向；
  • 将梯度方向发给服务端；
• 生产调度器（Scheduler）：管理方法网络服务器/手机客户端连接点，进行连接点中间数据库同步，连接点加上/删掉等作用。

1.2 历史时间追溯

主要参数网络服务器归属于深度学习训炼的一个方式，实际能够分成三代（现阶段各大企业应当有自身內部全新完成，能够算作第四代）。

在主要参数网络服务器以前，绝大多数分布式系统深度学习优化算法是根据按时同歩来完成的，例如结合通讯的all-reduce，或是 map-reduce类系统软件的reduce流程。可是按时同歩有两个难题：

• 同歩阶段只有做同歩，不可以训炼。
• straggler难题：因为一些硬件软件的缘故，连接点的计算水平通常各有不同。针对迭代更新难题而言，每一轮完毕时算得快的连接点都需等候算得慢的连接点算完，再开展下一轮迭代更新。这类等候在连接点数增加时将越来越尤其显著，进而拖慢总体的特性。

因而，当async sgd发生以后，就有些人明确提出了主要参数网络服务器。

主要参数网络服务器的定义最开始来自于Alex Smola于2010年明确提出的并行处理LDA的架构。它根据选用一个分布式系统的Memcached做为储放共享资源主要参数的储存，那样就给予了合理的体制用以分布式架构中不一样的Worker中间同歩实体模型主要参数，而每一个Worker只必须储存他测算时因此 来的一小部分主要参数就可以，也防止了全部过程在一个时间点上面慢下来同歩。可是单独的kv对产生了非常大的通讯花销，并且服务器端端无法程序编写。

第二代由Google的Jeff Dean进一步明确提出了第一代Google大脑的解决方法：DistBelief。DistBelief将极大的深度神经网络实体模型遍布储存在全局性的主要参数网络服务器中，测算连接点根据主要参数服务器虚拟机信息的传递，很切实解决了SGD和L-BFGS优化算法的分布式系统训炼难题。

再之后便是李沐所属的DMLC组所设计方案的主要参数网络服务器。依据毕业论文中常写，该parameter server归属于第三代主要参数网络服务器，便是给予了更为通用性的设计方案。构架上包含一个Server Group和多个Worker Group。

1.3 毕业论文构架

大家最先用沐神毕业论文中的图一起来看看系统架构图。

解释一下图上总体构架中每一个控制模块：

• resource manager：资源配置及管理工具。主要参数网络服务器应用业内目前的资源优化配置系统软件，例如yarn，k8s。
• training data：几十上百亿元的训炼数据信息一般储存在分布式存储上（例如HDFS），resource manager会匀称的分派到每一个worker上。
• 主要参数网络服务器的连接点被区划到一个 server group 和好几个 worker group。
• server group：一次训练科目中申请办理的servers，用以实体模型主要参数的升级和pull回复。
  • server group 中的每一个 server 只承担自身分得的一部分全局性共享资源主要参数（server 一同保持一个全局性共享资源主要参数），一般优化器在这里完成。
  • server 中间互相通讯便于开展主要参数的备份数据/转移。
  • server group 有一个 server manager node，承担维护保养 server 数据库的一致性，比如连接点情况，主要参数的分配原则。一般不容易有什么逻辑，仅有当有server node添加或撤出的情况下，为了更好地保持一致性哈希而做一些调节。
• worker group：一次训练科目中申请办理的workers，用以前向全过程和梯度方向测算。
  • 每一个 worker group 运作一个测算每日任务，worker group 中的 每一个worker 应用一部分数据信息开展训炼。
  • 分为好几个group，那样就可以适用多个任务的并行处理。
  • 每一个 worker group 有一个 task scheduler，承担向 worker 布置任务，并监管她们的运作状况，当有 worker 进到或是撤出时，task scheduler 分配没完成的每日任务。
  • worker 中间沒有通讯，只和相匹配的 server 通讯开展主要参数升级。

在分布式计算梯度方向时，系统软件的数据流分析以下：

图上每一个流程的功效为：

1. worker 连接点 根据该 batch 内的样版测算实体模型权重值的梯度方向；
2. worker将梯度方向以key-value的方式消息推送给server；
3. server按特定的优化器模型拟合权重值开展梯度方向升级；
4. worker从server中拉取全新的实体模型权重值；

上边2个图的根据是其初始编码。ps-lite 是之后的精简编码，因此 有一些作用在 ps-lite 当中沒有给予。

1.4 ps-lite发展史

从在网上找到一些 ps-lite发展史，能够见到其演变的构思。

第一代是parameter，对于特殊优化算法（如逻辑回归和LDA）开展了设计方案和提升，以达到经营规模巨大的工业生产深度学习每日任务（几百亿个实例和10-100TB数据信息尺寸的作用）。

之后试着为深度学习优化算法搭建一个开源系统通用性架构。 该新项目坐落于dmlc / parameter_server。

由于别的新项目的要求持续提高，建立了ps-lite，它给予了一个整洁的数据通讯API和一个轻量的完成。 该完成根据dmlc / parameter_server，但为不一样的新项目重新构建了工作驱动器，文档IO和深度学习优化算法编码，如dmlc-core和wormhole

依据在开发设计dmlc / mxnet期内学得的工作经验，从v1进一步重新构建了API和完成。 关键转变包含：

• 库依赖感较少;
• 更灵便的客户界定回调函数，有利于别的语言表达关联;
• 让客户（如mxnet的依靠模块）管理方法数据信息一致性;

1.5 ps-lite 系统软件整体

ps-lite 实际上 是Paramter Server的完成的一个架构，在其中主要参数解决实际有关对策需客户自身完成。

Parameter Server包含三种人物角色：Worker，Server，Scheduler。实际关联如下图：

实际人物角色作用为：

• worker（工作中连接点）：多个，实行data pipeline、前向和梯度方向测算，以key-value的方式将实体模型权重值梯度方向push到server连接点及其从server连接点获取实体模型全新权重值；
• server（服务项目连接点）：多个，承担对worker的push和pull要求做response，储存，维护保养和升级实体模型权重值以供每个worker应用（每一个server仅维护保养实体模型的一部分）；
• scheduler（操纵连接点）：系统软件内只有一个。承担全部连接点的心率检测、连接点id分派和worker&server间的通讯创建，它还可用以将操纵数据信号发送至别的连接点并搜集其进展。

在其中引进scheduler的益处以下：

• 引进一个 scheduler 控制模块，则会产生一个较为經典的三人物角色分布式架构构架；worker 和 server 的人物角色和岗位职责不会改变，而 scheduler 控制模块则有比较多的挑选：
  • 只担负和下一层資源智能监控系统般若（相近 yarn、mesos）的互动；
  • 附加提升对 worker、server 心率监管、步骤操纵的作用；
• 引进 scheduler 控制模块的另一个益处是给完成实体模型并行处理空出了室内空间；
• scheduler 控制模块不但有益于完成实体模型并行处理训炼方式，也有别的益处：例如根据对于特殊实体模型主要参数关联性的了解，对主要参数训炼全过程开展粗粒度的生产调度，能够进一步加速实体模型收敛性速率，乃至还有机会提高实体模型指标值。

了解分布式架构的同学们很有可能会担忧 scheduler 控制模块的点射难题，这一根据 raft、zab 等 paxos 协议书能够获得比较好的处理。

1.6 基本控制模块

ps-lite系统软件中的一些基本控制模块以下：

• Environment：一个单例模式的系统变量类，它根据一个 std::unordered_map<std::string, std::string> kvs 维护保养了一组 kvs 进而储存全部系统变量名及其值；

• PostOffice：一个单例模式的全局性管理类专业，一个 node 在性命期限内具备一个PostOffice，依靠它的类组员对Node开展管理方法；

• Van：通讯控制模块，承担与别的连接点的通信网络和Message的具体收取和发送工作中。PostOffice拥有一个Van组员；

• SimpleApp：KVServer和KVWorker的父类，它给予了简易的Request, Wait, Response，Process作用；KVServer和KVWorker各自依据自身的重任调用了这种作用；

• Customer：每一个SimpleApp目标拥有一个Customer类的组员，且Customer必须在PostOffice开展申请注册，此类关键承担：

  • 追踪由SimpleApp推送出来 的信息的回应状况；
  • 维护保养一个Node的消息队列，为Node接受信息；

• Node ：信息内容类，储存了本连接点的相匹配信息内容，每一个 Node 能够应用 hostname port 来唯一标志。

0x02 开机启动

2.1 如何启动

从源代码中的事例能够看得出，应用ps-lite 给予的脚本制作 local.sh 能够运行全部系统软件，这儿 test_connection 为编译程序好的可执行文件。

./local.sh 2 3 ./test_connection

2.2 运行脚本制作

实际 local.sh 编码以下。留意，在shell脚本制作中，有三个shift，这就要脚本制作中自始至终应用$1。

对于大家的事例，脚本制作主要参数相匹配了便是

• DMLC_NUM_SERVER 为 2；
• DMLC_NUM_WORKER 为 3；
• bin 是 ./test_connection；

能够从脚本制作中见到，本脚本制作干了2件事：

• 每一次实行应用软件以前，都是会根据此次实行的人物角色来对系统变量开展各种各样设置，除开DMLC_ROLE设定得不一样外，别的自变量在每一个连接点上面同样。
• 在当地运作好几个不一样人物角色。那样 ps-lite 就用好几个不一样的过程（程序流程）一同协作进行工作中。
  • 最先运行Scheduler连接点。它是要固定不动好Server和Worker总数，Scheduler连接点管理方法全部连接点的详细地址。
  • 运行Worker或Server连接点。每一个连接点要了解Scheduler连接点的IP、port。运作时联接Scheduler连接点，关联本地端口，并向Scheduler连接点申请注册自身信息内容（汇报自身的IP，port）。
  • Scheduler等候全部Worker连接点都申请注册后，给其分派id，并把连接点信息内容传输出来 （比如Worker连接点要了解Server连接点IP和端口号，Server连接点要了解Worker连接点的IP和端口号）。这时Scheduler连接点早已准备好。
  • Worker或Server接受到Scheduler传输的信息内容后，创建相匹配连接点的联接。这时Worker或Server早已准备好，会全面启动。

实际以下：

#!/bin/bash
# set -x
if [ $# -lt 3 ]; then
    echo "usage: $0 num_servers num_workers bin [args..]"
    exit -1;
fi

# 对系统变量开展各种各样配备，自此不一样连接点都是会从这种系统变量中获得信息
export DMLC_NUM_SERVER=$1
shift
export DMLC_NUM_WORKER=$1
shift
bin=$1
shift
arg="$@"

# start the scheduler
export DMLC_PS_ROOT_URI='127.0.0.1'
export DMLC_PS_ROOT_PORT=8000
export DMLC_ROLE='scheduler'
${bin} ${arg} &


# start servers
export DMLC_ROLE='server'
for ((i=0; i<${DMLC_NUM_SERVER};   i)); do
    export HEAPPROFILE=./S${i}
    ${bin} ${arg} &
done

# start workers
export DMLC_ROLE='worker'
for ((i=0; i<${DMLC_NUM_WORKER};   i)); do
    export HEAPPROFILE=./W${i}
    ${bin} ${arg} &
done

wait

2.3 实例程序流程

大家仍然应用官方网事例看一下。

ps-lite 应用的是 C 语言表达，在其中 worker, server, scheduler 都应用同一套编码。这会让习惯Java，python的同学们十分不适合，大伙儿必须融入一个环节。

对于这一实例程序流程，最初会令人疑虑，为何每一次程序执行，编码上都会运行 scheduler，worker，server？实际上 ，从下边注解就可以看出去，实际实行是根据系统变量来决策。假如系统变量设定了此次人物角色是 server，则不容易运行 scheduler 和 worker。

#include <cmath>
#include "ps/ps.h"

using namespace ps;

void StartServer() {
  if (!IsServer()) {
    return;
  }
  auto server = new KVServer<float>(0);
  server->set_request_handle(KVServerDefaultHandle<float>()); //申请注册functor
  RegisterExitCallback([server](){ delete server; });
}

void RunWorker() {
  if (!IsWorker()) return;
  KVWorker<float> kv(0, 0);

  // init
  int num = 10000;
  std::vector<Key> keys(num);
  std::vector<float> vals(num);

  int rank = MyRank();
  srand(rank   7);
  for (int i = 0; i < num;   i) {
    keys[i] = kMaxKey / num * i   rank;
    vals[i] = (rand() % 1000);
  }

  // push
  int repeat = 50;
  std::vector<int> ts;
  for (int i = 0; i < repeat;   i) {
    ts.push_back(kv.Push(keys, vals)); //kv.Push()回到的是该要求的timestamp

    // to avoid too frequency push, which leads huge memory usage
    if (i > 10) kv.Wait(ts[ts.size()-10]);
  }
  for (int t : ts) kv.Wait(t);

  // pull
  std::vector<float> rets;
  kv.Wait(kv.Pull(keys, &rets));

  // pushpull
  std::vector<float> outs;
  for (int i = 0; i < repeat;   i) {
    // PushPull on the same keys should be called serially
    kv.Wait(kv.PushPull(keys, vals, &outs));
  }

  float res = 0;
  float res2 = 0;
  for (int i = 0; i < num;   i) {
    res  = std::fabs(rets[i] - vals[i] * repeat);
    res2  = std::fabs(outs[i] - vals[i] * 2 * repeat);
  }
  CHECK_LT(res / repeat, 1e-5);
  CHECK_LT(res2 / (2 * repeat), 1e-5);
  LL << "error: " << res / repeat << ", " << res2 / (2 * repeat);
}

int main(int argc, char *argv[]) {
  // start system
  Start(0); // Postoffice::start()，每一个node都是会启用到这儿，可是在 Start 涵数当中，会根据此次设置的人物角色来不一样解决，仅有人物角色为 scheduler 才会运行 Scheduler。
  // setup server nodes
  StartServer(); // Server会在这其中做合理实行，别的连接点不容易合理实行。
  // run worker nodes
  RunWorker(); // Worker 会在这其中做合理实行，别的连接点不容易合理实行。
  // stop system
  Finalize(0, true); //完毕。每一个连接点都必须实行这一涵数。
  return 0;
}

在其中KVServerDefaultHandle是functor，用与解决server接到的来自worker的要求，实际以下：

/**
 * \brief an example handle adding pushed kv into store
 */
template <typename Val>
struct KVServerDefaultHandle { //functor，用与解决server接到的来自worker的要求
    // req_meta 是储存该要求的一些元信息内容，例如要求来自于哪一个连接点，发给哪一个连接点这些
    // req_data 是推送回来的数据信息
    // server 是偏向当今server目标的表针  
  void operator()(
      const KVMeta& req_meta, const KVPairs<Val>& req_data, KVServer<Val>* server) {
    size_t n = req_data.keys.size();
    KVPairs<Val> res;
    if (!req_meta.pull) { //接到的是pull要求
      CHECK_EQ(n, req_data.vals.size());
    } else { //接到的是push要求
      res.keys = req_data.keys; res.vals.resize(n);
    }
    for (size_t i = 0; i < n;   i) {
      Key key = req_data.keys[i];
      if (req_meta.push) { //push要求
        store[key]  = req_data.vals[i]; //这里的实际操作是将同样key的value求和
      }
      if (req_meta.pull) {  //pull要求
        res.vals[i] = store[key];
      }
    }
    server->Response(req_meta, res);
  }
  std::unordered_map<Key, Val> store;
};

0x03 Postoffice

Postoffice 是一个单例模式的全局性管理类专业，其维护保养了系统软件的一个全局性信息内容，具备以下特性：

• 三种Node人物角色都依靠 Postoffice 开展管理方法，每一个 node 在性命期限内具备一个单例模式 PostOffice。
• 如大家以前常说，ps-lite的特性是 worker, server, scheduler 都应用同一套编码，Postoffice也是这般，因此 大家最好是分离叙述。
• 在 Scheduler侧，说白了，Postoffice 是邮政局，能够觉得是一个详细地址簿，一个管控管理中心，其纪录了系统软件（由scheduler，server， worker 团体组成的这一系统软件）中全部连接点的信息内容。实际作用以下：
  • 维护保养了一个Van目标，承担全部互联网的拉上、通讯、指令管理方法如提升连接点、清除连接点、修复连接点这些；
  • 承担全部群集基本资料的管理方法，例如worker、server数的获得，管理方法全部连接点的详细地址，server 端 feature遍布的获得，worker/server Rank与node id的转换，连接点人物角色真实身份这些；
  • 承担 Barrier 作用；
• 在 Server / Worker 端，承担：
  • 配备当今node的一些信息内容，比如当今node是哪一种种类(server，worker)，nodeid是啥，及其worker/server 的rank 到 node id的变换。
  • 路由器作用：承担 key 与 server 的对应关系。
  • Barrier 作用；

一定要注意：这种编码全是在 Postoffice 类内，沒有依照人物角色分离成好几个控制模块。

3.1 界定

类 UML 图以下：

下边大家只得出重要自变量和友元函数表明，由于每一个连接点都包括一个 PostOffice，因此 PostOffice 的算法设计中包含了各种各样连接点所必须的自变量，会看起来较为复杂。

关键自变量功效以下：

• van_ ：最底层通信目标；
• customers_ ：本连接点现阶段有什么 customer；
• node_ids_ ：node id 投射表；
• server_key_ranges_ ：Server key 区段范畴目标
• is_worker_, is_server_, is_scheduler_ ：标明了本连接点种类；
• heartbeats_ ：连接点心率目标；
• barrier_done_ ： Barrier 同歩自变量；

关键涵数功效以下：

• InitEnvironment ：复位系统变量，建立 van 目标；
• Start ：创建通讯复位；
• Finalize ：连接点堵塞撤出；
• Manage ：撤出 barrier 阻塞状态；
• Barrier ：进到 barrier 阻塞状态；
• UpdateHeartbeat ：
• GetDeadNodes ：依据 heartbeats_ 获得早已 dead 的连接点；

实际以下：

class Postoffice {
  /**
   * \brief start the system
   *
   * This function will block until every nodes are started.
   * \param argv0 the program name, used for logging.
   * \param do_barrier whether to block until every nodes are started.
   */
  void Start(int customer_id, const char* argv0, const bool do_barrier);
  /**
   * \brief terminate the system
   *
   * All nodes should call this function before existing.
   * \param do_barrier whether to do block until every node is finalized, default true.
   */
  void Finalize(const int customer_id, const bool do_barrier = true);
  /**
   * \brief barrier
   * \param node_id the barrier group id
   */
  void Barrier(int customer_id, int node_group);
  /**
   * \brief process a control message, called by van
   * \param the received message
   */
  void Manage(const Message& recv);
  /**
   * \brief update the heartbeat record map
   * \param node_id the \ref Node id
   * \param t the last received heartbeat time
   */
  void UpdateHeartbeat(int node_id, time_t t) {
    std::lock_guard<std::mutex> lk(heartbeat_mu_);
    heartbeats_[node_id] = t;
  }
  /**
   * \brief get node ids that haven't reported heartbeats for over t seconds
   * \param t timeout in sec
   */
  std::vector<int> GetDeadNodes(int t = 60);  
 private:  
 void InitEnvironment();  
  Van* van_;
  mutable std::mutex mu_;
  // app_id -> (customer_id -> customer pointer)
  std::unordered_map<int, std::unordered_map<int, Customer*>> customers_;
  std::unordered_map<int, std::vector<int>> node_ids_;
  std::mutex server_key_ranges_mu_;
  std::vector<Range> server_key_ranges_;
  bool is_worker_, is_server_, is_scheduler_;
  int num_servers_, num_workers_;
  std::unordered_map<int, std::unordered_map<int, bool> > barrier_done_;
  int verbose_;
  std::mutex barrier_mu_;
  std::condition_variable barrier_cond_;
  std::mutex heartbeat_mu_;
  std::mutex start_mu_;
  int init_stage_ = 0;
  std::unordered_map<int, time_t> heartbeats_;
  Callback exit_callback_;
  /** \brief Holding a shared_ptr to prevent it from being destructed too early */
  std::shared_ptr<Environment> env_ref_;
  time_t start_time_;
  DISALLOW_COPY_AND_ASSIGN(Postoffice);
}; 

3.2 ID 投射作用

最先大家详细介绍下 node id 投射作用，便是怎样在逻辑性连接点和物理学连接点中间做投射，怎样把物理学连接点区划成每个逻辑性组，怎样用简单的方式 保证给同组物理学连接点统一发信息。

• 1，2，4各自标志Scheduler, ServerGroup, WorkerGroup。
• SingleWorker：rank * 2 9；SingleServer：rank * 2 8。
• 随意一组连接点都能够用单独id标志，相当于全部id之和。

3.2.1 定义

• Rank 是一个逻辑性定义，是每一个连接点（scheduler，work，server）內部的唯一逻辑性标识。
• Node id 是物理学连接点的唯一标志，能够和一个 host port 的二元组唯一相匹配。
• Node Group 是一个逻辑性定义，每一个 group 能够包括好几个 node id。ps-lite 一共有三组 group ： scheduler 组，server 组，worker 组。
• Node group id 是 是连接点组的唯一标识。
  • ps-lite 应用 1，2，4 这三个数据各自标志 Scheduler，ServerGroup，WorkerGroup。每一个数据都意味着着一组连接点，相当于全部该种类连接点 id 之和。例如 2 就意味着server 组，便是全部 server node 的组成。
  • 为何挑选这三个数据？由于在二进制下这三个标值分别是 “001, 010, 100″，那样假如想给好几个 group 发信息，立即把 好多个 node group id 做 或实际操作 就可以了。
  • 即 1-7 内随意一个数据都意味着的是Scheduler / ServerGroup / WorkerGroup的某一种组成。
    • 假如想把某一个要求发给全部的 worker node，把要求总体目标连接点 id 设定为 4 就可以。
    • 假定某一个 worker 期待向全部的 server 连接点 和 scheduler 连接点与此同时推送要求，则只需把要求总体目标连接点的 id 设定为 3 就可以，由于 3 = 2 1 = kServerGroup kScheduler。
    • 假如想给全部连接点推送信息，则设定为 7 就可以。

3.2.2 逻辑性组的完成

三个逻辑性组的界定以下：

/** \brief node ID for the scheduler */
static const int kScheduler = 1;
/**
 * \brief the server node group ID
 *
 * group id can be combined:
 * - kServerGroup   kScheduler means all server nodes and the scheuduler
 * - kServerGroup   kWorkerGroup means all server and worker nodes
 */
static const int kServerGroup = 2;
/** \brief the worker node group ID */
static const int kWorkerGroup = 4;

3.2.3 Rank vs node id

node id 是物理学连接点的唯一标识，rank 是每一个逻辑性定义（scheduler，work，server）內部的唯一标识。这两个标识由一个优化算法来明确。

如下边编码所显示，假如配备了 3 个worker，则 worker 的 rank 从 0 ～ 2，那麼这好多个 worker 具体相匹配的 物理学 node ID 便会应用 WorkerRankToID 来推算出来。

    for (int i = 0; i < num_workers_;   i) {
      int id = WorkerRankToID(i);
      for (int g : {id, kWorkerGroup, kWorkerGroup   kServerGroup,
                    kWorkerGroup   kScheduler,
                    kWorkerGroup   kServerGroup   kScheduler}) {
        node_ids_[g].push_back(id);
      }
    }

实际测算标准以下：

  /**
   * \brief convert from a worker rank into a node id
   * \param rank the worker rank
   */
  static inline int WorkerRankToID(int rank) {
    return rank * 2   9;
  }
  /**
   * \brief convert from a server rank into a node id
   * \param rank the server rank
   */
  static inline int ServerRankToID(int rank) {
    return rank * 2   8;
  }
  /**
   * \brief convert from a node id into a server or worker rank
   * \param id the node id
   */
  static inline int IDtoRank(int id) {
#ifdef _MSC_VER
#undef max
#endif
    return std::max((id - 8) / 2, 0);
  }

那样我们可以了解，1-7 的id表明的是node group，单独连接点的id 就从 8 逐渐。

并且这一优化算法确保server id为双数，node id为合数。

• SingleWorker：rank * 2 9；
• SingleServer：rank * 2 8；

3.2.4 Group vs node

由于有时候要求要发给好几个连接点，因此 ps-lite用了一个 map 来储存每一个 node group / single node 相匹配的具体的node连接点结合，即 明确每一个id值相匹配的连接点id集。

std::unordered_map<int, std::vector<int>> node_ids_ 

怎么使用这一node_ids_？大家或是必须看以前的编码：

    for (int i = 0; i < num_workers_;   i) {
      int id = WorkerRankToID(i);
      for (int g : {id, kWorkerGroup, kWorkerGroup   kServerGroup,
                    kWorkerGroup   kScheduler,
                    kWorkerGroup   kServerGroup   kScheduler}) {
        node_ids_[g].push_back(id);
      }
    }

大家追忆一下以前的连接点信息内容：

• 1 ～ 7 的 id 表明的是 node group；
• 事后的 id（8，9，10，11 …）表明单独的 node。在其中偶数 8，10，12… 表明 worker 0, worker 1, worker 2，… 即（2n 8），9，11，13，…，表明 server 0, server 1，server 2，…，即（2n 9）；

因此 ，为了更好地完成 “设定 1-7 内随意一个数据 能够发给其相匹配的 全部node” 这一作用，针对每一个新连接点，必须将其相匹配好几个id（node，node group）上，这种id组便是本连接点能够与之通信的连接点。比如针对 worker 2 而言，其 node id 是 2 * 2 8 = 12，因此 必须将它与

• 12（自身）
• 4（kWorkerGroup）li
• 4 1（kWorkerGroup kScheduler）
• 4 2（kWorkerGroup kServerGroup）
• 4 1 2,（kWorkerGroup kServerGroup kScheduler ）

这 5 个id 相对性应，即必须在 node_ids_ 这一投射表格中相匹配的 4, 4 1, 4 2, 4 1 2, 12 这五个 item 当中加上。便是上边编码中的內部 for 循环系统标准。即，node_ids_ [4], node_ids_ [5],node_ids_ [6],node_ids_ [7] ,node_ids_ [12] 当中，都必须把 12 加上到 vector 最终。

3.3 主要参数表明

workers 跟 servers 中间根据 push 跟 pull 来通讯。worker 根据 push 将测算好的梯度方向发送至server，随后根据 pull 从server升级主要参数。

3.3.1 KV文件格式

parameter server 中，主要参数全是能够被表明成（key, value）的结合，例如一个降到最低损失函数的难题，key便是feature ID，而value便是它的权重值。针对稀少主要参数而言，value不会有的key，就可以觉得value是0。

把主要参数表明成 k-v， 方式更当然，便于了解和程序编写完成。

3.3.2 key-values

分布式系统优化算法有两个附加成本费：数据通讯成本费，web服务不理想化和设备特性差别造成的同歩成本费。

针对高维空间深度学习训炼而言，由于高频率特点升级极其经常，所知道造成互联网工作压力巨大。假如每一个主要参数都设一个key而且按key升级，那麼会促使通讯越来越更为经常低效能，为了更好地抹平这个问题，就必须有折中和均衡，即，
运用深度学习优化算法的特点，给每一个key相匹配的value授予一个空间向量或是引流矩阵，那样就可以一次性传送好几个主要参数，衡量了结合与同歩的成本费。

做那样的实际操作的前提条件是假定主要参数是有次序的。缺陷是在针对稀少实体模型而言，总是会在空间向量或是引流矩阵里会出现主要参数为0，这在单独主要参数情况下是无需存的，因此 ，导致了数据信息的沉余。

但那样做有二点益处：

• 减少通信网络
• 促使空间向量方面的实际操作越来越行得通，进而许多线形库的提升特点能够运用的上，例如BLAS、LAPACK、ATLAS等。

3.3.3 Range 实际操作

为了更好地提升测算特性和网络带宽高效率，主要参数网络服务器也会选用批号升级的方法，来缓解高频率 key 的工作压力。例如把minibatch当中高频率key合拼成一个minibatch开展升级。

ps-lite 容许客户应用 Range Push 跟 Range Pull 实际操作。

3.4 路由器作用（keyslice）

路由器作用指的便是：Worker 在做 Push/Pull 情况下，如何知道把信息发给什么 Servers。

我们知道，ps-lite 是多 Server 构架，一个很重要的难题是怎样遍布好几个主要参数。例如给出一个主要参数的键，如何确定其储存在哪儿一台 Server 上。因此 必定有一个路由器逻辑性用于建立 key与server的对应关系。

PS Lite 将路由器逻辑性置放在 Worker 端，选用范畴区划的对策，即每一个 Server 有自身固定不动承担的键的范畴。这一范畴是在 Worker 运行的情况下明确的。关键点以下：

• 依据编译程序 PS Lite 时是不是设置的宏 USE_KEY32 来决策主要参数的键的数据信息种类，要不是 32 位无符号整数，要不是 64 位的。
• 依据键的基本数据类型，明确其函数值域的确界。比如 uint32_t 的确界是 4294967295。
• 依据键域的确界和运作时获得的 Server 总数（即系统变量 DMLC_NUM_SERVER 的值）来区划范畴。
• 每一个server维护保养的key范畴按 uint32_t / uint64_t 由小到大定距分区段。给出确界 MAX 和 Server 总数 N，第 i 个 Server 承担的范畴是 [MAX/N*i, MAX/N*(i 1))。
• 对key的hash值结构有一定的规定以防止server间的key歪斜（如32位系统、16位、8位、4位、2位多少位互换）。
• Worker push和pull的key按降序排序开展slice以完成zero copy。

必须留意的是，在不可以恰好整除的状况下，键域确界的一小段被丢掉了。

实际完成以下：

最先，ps-lite的key只适用int类型。

#if USE_KEY32
/*! \brief Use unsigned 32-bit int as the key type */
using Key = uint32_t;
#else
/*! \brief Use unsigned 64-bit int as the key type */
using Key = uint64_t;
#endif
/*! \brief The maximal allowed key value */
static const Key kMaxKey = std::numeric_limits<Key>::max();

次之，将int范围平均分就可以

const std::vector<Range>& Postoffice::GetServerKeyRanges() {
  if (server_key_ranges_.empty()) {
    for (int i = 0; i < num_servers_;   i) {
      server_key_ranges_.push_back(Range(
          kMaxKey / num_servers_ * i,
          kMaxKey / num_servers_ * (i 1)));
    }
  }
  return server_key_ranges_;
}

3.5 复位自然环境

从以前剖析中我们可以了解，ps-lite 是根据系统变量来操纵实际连接点。

实际某一连接点归属于哪一种在于运行连接点以前设定了什么系统变量及其其标值。

系统变量包含：连接点人物角色，worker&server数量、ip、port等。

InitEnvironment 涵数便是建立了 Van，获得了 worker 和 server 的总数，获得了本连接点的种类。

void Postoffice::InitEnvironment() {
  const char* val = NULL;
  std::string van_type = GetEnv("DMLC_PS_VAN_TYPE", "zmq");
  van_ = Van::Create(van_type);
  val = CHECK_NOTNULL(Environment::Get()->find("DMLC_NUM_WORKER"));
  num_workers_ = atoi(val);
  val =  CHECK_NOTNULL(Environment::Get()->find("DMLC_NUM_SERVER"));
  num_servers_ = atoi(val);
  val = CHECK_NOTNULL(Environment::Get()->find("DMLC_ROLE"));
  std::string role(val);
  is_worker_ = role == "worker";
  is_server_ = role == "server";
  is_scheduler_ = role == "scheduler";
  verbose_ = GetEnv("PS_VERBOSE", 0);
}

3.6 运行

关键便是：

• 启用 InitEnvironment() 来复位自然环境，建立 VAN 目标；
• node_ids_复位。依据worker和server连接点数量，明确每一个id值相匹配的连接点id集。实际逻辑性大家前边有剖析。
• 运行 van，这儿会开展各种各样互动（有一个 ADD_NODE 同歩等候，与后边的 barrier 等候不一样）；
• 如果是第一次启用PostOffice::Start，复位start_time_组员；
• 假如设定了必须 barrier，则启用 Barrier 来开展 等候/解决 最后系统软件统一运行。即 全部Node提前准备并向Scheduler推送规定同歩的Message，开展第一次同歩；

实际编码以下：

void Postoffice::Start(int customer_id, const char* argv0, const bool do_barrier) {
  start_mu_.lock();
  if (init_stage_ == 0) {
    InitEnvironment();

    // init node info.
    // 针对全部的worker，开展node设定
    for (int i = 0; i < num_workers_;   i) {
      int id = WorkerRankToID(i);
      for (int g : {id, kWorkerGroup, kWorkerGroup   kServerGroup,
                    kWorkerGroup   kScheduler,
                    kWorkerGroup   kServerGroup   kScheduler}) {
        node_ids_[g].push_back(id);
      }
    }
		// 针对全部的server，开展node设定
    for (int i = 0; i < num_servers_;   i) {
      int id = ServerRankToID(i);
      for (int g : {id, kServerGroup, kWorkerGroup   kServerGroup,
                    kServerGroup   kScheduler,
                    kWorkerGroup   kServerGroup   kScheduler}) {
        node_ids_[g].push_back(id);
      }
    }
		// 设定scheduler的node
    for (int g : {kScheduler, kScheduler   kServerGroup   kWorkerGroup,
                  kScheduler   kWorkerGroup, kScheduler   kServerGroup}) {
      node_ids_[g].push_back(kScheduler);
    }
    init_stage_  ;
  }
  start_mu_.unlock();

  // start van
  van_->Start(customer_id);

  start_mu_.lock();
  if (init_stage_ == 1) {
    // record start time
    start_time_ = time(NULL);
    init_stage_  ;
  }
  start_mu_.unlock();
  // do a barrier here
  if (do_barrier) Barrier(customer_id, kWorkerGroup   kServerGroup   kScheduler);
}

3.7 Barrier

3.7.1 同歩

总的来讲，schedular连接点根据记数的方法完成每个连接点的同歩。从总体上便是：

• 每一个连接点在自身特定的指令运作完后会向schedular连接点推送一个Control::BARRIER指令的要求并自身堵塞直至接到schedular相匹配的回到后才消除堵塞；
• schedular连接点接到要求后则会在当地记数，看接到的要求数是不是和barrier_group的总数是不是相同，相同则表明每一个设备都运作完特定的指令了，这时schedular连接点会向barrier_group的每一个设备推送一个回到的信息内容，并消除其堵塞。

3.7.2 复位

ps-lite 应用 Barrier 来自动控制系统的复位，便是大家都做好准备再一起前行。这是一个选择项。实际以下：

• Scheduler等候全部的worker和server推送BARRIER信息内容；
• 在进行ADD_NODE后，每个连接点会进到特定 group 的Barrier堵塞同歩体制（推送 BARRIER 给 Scheduler），以确保以上全过程每一个连接点都早已进行；
• 全部连接点（worker和server，包含scheduler） 等候scheduler接到全部连接点 BARRIER 信息内容后的回复；
• 最后全部连接点接到scheduler 回复的Barrier message后撤出阻塞状态；

3.7.2.1 等候 BARRIER 信息

Node会启用 Barrier 涵数 告之Scheduler，随后自身进到等候情况。

留意，启用情况下是

if (do_barrier) Barrier(customer_id, kWorkerGroup   kServerGroup   kScheduler);  

换句话说，等候全部的 group，即 scheduler 连接点还要为自己推送信息。

void Postoffice::Barrier(int customer_id, int node_group) {
  if (GetNodeIDs(node_group).size() <= 1) return;
  auto role = van_->my_node().role;
  if (role == Node::SCHEDULER) {
    CHECK(node_group & kScheduler);
  } else if (role == Node::WORKER) {
    CHECK(node_group & kWorkerGroup);
  } else if (role == Node::SERVER) {
    CHECK(node_group & kServerGroup);
  }

  std::unique_lock<std::mutex> ulk(barrier_mu_);
  barrier_done_[0][customer_id] = false;
  Message req;
  req.meta.recver = kScheduler;
  req.meta.request = true;
  req.meta.control.cmd = Control::BARRIER;
  req.meta.app_id = 0;
  req.meta.customer_id = customer_id;
  req.meta.control.barrier_group = node_group; // 纪录了等候什么
  req.meta.timestamp = van_->GetTimestamp();
  van_->Send(req); // 给 scheduler 发送给 BARRIER
  barrier_cond_.wait(ulk, [this, customer_id] { // 随后等候
      return barrier_done_[0][customer_id];
    });
}

3.7.2.2 解决 BARRIER 信息

解决等候的姿势在 Van 类当中，大家提早放出来。

实际ProcessBarrierCommand逻辑性以下：

• 假如 msg->meta.request 为true，表明是 scheduler 接到信息开展解决。
  • Scheduler会对Barrier要求开展提升记数。
  • 当 Scheduler 接到最后一个要求时（记数相当于此group连接点数量），则将记数清零，推送完毕Barrier的指令。此刻 meta.request 设定为 false；
  • 向此group全部连接点推送request==false的BARRIER信息。
• 假如 msg->meta.request 为 false，表明是接到信息这一 respones，能够消除barrier了，因此开展解决，启用 Manage 涵数 。
  • Manage 涵数 将app_id相匹配的全部costomer的barrier_done_置为true，随后通告全部等候标准自变量barrier_cond_.notify_all()。

void Van::ProcessBarrierCommand(Message* msg) {
  auto& ctrl = msg->meta.control;
  if (msg->meta.request) {  // scheduler收到了信息，由于 Postoffice::Barrier涵数 会在推送情况下做设定为true。
    if (barrier_count_.empty()) {
      barrier_count_.resize(8, 0);
    }
    int group = ctrl.barrier_group;
      barrier_count_[group]; // Scheduler会对Barrier要求开展记数
    if (barrier_count_[group] ==
        static_cast<int>(Postoffice::Get()->GetNodeIDs(group).size())) { // 假如相同，表明早已收到了最后一个要求，因此 推送消除 barrier 信息。
      barrier_count_[group] = 0;
      Message res;
      res.meta.request = false; // 回应情况下，这儿便是false
      res.meta.app_id = msg->meta.app_id;
      res.meta.customer_id = msg->meta.customer_id;
      res.meta.control.cmd = Control::BARRIER;
      for (int r : Postoffice::Get()->GetNodeIDs(group)) {
        int recver_id = r;
        if (shared_node_mapping_.find(r) == shared_node_mapping_.end()) {
          res.meta.recver = recver_id;
          res.meta.timestamp = timestamp_  ;
          Send(res);
        }
      }
    }
  } else { // 表明这儿收到了 barrier respones，能够消除 barrier了。实际见上边的设定为false处。
    Postoffice::Get()->Manage(*msg);
  }
}

Manage 涵数便是消除了 barrier。

void Postoffice::Manage(const Message& recv) {
  CHECK(!recv.meta.control.empty());
  const auto& ctrl = recv.meta.control;
  if (ctrl.cmd == Control::BARRIER && !recv.meta.request) {
    barrier_mu_.lock();
    auto size = barrier_done_[recv.meta.app_id].size();
    for (size_t customer_id = 0; customer_id < size; customer_id  ) {
      barrier_done_[recv.meta.app_id][customer_id] = true;
    }
    barrier_mu_.unlock();
    barrier_cond_.notify_all(); // 这儿消除了barrier
  }
}

实际提示以下：

                                                     
    Scheduler                                       |                  Worker
                                                    |                      
        |                                           |                     |
        |                                           |                     |
         --------------------------------           |                      ----------------- 
        |                                |          |                     |                 |
        |                                |          |                     |                 |
        |                                |          |                     |                 |
        |                                v          |                     |                 v
        |                         receiver_thread_  |                     |           receiver_thread_
        |                                           |                     |                 |
        |                                |          |                     |                 |
        v              BARRIER           |          |   BARRIER           v                 |
Postoffice::Barrier  ----------------->  | <---------------------  Postoffice::Barrier      |
                                         |          |                                       |
        |                                |          |                     |                 |
        |                                |          |                     |                 |
        |                                |          |                     |                 |
        |                                v          |                     |                 |
        v                                           |                     v                 |
 barrier_cond_.wait          ProcessBarrierCommand  |               barrier_cond_.wait      |
        |                                           |                     |                 |
        |                                |          |                     |                 |
        |                  All Nodes OK  |          |                     |                 |
        |                                |          |                     |                 |
        |                  --------------           |   BARRIER           |                 |
        |                 |               ---------------------------------------------->   |
        |                 |  BARRIER     |          |                     |                 |
        |                  ------------> |          |                     |                 |
        |                                |          |                     |                 |
        |                                |          |                     |                 |
         <-------------------------------<          |                     | <--------------- 
        |          barrier_cond_.notify_all         |                     |    barrier_cond_.notify_all
        v                                           |                     v

手机上以下：

到此，Postoffice的剖析大家基本进行，其他作用大家可能融合 Van 和 Customer 在事后文章内容中剖析。

0xEE 私人信息

★★★★★★生活中和技术性的思索★★★★★★

微信平台账户：罗西的思索

假如您想立即获得本人撰发表文章的消息提醒，或是想看看本人强烈推荐的技术文档，敬请期待。

0xFF 参照

MXNet设计方案和完成介绍

史上最牛全方位的ps-lite了解

ps-lite 深层源代码讲解

ps-lite源代码分析

根据Parameter Server的可拓展分布式系统深度学习构架

ps-lite代码分析

ps-lite代码手记

分布式系统TensorFlow基础教程

分布式系统深度学习（上）-并行处理与深度学习

分布式系统深度学习（中）-并行处理与深度学习

分布式系统深度学习（下）-联邦学习

ps-lite 源码剖析

Talk – Scaling Distributed Machine Learning with System and Algorithm Co-design 手记