データレイクのオンラインポイントクエリのためのインデックス作成

オンラインポイントクエリのためのデータレイクのインデックス作成 Spotifyのような企業は、オンラインサービスや、ユーザーに代わって動作するAIエージェントのために、低レイテンシでアクセス可能な膨大な量のデータを必要としています。オンラインサービス、例えばユーザーの視聴履歴を使用または表示するポータルやパーソナライゼーション機能は、インタラクティブな速度でユーザーごとのデータを検索し、ページネーションする必要があります。AIエージェントは、「去年の夏は何を聴いていた？」のような質問に答えるために、ユーザーのデータを迅速に取得し、それを推論（フィルタリング、集計、あるいはローカルでのSQL実行など）してLLMプロンプトのコンテキストを構築する必要があります。どちらのパターンも、BigtableやDynamoDBのようなキーバリューストア（KVストア）に経済的に常駐させるには大きすぎるデータセットに対して、キーによる高速なポイントクエリという同じ基盤となるプリミティブを共有しています。 Spotifyでは、ペタバイトのデータがオンラインユースケースのためにBigtableに格納されていますが、エクサバイトはGCSデータレイクにあります。データレイクの基盤となるストレージは高速であり、さらに高速化しています。GCSはリクエストあたり30〜100ミリ秒を提供し、S3 Express One ZoneとGCS Rapid Storageは現在、シングルミリ秒台のレイテンシを提供しています。ボトルネックは、ストレージレイヤー自体ではなく、その上のクエリエンジンになりつつあります。TrinoやBigQueryのような分散SQLエンジンは、単一行ルックアップであっても、秒単位のジョブスケジューリングとクエリプランニングのオーバーヘッドを追加します。これらは分析スループット向けに設計されており、インタラクティブなポイントクエリ向けではありません。 Random Access Parquet (RAP) はこのギャップを埋めます。外部インデックスがキーを直接ファイル位置にマッピングし、正確な範囲読み込みがまさに必要なバイトを取得します。RAPは、MLパイプライン、ノートブック、実験プラットフォーム、バッチ分析によってすでに共有されている同じParquetファイル上で動作します。つまり、一度保存すれば一度だけ支払いが発生し、専用のサービングシステムに別々のコピーを維持する必要がありません。 分散SQLエンジンが干し草の中から針を見つける方法 ユーザーがAIエージェントに「去年の夏は何を聴いていたか」と尋ねます。視聴履歴データだけでも、数千の大きな日次ファイルにわたる数十億人のユーザーに及び、夏は約90日間です。1日あたり1,000ファイルと仮定すると、90,000個の個別のParquetファイルになります。オンラインユースケースで合理的な時間またはコンピューティング予算内で、各ファイルからわずかでも読み取ることは、実行不可能になります。 候補セットを減らす標準的な方法があります。各日次パーティション内で、ファイルをキーでさらにパーティション化できます。これは、結合を高速化するためによく使用される手法であり、キーが適切であればポイントルックアップにも役立ちます。ファイル名だけでも、エンジンは特定のユーザーIDがそのファイルに含まれる可能性があるかどうかを知ることができます。1日あたり1,000バケットで、候補セットは90,000から90に減少します。BloomフィルターをユーザーID列に適用すると、ファイルを開かずにファイルを破棄できます。メタデータストアにキャッシュされたBloomフィルターは、ユーザーが実際にアクティブだった12日間に候補を絞り込みます。 それでも、その12個のファイルを読み取る必要があります。各ファイルは大きく、1人のユーザーのデータをその中から見つけるには、一連の依存する読み取りが必要です。フッターの取得、行グループメタデータの解析、一致する行を見つけるためのキー列のスキャン、そして対応するページを各値列で見つけるための列とページインデックスの使用。これは、ファイルごと、列ごとにクラウドストレージへの複数の依存ラウンドトリップフェッチであり、各ラウンドトリップは他のすべての同時クエリとIOPSを競合します。キーによるパーティショニングとBloomフィルターはファイルの選択に役立ちますが、ファイル内の問題は解決しません。 RAPアプローチ 依存する読み取りの連鎖は根本的なボトルネックであり、すべてのストレージ階層に適用されます。各リンクはレイテンシ（次を開始する前に1回のラウンドトリップ）と帯域幅（次にどこを読むかを検出するためだけに読み取られるバイト）を消費します。クラウドストレージでは、各I/Oリンクは数十ミリ秒かかります。ローカルSSDではマイクロ秒、メモリではナノ秒です。絶対的な数値は変わりますが、構造は同じです。各ステップは前のステップの結果に依存します。その連鎖を折りたたむ、つまり依存する読み取りを単一の事前計算されたルックアップに置き換えることで、ストレージ階層に関係なくレイテンシと帯域幅の両方を節約できます。ここではクラウドオブジェクトストレージでアプローチを説明しますが、これはラウンドトリップごとのコストがメリットを最も劇的にするためであり、原則は一般的です。 スキャンする代わりに、RAPはルックアップします。外部インデックスが、各キーをそのデータが存在する各ファイルと行番号に直接マッピングします。キーが与えられると、リーダーはインデックスをルックアップし、キャッシュされたファイルメタデータを使用して行番号をページ位置に解決し、必要なページを正確に取得するために範囲読み込みを発行します。インデックスルックアップはO(1)であり、キャッシュされたページマッピングは低レイテンシ操作であり、データ取得は少数の正確な範囲読み込みです。重要なのは、これらの読み込みは並列に発行できることです。依存するロードチェーンはありません。 外部インデックス RAPは、特別な準備なしに既存のParquetファイル上で動作できます。インデックスビルダーは、取得される列のフッターとページ位置を読み取り、キー列をスキャンしてキーから位置へのマッピングを構築し、それを書き出します。新しいデータが到着するにつれて、各パイプライン実行は対応するインデックスエントリを生成します。インデックスは、既存のエントリを変更するのではなく、フラグメントを追記することで成長します。 インデックスはマルチマップです。単一のキーが多くのファイルやパーティションにわたるエントリを持つことができます。各エントリはコンパクトです。 フィールド 説明 key ルックアップキー（例：ユーザーID、複合キーの可能性あり） file Parquetファイル（辞書エンコードされた序数） row numbers そのファイル内の行 value count (optional) 値の数、ページネーションを可能にする 経験則として、テラバイトのインデックス作成はギガバイトのインデックスを生成し、ペタバイトのインデックス作成はテラバイトを生成します。大きなインデックスはハッシュバケットによって自然に分散されます。 これは、Parquetの組み込みのPageIndexやBloomフィルターとは根本的に異なります。それらは確率的であり、スキャンを絞り込みます。外部インデックスは決定的です。キーが与えられると、正確なファイルと行を返してスキャンを完全に排除します。 変更されていないファイルでは、RAPはターゲット行を含むページ全体を読み取ります。つまり、100バイトを抽出するために4MBのページを読み取る可能性があります。レイテンシまたはコストに敏感なワークロードの場合、書き込み時の準備により、読み取りが小さくなり、より正確にターゲット指定されます。これは、Parquetの内部とデータ処理パイプラインの詳細に入り込むことを意味しますが、そこに真の勝利があります。 準備されたParquetファイルのための最適化 外部インデックスは、リーダーがファイルに触れる前に知っていることを変更します。つまり、正確なファイル、行、および必要な列です。以下の最適化は、ポイントクエリを提供する列に適用されます。同じファイル内の他の列は、バッチ分析に最適なレイアウトを維持できます。これらの手法の多くはそれ自体で有用であり、一部はRAPだけでなく、あらゆるリーダーにメリットがあります。しかし、外部インデックスはトレードオフのバランスをシフトさせます。ファイル内の発見を助けるプロパティ（きめ細かいページインデックス、述語スキップのための小さなページ、プッシュダウンのための辞書エンコーディング）は重要性が低下し、最終的な読み取りを最小限に抑えるプロパティ（ラウンドトリップ回数の削減、読み取りバイト数の削減、連続したデータ）がより重要になります。 最適化は3つのカテゴリに分類されます。キーデータの集中化、読み取りあたりのバイト数の削減、読み取り回数の削減。 キーデータの集中化 キーによるソートは、同じキーのすべての行がファイル内で連続していることを保証し、それらをできるだけ少ないページに集中させます。多くのパイプラインはすでにソートされた出力を生成しています。ハッシュバケット（Spark、Scio SMB、Icebergバケット変換）は、各キーが一意に1つのファイルにマッピングされることを保証することで、さらに進みます。 コグループ化、つまり各キーが値とともに繰り返されるかネストされた列で1回だけ出現するようにスキーマを構造化すること（例：SELECT user_id, ARRAY_AGG(STRUCT(timestamp, track_uri, duration_ms)) FROM streams GROUP BY user_id）は、ソート順に依存せずにファイルごとに1つのキーの行を生成し、多くの場合自然です。 より粗いパーティショニングは、キーがまたがるファイルの数を減らします。日次パーティショニングは年間あたりキーごとに365ファイルを生成しますが、週次パーティショニングはこれを52に減らします。これにより、インデックスエントリ、並列読み取り、インデックスが小さくなります。これは、バッチクエリのパーティションプルーニングの粒度と引き換えられます。 読み取りバイト数の削減 インデックスが