ざっくり言えば、私はランダム化アルゴリズムが大好きなのですが、その中でもとりわけ愛着のあるものがあります。仕組みを理解した後でさえ、プログラマの視点から見ると今なお魔法のように感じられるアルゴリズムです。時間や空間という点で求めるものがごくわずかであるにもかかわらず、ほとんど非論理的とも思えることを成し遂げてくれます。このアルゴリズムはHyperLogLogと呼ばれ、今回Redisの新しいデータ構造として導入されることになりました。

ユニークなものを数える
===

通常、ユニークなものを数えるには――例えば今日あなたのWebサイトに接続したユニークなIPの数や、ユーザーが実行したユニークな検索の数を数えるには――これまでに出現したすべてのユニークな要素を覚えておく必要があります。次の要素を、すでに見た要素の集合と照合し、一度も見たことがない場合にのみカウンタを増やすためです。

これには、数えようとしている集合の濃度（要素数）に比例したメモリが必要となり、多くの場合、到底許容できない量になってしまいます。

ランダム性を利用して、一定かつ少量のメモリだけで集合内のユニークな要素数の近似値を求めるアルゴリズム群があります。現在知られている中で最も優れたものがHyperLogLogと呼ばれるアルゴリズムで、Philippe Flajoletによって考案されました。

HyperLogLogが目覚ましいのは、ごくわずかなメモリしか使わないにもかかわらず、集合の濃度を非常に高い精度で近似できる点です。Redisの実装では、キーあたりわずか12キロバイトで標準誤差0.81%のカウントが可能で、数えられる要素数に上限はありません。強いて言えば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枚のコインと、コインごとに1枚ずつ10枚の紙を用意し、それぞれについて表の最長連続を記録してもらいます。今回は観測できるデータが増えるので、推定の精度は高まります。

要するに、HyperLogLogがやっているのはこういうことです。観測した新しい要素ごとにハッシュ値を計算します。ハッシュの一部はレジスタを指し示すために使われます（先ほどの例でいうコインと紙のペアに相当します。つまり元の集合を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個のレジスタに対してわずか12kバイトしか使わない理由です。

Googleが[2]で提示したアルゴリズムの改良点の一つである64ビット出力の関数を用いているため、数えられる集合の濃度に実用上の上限はありません。さらに、小さな濃度では誤差が非常に小さくなる傾向があることも特筆に値します。次のグラフは、異なる2つの大きな集合に対してアルゴリズムを走らせた結果です。横軸が集合の濃度、縦軸が相対誤差（パーセント）を示しています。



赤と緑の線は、まったく無関係な2つの集合での別々の実行結果です。濃度が大きくなるにつれて誤差が一貫していることがわかります。ただし、はるかに小さな濃度では、さらに小さな誤差が得られます。



緑の線は濃度100までの一度の実行での誤差、赤い線は100回の実行で見つかった最大の誤差を示しています。数百程度までの濃度では、アルゴリズムは非常に小さな誤差しか出さないか、あるいは完全に正確な答えを返す可能性が非常に高いのです。これは、計算結果をユーザーに提示し、目視で正しさを確認できる場合に非常に有用です。

Redis実装のソースコードはGitHubで公開されています。

https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c

API
===

Redisの視点から見ると、HyperLogLogは単なる文字列であり、たまたま長さが正確に12k+8バイト（正確には12296バイト）になっているものに過ぎません。HyperLogLog用のコマンドはすべて、このサイズの文字列値に対して呼び出されれば正常に動作し、そうでなければエラーを返します。ただし、文字列に何が格納されていても呼び出しは安全です。ゴミデータを格納したままでも濃度の推定を求めることができ、いかなる場合でもサーバーがクラッシュすることはありません。

また、表現上のすべての要素はエンディアンに依存せず、プロセッサのワードサイズにも影響されないため、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は推定された濃度を返します。キーが存在しない場合はゼロを返します。

最後に、PFMERGEはN個の異なるHLL値を1つにマージできます。結果として得られるHLLが報告する推定濃度は、異なるHLL値でカウントした各集合の和集合の濃度となります。一見魔法のように思えますが、HLLはランダム性を持ちつつも完全に決定論的であるため、これが機能するのです。PFMERGEは、各レジスタについてN個のHLL値の中で最大の値を取るだけです。特定の要素は常に同じレジスタに同じゼロ連続でハッシュされるため、この方法で行われるマージでは、異なるHLL間で共通でない要素の分だけカウントが追加されることになります。

