BrainPad株式会社ブレインパッドのデータ活用に関する取り組みや製品・サービス開発の裏側、社員の日常などをご紹介します。マーケティングプラットフォーム本部で広告系製品の開発を担当している田頭です。現在、ブレインパッドでは、DMP(※1)に蓄積されたさまざまなデータをもとに、ユーザー数を確認しながら直感的にセグメントを作成できる「DeltaCube(デルタキューブ)」という製品を提供しています。ユーザーのセグメントを作成する際、担当者がストレスなくインタラクティブにセグメントの条件を設定しユーザー数を確認するためには、蓄積された大規模なデータの中から「高速に」ユニークユーザーの数を数えなければなりません。このため、DeltaCubeでは、集計処理にPrestoと呼ばれる分散処理ミドルウェアを利用しています。今回、このPrestoを利用したユニークユーザー集計の更なる高速化について検証作業を行いましたので、皆さんにご紹介したいと思います。「理論編」として、以下の内容を簡単に解説したいと思います。ついてさらに詳しく知りたい方は、ページ下部のスライドをあわせてご参照ください。DeltaCubeとは(ユニークユーザー数を高速に推定したい背景)現在、DeltaCubeは、主な機能として以下の2点を有しています。各セグメントや、サイト全体のユーザー像を把握することが可能ストレスなく、インタラクティブにユーザー数を確認しながらセグメントを作成するためには、そのレスポンスの速度が非常に大切になります。全ユーザーのトラッキングログなどの大規模なデータをもとにしているため、このユニークユーザー数の確認を厳密に行っていては、非常に遅いという問題があります。そこで今回、セグメントのユニークユーザー数というのは「1人単位まで厳密にわかる必要はなく、全体に対するそのボリューム感がわかれば良い(つまり、推定値で良い)」という点に着目しました。それでは、「ユニークユーザー数を高速に推定する」という今回のテーマについて、解説していきます。PrestoとはDeltaCubeでは、Prestoという分散処理ミドルウェアを利用して集計処理を行っています。PrestoはSQLクエリエンジンですので、当然SQLクエリを投げられます。以下の状況を考えます。t_log_dataテーブルにWebページのトラッキングログを格納しているuid列にユーザーを識別するためのユーザーIDが入っているその他の列に他のデータが入っているこのとき、Prestoでユニークユーザー数を求めるためには、以下のようなクエリを実行します。(絞り込みたい条件);ただし、ここでは厳密に集計処理を行っているため、実行速度は低速となります。x)」の推定値を返す関数です。使い方は簡単で、前述のユニークユーザー数を求めるためのクエリであれば、以下のように記述することでその推定値を求めることができます。set.(ただし、これは全ての入力に対して誤差の上限を与えるものではない)とも書かれています。そこで、Presto内部のapprox_distinctの実装を追ってみると、HyperLogLogと呼ばれるアルゴリズムが利用されていることがわかりました。以降では、まずHyperLogLogの理論的な面について調べた結果を、次にそのPrestoでの実装について、簡単に解説します。HyperLogLogとはHyperLogLogとは、上図の通り、(重複があってもよい)データのcardinalityを推定するアルゴリズムです。HyperLogLogについて、簡単な例を挙げてその具体的な考え方を解説したいと思います。M2を用意し、その初期値を0としておきます。レジスタとは、推定値計算のためにある値を保持しておくための箱だと思ってください。レジスタごとに推定値は計算され、それらをもとに最終的な推定値を求めます。ユーザーIDをハッシュ化し、対応するレジスタの値を更新していく※ここの手順は、通常はユーザーIDのリストの要素1つ1つに対して繰り返し実行されますが、説明の簡便のため、ハッシュ化やその後の処理を手順ごとでまとめています。ユーザーIDをハッシュ化ユーザーIDのリストを1行ずつ読み込み、そのユーザーIDを2進数(例として32ビット)にハッシュ化すると、以下のようになったとします。ビットで対応するレジスタを決定します。します(0の場合と1の場合の2通りで分けられる)。先頭が0の場合はレジスタM1に、1の場合はレジスタM2に割り当てるとすると、それぞれの割り当て結果は以下のようになります。レジスタM1の値として保持します。