HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

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

Indexing the Data Lake for Online Point Queries (engineering.atspotify.com)

8 pointsby kalaracey0 コメント

要約

Spotifyは、オンラインサービスやAIエージェントのために、低レイテンシでアクセス可能な膨大なデータを必要としています。従来の分散SQLエンジンは分析処理には適していますが、個々のデータポイントを高速に取得する点クエリにはオーバーヘッドが大きすぎます。Random Access Parquet (RAP) は、キーとデータファイルの場所を直接マッピングする外部インデックスを使用することで、このギャップを埋め、データレイク上のペタバイト級データを効率的にクエリ可能にします。

全文翻訳

データレイクをオンラインポイントクエリ用にインデックス化する

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) はこのギャップを埋めます。外部インデックスがキーを直接ファイル位置にマッピングし、正確な範囲読み込み(ranged read)が必要なバイトのみを取得します。RAPは、MLパイプライン、ノートブック、実験プラットフォーム、バッチ分析ですでに共有されているのと同じParquetファイル上で動作します。つまり、一度保存すれば一度だけ支払いが発生し、専門的なサービングシステムに個別のコピーを維持する必要がなくなります。

分散SQLエンジンは、 haystack(大量のデータ)の中から needle(目的のデータ)をどう見つけるか

ユーザーがAIエージェントに「去年の夏に何を聴いたか」と尋ねます。視聴履歴データだけでも、数十億人のユーザーにまたがり、数千の大規模な日次ファイルに分散しており、夏は約90日間です。1日あたり1,000ファイルと仮定すると、90,000個の個別のParquetファイルになります。オンラインユースケースにおいて、合理的な時間またはコンピューティング予算内で、これらのファイルのごく一部でも読み込むことは不可能です。

候補セットを絞り込む標準的な方法があります。各日次パーティション内では、ファイルをキーでさらにパーティショニングできます。これは、結合を高速化するためによく使用される手法ですが、キーが適切であればポイントルックアップにも役立ちます。ファイル名だけで、エンジンは特定のユーザーIDがそのファイルに含まれている可能性があるかどうかを知ることができます。1日あたり1,000バケットで、候補セットは90,000から90に減少します。BloomフィルターをユーザーID列に使用すると、ファイルを開かずにファイルを破棄できます。メタデータストアにキャッシュされると、90件の候補が、ユーザーが実際にアクティブだった12日間に絞り込まれる可能性があります。

それでも、その12個のファイルを読み込む必要があります。各ファイルは大きく、その中の1人のユーザーのデータを見つけるには、一連の依存する読み込みが必要です。まずフッターを読み込み、行グループのメタデータを解析し、キー列をスキャンして一致する行を見つけ、次に列とページインデックスを使用して各値列の対応するページを見つけます。これは、ファイルあたり、列あたり、複数回のラウンドトリップの依存読み込みであり、各ラウンドトリップは他のすべての同時クエリとIOPSを競合します。キーによるパーティショニングとBloomフィルターはファイルの選択に役立ちますが、ファイル内の問題は解決しません。

RAPのアプローチ

依存する読み込みの連鎖は根本的なボトルネックであり、すべてのストレージ階層に適用されます。各リンクはレイテンシー(次が開始される前に1回のラウンドトリップ)と帯域幅(次にどこを読み取るかを検出するためだけに読み取られたバイト数)を消費します。クラウドストレージでは、各I/Oリンクは数十ミリ秒かかります。ローカルSSDではマイクロ秒、メモリではナノ秒です。絶対的な数値は変わりますが、構造は同じです。各ステップは前のステップの結果に依存します。その連鎖を折りたたむこと、つまり依存する読み込みを単一の事前計算されたルックアップに置き換えることは、ストレージ階層に関係なく、レイテンシーと帯域幅の両方を節約します。このアプローチをクラウドオブジェクトストレージ上で説明しますが、ラウンドトリップごとのコストがその利点を最も劇的にするためであり、原則は一般的です。

