衍射的博客

记录学习中的点点滴滴

0%

[ISCA 2024] ElasticRec: A Microservice-based Model Serving Architecture Enabling Elastic Resource Scaling for Recommendation Models

发表于 更新于 分类于
本文字数： 6.7k 阅读时长 ≈ 12 分钟

题目：ElasticRec: A Microservice-based Model Serving Architecture Enabling Elastic Resource Scaling for Recommendation Models

来源：ISCA 2024

作者：韩国科学技术院

摘要

推荐系统（RecSys）广泛应用在许多线上服务中，为增加RecSys的推理时的吞吐量，数据中心通常对RecSys进行模型级别（model-wise）的资源管理。然而，RecSys中不同模块有着异构的资源需求，比如：

  • RecSys中MLP模块 对于计算资源的需求高
  • RecSys中Embedding Table模块对于内存资源的需求高

如果将RecSys模型看作一个整体进行服务部署、资源分配等操作，势必会造成大量的资源浪费；但对RecSys模型中的每一层进行资源管理又是非常具有挑战性的（这里类似于单体应用和微服务应用的关系）。因此，作者提出了ElasticRec，一种基于微服务架构的推荐系统细粒度资源分配方法，目标是减少部署时的内存消耗，提升RecSys的吞吐量。

背景

文章背景主要介绍了深度推荐模型的结构，以及深度推荐模型如何集成到Kubernetes集群中，为用户提供线上推理服务。

深度推荐模型（DLRM）

如图所示，深度推荐模型（DLRM）包含3个主要组件：

  • Bottom MLP
    • 输入：dense input（比如 用户年龄）
    • 输出：dense output（高维特征）
    • 类型：计算敏感型
  • Embedding Table
    • 输入：多个 sparse input（比如 商品ID）
    • 输出：dense output（高维特征）
    • 类型：内存敏感型
    • 作用：根据稀疏输入得到Embedding Table中的高维特征。一般来说，一次查询中所有的sparse input得到的dense output会执行pool操作进行池化，得到单个dense output
  • Top MLP
    • 输入：Bottom MLP的输出 拼接 Embedding Table的输出
    • 输出：给商品打分

在生产环境中，由于商品（item）的种类非常多，比如Amazon有数亿的商品种类。Embedding Table为每个商品种类都维护了一个特征，导致Embedding Table的大小可以达到几十GB，相比于Bottom MLP，有几点需要关注：

  1. Embedding Table对于计算不敏感，即pool操作并不需要太多计算资源；相反，对于内存带宽限制极为敏感，特别是有非常多的dense output需要pool时
  2. 在DLRM中，Embedding Table通常有多个，对内存的压力是极大的

模型服务架构（Model Serving Architectures）

模型容器化

这篇文章关注的是DLRM的推理。在线上应用中，DLRM被打包成镜像，镜像中包含了模型参数以及常用的机器学习库，以容器的方式运行在Kubernetes集群中，如Fig. 2（a）所示。

模型的自动伸缩

Kubernetes是一个容器编排工具，它能管理容器的生命周期，对容器进行自动化调度、资源分配。

吞吐量是一个衡量在线服务性能的指标，单位是QPS（query per second），吞吐量越高，代表在线服务单位时间内处理请求的数量

对于DLRM而言，处理单个请求的时间基本可以看作变化很小的，那么为提高吞吐量，可以采用Kubernetes的水平pod伸缩（Horizontal Pod Autoscaling，HPA）机制对DLRM进行副本复制，如Fig. 2 (b) 所示，增加DLRM的副本数可以提高系统的并行处理能力，从而增大吞吐量

然而，HPA 是一种 model-wise 的分配方案，它将整个DLRM模型进行复制，包括内存占用非常大的Embedding Table模块，但实际上Embedding Table并不涉及复杂的计算，所以一般不是（不是绝对）吞吐量的瓶颈所在。无脑进行HPA势必会造成大量内存浪费。

模型的硬件约束

因为 大型 DLRM 的 Embedding Table 通常有几十GB，将 Embedding Table 全部放在高内存带宽的GPU中通常不太可行，所以会退而求其次的使用如下两种方式：① CPU-only ② CPU-GPU。

  • CPU-only：Bottom MLP 和 Embedding Table 均运行在CPU
  • CPU-GPU：Bottom MLP 运行在GPU， Embedding Table 均运行在CPU

可以看到， Embedding Table 都运行在CPU关联的内存上，如果能优化这一部分的内存使用，就可以提升DLRM的最大副本数量，从而提高系统的吞吐量。

动机

文章的动机从两点出发，阐述为什么现有的资源分配方案会导致次优性能（sub-optimal performance）：

  1. RecSys的不同模块具有异构资源需求
  2. Embedding Table不同部分的访问频率相差极大

异构资源需求

Fig. 3 (a) 展示了三个推荐模型（RM1，RM2，RM3）的不同模块Bottom MLP 和 Embedding Table 在 ①计算复杂度（FLOPS）和 ②内存大小 上的差别。可以看出：Bottom MLP在计算复杂度上远高于 Embedding Table，但是内存占用远远小于 Embedding Table

