Zonghang Li、Wenjiao Feng、Weibo Cai、Hongfang Yu、Long Luo、Gang Sun、Hongyang Du 和 Dusit NiyatoIEEE/ACM Transactions on Networking, Vol. 32, No. 5, October 2024DOI: 10.1109/TNET.2024.3412429文章目录摘要I. 引言A. 先前工作、局限与动机B. 我们的方案与贡献II. 预备知识与研究动机A. 从星型拓扑演进为树型拓扑B. 从规则拓扑演进为不规则拓扑C. “聚合—转发”需要新的拓扑度量摘要分布式机器学习日益广泛地用于地理分布式数据分析使分散在不同地区数据中心的数据能够协同分析。这种范式无须将敏感原始数据集中到同一地点但却面临参数同步时延过高的重大挑战这一问题源于带宽受限、异构且持续波动的广域网。现有研究主要优化同步拓扑并已由星型结构演进至树型结构。然而这些方案通常依赖规则树结构且缺乏合适的拓扑度量因而提升有限。本文提出 NETSTORM这是一种自适应、高效的通信调度器用于加速地理分布式数据中心之间的参数同步。首先我们建立了一种有效度量以优化多根最快聚合路径树Fastest Aggregation Path Tree, FAPT同步拓扑。其次我们开发网络感知模块来获取网络知识以辅助拓扑决策。再次我们引入多路径辅助传输机制用于增强网络感知并实现多路径传输。最后我们设计了策略一致性协议以保证传输策略的无缝更新。实验结果表明NETSTORM 显著优于 MXNET、MLNET 和 TSEngine 等分布式训练系统相对 MXNET 可获得6.5 ∼ 9.2 6.5\sim 9.26.5∼9.2倍加速。索引词地理分布式机器学习GeoML、同步拓扑、通信调度、多路径传输。I. 引言随着数据中心和大数据在世界范围内的地理分布越来越广通过广域网Wide Area Network, WAN传输海量数据面临着更大挑战包括传输速度缓慢和数据隐私担忧。这些问题推动了地理分布式大数据分析的普及其中包括 MapReduce 和 Spark 等系统 [1], [2]以及针对数据并行 [3], [4] 和模型并行 [5] 优化的地理分布式机器学习Geo-Distributed Machine Learning, GeoML系统。具体而言各数据中心使用本地存储的数据训练其机器学习Machine Learning, ML模型副本然后与其他中心同步学得的参数或梯度以生成平均模型。这一交换过程称为参数同步。但与传统分布式机器学习Distributed Machine Learning, DML系统不同后者通常运行于由 InfiniBand 和 RoCE 技术支撑的大规模、高性能、同构且稳定的 GPU 集群 [6], [7]而 GeoML 运行在高时延、低带宽、异构且动态的 WAN 上。这些约束会造成显著的参数同步时延。具体来说GeoML 面临以下三项导致参数同步时延过高的主要挑战低带宽。WAN 具有低带宽和高时延特性在地理位置遥远的数据中心之间尤其如此。然而传统 GeoML 系统 [8]–[15] 倾向于在数据中心之间使用低效的星型同步拓扑 [16]从而进一步延长同步时延。网络异构性。数据中心之间的传输速度差异很常见 [17]速度较慢的中心会在参数同步过程中阻塞其他中心。这种阻塞不仅发生在参数服务器上 [18]也会发生在中间聚合节点上 [4]。网络动态性。WAN 资源持续波动高峰期可能出现拥塞而低谷期可用带宽更多。适应网络变化至关重要因为过时的通信策略可能使效率大幅下降。A. 先前工作、局限与动机解决上述挑战需要优化参数同步拓扑。当前研究 [4], [17], [19]–[29] 已从星型拓扑演进至更具适应性的树型结构。树型拓扑以层次化方式连接数据中心在中间中心聚合模型流量从而降低传输开销。然而[19], [20], [24], [27], [28] 和 [21] 依赖一个已知的、规则对称且支持全双工带宽的物理网络拓扑[17], [19], [20], [21], [23], [29] 则采用静态平衡树完成参数同步缺乏对 WAN 异构性与动态性的适应能力。此外[23] 和 [24] 需要配置可编程交换机和光交换机这会增加部署难度也可能干扰其他通信服务。最后[4], [25], [26] 忽略了中间聚合节点的阻塞时延没有考虑 DML 参数同步的“聚合—转发”特性说明这一方向仍有巨大改进空间。上述工作及其局限促使我们思考以下问题应优化哪一类拓扑物理 WAN 拓扑通常对 GeoML 应用不可见也不受应用控制因此基于物理拓扑的优化并不实际。这促使我们转向基于覆盖网络拓扑的优化将数据中心视为节点并通过 VPN 隧道互连。这样即可在可见的覆盖网络中优化参数同步拓扑。注三类拓扑的关系。这里的“基于网络的拓扑优化”并非改造物理 WAN而是根据可见、可测量的覆盖网络决定模型参数“由谁传给谁、经过哪些节点、在哪里聚合”。层次含义是否由 GeoML 控制物理网络拓扑光纤、交换机、路由器及真实链路的连接关系通常不可见、不可控覆盖网络拓扑将数据中心视为节点将 VPN 隧道视为逻辑链路可见、可测量参数同步拓扑从覆盖网络中选择部分链路规定参数的传输与聚合关系可以优化覆盖网络拓扑Overlay Network Topology。它是构建在真实物理网络之上的一张“逻辑网络图”。在本文中该拓扑可表示为G ( V , E ) G(V,E)G(V,E)V VV各个地理分布式数据中心E EE数据中心之间建立的 VPN 隧道或逻辑连接边的属性应用测得的端到端带宽、吞吐量和时延。例如北京数据中心与上海数据中心之间的一条 VPN 隧道在覆盖网络中表现为一条直接的逻辑边该逻辑边在底层物理网络中则可能经过多个路由器和物理链路。直观理解。物理 WAN 是应用无法修改的“道路系统”覆盖网络是应用能够观察和测量的“路线图”参数同步拓扑优化则是在这张路线图上为模型参数规划最高效的传输与汇总路线。如何优化参数同步拓扑大多数现有研究无法感知网络资源的可用性通常假设底层拓扑对称且同构并因此使用僵化的平衡树the use of rigid balanced trees进行参数同步。尽管 [4], [25], [26] 已经探索了不规则树拓扑但这些工作在优化目标中忽略了阻塞时延。因此应当建立网络感知能力并设计能够反映“聚合—转发”特性的合适目标。B. 我们的方案与贡献本文提出 NETSTORM这是一种自适应、高效的通信调度器专门用于加速地理分布式数据中心之间的参数同步这些数据中心往往受到稀缺、异构和动态网络资源的约束。针对缺少合适目标函数的问题我们为具有“聚合—转发”模式的 GeoML 流量设计了一种拓扑度量。该度量同时考虑传输时延、阻塞时延和聚合时延尤其关注非叶节点它们必须等待所有子节点的模型参数到达然后执行本地聚合再将聚合结果转发至父节点。因此该度量能给出更准确的性能评估。注1. NETSTORM 的角色。NETSTORM 是参数同步的通信调度器主要决定由哪个数据中心担任根节点、各节点向谁传输参数、参数在哪里聚合以及网络状态变化后是否调整同步拓扑。它优化的是数据中心之间的参数传输与聚合方式而不是机器学习模型本身。2. 网络资源的三类约束。稀缺跨地域 WAN 的可用带宽有限异构不同链路的带宽、吞吐量和时延存在差异动态链路性能会随其他业务流量和网络状态而变化。因此一棵固定的平衡树可能把关键流量安排到慢链路上拖慢整轮同步。3. “聚合—转发”模式。假设 A、B 是叶节点C 是中间聚合节点R 是 C 的父节点或根节点A ──┐ ├──→ C聚合──→ R B ──┘C 的工作过程是接收 A 的参数接收 B 的参数等待 A、B 的参数全部到达将 A、B 和自己的参数聚合把聚合结果转发给 R。因此中间节点不能像普通流式转发那样收到一份数据便立即继续发送而要先“收齐并聚合”再向上转发。4. 拓扑度量的作用。“拓扑度量”可以理解为一种拓扑评分方法给定一棵参数同步树估算它完成一轮参数同步需要多长时间。NETSTORM 比较不同候选树的预计同步时延然后选择预计最快的一棵。其基本思想可以概括为$$\text{路径时延}\text{传输时延}\text{阻塞时延}\text{聚合处理时延}$$整棵树的同步时间通常由完成时间最晚的叶节点到根节点路径决定也就是树中的关键路径。5. 三类时延。时延含义传输时延模型参数通过网络链路所需的时间主要由参数量和链路吞吐量决定阻塞时延中间节点已经收到部分参数但仍需等待较慢子节点的时间聚合时延中间节点对收到的模型参数执行求和、平均等聚合计算所需的时间例如若两个子节点分别在 2 秒和 6 秒后将参数送达同一父节点则先到达的参数需要额外等待 4 秒父节点才能开始聚合。6. 为什么该度量更准确。只计算链路传输时间会忽略中间节点“等待所有子节点”的同步约束一条慢链路可能阻塞其父节点并进一步推迟整条上行路径。NETSTORM 同时计算参数何时到达、何时能够聚合以及何时能够继续转发因此比只比较跳数或链路传输时延更贴近实际同步完成时间。在此度量基础上我们提出多根 FAPT 拓扑来高效完成参数同步利用多个根服务器均匀分散网络负载并尽可能降低总同步时延。参数同步拓扑的决策依赖于网络资源可用性知识这些知识由我们的被动网络感知模块提供our passive network awareness module。该模块无须注入额外探测流量即可以轻量、精确的方式感知网络从而支持动态调整参数同步拓扑使其与持续波动的网络状态保持一致。注1. FAPT 是什么FAPT 是最快聚合路径树Fastest Aggregation Path Tree。它根据前述拓扑度量为各数据中心选择通往根节点的快速聚合路径使模型参数能够沿树逐级聚合并传送到根节点。传统平衡树主要追求结构规则FAPT 则根据链路的实际吞吐量和传输时延构造因此可能是一棵不规则树。2. 为什么使用多个根服务器如果只有一个根所有模型参数最终都会流向同一节点容易使根服务器及其附近链路成为热点。NETSTORM 将模型参数切分为多个分块交给不同根服务器负责并为每个根构建一棵相应的 FAPT┌── 参数分块 1、2 ──→ FAPT 1 ──→ 根服务器 R1 模型参数 ──切分────┤ └── 参数分块 3、4 ──→ FAPT 2 ──→ 根服务器 R2多棵树可以并行同步不同参数分块从而分散流量、缓解单根拥塞并利用更多空闲链路。这里的“均匀分散”并非要求各根获得完全相同的参数量在具体实现中同步效率更高的根可以负责更多参数分块。3. 多根 FAPT 优化什么一轮参数同步必须等待所有参数分块完成因此整体同步时间通常由完成最慢的那棵树决定。例如FAPT完成时间根服务器 R1 对应的树4 秒根服务器 R2 对应的树6 秒根服务器 R3 对应的树9 秒此时整轮同步仍需要约 9 秒。NETSTORM 因而不仅要让各棵树分别变快还要避免出现一棵特别慢的树即尽可能降低所有树中的最大同步时延。4. 什么是被动网络感知常规主动探测需要额外发送测试流量而 NETSTORM 直接把训练过程中本来就要传输的模型参数分块作为探针通过分块大小和传输时间估算链路吞吐量正常传输模型参数分块 ↓ 记录分块大小和传输时间 ↓ 估算链路吞吐量因此该模块无须注入额外探测流量就能为同步拓扑的选择和后续调整提供当前网络状态信息。不过被动方式可能导致网络知识不完整并造成次优的拓扑决策。为缓解这一问题我们引入多路径辅助传输机制a multipath auxiliary transmission mechanism利用位于决策拓扑之外的空闲链路协助主路径传输模型分块。这样既能感知空闲链路也能利用它们完成并行传输进一步加速参数传输。最后我们实现了策略一致性协议以保证在响应网络变化时旧拓扑配置能够平滑过渡到新配置。注1. 为什么被动感知会造成网络知识不完整被动网络感知使用正常传输的模型参数作为探针因此只能测量当前同步拓扑实际经过的链路。覆盖网络中未被选中的链路没有参数流量即使后来性能变好调度器也可能无法及时发现从而形成以下反馈循环没有选择某条链路 ↓ 该链路没有参数流量 ↓ 无法测量该链路 ↓ 调度器仍然不会选择它论文将这种现象称为被动网络感知中的“雪崩效应”它可能使系统长期使用次优拓扑。2. 什么是多路径辅助传输NETSTORM 在已经选定的 FAPT 主路径之外再寻找由空闲链路组成的辅助路径并将少量模型分块安排到这些路径上传输主路径 A ─────────→ C 传输大部分参数分块 辅助路径A ──→ B ──→ C 传输少量参数分块辅助路径同时发挥两个作用一是让参数流量经过原本未使用的链路使系统能够测量其吞吐量二是承担一部分真实参数传输任务与主路径并行工作并分担负载。因此辅助流量不是单纯为了探测而产生的额外流量而是既传输有效模型数据又充当网络探针。3. 为什么需要策略一致性协议a policy consistency protocol论文将参数同步拓扑和辅助路径统称为“策略”。网络状态变化后调度器会生成新策略但不同节点收到更新的时间可能不同节点 A已经使用新策略 节点 B仍在使用旧策略 节点 C已经使用新策略新旧策略同时存在时可能出现丢包、节点相互等待形成的死锁以及辅助路径上的转发环路。NETSTORM 对两类路径分别处理同步拓扑这里指多根 FAPT 中承担“聚合—转发”的主路径拓扑它规定各节点的父子关系和参数发送方向。节点完成本地训练、准备执行 PUSH 时先通过拓扑请求协议Topology Request Protocol, TRP向调度器查询最新策略在收到新拓扑或“无须更新”的确认前本次 PUSH 暂不发送以免按照过时路径把参数发给错误节点。准备 PUSH → 发送 TRP → 等待响应 ↓ 更新或确认拓扑 → 发送参数这里的等待只是暂缓本次发送并非前述聚合节点等待慢子节点产生的阻塞时延。由于控制消息到达各节点的时间不同发送方可能先切换到新拓扑。例如路径从A → B → R改为A → C → R后A 可能在 C 更新前就把参数发给 C此时 C 会先缓存数据待确认新的父子关系后再进行处理和聚合从而避免丢包与相互等待。辅助路径数据的元数据携带完整路径序列中间节点按照数据携带的路径转发而不依赖自己的本地旧配置。因而即使新策略尚未同时到达所有节点系统也能继续正确传输参数避免丢包、死锁和转发环路实现新旧配置的平滑过渡。在 Klonet [30] 仿真的 WAN 上进行的实验展示了 NETSTORM 的显著加速效果其训练速度可达采用星型拓扑的常用系统 MXNET [31] 的6.5 ∼ 9.2 6.5\sim 9.26.5∼9.2倍而且在动态和静态网络中均超过 MLNET [20] 和 TSEngine [4] 等树型系统。本文的主要贡献如下我们设计了遵循“聚合—转发”模式的拓扑度量并提出用于高效参数同步的多根 FAPT 拓扑在异构动态 WAN 中实现了7.6 × 7.6\times7.6×加速。我们设计了基于模型参数探针的被动网络感知模块。它能以轻量、精确的方式测量链路吞吐量在不使用多路径辅助传输时仍可带来20 % 20\%20%的加速。我们提出多路径辅助传输利用空闲链路分担少量模型传输任务从而增强网络感知并实现并行传输可额外获得65 % 65\%65%加速。我们在 MXNET 之上实现了 NETSTORM 原型通过标准化的 PUSH/PULL 接口提供参数同步服务。对比实验和消融实验证明了该系统的高效性且代码已开源。[^1]II. 预备知识与研究动机同步拓扑对于减少同步时延、实现高效训练至关重要。本节回顾 GeoML 应用中同步拓扑的演进包括从星型到树型、从规则结构到不规则结构的变化。A. 从星型拓扑演进为树型拓扑参数服务器Parameter Server, PS[16] 是一种常用同步框架广泛用于 TensorFlow [32]、MXNET [31] 和 NBSync [13] 等 DML 系统以及 [8], [9], [10], [14], [15] 等 GeoML 系统。如图 1(b) 所示该框架采用由一个中央参数服务器和多个工作节点构成的星型同步拓扑。在每一轮训练中工作节点训练其本地模型副本将学得的参数或梯度推送至参数服务器再拉取更新后的全局模型参数以完成该轮训练。注1. 工作节点Worker是什么工作节点是实际执行模型训练的节点。在 GeoML 场景中通常可以将每个地理分布式数据中心视为一个工作节点它保存本地训练数据和一份模型副本并利用 CPU 或 GPU 完成训练。各工作节点不需要交换原始数据而是将计算得到的模型参数或梯度发送给参数服务器。读取本地数据 ↓ 执行前向传播和反向传播 ↓ 计算本地梯度或模型参数 ↓ 将结果 PUSH 给参数服务器2. 参数服务器Parameter Server, PS是什么参数服务器是负责维护和更新全局模型参数的中心节点。它接收各工作节点 PUSH 的梯度对这些梯度进行求和、平均等聚合操作更新全局模型再向工作节点提供更新后的参数工作节点通过 PULL 获取这些参数并开始下一轮训练。工作节点 A ──PUSH 梯度──┐ 工作节点 B ──PUSH 梯度──┼──→ 参数服务器 工作节点 C ──PUSH 梯度──┘ │ │ 聚合并更新全局模型 ↓ 工作节点 A、B、C ←────PULL 更新后的参数“工作节点”和“参数服务器”表示系统中的功能角色并不必然对应不同类型的物理机器参数服务器通常部署在某个数据中心内。为提高 GeoML 训练的通信效率现有工作提出了以下方法参数服务器选择Li 等人 [8] 提出选择通信开销更低的节点作为参数服务器。在线流量调度Fan 等人 [9] 使用在线流量调度解决多个训练作业之间的带宽争用。自适应梯度量化Fan 等人 [10] 使工作节点能够根据自身带宽调整量化程度从而降低通信开销并缓解慢节点引起的时延。然而这些系统存在固有局限所有工作节点都必须与参数服务器建立直接连接establish direct connections to the parameter server会在该节点形成显著拥塞并给系统可扩展性带来挑战。图 1.(a) 覆盖网络拓扑(b) 星型结构©–(e) 三种树型变体(f) 同步时延比较。每条边上的数字表示经该链路传输一单位数据所产生的时延。注图 1© 的树形结构。图中以节点 1 为根节点 2、3、4、5 是第一层中间节点其余节点是第二层叶节点。按照父子关系重新排列如下根节点 1 ┌────────┬────────┬────────┐ 5 3 4 2 │ / \ /|\ /|\ 12 9 14 10 13 11 6 7 8为什么称为“平衡树”所有叶节点到根节点都经过两条边例如12 → 5 → 1、14 → 3 → 1和6 → 2 → 1。因此最深叶节点与最浅叶节点的深度差为 0各分支经历的传输和聚合层数基本一致。“平衡”的范围。平衡主要指树的层级和分支深度相近并不要求每个中间节点拥有完全相同数量的子节点也不表示各链路具有相同带宽或时延。例如节点 2、3、4、5 分别拥有 3、2、3、1 个子节点但所有叶节点仍位于同一深度。平衡不等于最快。路径12 → 5 → 1的累计传输时延为7 50 57 7505775057其中节点 5 到节点 1 的链路成为瓶颈所以图 1(f) 中平衡树的同步时延为 57高于单根 FAPT 的 48。这说明平衡树只保证结构规则在异构 WAN 中结构平衡并不代表通信性能最优。因此研究重心已转向更高效、更可扩展的树型同步拓扑。在这类拓扑中一个节点作为根其他节点作为叶节点或中间节点共同形成树结构。模型参数从叶节点流出经过中间节点聚合最终汇集到根节点。需要注意非叶节点必须同时聚合子节点的参数和自身参数。树型拓扑具有诸多优点例如减少网络中的模型流量、缓解参数服务器拥塞以及更充分地利用非根节点之间的空闲链路。事实上研究 [26], [28] 已证实生成树是参数同步的最佳选择。然而由于缺乏对网络异构性的了解大多数系统都假设网络资源同构并默认使用图 1© 所示的平衡树结构。其中[23] 和 [27] 讨论的平衡二叉树保证每个非叶节点至多有两个子节点且深度差不超过 1从而提供对数级通信复杂度并比 PS 等扁平架构更高效。此外[11], [12], [19]–[21], [29], [33] 研究的平衡k kk叉树通过增加子节点数量来减少传输跳数进一步提高通信效率。值得注意的是尽管 [11], [12] 面向 GeoML 应用它们在数据中心间同步时仍使用扁平的 PS 架构。B. 从规则拓扑演进为不规则拓扑近期研究 [4], [25], [26] 指出规则树结构不足以应对 WAN 中的资源异构性因为这类结构往往会导致瓶颈链路和同步阻塞。因此引入网络感知能力来开发不规则树型拓扑对降低同步时延至关重要。代表性方法包括最小生成树MSTZhou 等人 [4] 使用最小生成树Minimum Spanning Tree, MST构建 TSEngine 系统如图 1(d) 所示该方法优先使用数据吞吐量最高的链路传输以避免瓶颈连接。打包生成树Wang 等人 [25] 使用打包生成树packing spanning trees以最大化从选定根节点到其他所有节点的流量。斯坦纳森林Zhang 等人 [26] 认识到真实场景中可能只有部分节点活跃因此提出使用斯坦纳森林Steiner forest高效聚合和广播参数。在该模型中每棵斯坦纳树以不同节点为根负责传输不同模型分段其目标是最大化网络带宽利用率并最小化取决于树内最小链路带宽的聚合与广播时间。当所有节点都处于活跃状态时斯坦纳树就成为生成树。C. “聚合—转发”需要新的拓扑度量现有工作 [25] 以最大化数据流为目标而 [4], [26] 等工作以提高瓶颈链路带宽为目标它们都将 DML 流量视为普通数据流忽略了其独特的“聚合—转发”特性。在常规路由优化中数据包从源端出发通过网络的多跳传输到达目的地。尽管这一过程表面上与“聚合—转发”模式相似但网络设备的行为不同它们只是按照路由表转发数据包并不执行数据聚合。参数同步拓扑优化不同于常规路由优化因为 DML 流量需要在非叶节点上而不是网络设备上聚合数据包。在此过程中非叶节点必须先收集所有子节点的数据包在本地聚合然后将结果转发至父节点。这种被称为“聚合—转发”的传输模式迫使非叶节点等待所有子节点的数据包到达从而产生阻塞时延。因此如图 1(e) 和图 1(f) 所示我们可以找到一种同步时延更低、效率更高的树结构。DML 流量的“聚合—转发”特性超越了基本的流式数据传输数据会沿同步拓扑逐跳传输同时阻塞时延在非叶节点处累积。这促使我们重新评估现有拓扑度量和优化目标使其纳入这些时延并重新设计 GeoML 系统的通信调度器。