Rest Term

RedisのHyperLogLogを使ってユニークユーザー数を推定する

Pocket

去年の内に公開することが出来ず、ずっと下書き状態だったエントリーをちょっとずつ消化していきたいと思います。ネタとして古いものも含まれていたりすると思いますがしばらくご辛抱ください。。


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 氏に敬意を表して付けたそうです。

試してみます。

和集合に対して計算してくれるのは便利ですね。数日分のログデータを合わせて集計したい時などに活用できそうです。

Pythonクライアント

redis-py モジュールからも簡単に利用できます。

redis-py モジュールでは2014/05現在 PFCOUNT コマンドに複数のキーを指定できないようです(すぐに改修されると思いますが)。

実装

異なり数を求めるのにハッシュ(セット)を用いたユニークデータ全てを記憶するようなナイーブな実装では大規模データに適用するのは現実的ではありません。HLLは LogLog Counting アルゴリズムから派生したもので、ハッシュ + ビットマップを使って異なり数を推定します。観測されるビットパターンが疎であることに注目して省メモリで推定できるようになっています。HLLでは異なり数が小さい場合は精度が低くなるという欠点があるのですが、Redisの実装では値の小さい内は Linear Counting アルゴリズムで計算しています。また、HLLに切り替えた後は回帰でバイアスを求めて補正しています。あらかじめバイアスを計算してルックアップテーブルを持っておく方法と比べてどちらが良いかはわかりませんが、個人的にはこちらの方が綺麗だと思います。パフォーマンスの点でどれくらいの差が出るのかは気になりますが。

HLLのオブジェクトはキャッシュ領域などを含む16バイトのヘッダが付いています。また、新しい型を追加しているわけではなくString型として扱っており、現在の状態はシリアライズされて格納されます。

大きな疎データを扱う場合はデータ更新があんまりないので、キャッシュを用いて効率良く処理しています。つまり PFCOUNT は書き込みが発生する可能性のあるコマンドということです(副作用がある)。データが更新されていない場合はキャッシュされている値を返すようになっています(card[0]のMSBが立っているかどうかで判断)。

特徴的なのは内部で密(dense)と疎(sparse)の2つのデータ表現を適切に切り替えている点で、疎なデータを扱う際はランレングス符号を使ってデータをコンパクトに保持していたりと細かい工夫がいろいろ施されているようです。また、ハッシュアルゴリズムはEndian Neutralな64ビットの MurmurHash を採用しており、Redisの特徴の1つであるポータブル性も考慮された実装になっています。

標準誤差を1%未満に抑えながらも1つのキーにつき最大で12KB程度のメモリしか使わないというのは魔法のようですね。

テスト

試しにHTTPサーバ(Nginx)のアクセスログに記録されるホスト名を数え上げてみます。異なり数、つまりここではユニークユーザー数を推定することになります。まず最初にログファイル内のホスト名(or IPアドレス)を全て数え上げて真の異なり数を求めておきます。

このコマンドだとソート処理に多くのCPUリソースを使いますし、データ量の増加に応じてメモリ使用量も線形に増加してしまいます。RedisのSetに全てのデータを登録して SCARD コマンドで異なり数を求めることもできますが、やはり同様の問題が発生します。

次にRedisのHLLで異なり数を推定します。予めRedisにホスト名のリストを PFADD コマンドで登録しておきます。

真の異なり数 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)

真の異なり数と推定値のグラフも描いてみます。対角線に近いほど精度が高いことを示しています。
NASA_access_log_Jul95_cardinality
NASA_access_log_Aug95_cardinality
驚異の精度ですね。ほぼまっすぐじゃないですか。値の小さいときも高い精度を保っていることがわかります。

感想

省メモリかつ高い精度で異なり数を推定できる 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で遊ぶ

あわせて読む:

Pocket

 

Tags: ,

Comments

No comments so far.

  • Leave a Reply
     
    Your gravatar
    Your Name