介绍

字节在《Monolith: Real Time Recommendation System With Collisionless Embedding Table》提出了它们的embedding table实现。

摘要

对于许多依赖于时间敏感客户反馈的业务来说，构建一个可扩展且实时的推荐系统至关重要，例如短视频排序或在线广告。尽管像TensorFlow或PyTorch这样的生产规模深度学习框架被广泛采用，但这些通用框架在推荐场景中的业务需求方面存在多种不足：

• 一方面，基于静态参数和dense计算调整系统对于具有动态和稀疏特征的推荐是不利的；
• 另一方面，这些框架设计时将批量训练阶段和服务阶段完全分离，阻止了模型与客户反馈实时互动。

这些问题促使我们重新审视传统方法并探索根本不同的设计选择。在本文中，我们介绍了Monolith1，一个为在线训练量身定制的系统。我们的设计理念受到了我们的应用工作负载和生产环境的观察，这与其他推荐系统有明显的不同。我们的贡献是多方面的：

• 首先，我们制作了一个无冲突的嵌入表，并进行了诸如可过期嵌入和频率过滤等优化以减少其内存占用；
• 其次，我们提供了一个具有高容错性的生产就绪在线训练架构；
• 最后，我们证明了系统可靠性可以与实时学习进行权衡。

Monolith已成功应用于BytePlus Recommend2产品中。

1 引言

过去十年见证了由推荐技术驱动的业务的蓬勃发展。为了追求更好的用户体验，为每个用户实时提供个性化内容是这些商业应用的共同目标。为此，用户最新互动的信息通常被用作训练模型的主要输入，因为它能最好地描绘用户画像，并预测用户的兴趣和未来行为。

深度学习已经在推荐模型中占据主导地位[5, 6, 10, 12, 20, 21]，因为海量的用户数据天然适合大规模数据驱动的神经网络模型。然而，在工业级推荐系统中利用深度学习的力量，不断遇到由现实世界用户行为数据的独特特性引发的问题。这些数据在两个方面与用于传统深度学习问题（如语言建模或计算机视觉）的数据截然不同：

• (1) 特征大多是稀疏的、类别型的并且动态变化的；
• (2) 训练数据的底层分布是非平稳的，即概念漂移（Concept Drift）[8]。

这些差异给从事推荐系统的研究人员和工程师带来了独特的挑战。

1.1 稀疏性和动态性

推荐的数据大多包含稀疏的类别型特征（sparse categorical features），其中一些特征出现的频率很低。将它们映射到高维嵌入空间的常见做法会引发一系列问题：

• 与单词片段数量有限的语言模型不同，推荐系统中的用户和ranking items的量级要大得多。如此庞大的嵌入表几乎无法适应单个主机内存；
• 更糟糕的是，随着更多用户和item的加入，嵌入表的大小预计会随着时间增长，而像[1, 17]这样的框架使用固定大小的dense变量来表示嵌入表。

在实践中，许多系统采用低冲突哈希[3, 6]来减少内存占用，并允许ID的增长。这依赖于一个过于理想化的假设，即嵌入表中的ID频率分布均匀，并且冲突对模型质量无害。不幸的是，这对于现实世界的推荐系统很少是真的，其中一小部分用户或item的出现次数明显更多。随着嵌入表大小的自然增长，哈希键冲突的几率增加，导致模型质量恶化[3]。

因此，对于生产规模的推荐系统来说，自然需要有能力在其参数中捕获尽可能多的特征，并且还要有能力灵活调整它试图管理的用户和item的数量。

1.2 非平稳分布

视觉和语言模式在几个世纪的时间尺度上几乎不会发展，而对一个话题感兴趣的用户可能在下一分钟就转移他们的热情。因此，用户数据的底层分布是非平稳的，这种现象通常被称为概念漂移[8]。

直观地说，更近期的历史信息可以更有效地预测用户行为的变化。为了减轻概念漂移的影响，服务模型需要尽可能接近实时地从新的用户反馈中更新，以反映用户的最新兴趣。