ご覧のとおり、HyperLogLogは完全に並列化可能です。集合をN個のサブセットに分割して独立にカウントし、後で値をマージして全体の濃度の近似値を得ることができるからです。RedisのHLLが単なる文字列であるという事実は、インスタンス間でHLL値を移動させるのにも役立ちます。

まず正しく、そして速く
===

RedisのHLLは、6ビット整数にパックされた16k個のレジスタで構成されています。これにより、あまり深く考えずに呼び出せるコマンドのAPIを提供するために解決すべきいくつかのパフォーマンス上の問題が生じます。

一つの問題は、レジスタへのアクセスが、正しい6ビット値を取り出すために複数バイトへのアクセス、シフト、マスクを必要とすることです。これは要素ごとに一つのレジスタにしか触れないPFADDにとっては大きな問題ではありませんが、PFCOUNTは16k個すべてのレジスタを使って計算を行う必要があるため、単一のレジスタへのアクセスに無視できない一定の時間がかかると、コマンドが遅くなる恐れがあります。さらに、レジスタにアクセスする際には、浮動小数点演算を伴うpow(2,-register)の合計を計算する必要があります。

計算を高速化するために6ビット整数の代わりに1バイト全体を使う誘惑に駆られるかもしれませんが、そうするとHLLごとに12kではなく16kバイトを使うことになり、無視できない差が生じるため、この案は早い段階で却下されました。コマンドは、以下の変更によって初期実装に比べて約3倍の高速化が図られました。

* m=16k（Redisのデフォルトで、実装自体はより汎用的で理論上は異なる値でも動作可能）の場合、実装は16個のレジスタを一度にアクセスするループを展開した高速パスを選択します。レジスタは、固定されたオフセット／シフト／マスクを使ってアクセスされます（次のイテレーションでは12バイト分進められるポインタを介して）。
* 浮動小数点演算は、可能な場合に複数の演算を並列に実行できるように修正されました。これは単に括弧を追加しただけのことでした。浮動小数点演算は可換ではありませんが、このケースでは精度の損失はありませんでした。
* pow(2,-register)の項はルックアップテーブルに事前計算されました。

上記の変更による3倍の高速化により、このコマンドは高速なハードウェアで毎秒約6万回の呼び出しを処理できるようになりました。しかしこれは、ユーザーの視点からは概念的に類似したSCARDのようなコマンドで可能な数十万回の呼び出しには、まだ遠く及びません。

近似濃度の計算をさらに最適化する代わりに、よりシンプルな解決策がありました。基本的に、アルゴリズムの出力はレジスタが変化したときにのみ変わります。しかし前述のとおり、ほとんどのPFADD呼び出しではレジスタは変化しません。これはつまり、最後の出力をキャッシュしておき、レジスタが変化したときだけ再計算すればよいということです。

そこで、私たちのデータ構造には、リトルエンディアン形式の64ビット符号なし整数を表す8バイトの末尾が追加されています。最上位ビットが立っている場合、事前計算された値は古くなっており再計算が必要ですが、そうでなければPFCOUNTはその値をそのまま利用できます。PFADDは、レジスタが変更されたときに単に「キャッシュ無効」ビットを立てるだけです。

この変更の後、50の同時クライアントで32要素のパイプラインを使って最大速度で要素を追加しようとしても、PFCOUNTは他のあらゆるO(1)コマンドと同等の、非常に小さな定数時間での性能を発揮できるようになりました。

多項式回帰によるバイアス補正
===

HLLアルゴリズムが実用的であるためには、あらゆる濃度の範囲で同等にうまく機能しなければなりません。残念ながら、アルゴリズムによる生の推定は、濃度がm*2.5未満（m=16384の場合は約40000要素）の範囲ではあまり良くありません。この範囲では、正確な領域によってはアルゴリズムの出力にバイアスがかかったり、誤差が大きくなったりするからです。

HLLの原論文[1]では、HLLアルゴリズムの前半で推定された生の濃度がm*2.5未満の場合にLinear Counting[5]に切り替えることが提案されています。

[5] http://dblab.kaist.ac.kr/Publication/pdf/ACM90_TODS_v15n2.pdf

Linear countingは、シンプルな概念を用いた別の濃度推定手法です。Nビットのビットマップを用意します。新しい要素をカウントするたびにハッシュ化し、そのハッシュを使ってビットマップ内のランダムなビットをインデックスし、そのビットを1にします。ビットマップ内で立っていないビットの数が、これまでに何要素を追加したかの目安となり、次の式で求められます。

    cardinality = m*log(m/ez);

ここで‘ez’はゼロビットの数、mはビットマップ内の総ビット数です。

