RedisのBitCountとHyperLogLogを使用した超高速Unique User数集計
1. 初めに
次世代システム研究室のT.Mです。今回次世代システム研究室でクォータ毎に実施している研究発表でRedisのUnique User集計の内容を発表したので、その内容を紹介させていただきます。
Redisは、一般的にオンメモリのKVSとして認知されていますが、普通のKVSと違い、Bitカウントの処理であったり、Unique Userの集計の機能を持っています。
今回は、それらの機能についてアルゴリズムを中心に調査して纏めてみました。
2. LinearCounting
Linear Countingは、IDをハッシュ化して数値化し、それをIndexとしてメモリ上のBitMapにフラグを立てます。そして、単純にBitMap上に立っているフラグの数を数えれば、UU数が取得できるというものです。
ただ、ハッシュ値をそのままIndexとして扱うと、32bitのHash関数だったとしても、255MB程度のBitMapが必要になります。
そのため、このアルゴリズムでは衝突を覚悟でMapサイズを抑えて計測する方法も取ることができます。
論文でも、BitMap内にk個のBitが立っている場合、n回の試行があったと推定する計算式が導出されています。
この計算式を使用すると、1億レベルのユニークユーザ計測でも同数のBitMap数（12MB程度）で処理しで計算でき、その計算速度も10ms程度で処理できます。
ある特定のユーザ群Aと、別のユーザ群Bの重複率を調べる際には、BitMap同士をORで結合することで実現します。
グループAとグループBのAND領域を計算するには、A + B – AUB で実現します。
3. HyperLogLog
HyperLogLogは、省メモリでありながら高精度でUU数をカウントできるアルゴリズムです。こちらは既にRedisに組み込まれているため、簡単なコマンドで扱うことができます。
ただし、HyperLogLogはORでしかグループ間の結合ができないため、基本的にはAND領域のUUを求めたい場合は A + B – AUB の処理をすることになります。
HyperLogLogでは、Base-2 Ranks というMinHashの派生形のアルゴリズムを使用します。
Hashの前方の0の連続数がp個続く確率は1/(2のp乗)になるため、それが発生する際に試行した回数は2のp乗となると推定するものです。
このアルゴリズムでは、各IDのハッシュ化した値群の中で、最も長い0の連続数を記録します。（長いほうが珍しいため。）
この方法であれば、0の数は最大32なので、必要なbit数は5bitになります。
精度を上げるため、k個のhash関数を利用しても、必要なbit数は 5 x k (bit) で済みます。
HyperLogLogは前述の通り、指数からの統計的な推定となるため、サンプル数が多くないと精度が悪いという特徴があります。
この点については2013年にGoogle社が改善方法の論文を出しており、その内容を紹介をします。
これは、UU数が少ないうちはLinear Countingの方が精度がよいため、一定の閾値以下の場合はLinear Countingで計測するというものです。
閾値を使わなくても少ないうちの精度を高めるという論文も出ています。
これは現在Redis未実装ですが、今後も注視しておきたい理論ですね。
4. 負荷分散
Redisはデータの投入に秒間3～5万のリクエストを捌けるため、一般的なアプリケーションでは十分な処理性能があると思います。（秒間3～5万のリクエストがピーク時に来る場合、一般的には、おおよそ月間500～600億程度のリクエストが来ることになります。）
ただ、広告配信システムなどでは、月間1000億を超えるリクエストが来ることもあり、障害時のリカバリなどを考えるとより短時間で処理することが求められます。
Linear CountingはUU数が少ないうちは精度がよく、逆にHyperLogLogでは精度が悪くなります。
分散するとLinear Countingはメモリ使用量が単純に(1/台数)となるため、分散させる場合はLinear Countingの方が適しているともいえます。
ある程度分散数を増やせば、そのまま配信に使える精度のBitMapが作成できるのではないかとも思っています。
5. 最後に
これらの内容はSlideShareでより詳しく記載しています。ぜひこちらもご覧ください。
参考資料
- Linear Counting
- HyperLogLog