鉴于这些区别，并观察到我们生产环境中出现的问题，我们设计了一个大规模推荐系统Monolith来解决这些痛点。我们进行了广泛的实验来验证和迭代我们的设计。Monolith能够：

• (1) 通过设计一个无冲突的哈希表和一个动态特征淘汰机制，为稀疏特征提供完整的表达能力；
• (2) 通过在线训练，将服务反馈实时循环回训练。

凭借这些架构能力，Monolith在大约相似的内存使用情况下，始终优于采用有冲突的哈希技巧的系统，并实现了最先进的在线服务AUC，而没有过度负担我们服务器的计算能力。

本文的其余部分组织如下。我们首先在第2节详细阐述Monolith如何通过无冲突哈希表和实时训练解决现有挑战的设计细节。第3节将展示实验结果，以及生产测试的结论和对时效性、可靠性和模型质量之间权衡的一些讨论。第4节总结相关工作并与Monolith进行比较。第5节结束本文。

2 设计

Monolith的整体架构通常遵循TensorFlow的分布式Worker-ParameterServer设置（图2）。在Worker-PS架构中，机器被分配不同的角色；Worker机器负责执行图定义的计算，而PS机器存储参数并根据Worker计算的梯度更新它们。

图2 Worker-PS架构

在推荐模型中，参数被分为两组：dense和sparse：

• dense参数是深度神经网络中的权重/变量
• sparse参数指的是对应稀疏特征的嵌入表

在我们的设计中，dense和sparse参数都是TensorFlow图的一部分，并存储在参数服务器上。

与TensorFlow的密集参数变量类似，我们为稀疏参数设计了一套高效、无冲突且灵活的哈希表操作。作为补充TensorFlow训练和推理分离限制的Monolith，其弹性可扩展的在线训练旨在在短间隔内高效地将参数从【训练-PS】同步到【在线服务-PS】，模型的鲁棒性由容错机制保证。

2.1 哈希表

我们在设计sparse参数表示时的一个首要原则是：避免将不同ID的信息压缩到同一固定大小的嵌入中。使用现成的TensorFlow变量模拟动态大小的嵌入表不可避免地会导致ID冲突，随着新ID的到来和表的增长，这种情况会加剧。

因此，我们没有在变量的基础上构建，而是为我们的sparse参数开发了一个新的键值哈希表。

我们的哈希表在底层使用Cuckoo哈希图[16]，它支持插入新键而不与现有键冲突。Cuckoo哈希在查找和删除上实现了最坏情况下的𝑂(1)时间复杂度，以及预期的平均𝑂(1)时间复杂度的插入。如图3所示，它维护两个表$𝑇_0,𝑇_1$，具有不同的哈希函数$ℎ_0(𝑥), ℎ_1(𝑥)$，一个元素将被存储在它们中的一个。当尝试将元素𝐴插入$𝑇_0$时，它首先尝试将𝐴放置在$ℎ_0(𝐴)$；如果$ℎ_0(𝐴)$被另一个元素𝐵占用，它会将𝐵从$𝑇_0$中驱逐出去，并尝试使用相同的逻辑将𝐵插入$𝑇_1$。这个过程将重复进行，直到所有元素稳定，或者在插入遇到循环时发生重新哈希。

图3 布谷鸟哈希（Cuckoo HashMap）

在我们的设计中，内存占用减少也是一个重要考虑因素。简单地将每个新ID插入哈希表会迅速耗尽内存。对真实生产模型的观察导致两个结论：

• (1) 只出现几次的ID对提高模型质量的贡献有限。一个重要的观察是，ID是长尾分布的，其中流行的ID可能出现数百万次，而不受欢迎的ID出现不超过十次。对应这些不频繁ID的嵌入由于缺乏训练数据而拟合不足，模型将无法基于它们做出良好的估计。归根结底，这些ID不太可能影响结果，因此从这些低频ID中移除不会影响模型质量；
• (2) 来自遥远历史的陈旧ID很少对当前模型做出贡献，因为它们中的许多从未被访问过。这可能是因为一个不再活跃的用户，或者一个过时的短视频。存储这些ID的嵌入对模型没有任何帮助，只会白白消耗我们的PS内存。