スキャンする代わりに、RAPはルックアップします。外部インデックスが、各キーをそのデータが存在するファイルと行番号に直接マッピングします。キーが与えられると、リーダーはインデックスをルックアップし、キャッシュされたファイルメタデータを使用して行番号をページ位置に解決し、必要なページのみを正確に取得するために範囲読み込みを発行します。インデックスルックアップはO(1)であり、キャッシュされたページマッピングは低レイテンシー操作であり、データ取得は少数の正確な範囲読み込みです。重要なのは、これらの読み込みは並列に発行できることです。依存するロードチェーンはありません。

外部インデックス

RAPは、特別な準備なしに、既存のParquetファイルで動作できます。インデックスビルダーは、取得される列のフッターとページ位置を読み込み、キー列をスキャンしてキーから位置へのマッピングを構築し、それを書き出します。新しいデータが到着すると、各パイプライン実行は対応するインデックスエントリを生成します。インデックスは、既存のフラグメントを変更するのではなく、フラグメントを追記することで成長します。

インデックスはマルチマップです。単一のキーが複数のファイルやパーティションにわたるエントリを持つことができます。各エントリはコンパクトです。

フィールド説明
keyルックアップキー(例: ユーザーID、複合キーの場合もある)
fileどのParquetファイルか(辞書エンコードされた序数)
row numbersそのファイル内の行番号
value count (オプション)値の数、ページネーションを可能にする

目安として、テラバイトのインデックス作成はギガバイトのインデックスを生成し、ペタバイトのインデックス作成はテラバイトを生成します。大きなインデックスは、ハッシュバケッティングによって自然に分散します。

これは、Parquetの組み込みPageIndexやBloomフィルターとは根本的に異なります。それらは確率的であり、スキャンを絞り込みます。外部インデックスは決定的です。キーが与えられると、正確なファイルと行を返します。これにより、スキャンが完全に不要になります。

変更されていないファイルでは、RAPはターゲット行を含むページ全体を読み込みます。100バイトを抽出するために4MBのページになる可能性があります。レイテンシーまたはコストに敏感なワークロードの場合、書き込み時の準備により、読み込みが小さく、より正確にターゲット指定されます。これは、Parquetの内部とデータ処理パイプラインの詳細に入り込むことを意味しますが、そこに真のメリットがあります。

準備されたParquetファイルのための最適化

外部インデックスは、リーダーがファイルに触れる前に知っていることを変更します。つまり、必要な正確なファイル、行、列です。以下の最適化は、ポイントクエリに使用される列に適用されます。同じファイル内の他の列は、バッチ分析に最適なレイアウトを維持できます。これらの手法の多くはそれ自体で有用であり、一部はRAPだけでなく、あらゆるリーダーにメリットがあります。しかし、外部インデックスはトレードオフのバランスをシフトさせます。ファイル内検出(きめ細かいページインデックス、述語スキップのための小さなページ、プッシュダウンのための辞書エンコーディング)に役立つプロパティは重要度が低下し、最終的な読み込み(ラウンドトリップ回数の削減、フェッチサイズの縮小、連続したデータ)を最小限に抑えるプロパティがより重要になります。

最適化は3つのカテゴリに分類されます。キーデータの集中、読み取るバイト数の削減、読み込み回数の削減です。

キーデータの集中

キーによるソートにより、同じキーのすべての行がファイル内で連続し、可能な限り少ないページに集中します。多くのパイプラインはすでにソートされた出力を生成しています。ハッシュバケッティング(Spark、Scio SMB、Icebergバケット変換)は、各キーが一意に1つのファイルにマッピングされることを保証することで、さらに進みます。

Co-grouping — スキーマを構造化して、各キーが繰り返されるまたはネストされた列の値とともに1回だけ出現するようにします。例: SELECT user_id, ARRAY_AGG(STRUCT(timestamp, track_uri, duration_ms)) FROM streams GROUP BY user_id。これは、ソート順に依存せず、ファイルごとにキーごとに1行を提供し、多くの場合自然です。

より粗いパーティショニングは、キーがまたがるファイル数を減らします。日次パーティションは年間365ファイル/キーを生成しますが、週次では52に削減されます。これにより、インデックスエントリ、並列読み込み、インデックスが減少します。これは、バッチクエリのパーティションプルーニングの粒度とトレードオフになります。

読み取るバイト数の削減

