Roblox が機械学習に最適化されたブルームフィルターを使用して Spark 結合クエリのコストを削減する方法 - Roblox ブログ

プラトン再発行

フォロワー： 0

抽象

Roblox では毎日 65.5 14.0 万人のユーザーが数百万のエクスペリエンスに参加し、合計 XNUMX 四半期ごとに 1 億時間。この相互作用により、分析と機械学習 (ML) の目的で強化されたペタバイト規模のデータレイクが生成されます。データレイク内のファクトテーブルとディメンションテーブルを結合するにはリソースを大量に消費するため、これを最適化し、データシャッフルを減らすために、ML を使用したスマートなデータ構造である学習済みブルームフィルター [XNUMX] を採用しました。これらのフィルターは存在を予測することで結合データを大幅にトリミングし、効率を高めてコストを削減します。その過程で、モデルアーキテクチャも改善し、メモリと CPU の処理時間の削減、および動作の安定性の向上に大きなメリットがもたらされることを実証しました。

概要

データレイクでは、ファクトテーブルとデータキューブは効率的なアクセスのために一時的にパーティション化されていますが、ディメンションテーブルにはそのようなパーティションがなく、更新中にそれらをファクトテーブルと結合するとリソースが大量に消費されます。結合のキー空間は、結合されるファクトテーブルの一時パーティションによって決まります。その時間パーティションに存在するディメンションエンティティは、ディメンションデータセット全体に存在するディメンションエンティティの小さなサブセットです。その結果、これらの結合内のシャッフルされたディメンションデータの大部分は最終的に破棄されます。. このプロセスを最適化し、不必要なシャッフルを減らすために、次の使用を検討しました。ブルームフィルター個別の結合キーを使用していましたが、フィルターサイズとメモリフットプリントの問題に直面していました。

それらに対処するために、私たちは調査しました学習済みブルームフィルターは、誤検知率を低く維持しながらブルームフィルターのサイズを削減する ML ベースのソリューションです。この革新により、計算コストが削減され、システムの安定性が向上するため、結合操作の効率が向上します。次の図は、分散コンピューティング環境における従来の最適化された結合プロセスを示しています。

学習済みブルームフィルターによる結合効率の向上

ファクトテーブルとディメンションテーブル間の結合を最適化するために、学習済みブルームフィルター実装を採用しました。ファクトテーブルに存在するキーからインデックスを構築し、その後、結合操作の前にそのインデックスをデプロイしてディメンションデータを事前にフィルタリングしました。

従来のブルームフィルターから学習されたブルームフィルターへの進化

従来のブルームフィルターは効率的ですが、望ましい誤検知率に達するためにロードする必要があるワーカーノードごとに 15 ～ 25% の追加メモリが追加されます。しかし、Learned Bloom Filters を利用することで、同じ誤検知率を維持しながらインデックスサイズを大幅に削減することができました。これは、ブルームフィルターがバイナリ分類問題に変換されるためです。正のラベルはインデックスに値が存在することを示し、負のラベルは値が存在しないことを意味します。

ML モデルの導入により、値の最初のチェックが容易になり、その後、偽陰性を排除するためのバックアップブルームフィルターが実行されます。サイズの縮小は、モデルの圧縮表現と、バックアップブルームフィルターに必要なキーの数の減少に起因します。これは、従来のブルームフィルターアプローチとは異なります。

この作業の一環として、学習済みブルームフィルターアプローチを評価するための XNUMX つの指標、つまりインデックスの最終シリアル化オブジェクトサイズと結合クエリ実行時の CPU 消費量を確立しました。

実装上の課題を乗り越える

私たちの最初の課題は、ファクトテーブルにディメンションテーブルキーがほとんどない、非常に偏ったトレーニングデータセットに対処することでした。その際、テーブル間で約 2 分の XNUMX のキーが重複していることが観察されました。これに取り組むために、私たちは Sandwich Learned Bloom Filter アプローチを活用しました [XNUMX]。これは、初期の従来のブルームフィルターを統合し、ファクトテーブルから欠落していたキーの大部分を削除することでデータセットの分布を再調整し、データセットから負のサンプルを効果的に排除します。その後、最初のブルームフィルターに含まれるキーのみが、誤検知とともに、「学習されたオラクル」と呼ばれる ML モデルに転送されました。このアプローチにより、学習されたオラクルのバランスの取れたトレーニングデータセットが得られ、バイアスの問題が効果的に克服されました。