Fig.3 (b) 展示了三个推荐模型的不同模块在两种硬件约束下的延时占比。原文虽然没有讨论，但可以推测，在CPU-only架构下，推理的延时开销主要集中在Bottom MLP的计算；在CPU-GPU架构下，延时的开销在于将 Embedding Table 的数据从CPU传输到GPU

此外，文章还讨论了吞吐量的瓶颈问题，Fig. 4展示了作者的想法，实际上Bottom MLP 计算开销大，内存占用小，适合扩充副本来提升吞吐量；而 Embedding Table 本身吞吐量就很大，但是内存占用大，所以对于副本扩充应该谨慎。

当然，作者还通过实验，验证了不同硬件约束下不同模块的吞吐量存在差异，来支撑上述想法：

综上所述，文章说明RecSys中不同模块的异构资源需求，以及吞吐量的差异。为后续对不同模块分别进行切分提供了实验依据

Embedding Table 的倾斜访问模式

这一个实证分析较为简单，主要验证Embedding Table不同索引的访问频率的差异，如Fig. 6所示，在三个数据集中，大部分的访问集中在少数的索引（热点嵌入，hot embeddings）

换句话说，将资源选择性地分配给 hot embeddings，可以在提升吞吐量的同时，达到节省资源的目的

方法设计

Fig. 7展示了ElasticRec的系统架构，整体思路分为三个模块：

  1. 部署开销估计
  2. 基于动态规划（DP）的Embedding Table划分
  3. 推理时重索引

部署开销估计

前置处理：将Embedding Table的index按照访问频率从大到小排序，hot embeddings集中在最左侧

根据动机中提到的“将资源选择性地分配给 hot embeddings，可以在提升吞吐量的同时，达到节省资源的目的”，文章将Embedding Table切分为shards，每个shard包含了Embedding Table的一部分index。那么如何切分Embedding Table，以及如何评估切分策略的优劣呢？

文章首先定义了如何评估切分策略的优劣，切分策略的优劣由固定吞吐量的前提下，所有shard的内存开销决定。用最少的内存达到目标吞吐量，评估算法如下：

算法入口为COST(k, j)，表示范围为[k,j]的shard的内存消耗，这个内存消耗由两部分组成：

  • REPLICAS(k,j)： 计算特定吞吐量下，shard应该被分配的副本数量
    1. 计算shard被访问的概率probability和被访问的向量数ns，probability = CDF(j)- CDF(k)，ns = probability × nt
    2. 估计单个shard的副本在给定的访问向量数ns下能达到的QPS，estimated QPS = QPS(ns)，这里的QPS()是一个回归模型，可以线下测试得到
    3. 估计达到目标吞吐量target_traffic需要的副本数，num_replicas = target_traffic/estimated_QPS
  • CAPACITY(k,j)：对于shard的每一个副本，计算存储embedding的内存开销
    • 直接计算shard的副本大小：(j − k +1)×(size_of_a_single_embedding_vector)

这里需要特别注意回归模型QPS()，输入的参数除了需要访问的向量数ns外，还需要考虑向量本身的大小，如下图所示，QPS既与向量数有关，也与向量本身维度相关

基于DP的Embedding Table分区算法

在上一节中，当给定一个shard划分策略，我们可以评估每个shard在目标QPS下的内存开销，进而可以尝试找到给定QPS下最小内存开销的分区策略

这里文章有一个前提，即无论怎么划分，所有shard的目标QPS都是一样的，这样可以保证不存在多余的资源浪费

这个分区问题有两个操作：① 分多少shard ②每个shard的范围。假设我们用\(Mem[num_{shards}][x]\)表示Embedding Table在\([0:x]\)范围下，分区数量为\(num_{shards}\)的最小内存开销。那么这个问题具有两个明显的特性：最优子结构和重叠子问题

  • 最优子结构：\(Mem[num_{shards}][x]\)可以由子问题的最优解构造而来，假设最后一个shard的大小为\(m\)，那么可以简化表示为\(Mem[num_{shards}][x] = min(Mem[num_{shards}-1][x-m] + COST(m))\)，比如下图中，\(Mem[3][5]=min(Mem[2][5-m]+COST(m))=Mem[2][3]+COST(4,5)=4\)

  • 重叠子问题：求解过程中会反复遇到相同的子问题，需要将结果存储到表中，避免重复计算

因此，自然而然可以想到用动态规划（DP）求解，文章给出的算法如下：

最后根据最小内存开销回溯DP表可以得到分区策略

推理时重索引

这个部分的重点在于分区后，如何根据原始Embedding Table的index ID找到对应的shard中的某个embedding，以及确认index分别属于哪个input（为提高吞吐量，一个query包含了多个input）。

文章提出了两种索引：

  • indices：存储一次query要从Embedding Table中查找的具体ID。
  • offset：指示每个input对应的的indices中的起始位置。