インデックスが正確なページを指している場合でも、そのページはターゲットデータよりもはるかに大きい場合があります。

1ページあたり1キー。ライターはキーの境界でページをフラッシュします。キーが変わるたびにページ区切りが入ります。展開されたページ全体がターゲットキーに属するため、行の抽出は不要です。各ページが単一のキーに属するため、ページ位置はインデックスエントリに直接格納できます。個別のページインデックスは不要です。ファイルは標準的なParquetのままです。各キーの境界は、ページヘッダーのオーバーヘッドとして約20バイトを追加しますが、キーあたりのデータが substantial であれば無視できます。キーの境界でコンプレッサーをリセットすることは、圧縮率にほとんど影響しないことが多いですが、これはデータに依存します。副作用として、ParquetファイルにPageIndexが含まれている場合、それは従来のページ数ではなく、キーの数に比例して増加します。

ページ内のZSTDフレームリセット。1ページあたり1キーがPageIndexを肥大化させる場合、代替手段は従来のページサイズを維持しますが、各キーの行をページ内の個別のZSTDフレームとして圧縮します。インデックスは、各フレームのバイトオフセットとサイズを列ごとに格納し、個別のページインデックスなしで直接データにアドレス指定します。標準リーダーには、ページは通常どおり展開されます(ZSTDフレームは単純に連結されます)。RAPには、各フレームは独立してアドレス指定可能です。トレードオフ: 各フレーム内の値は、前のフレームなしで解釈可能である必要があります。これは、デルタエンコーディングやランレングスエンコーディングを排除します。PLAINまたは辞書エンコーディングはこれを満たしますが、一部のデータ型ではそれほどコンパクトではない場合があります。主要なRAPのユースケース(ブロブ、JSON、フラット値列)では、これは通常許容されます。

ストレージアラインメント。ZSTD スキップ可能なフレームは、フェッチをストレージブロック境界(例: 4KBまたは16KB)に合わせるためにキー間にパディングできます。ブロック境界をまたぐフェッチは、両方のブロックの読み込みを必要とします。IOPSが直接的な制約となるローカルディスクでは、アラインメントは不要なブロック読み込みを回避します。クラウドオブジェクトストレージでは、プロバイダーはIOPSごとに課金またはレート制限を行いませんが、基盤となるストレージは依然としてディスクでバックアップされているため、アラインメントは有用なマイクロ最適化のままです。パディングは小さく、ファイルは有効なParquetのままです。

読み込み操作の削減

標準的なParquetファイルでは、N列にわたるキーの値を取得するにはN回の並列読み込みが必要です。これはリクエスト容量のN倍を消費し、キーあたりのレイテンシーを分布のテールに押し上げます。読み込み回数の削減が最大の単一のメリットです。

ブロブとバリアント。ランダムアクセスに必要なフィールドを単一の列(JSON、Protobuf、またはParquet Variant)として格納すると、ファイルあたり1回の読み込みで済みます。これは、オンラインアプリケーションがデータをドキュメントとして消費する方法と自然に一致します。トレードオフは、バッチ分析がフィールドごとの列プルーニングとブロブ内の述語プッシュダウンを失うことです。

列のインターリーブ。複数の列が必要な場合(ポイントクエリ用、バッチ分析用など)、ライターはそれらを物理的にインターリーブできます。各キーの異なる列からのデータは隣接して書き込まれます。キー1の列A、キー1の列B、キー2の列A、キー2の列B。ZSTDスキップ可能なフレームは列間に配置され、各列は有効な圧縮ストリームのままになります。従来のリーダーは列Aをシーケンシャルに読み込み、デコンプレッサーはスキップフレーム内の列Bのデータをサイレントにスキップします。RAPリーダーは、キーのすべての列にまたがる単一の連続した範囲読み込みを発行します。ファイルは完全に有効なParquetのままです。

[画像: Interleaving Columns]

これは、後方互換性を壊すことなく、選択された列グループに対してレイアウトを事実上行優先にピボットすることです。トレードオフ: 単一のインターリーブ列を読み取る従来のリーダーは、他の列のデータもデッドスペースとして読み取るため、単一列スキャンのI/Oボリュームが増加します。ローカルストレージでは、これは通常OSキャッシュによって吸収されます。クラウドストレージでは、リーダーは重複する読み込みをマージする必要があります。

