確率的データ構造 — 数えずに数える

ブルームフィルタ・HyperLogLog・Count-Minスケッチを前提知識ゼロから解説。「少しだけ間違える権利」と引き換えにメモリを数KBに固定する仕組みと、巨大サービスの裏でどう運用されているかまで。

Space/Time Trade-offs in Hash Coding with Allowable Errors (Bloom

数えようとした瞬間に、メモリが足りなくなる

「今日このサイトを訪れたのは何人か」。素直に答えるなら、訪問者のIDを集合に入れていき、最後にその大きさを見ればいい。1日1000人なら何の問題もありません。

ところが1日1億人になり、しかも同じ数字を「1時間ごと」「国ごと」「記事ごと」に出せと言われた瞬間、事情が変わります。集合の数だけメモリが要る。同じ問題が「このURLは処理済みか」「いま最もアクセスの多いIPはどれか」にも起きます。どれも正直に答えようとすると、見たものを全部覚えることになるからです。

確率的データ構造——スケッチとも呼ばれます——は、この要求をたった1か所だけ緩めます。答えがときどき間違ってもよいことにするのです。代わりに、データが何件流れてこようとメモリが増えないという性質が手に入る。HyperLogLogなら1集計あたり12KB。1億人でも12KB、100億人でも12KB、誤差は1%弱です。

「正確に数える」は「全部覚える」の言い換えでしかない

なぜ1か所緩めるだけで桁が変わるのか。理由はアルゴリズムの巧妙さより手前、情報の量そのものにあります。

$n$ 個の異なるキーについて「あるか無いか」に一度も間違えず答えるには、その集合を他のあらゆる集合と区別できるだけの情報を保持しなければなりません。誤りを一切許さないなら、結局キーそのものと同等の情報が要る。ところが「入っていないものを『ある』と答えてしまう確率 $\varepsilon$ までは許す」と決めた途端、必要なビット数の下限はこう下がります。

$n$ は登録する要素数、$\varepsilon$ は許容する誤り率です。読み下すと「1要素あたり $\log_2(1/\varepsilon)$ ビットあれば足りる」。誤り1%なら約6.6ビット、0.1%でも約10ビット。ここで肝心なのは、この式にキーの長さが出てこないことです。100バイトのURLだろうが1KBの検索クエリだろうが、1要素あたり数ビット。誤りを許すというのは、キーの中身を捨てて痕跡だけを残す許可証なのです。

問いの種類ごとに、道具は3つに分かれます。

3つとも中核はハッシュ関数です。ハッシュは入力の偏り（連番のID、似たURL）を消して、どんな入力もランダムなビット列に見せてくれる。その「ランダムに見える」性質の上に統計が乗る、というのが共通の設計です。ハッシュ関数そのものの作り方はハッシュと近傍探索にまとめてあります。

以下、3つを順に、なぜそれで数えられてしまうのかまで分解します。

ブルームフィルタ: 「無い」だけを確実に言う

用意するのは $m$ ビットの配列（最初は全部0）と $k$ 個のハッシュ関数だけ。登録は「要素を $k$ 個のハッシュに通し、出てきた $k$ か所のビットを1にする」。問い合わせは同じ $k$ か所を見て、1つでも0なら確実に入っていない、全部1なら「たぶん入っている」。要素そのものは一切保存しません。

偽陰性（入っているのに「無い」）は原理的に起こりません。一度立てたビットは戻らないからです。偽陽性（入っていないのに「ある」）は、他の要素が立てたビットがたまたま $k$ か所そろったときに起きます。$n$ 個を登録したあとの偽陽性率は次の式で見積もれます。

$1 - e^{-kn/m}$ が「ある1ビットが誰かに立てられている確率」で、それが $k$ か所そろう確率が $p$ です。$k$ を増やすと「そろいにくくなる」効果と「配列が早く埋まる」効果がぶつかるので最適点があり、$k = (m/n)\ln 2$ のとき配列のちょうど半分が1になります。1要素あたり10ビット割けば偽陽性は1%弱。導出とコードは乱択アルゴリズム側に置いてあります。

ここで先ほどの下限と突き合わせると面白いことが分かります。$\varepsilon = 1\%$ の下限は1要素6.6ビットでした。ブルームフィルタは10ビット使う。つまり理論の最適より約44%多くメモリを食っている。効率で負けている分、ビット演算だけで動く単純さを買っているわけです。この差を詰めつつ削除もできるように設計されたのがカッコウフィルタや商フィルタで、要素の指紋（短いハッシュの断片）を保存する方式です。素のブルームフィルタが削除できないのは、ビットを0に戻すとそのビットを共有する他の要素まで「無い」ことにされ、あってはならない偽陰性が生まれるからです。

もう1つ、実務で効く使い方の型があります。ブルームフィルタは単体で使う道具ではなく、高価な確認の前に置く門番だということ。「無い」と即答できたら重い処理をまるごと省き、「ある」と言われたときだけ本体に問い合わせる。偽陽性は「無駄に本体を見に行った」で済み、答えの正しさは本体が保証するので、確率的な誤りがユーザーまで漏れません。

残る2つ——種類数を数えるHyperLogLogと、回数を数えるCount-Minスケッチ——は、ビットを立てる代わりに小さな統計量を持ちます。なぜハッシュの先頭に並ぶ0を眺めるだけで人数が当たるのか、なぜ最小値を取ると「数え過ぎ」だけで済むのか。ここから先はその2つと、巨大サービスがそれをどう運用しているかです。