ブルームフィルタ
実装:
data-structures/bloomfilter// 実行:go test ./data-structures/bloomfilter/
要素を保存せずに「たぶん有る / 確実に無い」だけを答える。1万件を1件あたり9.6ビットで持ち、誤って「有る」と言う率(偽陽性率)は設計値1%に対して実測1.03%とほぼ一致する。だが弱点も同じくらいはっきりしていて、想定の2倍入れただけで1%が17%になり、しかもエラーは何も出ない。消せないので、入れすぎたら作り直すしかない。
この章で作るもの
ハッシュマップは要素を全部保存して正確に答えた。ブルームフィルタは 逆に、要素を1つも保存しない。ビット配列だけで「集合に入っているか」を確率的に答える。
順に見ていく。
- 無いは確実、有るは疑い: 偽陰性が起きないので、重い処理の門番として安全に置ける
- 欲しい精度からサイズが逆算できる: 設計値と実測が小数点以下まで合う
- 入れすぎると黙って効かなくなる: 2倍で 1% が 17% になる。エラーは出ない
① 無いは確実、有るは疑い
ビット配列を1本用意する。要素を追加するときは、その要素を k 個のハッシュ関数に通して 得た k 個の位置のビットを立てる。判定するときは、同じ k 個の位置が全部立っているかを見る。
追加 apple → ハッシュ3つ → bit 2, 5, 11 を立てる
[0 0 1 0 0 1 0 0 0 0 0 1 0 ...]
↑ ↑ ↑
調べる grape → bit 2, 7, 11 → bit 7 が 0 → 絶対にない
調べる apple → bit 2, 5, 11 → 全部 1 → たぶんある// positions は key から k 個のビット位置を導く。
// ハッシュを2つ用意して h1 + i·h2 で k 個作る「ダブルハッシュ法」。
// 独立なハッシュを k 個実装しなくて済む定番テクニック。
func (f *Filter) positions(key string) []uint64 {
h := fnv.New64a()
h.Write([]byte(key))
sum := h.Sum64()
h1 := sum & 0xffffffff // 下位32bit
h2 := (sum >> 32) | 1 // 上位32bit(0 だと進まないので奇数化)
pos := make([]uint64, f.k)
for i := 0; i < f.k; i++ {
pos[i] = (h1 + uint64(i)*h2) % f.m
}
return pos
}
// Add は key を追加する。k 個のビットを立てるだけ。
func (f *Filter) Add(key string) {
f.added++
for _, p := range f.positions(key) {
f.bitset[p/64] |= 1 << (p % 64)
}
}
// MayContain は「たぶん入っている」なら true、「絶対に入っていない」なら false。
// k 個のビットが全部立っていれば true。1つでも立っていなければ確実に false。
func (f *Filter) MayContain(key string) bool {
for _, p := range f.positions(key) {
if f.bitset[p/64]&(1<<(p%64)) == 0 {
return false // 1つでも 0 なら、この key は絶対に入れていない
}
}
return true // 全部 1。入っているかも(偽陽性の可能性あり)
}なぜ偽陰性が起きないか: 追加時に立てたビットは二度と消えない。だから入れた要素を 調べれば、その k 個のビットは必ず全部立っている。「ない」と答えるのは1つでも 0 の ビットがあったときだけで、それは追加していない確たる証拠。
なぜ偽陽性が起きるか: 別々の要素が立てたビットが、たまたま組み合わさって、 入れていない要素の k 個の位置を全部埋めてしまうことがある。このとき「たぶんある」と 嘘をつく。要素数が増えてビットが埋まるほど、この確率は上がる。
試す: apple を追加してから grape を調べると「ない」。apple を調べると「ある」。 いくつか追加してビットを埋めると、追加していない語でも「ある(偽陽性)」が 出るようになる。黄色枠が「今調べた3つのビット」。
② 欲しい精度からサイズが逆算できる
ブルームフィルタの美しいところは、欲しい偽陽性率 p と入れる件数 n から、 必要なビット数 m とハッシュ関数の数 k が計算で決まること。
m = -n·ln(p) / (ln2)² ← 必要なビット数
k = (m/n)·ln2 ← 最適なハッシュ関数の数// Filter はビット配列と、使うハッシュ関数の数 k。
type Filter struct {
bitset []uint64 // ビットを 64 個ずつ詰めた配列
m uint64 // 総ビット数
k int // ハッシュ関数の数
added int // 入れた回数
}
// New は「n 件入れたときに偽陽性率が約 p になる」フィルタを作る。
// 最適なビット数 m とハッシュ関数の数 k は n と p から計算で決まる:
//
// m = -n·ln(p) / (ln2)² k = (m/n)·ln2
//
// 欲しい精度からサイズを逆算できるのが、この道具のいちばんの取り柄になる。
func New(n int, p float64) *Filter {
if n <= 0 {
panic("bloomfilter: n must be positive")
}
if p <= 0 || p >= 1 {
panic("bloomfilter: p must be in (0, 1)")
}
m := uint64(math.Ceil(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))
k := int(math.Round(float64(m) / float64(n) * math.Ln2))
if k < 1 {
k = 1
}
return &Filter{
bitset: make([]uint64, (m+63)/64),
m: m,
k: k,
}
}この式が本当に効いているかは測れる。1万件入れて、入れていない10万件で試すとこうなった:
| 設計した偽陽性率 | 実測 | 1件あたりのビット | ハッシュ関数の数 |
|---|---|---|---|
| 0.1 | 0.09707 | 4.8 | 3 |
| 0.01 | 0.01032 | 9.6 | 7 |
| 0.001 | 0.00111 | 14.4 | 10 |
| 0.0001 | 0.00012 | 19.2 | 13 |
小数点以下まで設計どおりになっている。しかも 1件あたりのビット数を見ると、精度を1桁上げるたびに +4.8 ビット ずつしか増えない。1万件を 1% で持つのに 12KB、0.01% にしても 24KB になる。
要素そのものを保存しないから、この軽さが出る。ハッシュマップならキーの実データだけで何十倍にもなる。テストで、3つの設計値それぞれについて実測が設計値の2倍以内に収まることを固定した。
コードの読みどころ: ダブルハッシュ法
positions は独立したハッシュ関数を k 個は用意していない。1つの64bitハッシュを 上下に割って h1, h2 を作り、h1 + i·h2 で k 個の位置を生成している(ダブルハッシュ法)。 独立ハッシュを k 個実装・計算するコストを避けつつ、偽陽性率はほぼ悪化しないことが 知られている定番テクニック。
使いどころは、重い処理の前の門番
偽陽性はあるが偽陰性はない、という非対称性が効くのは「空振りを安く弾きたい」場面。
- DBの読み取り: ディスクを読む前にブルームフィルタで「そのキーは無い」と分かれば、 ディスクアクセスを丸ごと省ける。LSM-Tree(RocksDB等)の各層に 必ず付いている
- キャッシュ: 「一度もアクセスされたことがないURLか」を軽く判定して、 無駄なキャッシュ照会を減らす
- 重複検出: クローラが「このURLもう見たか」を省メモリで概算する
共通するのは「false なら確実」を活かして、高い確率で無駄な重い処理を早期に弾く構図。 偽陽性で稀に本処理に進んでも、そこで正確に判定すればいいので実害はない。
③ 入れすぎると黙って効かなくなる
②の式は「n 件入れたら」という前提に立っている。前提が破れたときに何が起きるかも測っておく。
ビットの詰まり具合を見れば、入れた件数を知らなくても分かる:
// Added は入れた回数を返す。
func (f *Filter) Added() int { return f.added }
// Bits は総ビット数、Hashes は使うハッシュ関数の数を返す。
func (f *Filter) Bits() uint64 { return f.m }
func (f *Filter) Hashes() int { return f.k }
// FillRatio は立っているビットの割合を返す。
//
// 詰まり具合がそのまま精度になる。半分埋まれば、k 個すべてが
// たまたま立っている確率は (1/2)^k になる。
func (f *Filter) FillRatio() float64 {
var on int
for _, w := range f.bitset {
on += popcount(w)
}
return float64(on) / float64(f.m)
}
// EstimatedRate は今の詰まり具合から見込まれる偽陽性率を返す。
//
// 立っている割合の k 乗。入れた件数を知らなくても、ビットを見るだけで
// 「もう効いていない」が分かる。
func (f *Filter) EstimatedRate() float64 {
r := f.FillRatio()
out := 1.0
for i := 0; i < f.k; i++ {
out *= r
}
return out
}
func popcount(w uint64) int {
n := 0
for w != 0 {
w &= w - 1
n++
}
return n
}設計 1000件・1% のフィルタに、そのまま入れ続けた結果がこうなった:
| 入れた件数 | 実測の偽陽性率 | 立っているビットの割合 | ビットから見た見込み |
|---|---|---|---|
| 1,000(設計どおり) | 0.0107 | 0.525 | 0.0110 |
| 2,000(2倍) | 0.1687 | 0.777 | 0.1711 |
| 3,000 | 0.4514 | 0.894 | 0.4561 |
| 5,000(5倍) | 0.8355 | 0.975 | 0.8386 |
2倍入れただけで、1% が 17% になる。5倍では 84%、つまりほとんど「有る」と答えるだけの箱になっている。
問題は、この間エラーも警告も何も出ないことになる。Add は最後まで成功し、MayContain も答えを返し続ける。門番として置いたつもりのものが、いつのまにか素通しになっている。
しかも消せない。ビットを落とすと、そのビットを共有している他の要素の判定まで壊れる。入れすぎたフィルタは、作り直すしかない。
気づく手はある。上の表の右2列を見比べると、立っているビットの割合から出した見込みが、実測とほぼ一致している。件数を数えていなくても、ビットを見るだけで「もう効いていない」が分かる。テストで、5倍入れたときに実測が 0.5 を超えること、詰まり具合が 0.9 を超えることを固定した。
設計の観点
- 非対称な答えを活かす: 片側だけ確実なら、その側で早く弾く門番として置ける
- 欲しい精度から寸法を決める: 逆算できる形にしておくと、勘で決めずに済む
- 前提が破れたときの姿を測る: 想定の2倍でどうなるかを知らないと、置き場所を決められない
- 黙って壊れるものには見張りを付ける: 詰まり具合を見れば、件数を数えなくても気づける
- 直せないものは作り直す前提で持つ: 消せない構造なら、入れ替えの手順を先に決めておく
- 偽陽性の後始末を用意する: 通り抜けた先で正確に判定できるなら、実害は出ない
対照と実例
| 誤り | 消せるか | 1件あたり | 中身を出せるか | |
|---|---|---|---|---|
| ハッシュマップ | 無し | できる | キーの実データ | 出せる |
| ブルームフィルタ | 偽陽性のみ | できない | 9.6 ビット(1%) | 出せない |
| counting bloom | 偽陽性のみ | できる | 4倍前後 | 出せない |
| cuckoo filter | 偽陽性のみ | できる | 同等かやや小 | 出せない |
| HyperLogLog | 個数の誤差 | (該当なし) | 定数 | 出せない |
裏どり:
- Bloom(1970): 綴りの辞書を主記憶に載せるために考えられた。「入っていない語を安く弾ければ、あとはディスクを引けばよい」という構図は今と同じになる
- RocksDB / LevelDB / Cassandra: SSTable の各層にブルームフィルタが付いている。ディスクを読む前に「このキーは無い」と分かれば、読みを丸ごと省ける。LSM-Tree の読みが実用に耐えるのはこれがあるから
- ダブルハッシュ法: 独立したハッシュを k 個作らず、1つの64ビットを上下に割って
h1 + i·h2で k 個の位置を作っている。Less Hashing, Same Performance が、これで偽陽性率がほとんど悪化しないことを示している - Chrome の Safe Browsing: 悪性URLの一次判定をローカルのブルームフィルタでやり、当たったものだけサーバへ問い合わせる形を使っていた。偽陽性が「余計な問い合わせ」で済む構図になっている
- 消せないことへの答え: counting bloom filter はビットの代わりに小さなカウンタを持つ。scalable bloom filter は満杯になったら層を足す
簡略化したこと
- 消せない: カウンタを持つ形(counting bloom filter)は作っていない
- 大きさが固定: 満杯になったら層を足す形(scalable bloom filter)も無い
- 入れすぎを止めない: 詰まり具合は見られるようにしたが、
Addを拒む仕掛けは入れていない - ダブルハッシュ法: 理論上の最適からわずかにずれるが、実用上は問題にならない
- 並行安全でない: ビットを立てるだけなので競合しにくいが、保証はしていない
参考資料
- Bloom filter (Wikipedia) — パラメータ式の導出も載っている
- Less Hashing, Same Performance — ダブルハッシュ法の理論的裏付け
- RocksDB: Bloom Filter — 実DBでの使われ方
- 実装: data-structures/bloomfilter