去年の内に公開することが出来ず、ずっと下書き状態だったエントリーをちょっとずつ消化していきたいと思います。ネタとして古いものも含まれていたりすると思いますがしばらくご辛抱ください。。
Redis 2.8.9から追加された HyperLogLog をちょっと触ってみました。
環境
* CentOS 7.0 (x86_64) / Intel Xeon E312xx (Sandy Bridge) 2.4GHz 仮想3コア / 2GB RAM
* Redis 2.8.17
* redis-py (Python 2.7.5)
HyperLogLogとは
HyperLogLog (以下HLL)というアルゴリズムはデータマイニング(トラフィックデータの分析等)とか自然言語処理をやってる人ならともかく、Webアプリケーション開発者にはあまり馴染みがないかもしれません。
データのcardinality(異なり数、種類の数)を高速に推定するアルゴリズムで、高速かつ省メモリで実行できるそうです。乱択データ構造については詳しく知らないのですが、accuracy 99%とは驚きの精度です。
HLLは Algebird (Scalaの抽象代数学ライブラリ)でも実装されていて、話題の Summingbird (Storm + Hadoopのハイブリッドプラットフォーム)でも使うことができます。大きなデータを扱っているサービスにとっては有用ですね。よくあるユースケースとしてはWebサイトのユニークユーザー数を推定する際などに利用することができます。
コマンド
Redis 2.8.9におけるHLL関連のコマンドは以下の3つです。プレフィックスの’PF’は HyperLogLog アルゴリズムの考案者である Philippe Flajolet 氏に敬意を表して付けたそうです。
|
1 2 3 |
## キーに値を追加 ## O(1) to add every element. PFADD key element [element ...] |
|
1 2 3 |
## 異なり数を算出 ## O(1) with every small average constant times when called with a single key. O(N) with N being the number of keys, and much bigger constant times, when called with multiple keys. PFCOUNT key [key ...] |
|
1 2 3 |
## キーを結合 ## O(N) to merge N HyperLogLogs, but with high constant times. PFMERGE destkey sourcekey [sourcekey ...] |
試してみます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
## キーに初期値を追加、新規追加に成功すると1が返る redis> PFADD hll foo bar zap (integer) 1 ## 値"zap"はキー内に既に存在しているので新規追加しない、0が返る redis> PFADD hll zap zap zap (integer) 0 ## 同上 redis> PFADD hll foo bar (integer) 0 ## 異なり数を算出、foo, bar, zapの合計3 redis> PFCOUNT hll (integer) 3 ## 別のキーに値を新規追加 redis> PFADD some-other-hll 1 2 3 (integer) 1 ## 2つのキーそれぞれの異なり数を算出、foo, bar, zap, 1, 2, 3の合計6 redis> PFCOUNT hll some-other-hll (integer) 6 ## キーの結合 redis> PFADD hll1 foo bar zap a (integer) 1 redis> PFADD hll2 a b c foo (integer) 1 redis> PFMERGE hll3 hll1 hll2 OK ## 結合したキーの異なり数を算出、foo, bar, zap, a, b, cの合計6 redis> PFCOUNT hll3 (integer) 6 |
和集合に対して計算してくれるのは便利ですね。数日分のログデータを合わせて集計したい時などに活用できそうです。
Pythonクライアント
redis-py モジュールからも簡単に利用できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
>>> import redis >>> r = redis.Redis(host='localhost', port=6379) >>> r.pfadd('hll', 'foo', 'bar', 'zap') 1 >>> r.pfadd('hll', 'zap', 'zap', 'zap') 0 >>> r.pfadd('hll', 'foo', 'bar') 0 >>> r.pfcount('hll') 3 >>> r.pfadd('some-other-hll', '1', '2', '3') 1 >>> r.pfcount('some-other-hll') 3 >>> r.pfcount('hll', 'some-other-hll') Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: pfcount() takes exactly 2 arguments (3 given) >>> r.pfadd('hll1', 'foo', 'bar', 'zap', 'a') 1 >>> r.pfadd('hll2', 'a', 'b', 'c', 'foo') 1 >>> r.pfmerge('hll3', 'hll1', 'hll2') True >>> r.pfcount('hll3') 6 |
redis-py モジュールでは2014/05現在 PFCOUNT コマンドに複数のキーを指定できないようです(すぐに改修されると思いますが)。
実装
異なり数を求めるのにハッシュ(セット)を用いたユニークデータ全てを記憶するようなナイーブな実装では大規模データに適用するのは現実的ではありません。HLLは LogLog Counting アルゴリズムから派生したもので、ハッシュ + ビットマップを使って異なり数を推定します。観測されるビットパターンが疎であることに注目して省メモリで推定できるようになっています。HLLでは異なり数が小さい場合は精度が低くなるという欠点があるのですが、Redisの実装では値の小さい内は Linear Counting アルゴリズムで計算しています。また、HLLに切り替えた後は回帰でバイアスを求めて補正しています。あらかじめバイアスを計算してルックアップテーブルを持っておく方法と比べてどちらが良いかはわかりませんが、個人的にはこちらの方が綺麗だと思います。パフォーマンスの点でどれくらいの差が出るのかは気になりますが。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
/* Muliply the inverse of E for alpha_m * m^2 to have the raw estimate. */ E = (1/E)*alpha*m*m; /* Use the LINEARCOUNTING algorithm for small cardinalities. * For larger values but up to 72000 HyperLogLog raw approximation is * used since linear counting error starts to increase. However HyperLogLog * shows a strong bias in the range 2.5*16384 - 72000, so we try to * compensate for it. */ if (E < m*2.5 && ez != 0) { E = m*log(m/ez); /* LINEARCOUNTING() */ } else if (m == 16384 && E < 72000) { /* We did polynomial regression of the bias for this range, this * way we can compute the bias for a given cardinality and correct * according to it. Only apply the correction for P=14 that's what * we use and the value the correction was verified with. */ double bias = 5.9119*1.0e-18*(E*E*E*E) -1.4253*1.0e-12*(E*E*E)+ 1.2940*1.0e-7*(E*E) -5.2921*1.0e-3*E+ 83.3216; E -= E*(bias/100); } |
HLLのオブジェクトはキャッシュ領域などを含む16バイトのヘッダが付いています。また、新しい型を追加しているわけではなくString型として扱っており、現在の状態はシリアライズされて格納されます。
|
1 2 3 4 5 6 7 |
struct hllhdr { char magic[4]; /* "HYLL" */ uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */ uint8_t notused[3]; /* Reserved for future use, must be zero. */ uint8_t card[8]; /* Cached cardinality, little endian. */ uint8_t registers[]; /* Data bytes. */ }; |
大きな疎データを扱う場合はデータ更新があんまりないので、キャッシュを用いて効率良く処理しています。つまり PFCOUNT は書き込みが発生する可能性のあるコマンドということです(副作用がある)。データが更新されていない場合はキャッシュされている値を返すようになっています(card[0]のMSBが立っているかどうかで判断)。
特徴的なのは内部で密(dense)と疎(sparse)の2つのデータ表現を適切に切り替えている点で、疎なデータを扱う際はランレングス符号を使ってデータをコンパクトに保持していたりと細かい工夫がいろいろ施されているようです。また、ハッシュアルゴリズムはEndian Neutralな64ビットの MurmurHash を採用しており、Redisの特徴の1つであるポータブル性も考慮された実装になっています。
標準誤差を1%未満に抑えながらも1つのキーにつき最大で12KB程度のメモリしか使わないというのは魔法のようですね。
テスト
試しにHTTPサーバ(Nginx)のアクセスログに記録されるホスト名を数え上げてみます。異なり数、つまりここではユニークユーザー数を推定することになります。まず最初にログファイル内のホスト名(or IPアドレス)を全て数え上げて真の異なり数を求めておきます。
|
1 2 3 4 5 |
$ cut -d ' ' -f 1 access.log | sort | uniq | wc -l 10339 ## ホスト名 or IPアドレスが10339個、真の異なり数 ## アクセスログの例、行の最初のカラムがIPアドレス ## 118.152.126.19 [12/Oct/2014:23:15:09 +0900] "GET /archives/3038/ HTTP/1.1" 200 21827 "https://rest-term.com/archives/3018/" "Mozilla/5.0 (Windows NT 6.1; WOW64; rv:32.0) Gecko/20100101 Firefox/32.0" |
このコマンドだとソート処理に多くのCPUリソースを使いますし、データ量の増加に応じてメモリ使用量も線形に増加してしまいます。RedisのSetに全てのデータを登録して SCARD コマンドで異なり数を求めることもできますが、やはり同様の問題が発生します。
次にRedisのHLLで異なり数を推定します。予めRedisにホスト名のリストを PFADD コマンドで登録しておきます。
|
1 2 3 4 5 6 |
127.0.0.1:6379> PFCOUNT ip ## "ip"キーで登録して、異なり数を推定 (integer) 10248 ## 推定された異なり数 127.0.0.1:6379> TYPE ip string ## String型 127.0.0.1:6379> STRLEN ip (integer) 12304 ## 12KB |
真の異なり数 10339 に対して、HLLでの推定値は 10248 となり、高い推定精度を確認できました。ついでにNASAが公開しているApacheのアクセスログデータでも試してみます。
* NASA-HTTP – Two Months of HTTP Logs from the KSC-NASA WWW Server
| データソース | 推定異なり数 (真の異なり数) |
|---|---|
| NASA_access_log_Jul95 | 82494 (81984) |
| NASA_access_log_Aug95 | 74959 (75061) |
真の異なり数と推定値のグラフも描いてみます。対角線に近いほど精度が高いことを示しています。
驚異の精度ですね。ほぼまっすぐじゃないですか。値の小さいときも高い精度を保っていることがわかります。
感想
省メモリかつ高い精度で異なり数を推定できる HyperLogLog というアルゴリズムは様々な場面で活用できそうです。ユニークユーザー数の推定というのは1つの適用例として挙げたのですが、どれだけ高精度であっても実運用上では、コマース系や広告配信をしているWebサイトのユニークユーザー数を推定値で済ませるというのは難しいでしょう。やはり自然言語処理領域で活用するのが良いのかなと。RedisのHLL実装は内部で様々な工夫が施されているのでソースコードを読んでみることをオススメします。個人的にはポータブル性を犠牲にして最新プロセッサのアーキテクチャに最適化した実装も見てみたいです。こういうアルゴリズムに興味が湧いてきたのでまずは基礎から勉強し直そうと思いました。
参考
* P. Flajolet, Eric Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm. (元論文)
* HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm
* Sketch of the Day: HyperLogLog — Cornerstone of a Big Data Infrastructure
* Redis new data structure: the HyperLogLog
* HyperLogLogで遊ぶ