1. ブルームフィルタとは
ブルームフィルタ(Bloom filter)は一言で言えば、「絶対に無いとは断言できるが、有ると言った答えは間違うことがある」という非対称な性質を持つ、確率的な集合メンバーシップ判定のデータ構造である。ある要素がある集合に含まれているかどうかを、要素そのものを1件も保存せずに、ごく小さな固定長のビット配列だけで答える。
この非対称性はバグではなく設計そのものである。ブルームフィルタは偽陰性(false negative)を絶対に起こさない代わりに、偽陽性(false positive)をある確率で起こすことを許容する。「無い」と言われたら100%信頼してよいが、「有る」と言われたら一定確率で外れる——この特性を逆手に取り、「本当に問い合わせる前の高速な足切り」として使うのが典型的な用途になる。
この構造を考案したのは Burton H. Bloom で、1970年に Communications of the ACM 誌に発表した論文 “ Space/Time Trade-offs in Hash Coding with Allowable Errors ”( PDF )が初出である。原題が示す通り、モチベーションは「ハッシュ法において、一定の誤り(allowable errors)を許容する代わりに、時間・空間を大幅に節約する」ことにあった。半世紀以上前の論文だが、この発想は現代の分散データベース・検索エンジン・CDNの内部で今も現役で使われ続けている。
2. 仕組み: ビット配列とk個のハッシュ関数
ブルームフィルタの実体は、サイズ \(m\) ビットの配列(初期値はすべて0)と、\(k\) 個の独立したハッシュ関数 \(h_1, h_2, \dots, h_k\) (それぞれ \(0\) から \(m-1\) の整数を返す)の組だけである。
挿入(insert): 要素 \(x\) を挿入する際は、\(k\) 個のハッシュ関数それぞれで \(h_i(x)\) を計算し、対応するビットをすべて1に立てる。
判定(query): 要素 \(y\) が集合に含まれるか判定する際も同様に \(h_1(y), \dots, h_k(y)\) を計算し、対応する\(k\) 個のビットを調べる。
- 1つでも0のビットがあれば、\(y\) は絶対に挿入されていない(そのビットを1にした要素は過去に一度も無かったことになるため)。
- すべて1であれば、「たぶん挿入されている」と判定する。ただし、\(y\) 自身は一度も挿入していないのに、他の複数の要素の挿入によって偶然\(k\) 個すべてのビットが1になってしまっている可能性がある。これが偽陽性である。
下図はこの様子を図示したものである。判定対象 \(y\) (挿入済み)は3本の矢印が指すビットがすべて1なので正しく「有る」と判定されるのに対し、判定対象 \(z\) (未挿入)も偶然3本とも1のビットを指してしまい、誤って「有る」と判定されてしまっている。
なぜ削除ができないのか
通常のブルームフィルタには要素の削除操作が無い。理由は単純で、1本のビットは複数の要素で共有されているためである。ある要素を消したいからといって、その要素が指すビットを0に戻してしまうと、たまたま同じビットを共有していた別の要素の情報まで消えてしまい、まだ集合に存在するはずの要素が「無い」と誤判定されてしまう(これは偽陽性よりもさらに深刻な、許されないはずの偽陰性を生む)。ビットを1にする操作は非可逆であり、これがブルームフィルタの最大の制約になっている。この制約への対処は第8節で扱う。
3. 偽陽性率の導出
ブルームフィルタの実用上もっとも重要な指標は、偽陽性率 \(p\) である。これを理想的なランダムハッシュを仮定して段階的に導出する。
要素数 \(n\) を挿入し終えた後、ある1本のビットに注目する。1回のハッシュ計算でそのビットが選ばれる確率は \(1/m\) なので、選ばれない確率は \(1-1/m\) である。\(n\) 個の要素それぞれが\(k\) 個のハッシュ関数を使うので、挿入によるハッシュ計算の総数は \(kn\) 回。したがって、あるビットが一度も選ばれず0のままである確率は
\[ \left(1 - \frac{1}{m}\right)^{kn} \]である。ここで \(m \to \infty\) の極限で成り立つ有名な関係 \(\left(1-\frac{1}{m}\right)^{m} \to e^{-1}\) を使うと、
\[ \left(1 - \frac{1}{m}\right)^{kn} = \left[\left(1 - \frac{1}{m}\right)^{m}\right]^{kn/m} \approx e^{-kn/m} \]と近似できる。つまり、あるビットが0のままである確率は \(\approx e^{-kn/m}\) 、1になっている確率は \(\approx 1 - e^{-kn/m}\) である。
偽陽性が起きるのは、未挿入の要素 \(z\) について \(k\) 個のハッシュがすべて「たまたま1になっているビット」を指してしまう場合である。各ハッシュの結果を独立とみなす近似のもとで、これらを単純に掛け合わせると偽陽性率の標準的な近似式が得られる。
\[ p \approx \left(1 - e^{-kn/m}\right)^{k} \](なお、極限近似を使わない厳密な形は \(p = \left(1-(1-\frac{1}{m})^{kn}\right)^{k}\) であり、\(m\) が十分大きければ両者はほぼ一致する。第5節の実験ではこの厳密式も含めて実測と比較している。)
最適なハッシュ数 \(k\) の導出
\(m\) と \(n\) を固定したとき、\(p\) を最小化する \(k\) が存在する。\(x = kn/m\) とおくと \(p(x) = (1-e^{-x})^{x m/n}\) で、\(\ln p\) を \(x\) で微分してゼロと置くと、
\[ \ln(1-e^{-x}) + \frac{x\,e^{-x}}{1-e^{-x}} = 0 \]という方程式が得られる。\(u = e^{-x}\) と置換すると、\(x = -\ln u\) なので
\[ \ln(1-u) - \frac{u \ln u}{1-u} = 0 \]となり、これは \(u = 1/2\) のとき \(\ln(1/2) - \frac{(1/2)(-\ln 2)}{1/2} = -\ln 2 + \ln 2 = 0\) を満たす。したがって最適解は \(e^{-x^*} = 1/2\) 、すなわち \(x^* = kn/m = \ln 2\) である。ここから最適なハッシュ数
\[ k^{*} = \frac{m}{n}\ln 2 \approx 0.6931 \cdot \frac{m}{n} \]が導かれる。このときの最小偽陽性率は \(e^{-x^*}=1/2\) を代入するだけで求まり、
\[ p^{*} = \left(1-\frac{1}{2}\right)^{k^{*}} = 2^{-k^{*}} \approx 0.6185^{\,m/n} \]というきれいな形になる。つまり「ビット数を1個あたり何ビット割り当てるか(\(m/n\) )」を決めれば、最適なハッシュ数と、そのときに達成できる偽陽性率の下限が一意に決まる。次節ではこの理論式を実装し、実測でこの通りになるかを確認する。
4. Python実装
以下がnumpyを使った自作実装である。ビット配列は numpy.bool 型の配列(1要素1バイト)で表現し、ハッシュ関数には標準ライブラリの hashlib.blake2b をソルト付きで使う。ただし \(k\)
本の独立したハッシュを毎回計算するのは無駄が多いため、Kirsch–Mitzenmacher の二重ハッシュ手法を採用した。これは1つのキーに対して独立な2本のハッシュ値 \(h_1, h_2\)
さえ計算しておけば、
という線形結合だけで\(k\)
本のハッシュ関数を模擬できる、理論的にも実用上も広く使われている手法である(GuavaのBloomFilter実装などでも採用されている)。この方法のおかげで、\(k\)
やビット配列サイズ\(m\)
を変えて何十パターンも実験する際も、キーごとのblake2b計算は1回で済み、残りはnumpyのベクトル演算だけで完結する。
import hashlib
import math
import numpy as np
SALT = b"bloom-filter-blog-20260720"
def base_hashes(keys):
"""各キー(bytes)についてblake2bダイジェストからh1,h2(64bit整数)を算出する。"""
h1 = np.empty(len(keys), dtype=np.uint64)
h2 = np.empty(len(keys), dtype=np.uint64)
for i, k in enumerate(keys):
d = hashlib.blake2b(k, salt=SALT[:16], digest_size=16).digest()
h1[i] = int.from_bytes(d[:8], "little")
h2[i] = int.from_bytes(d[8:], "little")
return h1, h2
class BloomFilter:
"""m bit, k hash のブルームフィルタ。h1,h2は事前計算済みのものを渡す。"""
def __init__(self, m):
self.m = m
self.bits = np.zeros(m, dtype=bool)
def _indices(self, h1, h2, k):
m = np.uint64(self.m)
return [((h1 + np.uint64(i) * h2) % m).astype(np.int64) for i in range(k)]
def insert_all(self, h1, h2, k):
for idx in self._indices(h1, h2, k):
self.bits[idx] = True
def query_all(self, h1, h2, k):
"""各キーについて全k本のビットが立っていればTrue(=フィルタは「存在する」と判定)"""
present = np.ones(len(h1), dtype=bool)
for idx in self._indices(h1, h2, k):
present &= self.bits[idx]
return present
def theoretical_fp(k, n, m):
return (1 - math.exp(-k * n / m)) ** k
insert_all/query_all は1要素ずつのループではなく、挿入したい全要素・全クエリのハッシュ値をまとめて配列で受け取り、numpyのファンシーインデックスで一括にビットを立てる/読む設計にしている。こうすることで \(n=10万\)
件規模の実験を何十通りも(ビット配列サイズ \(m\)
・ハッシュ数 \(k\)
を変えながら)現実的な時間で回せる。
5. 実験1: 理論値と実測値は一致するか
理論式 \(p \approx (1-e^{-kn/m})^k\)
が実際のデータでどこまで正確かを検証する。挿入する要素数を \(n=100{,}000\)
件、判定に使う未挿入キーを \(100{,}000\)
件用意し(乱数シードを固定し、member-{i} / nonmember-{i} という互いに絶対衝突しない名前空間から生成)、ハッシュ数 \(k \in \{2,4,6,8\}\)
とビット比 \(m/n \in \{4,6,8,10,12,16,20\}\)
の全組み合わせで偽陽性率を実測した。
一部を抜粋する。
| k | m/n | 実測偽陽性率 | 理論値 \((1-e^{-kn/m})^k\) | 相対誤差 |
|---|---|---|---|---|
| 2 | 8 | 0.047330 | 0.048929 | 3.27% |
| 4 | 8 | 0.023580 | 0.023969 | 1.62% |
| 6 | 10 | 0.008780 | 0.008436 | 4.08% |
| 8 | 12 | 0.003060 | 0.003142 | 2.62% |
| 4 | 20 | 0.001020 | 0.001080 | 5.53% |
28通りの組み合わせ全体で見ると、相対誤差は多くの点で5%未満に収まっている。例外的に誤差が大きく見える点(例: \(k=6, m/n=20\) で実測0.000430 対理論0.000303、相対誤差41.85%)は、理論的な期待偽陽性件数がそもそも約30件(10万件中)しかない領域であり、ポアソン統計的なばらつき(\(\sqrt{30}\approx5.5\) )だけで実測43件とのズレが十分説明できる範囲に収まっている。つまり誤差が大きく見える箇所は理論式が外れているのではなく、単に「サンプル数に対して事象が稀すぎて統計誤差が相対的に目立つ」だけである。
図から分かる通り、対数スケールで見た理論曲線と実測点はほぼ完全に一致しており、極限近似 \(p \approx (1-e^{-kn/m})^k\) が実用上十分な精度を持つことが確認できた。
6. 実験2: 最適ハッシュ数kの実測
次に第3節で導出した最適ハッシュ数 \(k^{*} = \frac{m}{n}\ln 2\) が実測でも成立するかを検証する。\(m/n=10\) (要素1個あたり10ビット)に固定し、\(n=100{,}000\) に対して \(m=1{,}000{,}000\) ビット、ハッシュ数 \(k\) を1から10まで振って偽陽性率を実測した。理論上の最適解は \(k^{*} = 10 \times \ln 2 = 6.931\) である。
| k | 実測偽陽性率 | 理論値 |
|---|---|---|
| 1 | 0.09572 | 0.09516 |
| 2 | 0.03303 | 0.03286 |
| 3 | 0.01805 | 0.01741 |
| 4 | 0.01210 | 0.01181 |
| 5 | 0.01023 | 0.00943 |
| 6 | 0.00878 | 0.00844 |
| 7 | 0.00852 | 0.00819 |
| 8 | 0.00852 | 0.00846 |
| 9 | 0.00930 | 0.00913 |
| 10 | 0.01036 | 0.01019 |
実測値は \(k=7\) と \(k=8\) でどちらも100,000件中852件と、この測定精度の範囲では完全に同率の最小値になった。理論値 \(k^{*}=6.931\) を四捨五入するとちょうど7であり、実測の最小点(7〜8)とぴったり一致している。
図のU字カーブが示す通り、\(k\) が小さすぎるとビットが立つ位置が少なすぎて識別力が足りず、\(k\) が大きすぎると1回の挿入で大量のビットを1にしてしまい配列全体がすぐ埋まってしまう。この両者のトレードオフの谷底が理論通り \(k \approx (m/n)\ln 2\) 付近に存在することを、実測で確認できた。
7. 設計早見: n要素・目標偽陽性率pから m, k を決める
実務でブルームフィルタを設計する際に知りたいのは、「要素数 \(n\) 」と「許容できる偽陽性率 \(p\) 」から逆算した必要ビット数 \(m\) とハッシュ数 \(k\) である。第3節の結果 \(p^{*} = 2^{-k^{*}}\) 、\(k^{*}=\frac{m}{n}\ln2\) を \(p\) について \(n, p\) の式に立て直すと、
\[ m = -\frac{n \ln p}{(\ln 2)^2}, \qquad k = \frac{m}{n}\ln 2 \]という設計式が得られる。目標偽陽性率別の早見表は次の通り。
| 目標偽陽性率 \(p\) | 必要ビット数 (1要素あたり) | 最適ハッシュ数 \(k\) |
|---|---|---|
| 10% | 約4.8 bit | 3 |
| 5% | 約6.2 bit | 4 |
| 2% | 約8.1 bit | 6 |
| 1% | 約9.6 bit | 7 |
| 0.1% | 約14.4 bit | 10 |
| 0.01% | 約19.2 bit | 13 |
例えば「1億件のキーに対して偽陽性率1%以下を実現したい」場合、必要ビット数は約 \(9.6 \times 10^8\) ビット(約115 MB)、ハッシュ数は7本、という具合に一瞬で設計値が求まる。データベースやキャッシュのキー1件分の実データ(数十〜数百バイト)を丸ごと保持する場合と比べ、1件あたり1バイト強で済む点がブルームフィルタの空間効率の核心である。
8. 実システムでの使われ方
ブルームフィルタは学術的な面白さだけでなく、現代の主要なデータベース・インフラで実際に採用されている実用的な道具である。
LSM-tree系データベースのSSTable読み飛ばし: Cassandra や RocksDB のようなLSM-tree構造のデータベースは、書き込みを一度メモリ上のメモテーブルに蓄積し、それを不変(immutable)な SSTable ファイルとしてディスクにフラッシュしていく。1つのキーを読むとき、どのSSTableにそのキーがあるか事前に分からないため、最悪すべてのSSTableを開いて確認する必要が出てしまう。ここでブルームフィルタが効く。
Cassandra公式ドキュメント
によれば、各SSTableにはそのSSTableが持つキー集合のブルームフィルタが Filter コンポーネントとしてオフヒープに保持されており、bloom_filter_fp_chance(デフォルトはコンパクション戦略により0.01〜0.1)で偽陽性率を調整できる。「このSSTableには絶対に無い」と分かればディスクI/Oそのものをスキップできるため、存在しないキーの検索が劇的に速くなる。
RocksDBのBloom Filter実装
も同様の考え方で、デフォルトで約10 bit/keyのフィルタを各SSTファイルに持たせており、これは第7節の早見表の通りおよそ1%の偽陽性率に相当する。
CDNの一発屋(one-hit-wonder)判定: AkamaiのCDNでは、キャッシュされるアセットの実に75%が一度しかリクエストされない「一発屋」であったという分析結果を受け、ブルームフィルタで「そのURLが過去に一度でもリクエストされたことがあるか」を判定し、2回目以降のリクエストで初めてキャッシュに載せる仕組みを導入した。これにより、二度と参照されないコンテンツでキャッシュ容量を無駄に消費することを防ぎ、実効的なキャッシュ容量を大幅に増やす効果を得ている。
Milvusの削除判定: ベクトルデータベースMilvusでも、削除操作を即座の物理削除にせず delta log(削除ログ)として記録し、検索時に「このセグメントに削除済みのPrimary Keyが含まれているか」をブルームフィルタで高速に絞り込む実装になっている。詳細は Milvusの内部構造を解説した記事 で扱っている。
派生データ構造: 素のブルームフィルタは削除ができないという制約があるため、これを補う派生形も広く使われている。Counting Bloom Filter はビットの代わりに数ビット(通常4bit程度)のカウンタを持たせ、挿入時にインクリメント、削除時にデクリメントすることで削除操作を実現するが、単純なビット配列よりも数倍のメモリを要する。より新しい Cuckoo Filter は、ビットではなく要素のフィンガープリント(短いハッシュ値)をカッコウハッシュ法のテーブルに格納する方式で、フィンガープリントを1つ取り除くだけで削除ができ、目標偽陽性率が3%未満のような領域では素のブルームフィルタより省メモリになることが知られている。
まとめ
ブルームフィルタは、\(m\) ビットの配列と\(k\) 個のハッシュ関数という極めてシンプルな道具立てで、「絶対に無い」を保証しつつ「有るかもしれない」を低コストで判定する確率的データ構造である。偽陽性率は \(p \approx (1-e^{-kn/m})^k\) で近似でき、最適なハッシュ数は \(k^{*}=\frac{m}{n}\ln2\) のときに \(p^{*}=2^{-k^{*}}\) という最小値を取る。今回のnumpy自作実装による実測では、この理論式が実際のデータに対してもほぼ誤差5%以内で一致し、最適ハッシュ数も理論値6.93に対し実測7〜8で最小になることを確認できた。SSTableのスキップ、CDNのキャッシュ判定、ベクトルDBの削除フィルタなど、実システムの性能を陰で支える基礎技術として、今後も設計の選択肢に入れておく価値がある。
FAQ
Q1. 偽陰性(本当は挿入したのに「無い」と判定される)は起きますか? 起きない。挿入時に立てたビットは(削除操作をしない限り)0に戻ることが無いため、挿入済みの要素を判定すれば対応する\(k\) 個のビットは必ずすべて1になっている。理想的なハッシュ関数と正しい実装のもとでは、ブルームフィルタは偽陰性を原理的に起こさない。
Q2. 要素を削除したくなったらどうすればいいですか? 素のビット配列によるブルームフィルタは削除に対応していない(第2節参照)。削除が必要な場合は、ビットの代わりにカウンタを持つ Counting Bloom Filter か、フィンガープリントベースの Cuckoo Filter を使うのが定石である。あるいは、定期的にフィルタ全体を空の状態から再構築する運用でも回避できる。
Q3. ハッシュ関数は本当に\(k\) 個必要ですか? 理論上は独立な\(k\) 個のハッシュ関数を使う想定だが、実装上は第4節で紹介した Kirsch–Mitzenmacher の二重ハッシュ手法を使えば、独立な2本のハッシュ値さえ計算すれば \(h_i(x)=(h_1(x)+i\cdot h_2(x)) \bmod m\) という線形結合で\(k\) 本ぶんの効果を再現できる。理論的な偽陽性率にもほぼ影響を与えないことが知られており、実務ではこちらが標準的である。
Q4. ハッシュテーブルとどう使い分ければいいですか? ハッシュテーブルはキーそのもの(または十分な情報)を保持するため偽陽性を一切起こさないが、要素数に比例して数バイト〜数十バイトのメモリが必要になる。ブルームフィルタは1要素あたり1〜2バイト程度で済む代わりに偽陽性を許容する。したがって、ブルームフィルタは「本当のデータストア(ディスク上のSSTable、ネットワーク越しのDBなど)に問い合わせる前段の高速な足切りフィルタ」として使い、実際の存在確認そのものはハッシュテーブルや実データストアに委ねる、という組み合わせが典型的な使い方になる。
他の分野の定番書は エンジニアにおすすめの技術書10選 にまとめている。