基于这些观察，我们为哈希表设计了几项特征ID过滤启发式方法，以实现更内存高效的实现：

• (1) 在ID被允许进入嵌入表之前进行过滤。我们有两种过滤方法：首先，我们根据它们出现的次数在它们被插入为键之前进行过滤，出现次数的阈值是一个可调的超参数，每个模型各不相同；此外，我们使用概率过滤器进一步减少内存使用；
• (2) ID被定时，并在一定时间内不活跃后被设置为过期。过期时间也是每个嵌入表可调的，以允许区分对历史信息敏感度不同的特征。

在我们的实现中，哈希表被实现为TensorFlow资源操作。与变量类似，查找和更新也被实现为原生TensorFlow操作，以便于集成和更好的兼容性。

2.2 在线训练

在Monolith中，训练被分为两个阶段（图1）：

图1 Monolith在线训练架构

• (1) 批量训练阶段。这个阶段作为一个普通的TensorFlow训练循环工作：在每个训练步骤中，训练工作器从存储中读取一小批训练样本，从PS请求参数，计算前向和反向传播，最后将更新后的参数推送到training PS。与其他常见的深度学习任务略有不同，我们只对数据集进行一次遍历的训练。批量训练对于我们在修改模型架构并重新训练模型时训练历史数据很有用；
• (2) 在线训练阶段。模型部署到在线服务后，训练不会停止，而是进入在线训练阶段。训练工作器不是从存储中读取小批量样本，而是实时消费实时数据并更新training PS。training PS定期将参数同步到serving PS，这将立即在用户端生效。这使我们的模型能够根据用户的反馈实时互动适应。

2.2.1 流式引擎

Monolith构建了无缝切换批量训练和在线训练的能力。这是通过我们设计的流式引擎实现的，如图4所示。 在我们的设计中，我们使用一个Kafka队列来记录用户的行为（例如点击一个项目或喜欢一个项目等），另一个Kafka队列用于特征。引擎的核心是一个Flink流式作业在线特征Joiner。在线Joiner将特征与用户行为的标签连接起来，生成训练样本，然后写入Kafka队列。训练样本队列被在线训练和批量训练都消费：

图4 Streaming Engine

• 对于在线训练，训练工作器直接从Kafka队列读取数据；
• 对于批量训练，数据转储作业首先将数据转储到HDFS；在HDFS中累积了一定量的数据后，训练工作器将从HDFS检索数据并执行批量训练。

training PS中更新的参数将根据参数同步计划推送到serving PS。

2.2.2 在线Joiner

在现实世界的应用中，用户行为日志和特征是无时间顺序保证地流式传输到在线Joiner（图5）。因此我们使用每个请求的唯一键，以便用户行为和特征能够正确配对。用户行为的延迟也可能是一个问题。例如，用户可能在几天前他们被展示的项目后决定购买。这对于Joiner来说是一个挑战，因为如果所有特征都保留在缓存中，它将无法适应内存。在我们的系统中，使用磁盘上的键值存储来存储等待超过一定时间周期的特征。当用户行为日志到达时，它首先查找内存缓存，如果缓存缺失，则查找键值存储。

图5 Online Joiner

在现实世界的应用中出现的另一个问题是，负样本和正样本的分布高度不均匀，前者的数量可能比后者高几个数量级。为了防止正样本被负样本淹没，一个常见的策略是进行负采样。这肯定会改变训练模型的底层分布，将其调整为更高概率的正预测。作为补救措施，我们在服务期间应用对数几率校正[19]，确保在线模型是原始分布的无偏估计器。

2.2.3 参数同步