インターリーブは、部分的にシュレッドされたVariant列に特に役立ちます。型付けされた列は高速なベクトル化分析を可能にし、Variantブロブをそれらと並べて配置することで、RAPの単一読み込みアクセスを、分析リーダーのオーバーヘッドを最小限に抑えながら実現できます。

カバリングインデックスとホイスト値。インデックスビルダーは、ビルド時にすべての行を訪問します。小さな値の場合、値をインデックスエントリに直接ホイストできます。これは、ストレージ読み込みを完全に排除するカバリングインデックスであり、読み込み回数をゼロに削減します。これは、事前計算された集計にまで拡張されます。キーごとのイベント数、総再生時間、カテゴリの内訳などが、インデックスルックアップ速度で利用可能になります。ホイストされた値は、ストレージ読み込みを行う前にエントリをフィルタリングすることで、インデックスレベルでの述語プッシュダウンも可能にします。

要約
最適化ポイントルックアップのメリット分析のトレードオフ
キーによるソートキーあたりのファイル数とページ数が少ないなし
Co-groupingキーあたり1行。自然に集中
より粗いパーティショニングキーあたりのファイル数が少ない(時間経過)より粗いパーティションプルーニング
1ページあたり1キーページ全体が結果PageIndexの適度な増加
ZSTDフレームリセットページ増加なしでO(1)アクセスPLAINエンコーディングのみ。ファイルサイズの適度な増加
ブロブ/バリアントキーあたり単一列読み込みフィールドごとのプルーニングなし
列のインターリーブすべての列に対する単一の連続読み込み単一列スキャンのI/O増加
ストレージアラインメント境界での読み込み増幅なしファイルサイズの適度な増加
カバリングインデックスストレージ読み込みは全く不要インデックスサイズの増加

これらの最適化を組み合わせることで、ポイントクエリを数キロバイトの単一範囲読み込みに削減できます。あるいは、ストレージ読み込みを完全に排除できます。

セカンダリインデックス

データセットには複数のルックアップディメンションがある場合があります。例えば、buyer_idとseller_idの両方でクエリされるトランザクションデータセットなどです。RAPは、各ディメンションごとに複数のアクセス構造を同じインデックスエントリ上に構築することでこれをサポートします。ハッシュテーブルはO(1)の正確なルックアップを提供し、ソート済みインデックスは範囲クエリを可能にします。セカンダリインデックスの追加または削除は、サービングレイヤーの決定であり、パイプラインの変更やデータの書き換えは不要です。

ファイルレイアウトは、データがソートされたディメンションを優先します。セカンダリールックアップはより多くのファイルにまたがる可能性がありますが、リーダーは隣接するバイト範囲を自動的にマージします。空間充填曲線(Zオーダー曲線やヒルベルト曲線など)は補完的です。これらはファイルレイアウトレベルでセカンダリディメンションのローカリティを改善し、セカンダリインデックスはアクセスパスを提供します。

結論

RAPの重要な特性は、データレイクにすでに存在するのと同じParquetファイル上で動作することです。BigQueryが週次集計レポートをスキャンするファイルと、AIエージェントがコンテキスト取得のために読み取るファイルは同じです。コピーなし、ETLなし、2番目のストレージ請求なし。

これにより、オンラインで提供できるデータの経済性が変わります。現在、チームはKVストアに何を保持するかについて厳しい選択をしていますが、それはGBあたりのコストが優先順位付けを強制するためです。RAPを使用すると、ポイントクエリのコストはクラウドストレージの読み込みコストにまで低下します。履歴データ、ロングテールエンティティ、低トラフィック機能など、すべてがインタラクティブアクセスに実行可能になります。AIエージェントは、KVストアが保持するものにコンテキストを限定する必要はありません。レイクの広範囲にわたって数ヶ月または数年を遡ることができます。

データレイクはもはやバッチ専用ではありません。同じストレージが分析ワークロードとインタラクティブワークロードの両方にサービスを提供します。1つのデータセット、2つのアクセスパターンです。