「论文笔记」Ekko: A Large-Scale Deep Learning Recommender System with Low-Latency Model Update

简要

问题：

DLRS（深度学习推荐系统）通常采用参数服务器的方式对模型参数进行保存（与客户端容错以及低延迟的通信），这些参数服务器通常保存在不同地理位置的数据中心中。DLRS离线训练/验证模型，并将这个模型传输到全局的推理集群中，因此，他们会导致显著的模型更新延迟（例如几十分钟），这对服务级别对象(SLO)会产生不利的影响。
现有的系统(Merlin,TFRA,Check-N-Run,BigGraph)基本都使用了局部采集数据和懒同步复制的方式更新复制的模型。然而，懒同步复制引入了非常关键的异步操作，这个异步操作通常会对SLO的性能有不好的影响。

Idea：允许服务器在线更新模型，并立即将模型更新传播到所有推理集群中。通过绕过长延迟的更新步骤（离线训练，模型检查，验证和广播）减少模型更新的延迟。其需要解决下面三个问题：

如何在带宽有限，网络路径异构的广域网上有效地传播海量模型进行更新
如何保护SLO面授网络拥塞的影响，从而延后重要的更新
如何保护SLO免受有损于模型精度的有偏差的模型更新

方案：Ekko——新颖的大规模DLRS，其可以低延迟地全局地更新复制模型，其从下面两个角度考虑DLRS模型更新的问题。

有效的点对点（P2P）模型更新传输
1. (现有的不足) 现有参数服务器采用的是主备份数据复制协议实现模型更新，这个协议由于更新延迟较长以及learder bottenecks而缺乏可伸缩性
2. (方案)设计了一个有效的基于状态的无日志同步算法。因为模型更新通常能够命中hot参数，所以这个算法在DLRS是有效的，这个算法只传输模型参数的最新版本。
3. Ekko必须允许参数服务器通过P2P的方法有效发现模型状态的不同，为此有下面的设计
  1. 模型更新缓存：允许参数服务器有效跟踪和比较模型状态
  2. shard versions：在对比模型状态时，能够显著减少网络带宽开销
  3. 广域网优化的传输拓扑：允许参数服务器优先考虑带宽丰富的数据中心内的网络路径，而不是带宽受限的数据中心间的网络路径。
SLO保护机制
1. （问题）Ekko不经验证的模型更新，会使得SLO容易收到网络拥塞和偏差更新的影响，这两种情况都可能发生在生产环境中。
2. （方案1）SLO感知的模型更新调度器，调度器为每个模型的在线更新计算下面的指标，以确定其优先度。
  1. 计算指标：跟新新鲜度优先级，更新重要性优先级，模型优先级
3. （方案2）使用一个新颖的推理模型状态管理器去处理偏差更新
  1. 管理器为每组推理模型创建一个baseline模型，其接收少量用户流量和服务，并作为推理模型的ground-truth。
  2. 管理器持续监控与质量相关的SLO以获取baseline和推理模型。
  3. 当有偏差的模型更新破坏了推理模型的状态时，管理器将通知witness servers将模型回滚到正常状态。

Ekko 系统结构

系统模型

Ekko在中央数据中心进行模型更新。其为全球的用户传输更新好的模型给距离他们最近的数据中心。Ekko使用KV对表示模型，其将模型分为多个shard。存储这些shard到一个KV存储中（叫做参数存储），并通过hash的方式分配KV对给这些shard。

Ekko使用基于软件的路由将参数请求引导到相应的模型shard中。路由为模型shard指派在数据中心的参数服务器为主服务器，并确保选择的主服务器能够实现参数请求的负载均衡。

通过这个路由，shard管理器可以处理资源过载，故障域以及copyset的问题。其与传统shard管理的不同在于采用了针对DLRS的优化

