LCL Engineers' Blog

バス比較なび・格安移動・バスとりっぷを運営する LCLの開発者ブログ

BigQueryでユニーク数を推測するHyperLogLog++について

バックエンドエンジニアの高橋です。

弊社ではデータ分析・可視化のためのデータ基盤としてBigQueryを用いていますが、その中でHyperLogLogアルゴリズムを活用したユニーク数の計測における工夫についてご紹介します。 なお、HyperLogLogアルゴリズム自体については詳細に理解していなくても実用上困ることは少ないのでこの記事では扱いません。詳細についてはネット上の記事を探ったりGoogleが公式に出している論文を当たるといいです。(私も説明できるほど詳細な理解はしてないです)

ユニーク数の計測の面倒臭さ

Webサイトのアクセス解析において重要な指標としてPV(ページビュー数)とUU(ユニークユーザー数)がありますが、PV数は単純に足し合わせでカウントすればいいのに対し、UUについては重複を排除した上でカウントする必要があるので分析上の取り扱いが面倒です。

簡単なお題で考えてみましょう。

例題.「12月1日のユーザー数は10人、12月2日のユーザー数は20人でした。では、12月1日と12月2日の合計ユーザー数は何人でしょうか？」

答えとしては「正確な人数は不明で最小20人、最大30人」です。「え？30人じゃないの？」と思った人はもう一度よく考えてみてください。^^;

これが実務上どんな時に困るかというと、集計の粒度が異なる場合に集計処理の計算コストが膨れ上がるケースです。ここでいう計算コストとは費用的な意味とパフォーマンス的な意味の両方です。

例えば、

  • Aさん「月間のUUを知りたい」
  • Bさん「日毎のUUを知りたい」

といった場合、BigQueryで集計するとしたら

  • Aさん用のSQL
select
  date,
  count(distinct user_id) as uu
from event_logs
group by date
  • Bさん用のSQL
select
  extract(month from date),
  count(distinct user_id) as uu
from event_logs
group by date

このような感じでAさん用とBさん用に異なる集計処理を行う必要が出てきます。他にも「訪問ページ別で集計したい」、「流入区分別に集計したい」などビジネスサイドからの要望はどんどん出てくることでしょう。

この集計元となっているテーブルのサイズが小さければ計算コストを気にする必要はないですが、Webトラフィックなどのデータは基本的に大量のデータなので毎度集計するようだと大変な計算コストがかかってしまいます。

仮に上記のような集計SQLを1回実行するたびに100GBが処理されるとして、必要とされる粒度によって集計を10通り行うとしたら1TBを処理することになります。

パフォーマンス的な意味でも処理されるデータ量は低く抑えたいですし、BigQueryをオンデマンド料金プランで利用している場合は処理されるデータ量に課金額が比例するので気を使うところでしょう。

この計算コストを抑えるテクニックとして、事前にある程度集計した中間テーブルのようなもの(事前集計テーブルやPre-Aggregationと呼ばれたりする)を作るケースがありますが、更にHyperLogLogアルゴリズムを組み合わせることでよりスマートになります。

HyperLogLog++の使い方

BigQueryではHyperLogLog++関数という名前のユニーク数を低コストでカウントするための関数を用意しています。

使い方としてはユニークにカウントしたい値の集合からsketchと呼ばれるハッシュ値を生成し、後続の集計処理でそれを用いてユニーク数を推定する(※)という流れになります。

※ HyperLogLogではアルゴリムの特性上正確なユニーク数を保証できません。よって数値が1でもずれるのが嫌な場合は適していませんのでご注意を。

説明してもよくわからないと思うので、お題として以下の3名の要望をそれぞれHyperLogLog++を使って集計してみます。

  • Aさん：「日別のUUを知りたい」
  • Bさん：「日別で流入区分別のUUを知りたい」
  • Cさん：「日別で訪問ページ別のUUを知りたい」

まずはユニークにカウントしたいuser_idを hll_count.init(user_id, 24) としてsketchを作成します。引数の24はスケッチの精度でこの値が高いほどより正確なユニーク数の推定ができるようになります。(ただし計算コストとのトレードオフになります)

CREATE TABLE preaggregated_event_logs as (
  select
    date,
    inflow_segment,
    page_url,
    hll_count.init(user_id, 24) as sketch
  from event_logs
  group by 1, 2, 3 
)

sketchを作成する場合は集計したい粒度でgroup by する必要があります。

また、SQLの出力結果は後続の集計段階で使いまわすので物理テーブルとして保存しておくといいです。一旦 preaggregated_event_logs と命名したテーブルに保存しています。

そして生成したsketchを以下のように hll_count.merge(sketch) とすればUU数の推定ができます。

  • Aさん「日別のUUを知りたい」
  select
    date,
    hll_count.merge(sketch) as uu
  from preaggregated_event_logs
  group by 1
  • Bさん「日別で流入区分別のUUを知りたい」
  select
    date,
    inflow_segment,
    hll_count.merge(sketch, 24) as uu
  from preaggregated_event_logs
  group by 1, 2
  • Cさん 「日別で訪問ページ別のUUを知りたい」
  select
    date,
    page_url,
    hll_count.merge(sketch, 24) as uu
  from preaggregated_event_logs
  group by 1, 2

