異なり数を数えるアルゴリズムとパフォーマンス比較
Posted on
プレイドが提供するKARTEでは、オンライン上のエンドユーザの行動データを活用するためにさまざまな分析機能を提供しています。
その中で非常によくある集計がユニークユーザのカウントです。SQLで言うところのCOUNT(DISTINCT user_id)です。KARTEはMAU約8億の膨大な量のユーザを扱っていて、ユニークユーザ数を効率的に集計することは重要なテーマです。
最適化のためにこのアルゴリズムについて深掘りする機会があったので、調べたことを説明していきます。
HashTable
最も一般的なのは、HashTable にキーを追加してカウントしていく方法でしょう。
擬似コードは以下です(Linear Probing)
initialize table
count = 0
insert(key):
h = hash(key)
bucket = h mod capacity;
while table[bucket] is occupied:
if table[bucket] == key:
break
bucket = (bucket + 1) mod capacity
table[bucket] = key
count = count + 1
if load_factor() > threshold:
resize()
挿入の計算量はO(1)ですが、擬似コードからもわかる通り実際には以下のようなオーバヘッドが乗ります。
- ハッシュ計算
- キーの一致判定
- リサイズ(テーブルが埋まってきたら、大きくして作り直す)
全体的にキーが長いほど、またテーブルが埋まっていくほど遅くなります。固定長で短いキーと比べて、可変長で長いキーの方が一致判定は遅くなりがちです。
使う側でできる最適化の余地としては以下のようなものがあります。
- リサイズの発生を抑えるために初期サイズを賢く設定する
- データの特性に合わせて適切なアルゴリズムを選択する
- 主に別々のキーでバケットが衝突した時に代わりのバケットを選ぶ方法について、Robin hoodやQuadratic probingなどさまざまな手法があります。
- Optimizing Open Addressing
Sketch
結果が近似値で良ければ Sketch が使えます。
HyperLogLog が有名ですが、すでに多くの記事で紹介されてるので代わりに KMV（K-Minimum Values）Sketchを紹介します。HyperLogLogも面白いので知らない方はぜひ調べてみてください。
KMV ではハッシュ関数をキーに適用して、得られた値のうち小さい順に k 個だけを保持します。
ユニークなキーが多ければ多いほど小さい数字(と大きい数字)もたくさん現れるわけですから、保持するk個の値はより小さい値で埋まっていくことになります。
言い換えると、k に含まれる値が小さいほどユニーク数が多そうだと言えます。
KMV ではこの k 個の中の最大の値 R を使って、ユニーク数を推定します。
推定値 = k / R
たとえば、 ハッシュ関数の出力が[0, 1)、 k=3 、R=0.5であれば、6個のユニークなキーがあると推定されます。
挿入の計算量はO(log k)で他の手法に劣りますが、メモリはかなり小さく保てます。
分散システムで顕著ですが、集計処理ではノード間での中間集計結果の受け渡しにコストがかかりがちです。そのコストが減らせるのも大きいメリットでしょう。
HyperLogLogより良いところとして、KMVはintersectionができます。実際の要素を保持していて、複数のSketchの共通要素を割り出せるためです。
HyperLogLogでもunionはできるため包除原理で共通要素数の推定ができますが(|A ∩ B| = |A| + |B| - |A ∪ B|)、以下のように、対象のSketchが増えるほど非効率になっていきます。
∣A∩B∩C∣=∣A∪B∪C∣−(∣A∣+∣B∣+∣C∣)+(∣A∩B∣+∣A∩C∣+∣B∩C∣)
https://agkn.wordpress.com/2012/07/09/sketch-of-the-day-k-minimum-values/
Bitmap
入力が小さな整数であれば、Bitmap が使えます。キーに対応する位置のビットを立てていきます。たとえば入力のキーが42であればビット列の42番目を1にします。
挿入処理が軽いことと、最大値が小さければ小さい容量で表現できるのがメリットです。
以下は挿入処理の擬似コードです。
bitmap = int64[(N + 63) / 64]
insert(key):
# word(int64)の位置の計算。key >> 6 は key / 64 の意味
word_index = key >> 6
# word内でのbit位置の計算。key & 63 は key % 64 の意味
bit_offset = key & 63
bitmap[word_index] |= (1 << bit_offset)
1キーに1byteを割り当てるシンプルなByteArrayにすれば、メモリを使う代わりにワードとビットの位置の計算も省略できそうです。CPUキャッシュミスが増える分遅くなることもあるので、データの特性によって検討するといいでしょう。
全てのキーを挿入したあと、立ってるビットを数えるにはCPU命令のpopcntを使うのが最も速いです。
古い言語や環境で動いていてpopcntが使えない場合はビットカウントアルゴリズムの出番です。もはや出番は少なさそうですが、面白いので紹介します。
ビットカウントアルゴリズムでは、ビット演算を駆使してビット列を2bit->4bit->8bitずつと小分けにして加算していきます。
以下分かりやすさのため8bitの入力を例にしますが、実際には64bitで処理することがほとんどです。
bit_count(bits):
bits = (bits & 0b01010101) + (bits >> 1 & 0b01010101);
bits = (bits & 0b00110011) + (bits >> 2 & 0b00110011);
bits = (bits & 0b00001111) + (bits >> 4 & 0b00001111);
return bits
基本的な演算をいくつか組み合わせるだけで何重にも並列で計算できてしまうのがすごいところです。
また、まとめてカウントするのではなく挿入時にビットのチェックをして都度カウントを増やす方法も取れます。空間に対して入力のキー数が少ないとわかっている場合は、その方が効率が良さそうです。ただしまとめてカウントする方も、分岐がない分CPU内での並列化も効いて速いので、多くの場合はそちらを採用していいと思います。(都度カウントしたいくらい入力が少ないとわかってるなら、そもそもBitmapよりHashTableの方が適してる気もします。最初のメモリ確保が小さく済ませられるため)
ベンチマーク
以下の3パターンでベンチマークを取りました。(kmvは良い実装が見つからず、AIもうまく書いてくれなかったので断念)
- HashTable(key=32byte, klibのkhash)
- ハッシュ関数はdjb2に類似した反復ハッシュ。Open AddressingでQuadratic Probing。初期サイズはデフォルトの16
- HashTable(key=4byte, kilibのkhash)
- ハッシュ関数はThomas Wangハッシュ。他は同上
- Bitmap(key=4byte)
パターン1だけ入力のキー長が違います。意図としては、HashTableによるナイーブなユニークユーザカウント(UUIDを想定して32bytesのstring)と、最適化を意図してキーをint32にした手法を比較することです。
入力のデータセットは下記で、全てのキーを追加してユニークカウントを取るまでの時間を測りました。
- トータルのキー数: 10,000,000
- ユニークなキー数: 100,000
- int32の場合の最大のキー: 10,000,000
それぞれ5回実行し、かかった時間の平均をとります。
コード: uniqueue_count_algorithm_benchmark
ベンチマークの結果
入力が32bytes stringのHashTableとint32(4bytes)のHashTableで、30倍の差が出ました。
stringの方をperfで見ると、strcmpが特に重いです。キーの一致判定をしてる部分ですね。
今回はCPU観点だけでの比較ですが、データベース上での扱いを考えると、安くて遅いストレージとの通信を減らして如何にキャッシュに載せるかも肝になります。その観点でもデータを小さくすると圧倒的に速いです。
また、同じint32でもHashTableよりもBitmapの方が6倍速い結果でした。
終わりに
行動分析に関して言えば、匿名ユーザも含めたデータ活用であればIDを4bytesまで短くすることは簡単ではないです。実際にはユニークユーザのカウントでここまで最適化した手法を使えることは多くないでしょう。
ただ本来は日本の全人口(1.2億)であってもわずか15mbのBitmapで表現できる量であり、空間分割や並列化を駆使しながら前処理をすればIDの短縮やBitmapカウントの適用も現実的なはずです。
この記事の内容はほんの一つに過ぎませんが、人の行動分析に対して、こういったアイデアを適用しながら新しいエンジンを開発中です。採用強化中です。応募待ってます！！