在在线训练期间，Monolith训练集群不断从在线服务模块接收数据并更新training PS上的参数。使在线serving PS能够从这些新训练的参数中受益的一个关键步骤是：同步更新的模型参数。在生产环境中，我们遇到了几个挑战：

• 在线serving PS上的模型在更新时不能停止服务。我们生产中的模型通常有数TB的大小，因此替换所有参数需要一段时间。在替换过程中停止在线PS服务模型是不可接受的，更新必须即时进行；
• 从training PS到在线serving PS传输数TB的模型将对网络带宽和PS上的内存造成巨大压力，因为这需要双倍的模型大小内存来接受新到达的模型。

为了使在线训练能够扩展到我们业务场景的规模，我们设计了一种增量式的即时定期参数同步机制，基于我们模型的几个显著特征：

• (1) sparse参数主导了推荐模型的大小；
• (2) 给定一个短时间窗口，只有一小部分ID会被训练，它们的embedding会被更新；
• (3) dense变量的变动速度远慢于sparse嵌入。这是因为：在基于动量的优化器（momentum-based optimizers）中，dense变量的动量积累被推荐训练数据的庞大size所放大，而单个数据批次中只有少数sparse嵌入接收更新。

(1) 和 (2) 允许我们利用所有特征ID的sparse更新。在Monolith中，我们维护一个被触摸键（touched keys）的哈希集合，代表自上次参数同步以来embedding中被训练的ID。我们以分钟级别的时间间隔将被触摸键集中的稀疏参数子集从training PS推送到在线serving PS。这种相对较小的增量参数更新包对网络传输来说很轻，并且在同步过程中不会导致内存急剧增加。

我们还利用 (3) 进一步减少网络I/O和内存使用，通过为稀疏参数设置更积极的同步计划，而不太频繁地更新密集参数。这可能会导致我们服务的dense参数与sparse部分相比是相对陈旧的版本。然而，由于 (3) 中提到的原因，这种不一致是可以容忍的，因为没有观察到明显的损失。

图6 DeepFM架构

2.3 容错性

作为一个生产系统中的系统，Monolith被设计为在PS（Parameter Server）失败时能够恢复。容错的一个常见选择是：定期对模型的状态进行快照，并在检测到PS故障时从最新的快照中恢复。快照频率的选择有两个主要影响：

• (1) 模型质量。直观上，随着快照频率的增加，模型质量受到近期历史丢失的影响较小。
• (2) 计算开销。对多TB模型进行快照并非没有成本。它会产生大量的内存复制和磁盘I/O。

作为模型质量和计算开销之间的权衡，Monolith每天都会对所有training PS进行快照。尽管在故障情况下PS会丢失一天的更新，但我们通过实验发现性能下降是可以接受的。我们将在下一节分析PS可靠性的影响。

3 评估

为了更好地理解我们提出的设计带来的益处和权衡，我们在生产规模上进行了一系列实验，并使用实时服务流量进行了A/B测试，以从不同方面评估和验证Monolith。我们希望通过实验回答以下问题：

• (1) 无冲突哈希表能带来多少好处？
• (2) 实时在线训练有多重要？
• (3) 在大规模生产场景中，Monolith的参数同步设计是否足够健壮？

在本节中，我们首先介绍我们的实验设置，然后详细讨论结果和我们的发现。

3.1 实验设置

3.1.1 嵌入表

如第2.1节所述，Monolith中的嵌入表实现为无冲突哈希表。为了证明避免嵌入表中冲突的必要性并量化我们无冲突实现的收益，我们在Movielens数据集和我们的内部生产数据集上分别进行了两组实验：

(1) MovieLens ml-25m数据集[11]。这是一个标准的公共电影评分数据集，包含约2500万个评分，涉及约162000名用户和62000部电影。

• 标签预处理。原始标签是0.5到5.0的评分，而在生产中我们的任务大多是接收用户的二元信号。为了更好地模拟我们的生产模型，我们将刻度标签转换为二元标签。

