Roblox 如何通过机器学习优化的布隆过滤器降低 Spark Join 查询成本 – Roblox 博客

抽象

每天在 Roblox 上，65.5 百万用户参与数百万次体验，总计 14.0 每季度 1 亿小时。 这种交互会生成 PB 级数据湖，该数据湖经过丰富的分析和机器学习 (ML) 目的。 在我们的数据湖中加入事实表和维度表是一项资源密集型工作，因此为了优化这一点并减少数据洗牌，我们采用了学习型布隆过滤器 [XNUMX]——使用 ML 的智能数据结构。 通过预测存在，这些过滤器可以显着修剪连接数据，从而提高效率并降低成本。 在此过程中，我们还改进了模型架构，并展示了它们在减少处理内存和 CPU 时间以及提高操作稳定性方面所带来的巨大优势。

介绍

在我们的数据湖中，事实表和数据立方体被临时分区以实现高效访问，而维度表缺乏这样的分区，并且在更新期间将它们与事实表连接起来是资源密集型的。 连接的键空间由所连接的事实表的时间分区驱动。 该时间分区中存在的维度实体是整个维度数据集中存在的维度实体的一小部分。 结果，这些连接中大部分打乱的维度数据最终被丢弃. 为了优化这个过程并减少不必要的洗牌，我们考虑使用 布隆过滤器 在不同的连接键上，但面临过滤器大小和内存占用问题。

为了解决这些问题，我们探索了 学习的布隆过滤器，一种基于 ML 的解决方案，可减少 Bloom Filter 的大小，同时保持较低的误报率。 这项创新通过降低计算成本和提高系统稳定性来提高连接操作的效率。 下图说明了我们的分布式计算环境中的传统连接过程和优化连接过程。

使用学习的布隆过滤器提高连接效率

为了优化事实表和维度表之间的连接，我们采用了 Learned Bloom Filter 实现。 我们根据事实表中存在的键构建了一个索引，然后在连接操作之前部署该索引来预过滤维度数据。 

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

虽然传统的布隆过滤器很高效，但它为每个工作节点增加了 15-25% 的额外内存，需要加载它才能达到我们期望的误报率。 但通过利用学习布隆过滤器，我们在保持相同误报率的同时显着减小了索引大小。 这是因为布隆过滤器转化为二元分类问题。 正标签表示索引中存在值，而负标签表示索引中不存在值。

ML 模型的引入有助于对值进行初始检查，然后使用备份布隆过滤器来消除误报。 尺寸的减小源于模型的压缩表示以及备份布隆过滤器所需的键数量的减少。 这与传统的布隆过滤器方法不同。 

作为这项工作的一部分，我们建立了两个指标来评估学习的布隆过滤器方法：索引的最终序列化对象大小和执行连接查询期间的 CPU 消耗。 

应对实施挑战

我们最初的挑战是解决事实表中维度表键很少的高度偏差的训练数据集。 在此过程中，我们观察到表之间大约有三分之一的键重叠。 为了解决这个问题，我们利用了三明治学习布隆过滤器方法 [2]。 它集成了初始的传统布隆过滤器，通过删除事实表中缺失的大部分键来重新平衡数据集分布，从而有效地消除数据集中的负样本。 随后，只有初始布隆过滤器中包含的键以及误报被转发到 ML 模型，通常称为“学习预言机”。 这种方法为学习预言机提供了一个均衡的训练数据集，有效地克服了偏差问题。

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

第三个挑战——推理延迟——需要的模型既能最大限度地减少误报，又能提供快速响应。 梯度增强树模型是这些关键指标的最佳选择，我们修剪了其特征集以平衡精度和速度。

我们使用学习到的布隆过滤器更新的连接查询如下所示：

成果

以下是我们在数据湖中使用学习布隆过滤器进行实验的结果。 我们将它们集成到五个生产工作负载中，每个工作负载都具有不同的数据特​​征。 这些工作负载中计算成本最高的部分是事实表和维度表之间的联接。 事实表的键空间大约是维度表的30%。 首先，我们讨论学习型布隆过滤器如何在最终序列化对象大小方面优于传统布隆过滤器。 接下来，我们展示了通过将学习型布隆过滤器集成到我们的工作负载处理管道中观察到的性能改进。

学习的布隆过滤器大小比较

如下所示，当考虑给定的误报率时，与传统的布隆过滤器相比，学习的布隆过滤器的两个变体将总对象大小提高了 17-42%。

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

学习到的布隆过滤器使用结果 

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

下表比较了使用和不使用学习型布隆过滤器的工作负载的性能。 总误报概率为 1% 的学习布隆过滤器演示了下面的比较，同时为两种连接类型保持相同的集群配置。 

首先，我们发现 Bloom Filter 实现的 CPU 小时数比常规连接高出 60%。 我们发现学习型布隆过滤器方法的扫描步骤的 CPU 使用率有所增加，因为评估布隆过滤器需要额外的计算。 但是，此步骤中完成的预过滤减少了混洗数据的大小，这有助于减少下游步骤使用的 CPU，从而减少总 CPU 时间。

其次，与常规连接相比，学习型布隆过滤器的总数据大小减少了约 80%，写入的总 shuffle 字节减少了约 80%。 这会带来更稳定的连接性能，如下所述。 

我们还在实验中发现其他生产工作负载的资源使用量有所减少。 在两周的时间里，所有五个工作负载的学习布隆过滤器方法产生了平均 日常成本节省 of 25％， 这也解释了模型训练和索引创建。

由于执行连接时洗牌的数据量减少，我们能够显着降低分析管道的运营成本，同时也使其更加稳定。下图显示了运行持续时间（墙）的变化性（使用变异系数）对于我们试验的五个工作负载，常规连接工作负载和基于学习布隆过滤器的工作负载在两周内的时钟时间）。 使用学习布隆过滤器的运行更加稳定——持续时间更加一致——这开启了将它们转移到更便宜的瞬态不可靠计算资源的可能性。 

参考资料

[1] T. Kraska、A. Beutel、EH Chi、J. Dean 和 N. Polyzotis。 学习索引结构的案例。 https://arxiv.org/abs/1712.012082017。

[2] M.米岑马赫。 通过三明治优化学习布隆过滤器。 

https://arxiv.org/abs/1803.014742018。

---

¹截至 3 年 30 月 2023 日的 XNUMX 个月

²截至3年30月2023日的XNUMX个月

• SEO 支持的内容和 PR 分发。 今天得到放大。
• PlatoData.Network 垂直生成人工智能。 赋予自己力量。 访问这里。
• 柏拉图爱流。 Web3 智能。 知识放大。 访问这里。
• 柏拉图ESG。 碳， 清洁科技, 能源， 环境， 太阳能， 废物管理。 访问这里。
• 柏拉图健康。 生物技术和临床试验情报。 访问这里。
• Sumber: https://blog.roblox.com/2023/11/roblox-reduces-spark-join-query-costs-machine-learning-optimized-bloom-filters/