为了分摊请求处理开销，Ekko对统一模型的并发推理请求进行批量处理，但这样的批处理通常到涉及到大规模的参数，会引起一定的长尾效应。因此，Ekko会限制分配给模型shard的服务器数量。
Ekko支持多个需要性能隔离的DLRS应用程序，其映射不同应用的shard到不同的服务器中，于是一个请求的shard的峰值请求就不会影响到这个shard的其他应用。

结构总览

是指点到点的模型更新,组织了中央数据中心广播式的模型更新,采用内部和跨数据中心的所有网络路径实现更新,从而提高了系统的吞吐量,其不需要中央协调器的控制，每个数据中心可以独立的选择合适的时间间隔实现模型同步更新。
是指SLO感知的模型更新调度器，其会先预测模型更新对推理结果的影响，然后根据预测结果计算各个模型的优先级，基于这个优先级，Ekko在训练数据中心协调那个模型更新首先传播，从而提高推理服务器上SLO的总体满意度。
是指模型状态管理器，其运行在推理集群上，管理推理模型的SLO相关的指标。当发现推理模型的性能下降时，回滚到最好的模型状态，以此恢复推理模型的性能。

有效的点到点模型更新

假设想要同步两个副本(replica 1和replica 2)之间的一个shard(表示为shard1)，shard1中有shard knowledge(总结参数的更新)和update cache(基于parameter version追踪最近模型的更新)。每个shard都有相应的shard version（用于判断shard是需要同步）。

更新过程：

replica2向replica1请求最近新盖的shard version
replica1收到请求后就发送shard version对应的最近修改列表给replica2
replica2将本地的shard version和replica1的所有shard version进行对比，然后发送相关的shard knowledge给replica11
最后replica1发送所有更新的参数给replica2

shard version $v$ 由一个KV对 $(t,id)$ 构成，t是时间戳，id是一个副本的唯一标识。Ekko确保t单调递增，Parameter Version的顺序定义如下：

$v_1\geq v_2 \iff (t_1>t_2)|((t_1=t_2)\land(id_1\geq id_2))$

用人话讲就是如果版本1比版本2更新，那么时间1要比时间2要大，或者两者时间相等，唯一标识id1要比id2要大。

无日志的参数同步

本文观察到DLRS通常覆写参数，而只有最后一次写入才会决定参数的状态，为此，本文决定只发送参数的最新版本。

传统的基于日志的同步算法，会造成网络链路的利用率比较低，当部分路由路径拥塞时，传输时间会延长，严重影响整个同步的速度。因此无日志的参数同步可以为服务器提供动态的同步时间间隔。

本文采用shard knowledge实现无日志参数同步，shard knowledge使用版本向量实现，其总结了他们已经学习的参数更新。Shard数据（与shard knowledge $VV_{shard}$ 相关）反应了一个空shard的状态，这个空shard从每个副本r中应用所有历史参数进行更新，这个更新对应的参数版本 $v \leq VV_{shard}[r]$ 。

用人话讲：假设参数p有一个更新要在副本r中处理。为了保持shard knowledge，这个副本生成新的参数版本 $v_p=(t,id)$ ，并设置 $VV_{shard}[id]=v_p$

shard同步步骤：

副本r发送他的shard knowledge $VV_{r1}$ 给被选择的副本s。副本s记录当前的shard knowledge $VV_s$ 。也就是说，副本s原子地读取 $VV_s$ ，并从他的存储中选择所有参数p，这个参数p的参数版本 $v_p=(t_p,id_p)\geq VV_{r1}[id_p]$ ，并用 $VV_s$ 响应r。然后r原子基于s的响应执行参数更新。进一步合并 $VV_s$ 到当前shard knowledge $VV_{r2}$ 中。

用人话讲：副本r和副本s要同步某个shard，副本r就要发送他的shard knowledge $VV_{r1}$ 给副本s，然后副本s原子地读取对应的shard 的shard version $VV_s$ ，并找出参数版本比 $VV_{r1}$ 高的部分，然后响应给副本r。然后副本r根据副本s的响应结果，原子地同步这个shard的shard knowledge。