(2) 内部推荐数据集。我们还在生产环境中的推荐模型上进行了实验。这个模型通常遵循多塔架构，每个塔负责学习预测一种专门的用户行为。

• 每个模型大约有1000个嵌入表，嵌入表的大小分布非常不均匀；
• 嵌入表的原始ID空间是$2^{48}$。在我们的基线中，我们应用了一种哈希技巧，通过分解来限制嵌入表的大小。具体来说，我们使用两个较小的嵌入表而不是一个巨大的表来为每个ID生成一个唯一的嵌入，通过向量组合：

\[ID_r = ID\ \% \ 2^{24} \\ ID_q = ID\ / \ 2^{24} \\ E = \mathbf{E}_{\text{l}} + \mathbf{E}_{\text{q}}\]

其中：

• $E_l$, $E_q$ ：分别对应于 $I_l$, $I_q$ 的嵌入。

这有效地将嵌入表的大小从$2^{48}$减少到$2^{25}$；

• 这个模型正在实时生产中服务，这个实验的性能是通过在线AUC和实时服务流量来衡量的。

3.1.2 在线训练

在在线训练期间，我们以分钟级别的间隔用最新的参数集更新我们的在线serving PS。我们设计了两组实验来验证模型质量和系统鲁棒性。

(1) 更新频率。为了调查分钟级更新频率的必要性，我们进行了实验，以不同的间隔从训练模型同步参数到预测模型。

我们使用的是Criteo Display Ads Challenge数据集，这是一个大规模的标准数据集，用于基准测试CTR模型。它包含了7天按时间顺序排列的数据记录特征和点击行为。在这个实验中，我们使用了一个标准的DeepFM模型，如第6节所述。为了模拟在线训练，我们对数据集进行了以下预处理。我们从数据集中取出7天的数据，并将其分为两部分：5天的数据用于批量训练，2天的数据用于在线训练。我们进一步将2天的数据按时间顺序分成N个片段。在线训练通过算法1模拟。因此，我们模拟了以数据片段数量确定的时间间隔将训练参数同步到在线serving PS的过程。我们尝试了N = 10, 50, 100，大致对应于5小时、1小时和30分钟的更新间隔。

算法1

（2）实时实验。此外，我们还进行了一个实时实验，使用真实的服务流量进一步展示在线训练在现实世界应用中的重要性。这个A/B实验比较了我们的一个生产广告模型中的在线训练和批量训练。

3.2 结果和分析

3.2.1 嵌入冲突的影响

来自MovieLens数据集和内部推荐数据集的结果都显示，嵌入冲突会危及模型质量。

图7 DeepFM模型在MovieLens数据集上的embedding冲突的效果

（1）无冲突哈希表的模型始终优于有冲突的模型。这一结论无论在以下情况下都成立：

• 训练周期数量的增加。如图7所示，无冲突嵌入表的模型从第一个周期开始就有更高的AUC，并在更高的值处收敛；
• 由于概念漂移，分布随时间的变化。如图8所示，无冲突嵌入表的模型也随着时间的推移和用户/项目上下文的变化而保持稳健。

图8 在生产环境下推荐模型的embedding冲突效果

（2）由无冲突嵌入表引起的数据稀疏性不会导致模型过拟合。如图7所示，无冲突嵌入表的模型在收敛后不会过拟合。

3.2.2 在线训练：

实时性与可靠性的权衡。我们发现，更高的参数同步频率总是有助于提高在线服务AUC，并且在线服务模型对PS（Parameter Server）部分数据丢失的容忍度超出我们的预期。

（1）参数同步频率的影响。在我们使用Criteo Display Ads Challenge数据集进行的在线流式训练实验中，模型质量随着参数同步频率的增加而持续提高，这可以从两个角度明显看出：

图9 在Criteo数据集上Online training vs. Batch training，蓝线：online training模型的AUC；黄线：batch training模型的AUC

