Cloudflare が「悪性 URL データベース 100 万件」を毎リクエスト全件確認するのは現実的ではない。Bloom Filter という確率的データ構造で、117KB のメモリで 99% を即時判定できる。「間違うけど、間違っても困らない方向に間違う」絶妙なアルゴリズム。
1. これで何が動いているか
- Cloudflare の悪性 URL ブロックリスト判定
- Bitcoin SPV (軽量ノード) の Merkle ブロック判定
- Google Chrome の Safe Browsing
- Cassandra / HBase / RocksDB の SSTable 前段フィルタ
- Akamai / CDN のキャッシュ判定
- スパムフィルタ の既知スパム URL 判定
2. 仕組みのざっくり
- 長さ m の bit 配列 (初期は全 0)
- k 個の独立ハッシュ関数
- 追加: 要素を k 個のハッシュにかけ、対応する k 個の bit を 1 に
- 判定: 要素を k 個のハッシュにかけ、全ての bit が 1 か チェック。1 つでも 0 なら 絶対に未追加、全部 1 なら 追加されている可能性あり (偽陽性あり)
「No は確実、Yes は確率的」
Bloom Filter の特性: 偽陰性 (No なのに実は含む) は 絶対に発生しない。偽陽性 (Yes なのに実は含まない) は 設計したパラメータ通りの確率で発生。これが「キャッシュ前段で No を即返す」のに最適。
3. Python 実装 (動作確認済)
10 万件・偽陽性率 1% の Bloom Filter
Python
import hashlibimport math
class BloomFilter: def __init__(self, n=100_000, p=0.01): '''n = 想定追加件数、p = 偽陽性率''' self.m = int(-n * math.log(p) / (math.log(2) ** 2)) self.k = int(self.m / n * math.log(2)) self.bits = bytearray(math.ceil(self.m / 8))
def _hashes(self, item): # 2 つの基底ハッシュから k 個を合成 (double hashing) b = str(item).encode() h1 = int.from_bytes(hashlib.sha256(b).digest()[:8], 'big') h2 = int.from_bytes(hashlib.blake2b(b, digest_size=8).digest(), 'big') return [(h1 + i * h2) % self.m for i in range(self.k)]
def add(self, item): for idx in self._hashes(item): self.bits[idx // 8] |= (1 << (idx % 8))
def __contains__(self, item): return all(self.bits[idx // 8] & (1 << (idx % 8)) for idx in self._hashes(item))
# テストbf = BloomFilter(n=100_000, p=0.01)for i in range(100_000): bf.add(f'item_{i}')
# 偽陽性率の確認: 100,000 件の未登録アイテムで判定fp = sum(1 for i in range(100_000, 200_000) if f'item_{i}' in bf)print(f'メモリ: {bf.m / 8 / 1024:.1f} KB ({bf.m:,} bits)')print(f'ハッシュ数 k: {bf.k}')print(f'偽陽性率: {fp / 100_000 * 100:.2f}% (target: 1.00%)')
# 実機実行結果:# メモリ: 117.0 KB (958,505 bits)# ハッシュ数 k: 6# 偽陽性率: 1.01% (target: 1.00%)4. メモリ・偽陽性率の設計
| 想定 n | p (偽陽性率) | m (bits) | メモリ | k (ハッシュ数) |
|---|---|---|---|---|
| 1 万 | 10% | 47,936 | 5.9 KB | 3 |
| 1 万 | 1% | 95,851 | 11.7 KB | 6 |
| 10 万 | 1% | 958,505 | 117 KB | 6 |
| 100 万 | 1% | 9,585,058 | 1.14 MB | 6 |
| 100 万 | 0.1% | 14,377,587 | 1.71 MB | 9 |
| 10 億 | 1% | 9,585,058,732 | 1.14 GB | 6 |
5. Counting Bloom Filter (削除可能版)
削除可能な拡張版
Python
class CountingBloomFilter: def __init__(self, n=100_000, p=0.01): self.m = int(-n * math.log(p) / (math.log(2) ** 2)) self.k = int(self.m / n * math.log(2)) self.counts = [0] * self.m # bit ではなく counter
def _hashes(self, item): b = str(item).encode() h1 = int.from_bytes(hashlib.sha256(b).digest()[:8], 'big') h2 = int.from_bytes(hashlib.blake2b(b, digest_size=8).digest(), 'big') return [(h1 + i * h2) % self.m for i in range(self.k)]
def add(self, item): for idx in self._hashes(item): self.counts[idx] += 1
def remove(self, item): # 削除可能だが「未追加要素を remove するとカウンタが負に」する注意 for idx in self._hashes(item): if self.counts[idx] > 0: self.counts[idx] -= 1
def __contains__(self, item): return all(self.counts[idx] > 0 for idx in self._hashes(item))6. 実用ライブラリ
pybloom-live (本番運用向け)
Python
# pip install pybloom-livefrom pybloom_live import BloomFilter, ScalableBloomFilter
# 固定容量bf = BloomFilter(capacity=100_000, error_rate=0.01)for i in range(100_000): bf.add(f'item_{i}')
# スケーラブル (容量超過時に自動拡張)sbf = ScalableBloomFilter(initial_capacity=10_000, error_rate=0.01)for i in range(1_000_000): sbf.add(f'item_{i}')7. 関連ツール
- RedisBloom: Redis の
BF.*コマンド - Cassandra / HBase: 内部で SSTable に Bloom 標準装備
- RocksDB: 同上、無効化も可能
- Apache DataSketches: Bloom + HLL + CMS 統合
8. 次の話
EP.06 では MinHash + LSH を扱います。「1 億件の文書から似た文書を発見」を高速にする確率的アルゴリズム。剽窃検査・レコメンドの実装。