HyperLogLogでの集計メリット

使い方は上記の通りですがそもそものHyperLogLogを利用するメリットを挙げると以下のような点があります。

  1. 集計処理が速い
  2. 集計で処理されるデータサイズが低く抑えられる

この内、2の処理データサイズが低く抑えられる点については事前集計テーブルを作ったことによる恩恵です。 ケースバイケースですが事前集計テーブルは元の集計前テーブルのサイズよりもかなり圧縮されます。

仮に100GB→10GBに圧縮されたと仮定すると、事前集計テーブルなしで集計を行った場合は100GBのテーブルの集計を3回行うことになるので単純計算で300GBの処理データサイズになりますが、事前集計テーブルを作成した場合は130GBになります。(事前集計テーブルの作成1回と10GBのテーブルの集計を3回)

事前集計テーブルの作成は１回でいいので、集計粒度が多ければ多いほどお得感が増していきますね。

事前集計テーブルの分割

事前集計テーブルは１回の作成でいいと今書いたばかりですが、集計粒度が細かくなりすぎると今度は事前集計テーブル自体が肥大化しすぎて困る場合があります。

例えば、集計粒度として、

  • 「日付」... 過去3年分 = 1095日
  • 「訪問ページ」... 1000ページ
  • 「流入区分」 ... 10種類
  • 「リファラードメイン」... 1000ドメイン
  • 「デバイス種類」 ... 5種類
  • 「OS」... 5種類
  • 「ユーザー年齢層」... 10区分

これらの粒度で事前集計テーブルを作ろうとすると、単純計算で１兆レコード数を超える事前集計テーブルができてしまいます。 これでは結局処理されるデータサイズが肥大化してしまい元も子もないので、一案としては事前集計テーブルを目的に合わせて分割する方法があります。

例えば、「日付」「訪問ページ」の粒度で集計したテーブルA、「日付」「流入区分」「リファラードメイン」の粒度で集計したテーブルB、「日付」「デバイス種類」「OS」「ユーザー年齢層」の粒度で集計したテーブルC、といった具合です。分割の基準は厳密にはないですが頻繁にクロスして集計する粒度かどうかで考えています。

また、事前集計テーブルを分割した場合でもテーブルを跨いで集計することが可能です。つまりは異なる集合の和集合を求めたいので高校数学でお馴染みの以下のような計算をすれば良いです。

\displaystyle |A \cap B| = |A| + |B| - A \cup B

例として、日付 × 訪問ページで事前集計したテーブルを preaggregated_visitsとし、日付 × 流入区分 × リファラードメイン で事前集計したテーブルをpreaggregated_inflows として、日付 × 訪問ページ × リファラードメインでUUの推測値を出してみます。

with

page_sketch as (
  select
    date,
    page_url,
    hll_count.merge_partial(sketch) as sketch
  from preaggregated_visits
  group by 1, 2
),

referrer_sketch as (
  select
    date,
    referrer,
    hll_count.merge_partial(sketch) as sketch
  from preaggregated_inflows
  group by 1, 2
),

uu_sketches as (
  select
    date,
    page_url,
    referrer,
    [by_page.sketch, by_referrer.sketch] as sketch_array
  from page_sketch
  left join referrer_sketch
  using (date)
)

select
  date,
  page_url,
  referrer,
  hll_count.merge(sketch_array[OFFSET(0)]) + hll_count.merge(sketch_array[OFFSET(1)] - hll_count.merge(sketch)) as uu
from uu_sketches, unnest(sketch_array) as sketch
group by 1,2,3

ポイントとしては、preaggregated_visits と preaggregated_inflowsをそのままjoinしてしまうとレコード数が爆発的になり処理時間が長くなってしまう可能性があるので、CTEで必要な粒度に沿って事前に集計します。CTEの段階ではUU数を出したいわけではないので、hll_count.merge_partial によって既存のsketchを更に部分的に集計した結果のsketchを出しています。

また、それぞれのテーブルのsketchは１つのカラムにする必要があるためjoinしてarrayにまとめ、最後のselectクエリのところで hll_count.merge(sketch_array[OFFSET(0)]) + hll_count.merge(sketch_array[OFFSET(1)] - hll_count.merge(sketch)) として上記公式の計算をすれば最終的に求めたいUU数となります。

最後に

今回はHyperLogLogを使ったユニーク数推定の実用方法についてご紹介しました。

冒頭でも述べたように、処理データサイズを低く抑えられるのでBigQueryをオンデマンド料金プランで利用している方にとっては重宝するテクニックかと思います。

ちなみにGoogleAnalyticsやAdobeAnalyticsなどのWebアクセス解析サービスでは事前定義済みの指標としてユニークユーザー数の可視化ができるので、アクセス解析だけが目的であればそもそもBigQueryを使う場面は少ないかと思います。ただ今回紹介したテクニックはWebアクセス解析だけに留まらず色々な場面で使えるものなので知っておいて損はないかと思います。

採用情報

LCLでは開発メンバーを募集しています。

カジュアル面談も行っていますので、少しでも興味をお持ちでしたらご連絡下さい。

www.lclco.com