---
id: wiki-2026-0508-bloom-filters
title: Bloom Filters
category: 10_Wiki/Topics
status: verified
canonical_id: self
aliases: [블룸 필터, probabilistic data structure, count-min sketch, hyperloglog, cuckoo filter]
duplicate_of: none
source_trust_level: A
confidence_score: 0.95
verification_status: applied
tags: [bloom-filter, probabilistic-data-structure, hash, cache, set-membership, big-data, redis, postgres]
raw_sources: []
last_reinforced: 2026-05-10
github_commit: pending
tech_stack:
  language: any
  framework: Redis / RocksDB / Cassandra / Postgres
---

# Bloom Filters

## 📌 한 줄 통찰
> **"매 set 의 'maybe / definitely not' 의 fast"**. 매 hash + bit array 의 probabilistic. 매 false positive 가능 가, 매 false negative X. 매 cache / DB / dedup 의 huge save. 매 modern: 매 cuckoo / xor filter 의 변형.

## 📖 핵심

### 매 algorithm
1. 매 m-bit array, 매 모두 0.
2. 매 k 개 hash function.
3. **Insert(x)**: 매 hash_i(x) % m 의 매 bit set.
4. **Query(x)**: 매 모든 매 bit 가 1 → "maybe present", else "definitely not".

### 매 false positive rate
$$FPR \approx \left(1 - e^{-kn/m}\right)^k$$

- m = bit array size.
- n = inserted items.
- k = hash count.

### 매 optimal k
$$k = (m/n) \cdot \ln 2$$

### 매 sizing 의 example
| Items (n) | FPR target | Bits (m) | k |
|---|---|---|---|
| 1M | 1% | 9.6M | 7 |
| 1M | 0.1% | 14.4M | 10 |
| 1M | 0.01% | 19.2M | 13 |
| 100M | 1% | 960M | 7 |

→ 매 약 매 9.6 bits / item / 1% FPR.

### 매 properties
- **No false negative**: 매 not present → 매 definitely not.
- **False positive**: 매 present → 매 maybe.
- **No deletion** (basic): 매 counting Bloom 의 답.
- **Space-efficient**: 매 hash table 의 1/10.
- **Constant time**: 매 O(k).

### 매 변형

#### Counting Bloom Filter
- 매 counter 의 array.
- 매 deletion 가능.
- 매 4× space.

#### Scalable Bloom Filter
- 매 series 의 BF 의 chain.
- 매 dynamic size.

#### Cuckoo Filter
- 매 cuckoo hash 의 base.
- 매 deletion 가능.
- 매 false positive ≤ Bloom.

#### Xor Filter (2019)
- 매 modern, 매 fastest, 매 smaller.
- 매 immutable.

#### Quotient Filter
- 매 cache-friendly.
- 매 mergeable.

### 매 응용

#### Cache filter (Bigtable, Cassandra, RocksDB)
- 매 disk 의 query 전 의 BF check.
- 매 not-in-set → 매 disk skip.

#### Web crawler
- 매 visited URL.

#### Email spam
- 매 known spam URL.

#### Database join
- 매 Bloom join.

#### Distributed cache (Redis)
- `BF.ADD`, `BF.EXISTS` (RedisBloom).

#### Postgres
- `bloom` extension on index.

#### Bitcoin
- 매 SPV (Simplified Payment Verification).

#### Dedup
- 매 stream 의 duplicate detect.

### 매 alternative
- **HashSet**: 매 exact, 매 매 large.
- **Cuckoo / Xor filter**: 매 modern Bloom 보다 better.
- **HyperLogLog**: 매 cardinality estimate (count, not membership).
- **Count-Min Sketch**: 매 frequency estimate.

## 💻 패턴

### Basic Bloom Filter (Python)
```python
import mmh3

class BloomFilter:
    def __init__(self, size=10_000_000, hash_count=7):
        self.size = size
        self.hash_count = hash_count
        self.bits = bytearray((size + 7) // 8)
    
    def _hashes(self, item):
        b = item.encode() if isinstance(item, str) else item
        for seed in range(self.hash_count):
            yield mmh3.hash(b, seed) % self.size
    
    def add(self, item):
        for h in self._hashes(item):
            self.bits[h // 8] |= 1 << (h % 8)
    
    def __contains__(self, item):
        return all((self.bits[h // 8] >> (h % 8)) & 1 for h in self._hashes(item))
```

### RedisBloom
```bash
# 매 server-side BF
> BF.RESERVE myfilter 0.01 1000000
OK
> BF.ADD myfilter "user:123"
(integer) 1
> BF.EXISTS myfilter "user:123"
(integer) 1
> BF.MADD myfilter "user:1" "user:2" "user:3"
1) (integer) 1 ...
```

