Redisの新しいデータ構造：HyperLogLog
一般論として、私は確率的アルゴリズムが大好きです。ただ、その中でも特に気に入っているものがあります。仕組みを理解したあとでさえ、プログラマーの視点から見ると魔法のように感じられるからです。時間や空間についてほとんど何も要求しないのに、ほとんど論理に反していると思えることを実現します。このアルゴリズムはHyperLogLogと呼ばれ、今日はRedisの新しいデータ構造として紹介します。
ユニークなものを数える
===
通常、ユニークなものを数えるには、たとえば今日Webサイトに接続したユニークなIPアドレスの数や、ユーザーが実行したユニークな検索の数を数えるには、それまでに遭遇したすべてのユニークな要素を記憶しておく必要があります。次の要素を、すでに見た要素の集合と照合し、新しい要素がこれまでに一度も見たことのないものだった場合にだけカウンターを増やすためです。
この方法では、数えている集合の基数（要素数）に比例したメモリ量が必要になります。これは、しばしばまったく現実的ではありません。
ランダム化を使い、一定量かつ少量のメモリだけで、集合に含まれるユニークな要素数を近似するアルゴリズム群があります。現在知られている中で最も優れたものがHyperLogLogで、Philippe Flajoletによるものです。
HyperLogLogが注目に値するのは、ごく少量のメモリでも集合の基数を非常によく近似できる点です。Redisの実装では、標準誤差0.81%で数える場合、キー1つあたりわずか12キロバイトしか使いません。また、数えられる要素数に上限はありません。2^64個に近づけば別ですが、これはかなり考えにくいでしょう。
アルゴリズムについては原論文[1]に記載されています。また、実用的な実装とその変種については、Googleによる2013年の論文[2]で詳しく扱われています。
[1] http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
[2] http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/40671.pdf
仕組み
===
HyperLogLogについてさらに学ぶには、[3]のような素晴らしい資料がたくさんあります。
[3] http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/
ここでは、[3]にある非常に巧みな例を使って、基本的な考え方だけ説明します。あなたが一日中コインを投げ続け、表が途切れずに何回連続したかを数えていたとします。その最長記録が表3回だったと聞けば、コインをそれほど何度も投げたわけではないと考えられます。一方、最長記録が13回だったなら、かなり長い時間コインを投げていたのでしょう。
しかし、運よく最初に表が10回連続して出てしまい、その時点でコインを投げるのをやめたとします。これは起こりにくいものの、あり得ることです。この場合、コインを投げていた時間について、私は非常に間違った推定をしてしまいます。そこで、実験を繰り返してもらうことにします。ただし今度はコインを10枚使い、紙も10枚用意します。コイン1枚につき紙1枚を割り当て、それぞれについて表の最長連続回数を記録します。今回はより多くのデータを観測できるので、推定はもっと正確になります。
要するに、HyperLogLogが行っているのはこれです。観測した新しい要素をすべてハッシュ化します。ハッシュの一部を使ってレジスタを1つ選びます。先ほどの例でいうコインと紙の組に相当するものです。つまり、元の集合をm個の部分集合に分割しています。ハッシュの別の部分を使って、ハッシュの先頭にゼロが何個連続しているかを数えます。先ほどの例でいう表の連続回数です。ゼロがN+1個連続する確率は、長さNの連続が起こる確率の半分です。そのため、各部分集合についてこれまでに観測したゼロの最長連続回数を保持する各レジスタの値を観測すれば、HyperLogLogは基数を非常に精度よく近似できます。
Redisの実装
===
HyperLogLogの標準誤差は1.04/sqrt(m)です。ここで「m」は使用するレジスタ数です。
Redisは16384個のレジスタを使うため、標準誤差は0.81%になります。
Redisの実装で使われているハッシュ関数の出力は64ビットです。そのうち14ビットを16k個のレジスタのアドレス指定に使うため、残りは50ビットです。したがって、遭遇し得るゼロの最長連続は6ビットのレジスタに収まります。RedisのHyperLogLogの値が、16k個のレジスタに対して12キロバイトしか使わないのはこのためです。
64ビット出力の関数を使っているため、数えられる集合の基数に実用上の制限はありません。これはGoogleが[2]で示したアルゴリズムの変更点の1つです。さらに、非常に小さな基数では誤差も非常に小さくなる傾向がある点にも注目すべきです。以下のグラフは、異なる2つの大きな集合に対してアルゴリズムを実行した結果を示しています。x軸は集合の基数、y軸は相対誤差（パーセント）です。
赤と緑の線は、互いにまったく関係のない2つの集合に対する異なる実行結果です。基数が増えても誤差が安定していることが分かります。ただし、もっと小さな基数では、さらに小さな誤差になります。
緑の線は、基数100まで1回実行したときの誤差を示しています。赤い線は、100回実行した中で見つかった最大誤差です。基数が数百までなら、アルゴリズムが非常に小さな誤差を出すか、正確な答えを返す可能性が高くなります。計算された値をユーザーに表示し、そのユーザーが答えが正しいかどうかを目で確認できる場合、これは非常に価値があります。
Redis実装のソースコードはGithubで公開されています。
https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c
API
===
Redisの観点から見ると、HyperLogLogは単なる文字列です。ただし、長さは正確に12k + 8バイト（厳密には12296バイト）です。HyperLogLogのコマンドは、このサイズと正確に一致するString値に対して呼び出せば問題なく実行され、それ以外の場合はエラーを報告します。ただし、文字列に何が格納されていても、すべての呼び出しは安全です。でたらめなデータを格納していても、基数の推定を要求できます。どのような場合でも、これによってサーバーがクラッシュすることはありません。
また、表現の中身はすべてエンディアンに依存せず、プロセッサのワードサイズにも影響されません。そのため、32ビットのビッグエンディアンプロセッサで、64ビットのリトルエンディアンプロセッサのHLLを読み取れます。
HyperLogLogを文字列にしたことで、RDBレベルに実際の型を追加せずに済みました。これにより、この変更は数日以内にRedis 2.8へバックポートされ、HyperLogLogをすぐに使えるようになります。さらに、形式は自動的にシリアライズされ、簡単に取得・復元できます。
APIは、次の3つの新しいコマンドで構成されます。
PFADD var element element … element
PFCOUNT var
PFMERGE dst src src src … src
コマンドの接頭辞が「PF」なのは、Philippe Flajolet [4]への敬意を表したものです。
[4] http://en.wikipedia.org/wiki/Philippe_Flajolet
PFADDは、「var」に格納されたHLLに要素を追加します。変数が存在しない場合は、Redis APIの呼び出しでは常にそうなるように、空のHLLが自動的に作成されます。このコマンドは可変個引数なので、非常に積極的なパイプライン処理や大量挿入が可能です。
コマンドは、基礎となるHyperLogLogが変更された場合に1を返し、それ以外の場合は0を返します。
これはユーザーにとって興味深い性質です。要素を追加していくと、実際にどれかのレジスタを変更する要素が現れる確率は低下するからです。新しい基数が得られたことをAPIから知らせられるため、要素を継続的に追加し、新しい基数が得られたときだけ近似値を取得するプログラムを作れます。
PFCOUNTは推定基数を返します。キーが存在しない場合は0です。
最後に、PFMERGEはN個の異なるHLL値を1つにマージできます。結果のHLLが返す推定基数は、それぞれのHLL値で数えた異なる集合の和集合の基数になります。
これは魔法のように見えますが、HLLはランダム化されている一方で完全に決定的に動作するため、うまくいきます。PFMERGEは、各レジスタについて、N個のHLL値にある値の最大値を取るだけです。ある要素は常に同じレジスタにハッシュされ、ゼロの連続回数も常に同じになります。そのため、この方法でマージすると、複数のHLLに共通しない要素の数だけが追加されます。
このように、HyperLogLogは完全に並列化できます。集合をN個の部分集合に分け、それぞれを独立に数えたあと、値をマージして集合全体の基数の近似値を得られるからです。RedisのHLLが単なる文字列であることは、HLLの値をインスタンス間で移動する際にも役立ちます。
まず正しく動かし、それから高速化する
===
RedisのHHLは、6ビット整数を16k個詰め込んだ構成になっています。このため、あまり深く考えずに呼び出せるコマンドAPIを提供するには、いくつかの性能上の問題を解決しなければなりません。
問題の1つは、レジスタへのアクセスに複数バイトの読み取り、シフト、マスク処理が必要で、正しい6ビット値を取り出さなければならないことです。PFADDは要素ごとに1つのレジスタに触れるだけなので、これは大きな問題ではありません。しかしPFCOUNTは16k個すべてのレジスタを使って計算するため、各レジスタへのアクセスに無視できない固定コストがあると、コマンドが遅くなるおそれがあります。さらに、レジスタにアクセスしながらpow(2,-register)の総和も計算する必要があり、ここには浮動小数点演算が含まれます。
計算を高速化するために、6ビット整数ではなく1バイトを丸ごと使いたくなるかもしれません。しかし、それでは各HLLが12kではなく16kを使うことになり、無視できない差が生じるため、残念な選択です。この方法は最初から採用しませんでした。代わりに、次の変更を行うことで、コマンドを初期実装と比べて約3倍高速化しました。
* Redisのデフォルトであるm=16k（実装はより汎用的で、理論上は別の値でも動作します）の場合、16個のレジスタに一度にアクセスするループ展開済みの高速経路を選びます。レジスタには固定オフセット、シフト、マスクを使ってアクセスします。次の反復では、ポインタの一部を12バイト進めます。
* 浮動小数点計算を変更し、可能な場合に複数の演算を並列に実行できるようにしました。これは単に括弧を追加するだけでした。浮動小数点演算は可換ではありませんが、この場合は精度の低下はありませんでした。
* pow(2,-register)の項をルックアップテーブルにあらかじめ計算しておきました。
上記の変更によって3倍高速化した結果、高速なハードウェアでは1秒あたり約6万回の呼び出しを処理できるようになりました。しかし、これはまだ、ユーザーから見て概念的に似ているSCARDのようなコマンドで可能な、毎秒数十万回には遠く及びません。
そこで、近似基数の計算をさらに最適化する代わりに、もっと単純な解決策を採りました。基本的に、アルゴリズムの出力はレジスタが変化したときにしか変わりません。しかし、すでに見たように、PFADDの呼び出しの大半ではレジスタは変化しません。つまり、最後の出力をキャッシュし、どれかのレジスタが変化したときだけ再計算すればよいのです。
そこで、このデータ構造には8バイトの追加領域を持たせ、リトルエンディアン形式の64ビット符号なし整数を格納します。最上位ビットがセットされていれば、事前計算された値は古くなっており、再計算が必要です。そうでなければ、PFCOUNTはそのまま値を利用できます。PFADDは、どれかのレジスタが変更されたときに「キャッシュ無効」ビットをオンにするだけです。
この変更後は、50個の同時クライアントから32要素のパイプラインを使って最大速度で要素を追加する場合でも、PFCOUNTは、固定コストが非常に小さい他のO(1)コマンドと同等の性能を発揮しました。
多項式回帰によるバイアス補正
===
HLLアルゴリズムを実用的なものにするには、どの基数の範囲でも同じようによく機能しなければなりません。しかし残念ながら、HLLアルゴリズムの前半で行う生の推定は、m*2.5未満の基数（m=16384なら約40000要素）ではあまりよくありません。この範囲では、正確な範囲によって、アルゴリズムが偏った結果や、より大きな誤差を持つ結果を出すからです。
HLLの原論文[1]では、アルゴリズム前半で推定した生の基数がm*2.5未満の場合、Linear Counting [5]に切り替えることを提案しています。
[5] http://dblab.kaist.ac.kr/Publication/pdf/ACM90_TODS_v15n2.pdf
Linear Countingは、別の基数推定法で、単純な考え方に基づいています。Nビットのビットマップがあるとします。新しい要素を数えるたびにハッシュ化し、そのハッシュを使ってビットマップ内のランダムなビットを選び、1にします。ビットマップ中の0のビット数から、次の式でそれまでに追加した要素数を推定できます。
cardinality = m*log(m/ez);
ここで「ez」は0ビットの数、「m」はビットマップの全ビット数です。
Linear Countingは、大きな基数ではHyperLogLogに比べてうまく機能しません。しかし、小さな基数では非常によく機能します。HLLのレジスタは副作用としてLinear Countingのビットマップの役割も果たすため、0のレジスタ数を数えれば、HLLがうまく機能しない範囲にLinear Countingを適用できます。これが可能なのは、レジスタを更新するとき、実際にはゼロの最長連続回数ではなく、ゼロの最長連続回数に1を加えた値を使っているからです。つまり、要素が追加され、それまで一度もアドレス指定されていないレジスタが選ばれた場合、そのレジスタは0から別の値（少なくとも1）に変わります。
Linear Countingの問題は、基数が大きくなるほど出力誤差も大きくなるため、できるだけ早くHLLへ切り替える必要があることです。しかし2.5mで切り替えると、HLLにはまだバイアスが残っています。以下の画像では、同じ基数について異なる1000個の集合をテストし、それぞれの実行結果の誤差を点として示しています。
青い線は誤差の平均です。Linear Countingを使う基数40kまでは、基数が大きくなるほど点の「ビーム」が広がり、誤差が大きくなっていることが分かります。HLLの生の推定値に切り替えると誤差は小さくなりますが、バイアスが生じます。基数40k〜80kの範囲で、アルゴリズムは基数を過大推定します。
Googleのエンジニアは、この問題を広範に研究し、バイアスを補正しました[2]。彼らの解決策は、基数の値と対応するバイアスをまとめた実測テーブルを作ることでした。変更されたアルゴリズムは、そのテーブルと補間を使って、特定の範囲におけるバイアスを求め、それに応じて補正します。
私は別の方法を使いました。バイアスはランダムではなく、非常に滑らかな曲線のように見えます。そこで、基数とバイアスのサンプルをいくつか計算し、その曲線を近似する多項式を見つけるために多項式回帰を行いました。
現在は4次多項式を使い、40960〜72000の範囲を補正しています。バイアス補正後の結果は次のとおりです。
2つのアルゴリズムの切り替え地点にはまだ若干のバイアスが残っています。それでも、補正前の素のHLLアルゴリズムと比べれば、結果はかなり満足できるものです。ただし、バイアス曲線にさらによく合う曲線を使える可能性はあります。これについては、さらに調査する時間がありませんでした。
なお、調査中に分かったことがあります。バイアス補正を使わない場合、少なくともm=16384では、Linear CountingからHLLの生の推定値へ切り替える最適な値は、[1]で述べられている2.5ではなく、実際には3に近い値です。3にするとバイアスと誤差の両方が改善されます。3より大きい値にするとバイアスは改善します（4なら完全に補正されます）が、誤差には悪影響が出ます。
原理論文のHLLアルゴリズムは、2^32に近づく値についても補正します[1][2]。非常に大きな値になると、ハッシュ関数での衝突が問題になり始めるからです。しかし、64ビットのハッシュ関数と6ビットのカウンターを使っているため、この補正は必要ありません。これはGoogleのエンジニアが提案し[2]、Redisの実装で採用した変更点の1つです。
今後の課題
===
直感的には、追加で得られる情報を活用すれば、Linear Countingを使う場合のアルゴリズム出力の誤差を改善できそうです。標準的なLinear Countingアルゴリズムでは、レジスタの幅は1ビットだけです。そのため、得られる情報は「これまでに要素がこのビットへハッシュされたかどうか」の2種類しかありません。それでも、当初提案されたHLLアルゴリズム[1]も、Googleで変更されたもの[2]も、Linear Countingへ戻る際には0のレジスタ数だけを入力として使っています。レジスタに格納された情報も使えば、出力を改善できる可能性があります。
たとえば、標準的なLinear Countingで10ビットあるとし、5つの要素を追加したところ、すべて同じビットを指したとします。これは特殊なケースですが、アルゴリズムには補正する方法がなく、実際の基数より小さい推定値になりそうです。しかし、HLLで使われるLinear Countingの場合、同じような状況で、1つだけセットされたレジスタの値から、そこに複数の要素が衝突したことを示唆する情報を得られます。これによって出力を補正できるかもしれません。
結論
===
HyperLogLogは驚くべきデータ構造です。数日以内に安定版（Redis 2.8.9に含まれる予定）で利用できるようになるRedis実装によって、多くのプログラマーがこのツールをすぐに使える形で利用できるようになることを願っています。
HNの投稿はこちらです：https://news.ycombinator.com/item?id=7506774