2012年頃、とても大きなログデータを扱う仕事をしていました。そのとき、クライアントから、任意期間でユニークユーザーを数えてレポートできるようにして欲しい、と言われたことがあります。つまり今月のユニークユーザーは何人、今週は、今年は、という固定期間ではなく、Google Analyticsのように、自由な範囲で人数を数えたいというのです。
ログデータの集計をしたことがある人ならわかると思います。たとえば、Webサーバーが吐き出す標準的なログデータを構文解析して、データベースに投入すれば、SQLでWHERE accessDate BETWEEN '2021-01-01' AND '2021-01-15'として検索対象を任意期間に絞り込み、userID単位で行数を数えればユニークユーザー数は算出できます。ところがログデータが1日で数千件以上の規模になると、もうこの方法では時間がかかりすぎて実用的ではなくなるのです。何か工夫が必要です。
Google Analyticsがどう実装しているのか、日本語でも英語でも調べましたが資料がありません。見つかるのは、どうすればそんな魔法のようなことができるのか、という質問ばかりでした。しかしGoogleにできているのだから自分にもできるだろうと思って考えていたら、ピコーンと来ました。この記事は、その日の数十分間の思考過程の再現です。
中間データを作る
大規模なデータを集計するときは、データそのものを扱わずに、集計したい単位で中間データを作ります。たとえば、アクセスログを日次で、ユニークユーザー別に集計したいなら、日次でユニークユーザー別に集計した中間データを作ればいいのです。こうすれば、たとえばAさんが1日に1000回アクセスしていても、ある日のAさんのアクセス数は1000でした、という1件にまとめられます。
今回欲しいのは任意の期間のユニークユーザー数ですから、この日のユニークユーザーは1000人でしたというように、1日のアクセスを1件にまとめてしまえば、たとえ1日100万件、1年間で数億件のログデータがあっても、10日間の集計なら足し算10回、1年の集計でも365回の足し算で済みます。コンピューターにとって、さすがに数億件のログからユニークユーザー数を実用的な時間で計算するのは時間がかかってしまい、リアルタイムでレポートが出せる集計・レポートツールにはなりませんが、365回なら何とかなります。
まず、以下のようなアクセスがあったことにしましょう。
上の表は、A～Jさんの10人が、1月1日～1月10日までの10日間にアクセスした記録です。たとえば、1月1日は、A、B、Fさんの3人がアクセスしています（表中の「✓」はアクセスありの意味）のでユニークユーザー数は3、1月10日は、A～Gさんの7人がアクセスしていますのでUUは7です。各人が1日1回アクセスしていたとすると10人×10日間＝100件のログですが、求めたいのはUU数なので、上の表の最終行のように、10件（表では10列）の中間データにサマライズできています。
ただし、毎日のユニークユーザーを数えても、期間のUUにはなりません。たとえば、1月1日～1月2日にアクセスしたのはA、B、E、Fさんの4人ですから、UUは4が正解でが、1月1日～1月2日のUU数を数えると、3+2＝5人になってしまいます。どうしたら延べ人数でなく、任意の期間でユーザー数を数えられるでしょうか。
集計期間中の新規ユーザーを数える
任意の期間でユニークユーザー数を数えるときの課題は、ログの中に新規ユーザーと再訪ユーザーが混じっていることです。ある期間のユニークユーザー数は、新規ユーザー数≦ユニークユーザー数という関係ですから、まずは任意の期間の新規ユーザーを正確に数えることにしましょう。
あるユーザーのアクセスを特定するには、ユーザーにIDを割り当てればよさそうです。そこで、ユーザーIDという項目がひとつだけあるユーザー表というテーブルを用意します。1日のログを集計するとき、ユーザー表にユーザーIDがあれば再訪ユーザー、なければ新規ユーザーと判断できます。そうすると、以下のように集計できます。
上の表の赤枠部分を左から右に見ていきましょう。赤枠にあるのは、毎日の新規ユーザー数と再訪ユーザー数です。たとえば1月1日は記録初日なのでA、B、Fさんの3人が新規ユーザーです。1月2日は記録2日目なので、2人の訪問者がいますが、新規ユーザーはEさんのみで1人、Aさんは再訪ユーザーです。では、たとえば1月1日～1月5日のUUはどうすれば算出できるでしょうか。正解は7人ですから、新規ユーザー数の3+1+1+1+1＝7人という式でも正解です。しかし、1月6日～1月10日になると、正解は8人ですが、新規ユーザー数の1+1+1+0+0＝3人では正解になりません。ここに再訪ユーザー1+1+0+1+7＝10人を足しても正解になりません。ある期間の再訪ユーザーのアクセスは、2回目以降を取り除かないと任意の期間でユニークユーザー数は数えられないのです。
集計期間中の再訪ユーザーを数える
任意の集計期間中の1度目の再訪だけを数えるには、あるユーザーのアクセスが1回目なのか2回目なのかだけでなく、前回のアクセスから何日目のアクセスなのかを数える必要があります。そこで、ユーザー表を、ユーザーIDだけを記録するのではなく、前回アクセス日を記録できるように拡張しておきます。そうすると、以下のような表が作れます。
上の表を使うと、任期期間のユニークユーザーを集計できます。集計期間の初日である1月1日は、3人の新規ユーザーがいます。再訪ユーザーはいません。1月2日は、1人の新規ユーザーと1人の再訪ユーザーがいますが、このユーザーは前日にも訪れていますので、1日前に来た再訪ユーザー1人は数えなくてよいとわかります。したがって1月1日～1月5日のユニークユーザー数は、期間中の新規ユーザー3+1+1+1+1＝7人、期間中の期間外の再訪ユーザー0+0+0+0+0＝0人を足して7人とわかります。また、1月6日～1月10日のユニークユーザー数の正解は8人ですが、期間中の新規ユーザー1+1+1+0+0＝3人、期間中の期間外の再訪ユーザー2+1+0+0+2＝5人を足して8人と計算できます。
ユニークユーザー数＝集計対象期間中の新規ユーザー数＋集計期間日数以上ぶりに再訪したユーザー数
ここまでの議論を振り返りましょう。まず、大きなログデータを集計するときは、直接集計するより、準備しておいた中間データを集計します。任意の期間のユニークユーザー数を求めるには、集計対象期間中の新規ユーザー数と、集計対象日数ぶりに再訪したユーザー数の合計（集計期間が10日間なら、1日目は前日にアクセスしたユーザーを含めてもよいが、2日目は2日ぶりのユーザー、10日目は10日以上ぶりに訪れた再訪ユーザー数）を求めればよいことがわかりました。
アルゴリズムとしてはこれでよいのですが、このままでは実用上の課題を解決しきれません。任意期間で集計するためには、何日ぶりの再訪ユーザーなのかを集計する上限が決められないのです。仮に集計期間の上限を2年分（730日）にしても、ユニークユーザー数を数えるために、731項目を毎日集計するのはちょっとどうかと思いますし、計算量を少なくするためにサマライズしたいのに、中間データの生成にたくさんの計算量を毎日使うことになりそうです。
ここで、ピコーンと来ました。統計学は大学1年生のときに学んで以来なので、これが何の話だったか忘れましたが、めったに起きないことは、期間を長くするともっとめったに起きない、みたいな確率分布があったような気がしました。Webだろうがアプリだろうが、アクセス数というのは、毎日使っている人は毎日アクセスするし、週末にしか使わない人は7日間隔でしかアクセスしません。さらに、30日ぶりにアクセスした人は前回が60日前だろうが70日前だろうが、「90日間では2回」くらいに割切ったレポートでもいいはずです。だって考えてみてください。この考察の発端は、「Googleにできているのだから自分にもできる」です。Googleというのは、本当に全部調べているはずがないのに、「あなたが探しているキーワードに合致する文書はこれです！」と1秒未満で表示してしまう、とても高速でいい加減な仕組みを提供する会社です。再訪ユーザーを1日単位で記録するのは7日間くらいにして、その先はざっくり集計することにしましょう。
上の表では、8日以降の再訪ユーザー数を8～14日前とひとくくりにして集計しています。たとえばFさんは1月10日に10日ぶりに訪問しています。ここで1月1日～1月10日のユニークユーザー数を検討したアルゴリズムで計算すると、新規ユーザー数は3+1+1+1+1+1+1+1+0+0＝10人、集計日数ぶりの再訪ユーザーは0+0+0+0+0+0+0+1人＝1人となり、UUは11人になります。正解は10人ですから1人多くなりますが、誤差がスゴく大きいわけでもありません。8～14日、15～30日、31～60日、61～90日、91～180日、181～365日の区切りで計算するようにして、いろいろなパターンで正解との誤差を求めたところ、このときのプロジェクトでは1％未満でした。
Google Analyticsのユニークユーザー数のブレ
Google Analyticsには、集計期間を変えるとユニークユーザー数がブレるという有名な謎があります（もう解消されているかもしれませんが）。このブレの正体は、上記で説明した雑な集計期間のせいのハズです。どんな巨大なサイトのログデータでも高速で集計するための工夫のせいで、集計期間の解像度がぼやけると、結果までぼやけてしまうのでしょう。わたし自身は「めったに起きないことは、期間を長くするともっとめったに起きない」が何分布だったか思い出せなかったので実装しませんでしたが、Googleなら何かの確率分布を使って、数学的に解像度を高めているかもしれません。
というわけで、Google Analyticsのようにユニークユーザーを任意の期間で集計する方法を考えたときの話でした。