Roblox 如何利用机器学习优化的布隆过滤器降低 Spark 连接查询成本

摘要

在 Roblox 上，每天有 7000 万用户参与数百万个体验项目，每季度总时长达 160 亿小时。这些交互产生了规模达 1 PB 的数据湖，并经过丰富处理以满足分析和机器学习 (ML) 的需求。在我们的数据湖中连接事实表和维度表非常耗费资源，因此为了优化这一过程并减少数据捣乱，我们采用了学习型布隆过滤器 [1]——一种利用机器学习的智能数据结构。 通过预测数据存在性，这些过滤器显著缩减了联接数据量，从而提升了效率并降低了成本。在此过程中，我们还改进了模型架构，并证明了这些改进在减少处理所需的内存和 CPU 时间以及提高运行稳定性方面带来的显著效益。

引言

在我们的数据湖中，事实表和数据立方体按时间分区以实现高效访问，而维度表则缺乏此类分区，因此在更新过程中将其与事实表进行连接会消耗大量资源。连接的关键空间由待连接事实表的时间分区决定。 该时间分区中包含的维度实体仅是整个维度数据集的一小部分。因此，这些连接操作中大部分经过洗牌的维度数据最终会被丢弃。为优化此过程并减少不必要的洗牌，我们曾考虑在不同的连接键上使用布隆过滤器，但面临过滤器大小和内存占用问题。

为解决这些问题，我们探索了基于机器学习的“学习型布隆过滤器”（Learned Bloom Filters），该方案在保持较低误报率的同时，有效缩减了布隆过滤器的规模。这一创新通过降低计算成本并提升系统稳定性，显著提高了连接操作的效率。下图展示了我们在分布式计算环境中传统连接流程与优化后的连接流程。

利用学习型布隆过滤器提升连接效率

为优化事实表与维度表之间的连接操作，我们采用了学习型布隆过滤器的实现方案。我们基于事实表中的键构建了索引，并在连接操作前部署该索引对维度数据进行预过滤。 

从传统布隆过滤器到学习型布隆过滤器的演进

虽然传统布隆过滤器效率很高，但为了达到我们期望的假阳性率，每个需要加载它的 worker 节点都会增加 15-25% 的额外内存。但通过利用学习型布隆过滤器，我们在保持相同假阳性率的同时，显著缩小了索引大小。这是因为将布隆过滤器转化为二分类问题：正标签表示索引中存在该值，负标签则表示不存在。

引入机器学习模型后，系统会先通过模型进行初始值检查，随后借助备用布隆过滤器消除漏检。索引大小的缩减源于模型的压缩表示形式，以及备用布隆过滤器所需键值的减少。这使其与传统的布隆过滤器方法有所区别。 

作为本研究的一部分，我们建立了两项指标来评估我们的“学习型布隆过滤器”方法：索引的最终序列化对象大小以及执行连接查询时的 CPU 消耗。 

应对实现挑战

我们面临的最初挑战是处理一个高度偏倚的训练数据集，其中事实表中包含的维度表键值极少。在此过程中，我们观察到各表之间约三分之一的键值存在重叠。为解决这一问题，我们采用了“三明治式学习布隆过滤器”方法[2]。该方法整合了初始的传统布隆过滤器，通过移除事实表中缺失的大部分键值来重新平衡数据集分布，从而有效地从数据集中剔除了负样本。 随后，仅将初始布隆过滤器中包含的键值（连同误报项）一并传递给机器学习模型（通常称为“学习型预言机”）。这种方法为学习型预言机生成了分布均衡的训练数据集，从而有效解决了数据偏差问题。

第二个挑战集中在模型架构和训练特征上。与经典的钓鱼网址问题 [1] 不同，我们的连接键（在大多数情况下是用户/体验的唯一标识符）本身并不具备信息价值。这促使我们探索维度属性作为潜在的模型特征，以帮助预测某个维度实体是否存在于事实表中。 例如，设想一个包含特定语言体验用户会话信息的事实表。用户维度中的地理位置或语言偏好属性，便是判断特定用户是否存在于事实表中的良好指标。

第三个挑战——推理延迟——要求模型既要最大限度地减少漏检，又要提供快速响应。梯度提升树模型是满足这些关键指标的最佳选择，我们对其特征集进行了剪枝，以平衡精度与速度。

我们利用已训练的布隆过滤器（Bloom Filters）更新的连接查询如下所示：

结果

以下是我们针对数据湖中学习型布隆过滤器（Learned Bloom filters）的实验结果。我们将该技术集成到五个生产工作负载中，每个工作负载具有不同的数据特征。这些工作负载中计算成本最高的部分是事实表与维度表之间的连接操作。 事实表的键空间约为维度表的 30%。首先，我们将探讨在最终序列化对象大小方面，学习型布隆过滤器如何优于传统布隆过滤器。接下来，我们将展示将学习型布隆过滤器集成到工作负载处理管道中后所观察到的性能提升。

学习型布隆过滤器大小对比

如下所示，在给定的误报率下，与传统布隆过滤器相比，两种变体的学习型布隆过滤器可将总对象大小缩减 17% 至 42%。

此外，通过在基于梯度提升树的模型中使用更小的特征子集，我们在加快推理速度的同时，仅损失了极小比例的优化效果。

布隆过滤器应用结果 

在本节中，我们将基于布隆过滤器的连接与常规连接在多个指标上的性能进行比较。 

下表对比了使用和未使用学习型布隆过滤器的工作负载性能。下表的对比基于一个总误报率为1%的学习型布隆过滤器，且两种连接类型均采用相同的集群配置。 

首先，我们发现布隆过滤器的实现方案在 CPU 小时数上比常规连接操作高出多达 60%。由于评估布隆过滤器需要额外的计算开销，我们观察到基于学习型布隆过滤器方法的扫描步骤 CPU 使用率有所增加。然而，该步骤中进行的预过滤减少了需要进行洗牌的数据量，从而降低了下游步骤的 CPU 消耗，进而减少了总 CPU 小时数。

其次，与常规连接相比，学习型布隆过滤器的总数据量减少了约 80%，写入的总洗牌字节数也减少了约 80%。这使得连接性能更加稳定，如下文所述。 

在实验中的其他生产工作负载中，我们也观察到资源使用量的降低。在为期两周、涵盖全部五个工作负载的测试中，基于学习型布隆过滤器的方案平均每日节省了25%的成本，这一数据已包含模型训练和索引创建的开销。

由于执行连接时数据洗牌量减少，我们不仅显著降低了分析管道的运营成本，还提升了其稳定性。下图展示了在为期两周的实验期间，针对我们测试的五项工作负载，常规连接工作负载与基于学习型布隆过滤器的工作负载在运行时长（实际运行时间）上的波动情况（使用变异系数衡量）。 采用学习型布隆过滤器的运行更加稳定——持续时间更为一致——这为将其迁移至成本更低、可靠性较低的临时计算资源提供了可能性。 

参考文献

[1] T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis. 《学习型索引结构的论据》。https://arxiv.org/abs/1712.01208，2017。

[2] M. Mitzenmacher. 通过夹层法优化自适应布隆过滤器。 

https://arxiv.org/abs/1803.01474，2018年。

¹截至2023年6月30日的三个月

²截至2023年6月30日的三个月