この記事は株式会社TimeTree Advent Calendar 2023の18日目の記事です。
はじめに
こんにちは！TimeTreeでバックエンドエンジニアとして働いているScholzです。
みなさんはHyperLogLogをご存知でしょうか？かわいい名前をしていますよね。
HyperLogLog(以下、HLL)はDistinctなものの個数を近似的に数えることができるアルゴリズムです。
つまり、重複した要素をもつ集まりに含まれる、異なる要素の個数を近似計算してくれます。
この記事では、HLLのアルゴリズムがどんなものなのかを例え話でお伝えします。
例え話ではHLLの仕組みを数式を使わずに説明しようとしています。
記事の後半では、HLLをどのように活用できるのかを簡単に紹介します。
これを読んで、「HLLってすごい！」と実感できた方が1人でもいらっしゃればとても嬉しいです。
HLLを例える
HLLのアルゴリズムがどんなものかを理解してもらうために2つの例え話を用意しました。
1つ目は、HLLが最終的にやっていることのイメージを持ってもらうことにフォーカスしたものになります。
例え話1(スマホゲームのガチャ)
お金を支払うことでガチャを引くことができるスマホゲームをやったことはありますか？[1]
以下の前提を満たすスマホゲームを考えてみましょう。
- ユーザーはガチャを引くことでキャラクターを入手できる。
- キャラクターにはたくさんの種類がある。
- 同一のキャラクターにも複数のレアリティがある。
- ガチャ一覧ページには、これまでそのユーザーが引いたキャラクターの一覧が表示される。
- 同一キャラクターを複数引いたことがある場合、最もレアリティの高いものが表示される。
このゲームのユーザーであるAさんとBさんにガチャ一覧を見せてもらいます。
すると、Aさんの画面はレアなキャラクターで埋め尽くされており、Bさんの画面はレアなキャラクターが少なく、空欄(まだ一度も引いていないキャラクターが入る欄)も目立っていました。
あなたはAさんとBさんのうち、どちらのほうが多くガチャを引いたと推測しますか？
ガチャ一覧画面を見て、ユーザーが何回ガチャを引いたかを推定するのが、HLLが最終的にやっていること、と例えることができます。
例え話2(テーマパークの来場者数)
2つ目の例は実際にHLLがよく使われるシーンに即したものになっています。
状況設定が複雑ですがお付き合いください。
時樹パーク
時樹パークは毎日たくさんの人が遊びに来る、とても広い無料のテーマパークです。
入口と出口は分離されており、入り口は1つしかありません。出口はたくさんあります。
とても楽しいテーマパークなので、１日に複数回遊びに来る人もたくさんいます。
不思議なカメラ
このカメラで人を撮影すると、筐体からは写真ではなくスクラッチくじが出てきます。
このスクラッチくじは1等から10等まであり、ハズレはありません。
また、全てのくじの裏面には1から8までの数字がランダムに印刷されています。
さらに、このカメラで同一人物を撮影した場合、くじの結果も裏の数字も以前と全く同じ内容のスクラッチくじが出てきます。
HLLくん
HLLくんは時樹パークの管理人です。彼の仕事は8人の同僚と協力して、時樹パークに1日に遊びに来る人の数を推計することです。この仕事の難しさは、１日に複数回遊びに来る人をその分だけカウントしてはいけないことにあります。
不思議なカメラはHLLくんの所有物です。
HLLくんと同僚たちのある日の仕事
HLLくんと同僚たちは以下の手順で1日に遊びに来た人の人数を集計します。
- HLLくんは以下のようなフォーマットの集計カードを毎日新たに用意します。
ある日の集計カード
| 同僚1 | 同僚2 | 同僚3 | 同僚4 | 同僚5 | 同僚6 | 同僚7 | 同僚8 |
|---|---|---|---|---|---|---|---|
| - | - | - | - | - | - | - | - |
- HLLくんは不思議なカメラを使って入口から入場者をもれなく撮影していきます。
- HLLくんは印刷されるくじの裏の数字に応じて、そのくじを同僚に渡します。
- 同僚はくじを削って何等が当たったか確認したあと、くじを捨てます。
- 同僚は確認したくじが、集計カードの自分の欄に記入されている結果よりも良いものだったら、自分の欄をその結果に書き換えます。初めてくじを引いた場合はその結果を書き込みます。
- 1日が終わるとHLLくんは集計カードを眺めて、何人くらいがパークを訪れたのかを独自の計算で推定します。
例えば以下のような2つの集計カードがあったとしましょう。
12月18日の集計カード
| 同僚1 | 同僚2 | 同僚3 | 同僚4 | 同僚5 | 同僚6 | 同僚7 | 同僚8 |
|---|---|---|---|---|---|---|---|
| 2等 | 4等 | 3等 | 5等 | 2等 | 1等 | 3等 | 4等 |
12月19日の集計カード
| 同僚1 | 同僚2 | 同僚3 | 同僚4 | 同僚5 | 同僚6 | 同僚7 | 同僚8 |
|---|---|---|---|---|---|---|---|
| 8等 | 5等 | 7等 | 4等 | 6等 | 5等 | 7等 | 8等 |
このとき、HLLくんは12月18日のほうが多い来場者数だったと推測するでしょう。
当たりにくいくじを当てている人が多いため、より多くのくじを引いたはずだと考えるのです。
これでDistinctな人数を推計できる理由は不思議なカメラの特性にあります。
不思議なカメラは、同一人物に対して同じ結果しか出さないことを思い出しましょう。
入場者がたくさんいれば、ある同僚はいつか1等を引くかもしれません。
その1等のくじを出すような入場者が同じ日にもう一度入場したとしても、集計カードに変更は生じ得ません。
集計カードを更新させるには、少なくともそれまでに出てきていない組み合わせのスクラッチくじを出す必要があるのです。
集計カードの威力
集計カードは、「その日の来場者数を推計するための材料」以上の情報を持っています。
以下の12月24日、25日分の集計カードについて考えます。
12月24日の集計カード
| 同僚1 | 同僚2 | 同僚3 | 同僚4 | 同僚5 | 同僚6 | 同僚7 | 同僚8 |
|---|---|---|---|---|---|---|---|
| 2等 | 4等 | 3等 | 5等 | 2等 | 1等 | 3等 | 4等 |
12月25日の集計カード
| 同僚1 | 同僚2 | 同僚3 | 同僚4 | 同僚5 | 同僚6 | 同僚7 | 同僚8 |
|---|---|---|---|---|---|---|---|
| 3等 | 4等 | 1等 | 3等 | 2等 | 2等 | 3等 | 5等 |
これらを使って、次のような新しい集計カードを作ることを考えます。
このカードは上の2枚のカードのうち、同僚ごとに、よりレアな結果を書き込むことで作成します。
| 同僚1 | 同僚2 | 同僚3 | 同僚4 | 同僚5 | 同僚6 | 同僚7 | 同僚8 |
|---|---|---|---|---|---|---|---|
| 2等 | 4等 | 1等 | 3等 | 2等 | 1等 | 3等 | 4等 |
実はこのカードは24日と25日の2日間の来場者数を推計できるカードです。
このことは、前述のHLLくん達の仕事で、25日の朝に集計カードを新たに用意せず、24日のものを引き続き利用することで完成するカードのことを考えるとわかります。
つまり複数枚の集計カードは、結果の良いとこ取りをすることで、その期間にわたる来場者数を計算できるのです。
カメラが不思議ではなかった場合
HLLくんのカメラが、撮ると写真が出てくるという普通のカメラだった場合、HLLくんの仕事がどう変わるか考えてみましょう。
HLLくんは入り口で入場者をもれなく普通のカメラで撮影していきます。
その後、出てきた写真と、その日それまでの時間に撮影した全ての写真を見比べ、同一人物をすでに撮影していないかをチェックします。同一人物がいなければ、新規入場者としてカウントします。
この方法だと写真の枚数はどんどん増えていき、人が通りかかるたびにそれら全てを使ってチェックしなければなりません。
それか、チェックは後回しにしておいて、閉園後に重複している写真を排除していくという方法もあるかもしれません。いずれにしても気が遠くなるような仕事です。
不思議なカメラを使った方法では、正確な値を求めることはできません。
しかし、普通のカメラを使った場合に比べてHLLくんにかかる負担はずっと少ないでしょう。
例え話は以上になります。
状況設定が複雑なので、納得しながらここまで辿り着けた方はとてもすごいです！お疲れ様でした！
例え話と実際との対応関係
時樹公園の例え話と、実際のHLLの対応関係を軽く説明しておきます。
説明に利用している数値は実装されているソフトウェアの仕様や設定によって異なる場合があります。
まず、例で使った数字は実際にはもっと大きい数字になります。
HLLくんの同僚の人数は16384(=2の14乗)人であり、くじは1等から51等まであります。
スクラッチくじの裏の数字も1から51までの数字がランダムに印刷されます。
不思議なカメラは、ハッシュ関数です。受け取った値を64bitで表される整数に変換します。したがって、スクラッチくじは64bitの整数に対応しています。
64bitの整数のうち、先頭14bitが裏面、残りの50bitが表面に対応しています。
くじの結果は50bitの整数(2進数表記)を左から見て0が続く個数に対応しています。
0が続くほど良い結果です。
例えば00111110101101010010010111110100001001010111100111は49等であり、00000000000000000000000000000000000000000000000101は4等です。
HLLくんの同僚はレジスタと呼ばれています。レジスタは集計カードの各欄と同一視されます。
つまり、集計カードの各同僚に対応する記入欄のこともレジスタと呼びます。
集計カードは、HyperLogLogのスケッチと呼ばれるものに相当します。
スケッチからDistinctな個数を推計するのには、各レジスタに記入された値の調和平均に補正を加えます。
例え話の中でも書いたように、この方法では今まで受け取った値を覚えておく必要はなく、スケッチさえあれば個数の計算を行うことができます。したがってメモリもこれらの分だけ確保できていれば良いです。
各レジスタに入る値は最大値が50なのでたったの6bitで済みます。
スケッチのマージは複数の集計カードの良いとこどりに相当します。
レジスタの個数が一定なので、これは定数時間で行えます。これはすごいことです。
一般に二つの集合
しかし、
HLLの活用例
HLLにはどんな活用方法がありそうでしょうか？
時樹公園の例え話を読んだ方はDAUやMAUなどの特定期間におけるアクティブユーザーの数を計算するのに使えると思ったのではないでしょうか？
今回はBigQueryのHyperLogLog++関数を使ってこれらを計算する例を見ていきましょう。
以下のスキーマのテーブルを使ってDAUやWAUを計算することを考えます。
ユーザーがサービスにアクセスするとそのユーザーのidとそのアクセス日時をもつレコードが作成される想定です。
user_sessionsテーブル
| column_name | type |
|---|---|
| user_id | INT64 |
| session_time | DATETIME |
DAUの計算
以下のクエリで特定の期間のDAUを近似計算できます。
WITH dau_hll AS (
SELECT
Date(session_date) AS date,
HLL_COUNT.INIT(user_id, 24) AS hll
FROM
user_sessions
WHERE
Date(session_time) BETWEEN from_date AND to_date
GROUP BY
date
)
SELECT
date,
HLL_COUNT.EXTRACT(hll) as approx_dau
FROM
dau_hll
HLL_COUNT.INIT(user_id, 24) の 24は近似の精度オプションです。今回は最高精度で計算しています。この数字の大小はHLLくんの同僚の人数、すなわちレジスタの個数の大小に相当します。
内部ロジックを理解しておくと、精度を調整することが何を調整することなのかが分かって気持ちが良いですね！
MAUの計算
MAUを計算する場合は以下のようなクエリになるでしょう。
WITH hll_dau AS (
SELECT
DATE(session_time) AS date,
HLL_COUNT.INIT(user_id, 24) AS hll
FROM
user_sessions
WHERE
DATE(session_time) BETWEEN DATE_SUB(CURRENT_DATE, INTERVAL 3 MONTH) AND DATE_SUB(CURRENT_DATE, INTERVAL 1 DAY)
GROUP BY
date
),
date_range AS(
SELECT
date,
DATE_SUB(date, INTERVAL 29 DAY) AS start_date
FROM hll_dau
),
merged_hll AS(
SELECT
date_range.date,
HLL_COUNT.MERGE_PARTIAL(hll_dau.hll) AS user_count
FROM date_range
JOIN hll_dau
ON hll_dau.date BETWEEN date_range.start_date AND date_range.date
GROUP BY date_range.date
)
SELECT
date,
HLL_COUNT.EXTRACT(user_count) AS approx_mau
FROM
merged_hll
ORDER BY
date DESC;
MAUの計算では HLL_COUNT.MERGE_PARTIAL(hll_dau.hll) でDAUのスケッチをマージしています。
定義通りにMAUを計算しようとすると、今回のクエリのように複数日まとめて計算したい時に、既に見た日のアクティブユーザーを再度カウントし直す必要がありますが、HLLを利用することでそれを回避することができ、時間とメモリを大幅に節約できます。
今回の場合、既存のMAUカウントよりも30倍程度高速に計算できるようでした。
データアナリストのCharlieが近似精度を報告してくれました。
近似が高精度であることがグラフからも分かります。
レジスタの個数を調整することで、精度を犠牲にする代わりに計算速度を上げることもできるので、これからちょうど良い設定を探していこうと思っております。
おわりに
今日はHyperLogLogのアルゴリズムの紹介をしました。
HLLを勉強してから、まずは一つという気持ちでDAU,MAUの計算に適用してみたのですが、想像よりもずっと高精度で驚きました。
今後も、これ以外にも使える場所がないか、既存のクエリ内の COUNT (DISTINCT ...)に目を光らせていこうと思います。
TimeTreeの採用情報
TimeTreeのミッションに向かって一緒に挑戦してくれる仲間を探しています。TimeTreeで働くことに興味がある方はぜひ、Company Deck（会社紹介資料）や採用ページをご覧ください！
-
私はありません！ガチャの認識が大きく違っていたら申し訳ないです！ ↩︎
TimeTreeのエンジニアによる記事です。採用情報: timetreeapp.com/intl/ja/corporate/careers / TimeTree Company Deck: bit.ly/3IyEEWt
Discussion