大規模かつ迅速な近似分析: Apache DataSketches が BigQuery で利用可能に
Nikunj Bhartia
Cloud Data Engineer, Google
Matthew Sajban
Director of Software Development Engineering, Yahoo Inc.
昨今のデータドリブンな世の中では、大規模なデータセットを理解するために多くの場合、複雑な非加算集計演算を何度も行う必要があります1。しかし、データのサイズが膨大になると、従来の方法ではこのような演算は計算コストが高額になり、時間もかかります2。そこで役立つのが Apache DataSketches です。このたび、大規模な近似分析のための優れたツールとして、BigQuery 内で Apache DataSketches 関数を利用できるようになりました。
Apache DataSketches は、スケッチ（大規模なデータセットを効率的に要約する特殊なストリーミング アルゴリズム）のオープンソース ライブラリです。スケッチは、メモリと計算のオーバーヘッドを最小限に抑えつつ、データを 1 回処理するだけで、個別のカウント、分位数、ヒストグラム、その他の統計的測定値を高精度で推定できる小規模な確率的データ構造です。一部を除き、これらのスケッチは数学的に証明された誤差範囲、つまり真の値とその推定値または近似値の間の最大差を提供します。こうした誤差範囲は、スケッチのサイズと誤差範囲のサイズのトレードオフとしてユーザーが調整できます。構成するスケッチが大きいほど、誤差範囲のサイズは小さくなります。
スケッチを使用すると、特に正確な計算が現実的でない場合や不可能な場合、大規模なデータセットから迅速に分析情報を得ることができます。スケッチ自体をマージして加算したり、高度に並列化したりできるため、複数のデータセットのスケッチを組み合わせて詳細な分析を行うことができます。このようにサイズが小さく、マージ可能なため、従来の方法と比較して計算ワークロードの速度が桁違いに向上します。
BigQuery で DataSketches を使用する理由
BigQuery はペタバイト規模のデータを処理できることで知られており、DataSketches はこのような環境に適しています。DataSketches 関数を使用すると、BigQuery で次のことが可能になります。
-
迅速な近似クエリの実行: 大規模なデータセットについて、個別のカウント、分位数分析、アダプティブ ヒストグラム、その他の非加算集計計算の結果をほぼ瞬時に取得できます。
-
リソースの節約: 元データではなくコンパクトなスケッチを使用することで、クエリの費用とストレージの必要量を減らすことができます。
-
システム間の移動: DataSketches は明確に定義されたバイナリ表現を保存しているため、精度を損なうことなく、スケッチをシステム間で転送し、Java、C++、Python という 3 つの主要言語で解釈できます。
Apache DataSketches は、WebAssembly（WASM）ライブラリにコンパイルされた Apache DataSketches C++ コアライブラリを使用し、カスタム C++ 実装を通じて BigQuery に導入され、BigQuery の JavaScript ユーザー定義集計関数（JS UDAF）内に読み込まれます。
BigQuery のお客様による Apache DataSketches の使用事例
Yahoo は 2011 年に Apache DataSketches プロジェクトを開始し、2015 年にオープンソース化しました。現在も Apache DataSketches ライブラリを使用しています。また、個別のカウント、分位数、最頻アイテム（別名「ヘビーヒッター」）などのさまざまな分析クエリ オペレーションで、近似結果が使用されています。Yahoo は最近、Google Cloud と BigQuery プラットフォームに対する Google 定義の JavaScript ユーザー定義集計関数（UDAF）インターフェースを使用して、大規模な BigQuery を活用できるように DataSketches ライブラリを改良しました。
「Yahoo は 10 年以上にわたって Apache DataSketches ライブラリを使用し、社内の本番環境処理システムで大量のデータを分析してきました。データスケッチにより、総当たり計算に比べてわずかな時間と費用で、数秒でデータを要約する幅広いクエリに対応できるようになりました。このパワフルなテクノロジーを開発した初期のイノベーターとして、この高速で精度の高い大規模なオープンソース テクノロジーが Google Cloud BigQuery 環境のユーザーの方々にご利用いただけるようになることを嬉しく思います。」- Yahoo、ソフトウェア開発エンジニアリング担当ディレクター Matthew Sajban 氏
注目のスケッチ
では、Apache DataSketches で何ができるのでしょうか。BigQuery と統合されたスケッチをご紹介します。
カーディナリティ スケッチ
-
Hyper Log Log Sketch（HLL）: DataSketches ライブラリは、この歴史的に有名なスケッチ アルゴリズムを汎用的に実装しています。単純な個別のカウント（またはカーディナリティ）の推定に最適です。精度要件に応じて、約 50 バイトから約 2 MB までのさまざまなサイズに適応できます。また、HLL_4、HLL_6、HLL_8 という 3 つのバリエーションがあり、速度とサイズの追加調整が可能です。
-
Theta Sketch: このスケッチは集合表現に特化しており、通常の加算和集合だけでなく、積集合と差集合を使用したスケッチ間の完全な集合表現も可能です。代数の機能があるため、特によく使用されています。サイズは、精度要件に応じて数百バイトから数メガバイトまでさまざまです。
-
CPC Sketch: このカーディナリティ スケッチはアルゴリズムに関する最近の研究成果を活用しており、従来の HLL スケッチよりも小さい保存サイズで同じ精度が得られます。保存サイズあたりの精度が最も重要な指標となる状況を対象としています。
-
Tuple Sketch: Theta Sketch を拡張し、スケッチによって保持される一意のアイテムのそれぞれに、他の値を関連付けられるようにします。これにより、インプレッション数やクリック数などの属性の要約を計算したり、顧客エンゲージメントなどの複雑な分析を行ったりできます。
分位スケッチ
-
KLL Sketch: このスケッチは、分位数（中央値、パーセンタイルなど）の推定用に設計されており、分布の理解、密度とヒストグラムのプロットの作成、大規模なデータセットのパーティショニングに最適です。このスケッチで使用されている KLL アルゴリズムは、所定のサイズに対して統計的に最適な分位近似精度を得られることが証明されています。KLL Sketch は、比較可能なあらゆる種類のデータ（アイテム間の並べ替え順序が定義されているデータ）に使用できます。KLL の精度は入力データの分布の影響を受けません。
-
REQ Sketch: この分位スケッチは、ランクドメインの端の精度が中央値よりも重要である状況向けに設計されています。つまり、99.99 パーセンタイルの精度に最も関心があり、50 パーセンタイルの精度にはそれほど関心がない場合は、このスケッチを選択します。KLL Sketch と同様に、このスケッチには数学的に証明された誤差範囲があります。REQ Sketch は、比較可能なあらゆる種類のデータ（アイテム間の並べ替え順序が定義されているデータ）に使用できます。設計上、REQ の精度は、正規化されたランクドメインの端（ランク 0.0 またはランク 1.0）にアイテムがどれほど近いかに左右されます。それ以外の場合は入力の分布の影響を受けません。
-
T-Digest Sketch: これも分位スケッチですが、ヒューリスティック アルゴリズムに基づいており、数学的に証明された誤差特性はありません。また、厳密に数値データに限定されます。T-Digest Sketch の精度は入力データの分布の影響を受けることがあります。ただし、これは非常に優れたヒューリスティック スケッチであり、高速でフットプリントが小さく、ほとんどの状況で優れた結果が得られます。
頻度スケッチ
-
Frequent Items Sketch: このスケッチはヘビーヒッター スケッチとも呼ばれます。このスケッチはアイテムのストリームが与えられた場合、スケッチのサイズによってユーザーが構成するノイズしきい値よりも頻繁に発生するアイテムを 1 回の処理で識別します。これはリアルタイムの状況で特に役立ちます。たとえば、過去 1 時間、1 日、1 分間に、ウェブサイトで最も頻繁にクエリされているアイテムは何でしょうか。出力は実質的に、アクセス頻度の高いアイテムの順序付きリストとなります。このリストは動的に変化するため、たとえば 1 時間ごとにスケッチにクエリを行い、1 日を通じたクエリの動きを把握できます。たとえば静的な状況では、メモリ使用量を少なく抑えつつ、1 回の処理でデータベース内の最大のファイルを検出するために使用できます。
ご利用方法
BigQuery で DataSketches を活用するには、bqutil.datasketches データセット（米国のマルチリージョン ロケーションの場合）または bqutil.datasketches_<bq_region> データセット（他のリージョンとロケーションの場合）内の新しい関数を使用します。使用可能な関数とその使用方法の詳細については、DataSketches README をご覧ください。また、GitHub リポジトリには、KLL Sketch、Theta Sketch、FI Sketch のデモ ノートブックもあります。
例: KLL 分位スケッチを使用して、最小値、最大値、中央値、75 パーセンタイル、95 パーセンタイル、合計数の推定値を得る
100 個の異なるパーティションまたはグループに、100 万件の比較可能なレコードがあるとします3。メモリにまとめたり、並べ替えたりすることなく、パーセンタイルやランクごとにレコードがどのように分布しているかを把握することを考えます。
このコードから次の結果が得られます。
例: ユーザー エンゲージメント指標の推定
DataSketches Tuple Sketch は、一意の識別子に自然に関連付けられた特性を分析するための優れたツールです。
たとえば、ユーザー ID と、ユーザーがさまざまな要素をクリックした回数を記録する大規模なウェブ アプリケーションがあるとします。この大規模なデータセットを効率的に分析して、ユニーク ユーザーあたりのクリック数の大まかな指標を取得したいと考えています。Tuple Sketch はユニーク ユーザー数を計算します。これにより、一意の識別子に自然に関連付けられた他の特性も把握できます。
結果は次のようになります。
さらに迅速に、精度の高い推定値を得る
まとめると、近似分析の新たな次元を拓く BigQuery の DataSketches は、大規模なデータセットから迅速かつ効率的に価値のある分析情報を得るために役立ちます。ウェブサイト トラフィックのトラッキング、ユーザー行動の分析、その他の大規模なデータ分析のいずれの場合でも、DataSketches は精度の高い推定を迅速に行うツールとして頼りになります。
BigQuery で DataSketches の使用を開始するには、DataSketches-BigQuery リポジトリの README を参照し、ご利用の環境で DataSketches-BigQuery ライブラリのビルド、インストール、テストを行ってください。各スケッチ フォルダに、そのスケッチで使用できる具体的な関数の仕様を詳しく説明した README が用意されています。
BigQuery 環境をご利用の場合、DataSketches-BigQuery ライブラリはすでに、すべてのリージョンの一般公開 BigQuery データセットで使用できるようになっています。
1. たとえば、個別のカウント、分位数、上位 N、K 平均法、密度推定、グラフ分析などです。1 つの並列パーティションの結果を別のパーティションの結果に単純に「加算」することはできないため、非加算という用語を使用しています（別名「非線形演算」）。
2. 大規模 - 通常、ランダムアクセス メモリに簡単に保持できる規模よりはるかに大きくなります。
3. 任意の 2 つのアイテムを比較して順序を決定できます。つまり、A < B であれば、A は B よりも前にきます。
-Google、クラウド データ エンジニア、Nikunj Bhartia
-Yahoo Inc.、ソフトウェア開発エンジニアリング担当ディレクター、Matthew Sajban 氏