### Postgres Bloom index
```sql
CREATE EXTENSION bloom;

CREATE INDEX users_bloom_idx ON users
USING bloom (id, email, country)
WITH (length=80, col1=4, col2=2, col3=2);

-- 매 multi-column lookup 의 fast
EXPLAIN SELECT * FROM users WHERE id = 100 AND country = 'US';
```

### Counting Bloom (with deletion)
```python
class CountingBloomFilter:
    def __init__(self, size=10_000_000, hash_count=7):
        self.size = size
        self.hash_count = hash_count
        self.counts = [0] * size
    
    def add(self, item):
        for h in self._hashes(item):
            self.counts[h] += 1
    
    def remove(self, item):
        if item not in self: return
        for h in self._hashes(item):
            if self.counts[h] > 0: self.counts[h] -= 1
    
    def __contains__(self, item):
        return all(self.counts[h] > 0 for h in self._hashes(item))
```

### Cuckoo Filter (Python)
```python
# 매 cuckoo-filter package
from cuckoo.filter import CuckooFilter

cf = CuckooFilter(capacity=1_000_000, fingerprint_size=8)
cf.insert('user:123')
print(cf.contains('user:123'))  # True
cf.delete('user:123')
print(cf.contains('user:123'))  # False
```

### Xor Filter (Rust binding)
```python
# 매 xorfilter package
import xorfilter
keys = [hash(f'user:{i}') for i in range(1_000_000)]
xf = xorfilter.Xor8(keys)
print(xf.contains(hash('user:42')))  # True
print(xf.contains(hash('user:9999999')))  # 매 maybe (false positive 가능)
```

### Sizing calculator
```python
import math

def bloom_size(n, fpr):
    """매 optimal m, k 의 return."""
    m = -n * math.log(fpr) / (math.log(2) ** 2)
    k = m / n * math.log(2)
    return int(math.ceil(m)), int(math.ceil(k))

m, k = bloom_size(n=1_000_000, fpr=0.01)
# m ≈ 9.6M bits, k ≈ 7
```

### LSM Tree integration (RocksDB)
```python
import rocksdb

opts = rocksdb.Options()
opts.create_if_missing = True
table_options = rocksdb.BlockBasedTableFactory(
    filter_policy=rocksdb.BloomFilterPolicy(10),  # 매 10 bits / key
)
opts.table_factory = table_options
db = rocksdb.DB('mydb', opts)
# 매 disk read 전 의 BF check 자동.
```

## 🤔 결정 기준
| 상황 | Filter |
|---|---|
| Static set | Xor filter (smallest) |
| Dynamic + delete | Counting / Cuckoo |
| Distributed cache | RedisBloom |
| Database index | RocksDB / Cassandra / Postgres |
| Stream dedup | Bloom + TTL |
| Web crawler | Scalable Bloom |
| Cardinality (count) | HyperLogLog (NOT Bloom) |
| Frequency | Count-Min (NOT Bloom) |

**기본값**: 매 immutable + 매 small = Xor. 매 dynamic = Cuckoo. 매 simple = Bloom.

## 🔗 Graph
- 부모: [[Hash-Tables]]
- 변형: [[Cuckoo-Filter]]
- 응용: [[RocksDB]] · [[Cassandra]]
- Adjacent: [[HyperLogLog]] · [[Count-Min-Sketch]] · [[MinHash]] · [[LSM-Tree]]

## 🤖 LLM 활용
**언제**: 매 set membership 의 fast check. 매 cache miss 의 minimize. 매 disk read 의 reduce. 매 dedup.
**언제 X**: 매 false positive 의 X 인 case. 매 cardinality / frequency.

## ❌ 안티패턴
- **Wrong sizing**: 매 over / under-allocate.
- **Same hash family k 개 만**: 매 collision.
- **Bloom 의 deletion**: 매 false negative.
- **Bloom 의 cardinality count 의 사용**: 매 wrong tool.
- **Single bloom 의 grow**: 매 scalable BF 의 use.
- **Server-side hash 의 mismatch**: 매 cross-implementation 의 break.

## 🧪 검증 / 중복
- Verified (Bloom 1970, Cuckoo Filter 2014, Xor Filter 2019).
- 신뢰도 A.
- Related: [[HyperLogLog]] · [[Count-Min-Sketch]] · [[Hash-Tables]] · [[LSM-Tree]] · [[RocksDB]].

## 🕓 Changelog
| 날짜 | 변경 |
|---|---|
| 2026-05-08 | Phase 1 (originally HTTP Filters content — corrected to Bloom Filter data structure) |
| 2026-05-10 | Manual cleanup — algorithm + variant + sizing + 매 Python / Redis / Postgres / RocksDB code |