1 番目の課題は、モデルのアーキテクチャとトレーニング機能に重点を置きました。フィッシング URL の古典的な問題 [XNUMX] とは異なり、結合キー (ほとんどの場合、ユーザー/エクスペリエンスの一意の識別子) は本質的に有益ではありませんでした。これにより、ディメンションエンティティがファクトテーブルに存在するかどうかを予測するのに役立つ潜在的なモデル機能としてディメンション属性を調査するようになりました。たとえば、特定の言語でのエクスペリエンスに関するユーザーセッション情報を含むファクトテーブルを想像してください。ユーザーディメンションの地理的位置または言語設定属性は、個々のユーザーがファクトテーブルに存在するかどうかを示す良い指標となります。

XNUMX 番目の課題である推論遅延については、偽陰性を最小限に抑え、迅速な応答を提供するモデルが必要でした。これらの主要な指標には、勾配ブーストツリーモデルが最適な選択であり、精度と速度のバランスを取るためにその機能セットを削減しました。

学習されたブルームフィルターを使用した更新された結合クエリは次のとおりです。

結果

データレイクで学習したブルームフィルターを使用した実験の結果を次に示します。これらを 30 つの本番ワークロードに統合し、それぞれが異なるデータ特性を持っていました。これらのワークロードの中で最も計算コストがかかる部分は、ファクトテーブルとディメンションテーブルの間の結合です。ファクトテーブルのキースペースは、ディメンションテーブルの約 XNUMX% です。まず、最終的なシリアル化されたオブジェクトサイズの点で、学習済みブルームフィルターが従来のブルームフィルターよりも優れたパフォーマンスを発揮したことについて説明します。次に、Learned Bloom Filters をワークロード処理パイプラインに統合することで観察されたパフォーマンスの向上を示します。

学習済みブルームフィルターのサイズ比較

以下に示すように、特定の誤検知率を見ると、学習されたブルームフィルターの 17 つのバリアントは、従来のブルームフィルターと比較して、合計オブジェクトサイズが 42 ～ XNUMX% 向上します。

さらに、勾配ブーストされたツリーベースのモデルで機能のより小さなサブセットを使用することで、推論を高速化しながら最適化の損失をほんのわずかに抑えることができました。

学習されたブルームフィルターの使用結果

このセクションでは、ブルームフィルターベースの結合のパフォーマンスを、いくつかのメトリックにわたって通常の結合のパフォーマンスと比較します。

以下の表は、学習済みブルームフィルターを使用した場合と使用しない場合のワークロードのパフォーマンスを比較しています。合計誤検知確率が 1% の学習済みブルームフィルターは、両方の結合タイプで同じクラスター構成を維持しながら、以下の比較を示します。

まず、ブルームフィルターの実装は、CPU 時間で通常の結合よりも 60% も優れたパフォーマンスを示したことがわかりました。ブルームフィルターの評価に追加のコンピューティングが費やされたため、学習済みブルームフィルターアプローチのスキャンステップの CPU 使用率が増加しました。ただし、このステップで行われた事前フィルタリングにより、シャッフルされるデータのサイズが削減され、下流のステップで使用される CPU が削減され、合計 CPU 時間が削減されました。

第 80 に、学習済みブルームフィルターでは、通常の結合よりも合計データサイズが約 80% 少なく、書き込まれる合計シャッフルバイト数も約 XNUMX% 少なくなります。これにより、以下で説明するように、結合パフォーマンスがより安定します。

また、実験中の他の運用ワークロードでもリソース使用量の削減が確認されました。 XNUMX つのワークロードすべてにわたって XNUMX 週間にわたって、学習済みブルームフィルターアプローチにより平均値が生成されました。 日々のコスト削減 of 25％、 これには、モデルのトレーニングとインデックスの作成も含まれます。

結合の実行中にシャッフルされるデータの量が減少したため、分析パイプラインの運用コストを大幅に削減すると同時に、分析パイプラインの安定性を高めることができました。次のグラフは、実行時間 (ウォール) の変動性 (変動係数を使用) を示しています。実験した XNUMX つのワークロードについて、通常の結合ワークロードと学習済みブルームフィルターベースのワークロードを XNUMX 週間にわたって実行しました。学習済みブルームフィルターを使用した実行はより安定しており、継続時間がより一貫しているため、安価で一時的な信頼性の低いコンピューティングリソースに移行できる可能性が開かれています。