Linear countingは、HyperLogLogと比べると大きな濃度ではあまりうまく機能しませんが、小さな濃度では非常にうまく機能します。HLLのレジスタは副次的にlinear countingのビットマップとしても機能するため、ゼロレジスタの数を数えることで、HLLがうまく機能しない範囲でlinear countingを適用することが可能です。これは、レジスタを更新する際に実際にはゼロの最長連続そのものではなく、ゼロの最長連続プラス1を使っているため可能になっています。つまり、要素が追加され、これまで一度もアクセスされたことのないレジスタを指し示した場合、レジスタは0から別の値（少なくとも1）へと変化するということです。

linear countingの問題は、濃度が大きくなるにつれて出力の誤差も大きくなるため、できるだけ早くHLLに切り替える必要があることです。しかし、2.5mで切り替えると、HLLはいまだバイアスがかかっています。次の画像では、同じ濃度を1000種類の異なる集合でテストし、各実行の誤差を点としてプロットしています。



青い線は誤差の平均です。ご覧のとおり、linear countingが使われる濃度40k以前では、濃度が大きくなるにつれて点の「帯」が広がっていきます（誤差が大きくなります）。HLLの生の推定値に切り替えると誤差は小さくなりますが、バイアスが存在します。アルゴリズムは40k〜80kの範囲で濃度を過大評価するのです。

Googleのエンジニアたちはこのバイアスを補正するためにこの問題を徹底的に研究しました[2]。彼らの解決策は、濃度の値とそれに対応するバイアスの経験的なテーブルを作成することでした。彼らの改良版アルゴリズムは、そのテーブルと補間を用いて特定の範囲でのバイアスを求め、それに応じて補正します。

私は異なるアプローチを取りました。バイアスはランダムではなく、非常に滑らかな曲線のように見えることがわかるので、いくつかの濃度-バイアスのサンプルを計算し、多項式回帰を行ってその曲線を近似する多項式を求めました。

現在、40960〜72000の範囲を補正するために4次の多項式を使用しており、バイアス補正後の結果は次のとおりです。



2つのアルゴリズムの切り替え点ではまだ若干のバイアスが残っていますが、素のHLLアルゴリズムと比べるとかなり満足のいく結果です。ただし、おそらくバイアス曲線によりよくフィットする曲線を使うことも可能でしょう。私はそれ以上深く調べる時間がありませんでした。

調査の過程で、バイアス補正を行わない場合、少なくともm=16384においては、linear countingからHLLの生の推定値へ切り替える最適な値は[1]で言及されている2.5ではなく、実際には3付近であることがわかりました。3という値はバイアスと誤差の両方を改善するからです。3より大きな値はバイアスを改善しますが（4という値はバイアスを完全に補正します）、誤差に悪影響を及ぼします。

HLLの元々のアルゴリズムでは、非常に大きな値に近づくとハッシュ関数の衝突が問題になり始めるため、2^32に近い値に対する補正も行われます[1][2]。私たちは64ビットのハッシュ関数と6ビットカウンタを使用しており、これはGoogleのエンジニアによって提案され[2]、Redisの実装でも採用された改良点の一つであるため、このような補正は必要ありません。

今後の課題
===

直感的には、linear countingが使われる際のアルゴリズム出力の誤差は、私たちが持っている追加情報を活用することで改善できるように思えます。標準的なlinear countingアルゴリズムではレジスタの幅はわずか1ビットなので、得られる情報は2つだけです。すなわち、これまでに要素がこのビットにハッシュされたかどうかだけです。それでも、最初に提案されたHLLアルゴリズム[1]やGoogleで改良されたもの[2]では、linear countingに戻る際にも入力としてゼロレジスタの数のみを使用しています。レジスタに格納された情報を併用することで、出力が改善される可能性があります。

例えば標準的なlinear countingで10ビットあると仮定すると、5つの要素を追加した際に、たまたまそれらすべてが同じビットを指すことがあり得ます。これはアルゴリズムが補正する術を持たない稀なケースであり、提供される推定値は実際の濃度よりも小さくなる可能性が高いでしょう。しかし、HLLで使われるlinear countingアルゴリズムでは、同様の状況で唯一セットされたレジスタの値が、そこで複数の要素が衝突していることのヒントとなり、出力の補正が可能になるかもしれません。

おわりに
===

HyperLogLogは驚くべきデータ構造です。数日以内に安定版リリースで利用可能になるRedisの実装（Redis 2.8.9に含まれる予定です）が、このツールをすぐに使える形で多くのプログラマに提供してくれることを願っています。

Hacker Newsの投稿はこちらです: https://news.ycombinator.com/item?id=7506774