对于Fig. 11（a）未分区前，一个query（indices）包含了两个input，分别为红色的[1, 7]，灰色的[3,4,8]，offset表示第一个input要从indices第0个元素算起，第二个input从indices第1个元素算起，即input1为[1,7]，input2为[3,4,8]

对于Fig. 11（b）分区后，首先计算中间的indices，具体为根据indices中的index计算应该被分到哪个分区（减去之前分区的大小），可以很容易把indices划分为shard A 的[1,3,4]和shard B 的[7,8]，同时把offset进行划分（基于indices）

对于Fig. 11（b）分区后，由于各shard索引重置了，所以需要在中间的indices和offset的基础上，进行重索引，具体为减去之前分区的大小，比如Fig. 11(b) 中 shard B的[7,8]减去shard A的大小后，变成[1,2]。这样便可以直接从各shard中查找embedding了

最终部署

因为Kubernetes的 horizontal pod autoscaling 提供了弹性伸缩时参考指标的接口，对于：

  • Embedding Table的shard，文章直接将每个shard可以承受的最大吞吐量作为参考指标，到达最大吞吐量则扩容
  • Bottom MLP，则采用SLA的65%作为扩容的阈值

（这里不是很明白为什么要采用不同的阈值指标，为什么不都用吞吐量？）

实验部分

文章分别验证了 ElasticRec 在 CPU-only 以及 CPU-GPU 环境下的性能表现：

  • CPU-only：本地集群（1 master + 11 worknode）
  • CPU-GPU：云集群（20 CPU-GPU nodes，GPU为 NVIDIA Tesla T4，节点间有31Gbps的带宽）

DLRM模型的开发是基于facebook的dlrm1。Kubernetes自动伸缩器采用的custom metric来自prometheus。SLA设置为400ms。而对于验证的DLRM模型，作者选择了三个先进的推荐模型（RM1, RM2, RM3），并在RM1的基础上进行参数改造，设置了很多个microbenchmarks，参数变动和三个RM模型如下：

其中 Locality 指标 \(P\) 代表多少请求分布在前10%的热点向量，\(P\)越大，代表请求分布越集中在热点。

Microbenchmarks实验

文章一开始探讨了不同RM配置下的内存消耗：

  1. MLP size：随着MLP size的扩大，计算复杂度提高，延时会逐渐违背SLA。Model-wise的方法会扩容整个模型，而ElasticRec只需要扩容内存开销极小的Bottom MLP，所以内存消耗差距很大
  2. Locality：访问越集中在热点，ELasticRec效果越好，因为只需要扩容热点那一部分
  3. Number of tables：系统中可能不止一个Embedding Table，比如用户ID表和商品ID表，随着表数量的增多，ELasticRec对每个表都进行分片，降低扩容时的内存开销
  4. Number of shards：分片数量并不是越多越好，因为每个shard会有最小内存消耗（程序运行必须的消耗），即算法1中的min_mem_alloc，所以当分片数量大于4后，效果没有那么明显了

不同 RM 在 CPU-only 环境下的性能

文章接下来在CPU-only环境下，比较了ElasticRec和Model-wise方法在三个推荐模型（RM1，RM2，RM3）的性能表现。以下实验都是在吞吐量为100QPS的下进行的

  1. Fig. 13 展示了内存消耗的对比
  2. Fig. 14 展示了内存利用率的对比，这里的内存利用率是作者自己定义的，表示当前shard在前1000个请求中被访问的embedding的比例，可以看出Model-wise只有一个shard（S1），并且内存利用率很低，对整个shard扩容显得很不值；ElasticRec有4个shard，前3个内存利用率很高（高频shard），最后一个非常低。
  3. Fig. 15 展示了两种方法在吞吐量为100QPS所需要消耗的CPU服务器数量。这里我不太清楚是如何算出需要消耗的CPU服务器数量的（一般算的是虚拟CPU使用量？）

不同 RM 在 CPU-GPU 环境下的性能

在CPU-GPU环境下，ElasticRec将 MLP 模块设计为 GPU-centric 容器，将 Embedding Table 模块设计为只用 CPU 的容器；Model-wise 则将CPU和GPU都分配给一个容器。以下实验都是在吞吐量为100QPS的下进行的，实验效果如下

动态输入流量实验

前几个实验都是在固定吞吐量（QPS=100）下进行的，这个实验动态调整流量大小，然后观察ElasticRec和Model-wise的吞吐量表现、资源消耗以及尾部延时。

流量大小先逐步增大，然后降到一个固定值

可以发现，ElasticRec的吞吐量、内存消耗以及SLA违背都低于对比方法

与 GPU Embedding Caches 的对比

GPU Embedding Caches 方法是之前的一个工作，原理是把Embedding Table的hot embeddings存到GPU缓存中，能缓解CPU内存带宽压力（减少CPU与GPU的交互）

文章对比了 Model-wise、Model-wise (cache) 和 ElasticRec 在200 QPS 的内存消耗，ElasticRec的内存消耗仍然是最低的

这里我很好奇为什么不比较延时？ElasticRec延时应该比不过Model-wise (cache)，毕竟CPU和GPU交互需要时间。