• 进行在线训练的模型比没有进行在线训练的模型表现更好。图9a、9b、9c比较了在线训练模型按后续数据片段评估的AUC与批量训练模型按每个数据片段评估的AUC；
• 参数同步间隔较小的模型比间隔较大的模型表现更好。图10和表2比较了同步间隔为5小时、1小时和30分钟的模型的在线服务AUC。

图10 online training中不同同步间隔的比较

在生产环境中，在线训练与批量训练的实时A/B实验也显示在线服务AUC有显著提升（表3）。

受此观察启发，我们将稀疏参数尽可能频繁地同步到生产模型的serving PS（目前是分钟级），以忍受计算开销和系统可靠性的程度。回想第2.2.3节中提到的密集变量需要较不频繁的更新，我们每天更新它们。这样做，我们可以将计算开销降到非常低的水平。假设每分钟有100,000个ID更新，嵌入的维度是1024，需要传输的总数据大小是4KB × 100,000 ≈ 400MB每分钟。

对于密集参数，由于它们是每天同步的，我们选择在流量最低的时候（例如午夜）安排同步。（2）PS可靠性的影响。在分钟级参数同步的情况下，我们最初期望更频繁地对training PS进行快照以匹配实时更新。令人惊讶的是，我们将快照间隔扩大到1天，仍然几乎观察不到模型质量的损失。

在个性化排序系统中，找到模型质量和计算开销之间的正确权衡是困难的，因为用户对推荐质量非常敏感。传统上，大规模系统倾向于为它们的模型设置频繁的快照计划，以牺牲计算资源为代价，以最小化模型质量的损失。我们也在这方面做了很多探索，令人惊讶的是，模型质量比预期的更稳健。在PS机器每天有0.01%的故障率的情况下，我们发现前一天的模型出奇地好用。这个可以通过以下计算来解释：假设一个模型的参数分布在1000个PS上，并且它们每天快照一次。鉴于0.01%的故障率，每10天就会有其中一个故障，我们失去了这个PS上一天的所有更新。假设日活跃用户（DAU）为1500万，用户ID在每个PS上均匀分布，我们每10天就会失去来自15000用户的一天反馈。这是可以接受的，因为：

-（a）对于用户特定的稀疏特征，这相当于失去了0.01% DAU的微小部分； -（b）对于密集变量，由于它们更新缓慢，如我们在2.2.3节中讨论的，失去1000个PS中一天的更新是微不足道的。

基于上述观察和计算，我们大幅降低了快照频率，从而节省了大量的计算开销。

4 相关工作

自从深度学习在工业级推荐系统中最早成功应用以来[6, 10]，研究人员和工程师一直在采用各种技术来改善第1节中提到的问题。

为了解决稀疏特征表示的问题，[3, 6]使用固定大小的嵌入表和哈希技巧。还有尝试改进哈希以减少冲突[3, 7]。其他工作直接使用原生键值哈希表，以允许表大小的动态增长[12, 15, 20, 21]。这些实现基于TensorFlow，但依赖于特别设计软件机制[14, 15, 20]或硬件[21]来访问和管理它们的哈希表。与这些解决方案相比，Monolith的哈希表是另一种原生TensorFlow操作。它对开发者友好，具有更高的跨平台互操作性，适合ToB场景。与TensorFlow的有机紧密集成还使得计算性能的优化更容易。

弥补训练和部署之间的差距和缓解概念漂移[8]是另一个感兴趣的话题。为了支持在线更新并避免内存问题，[12]和[20]设计了特征逐出机制，以灵活调整嵌入表的大小。[12]和[14]都支持某种形式的在线训练，其中学习到的参数与传统批量训练相比，以相对较短的时间间隔同步到服务，具有容错机制。Monolith采取了类似的方法来弹性地接纳和逐出特征，同时它有一个更轻量级的参数同步机制来保证模型质量。

参考

• 1.https://arxiv.org/pdf/2209.07663