---
id: cs-bloom-cuckoo-filter
title: Bloom / Cuckoo Filter — set membership 빠른
category: Coding
status: draft
source_trust_level: B
verification_status: conceptual
created_at: 2026-05-09
updated_at: 2026-05-09
tags: [cs, probabilistic, vibe-coding]
tech_stack: { language: "TS", applicable_to: ["Backend", "CS"] }
applied_in: []
aliases: [Bloom filter, Cuckoo filter, set membership, probabilistic, false positive, no false negative]
---

# Bloom / Cuckoo Filter

> "이 element 가 set 에 있나?" 빠르게. **Bloom = 지원 add only. Cuckoo = add + delete**. False positive 만 (no negative).

## 📖 핵심 개념
- Bit array + N hash function.
- Add: bit set.
- Check: 모든 bit set = "probably in".
- False positive 만, false negative X.

## 💻 코드 패턴

### Bloom filter (bit)
```ts
class BloomFilter {
  private bits: Uint8Array;
  
  constructor(private size: number, private hashes: number) {
    this.bits = new Uint8Array(Math.ceil(size / 8));
  }
  
  private hash(item: string, seed: number): number {
    return murmur3(item, seed) % this.size;
  }
  
  add(item: string) {
    for (let i = 0; i < this.hashes; i++) {
      const idx = this.hash(item, i);
      this.bits[idx >> 3] |= 1 << (idx & 7);
    }
  }
  
  has(item: string): boolean {
    for (let i = 0; i < this.hashes; i++) {
      const idx = this.hash(item, i);
      if (!(this.bits[idx >> 3] & (1 << (idx & 7)))) return false;
    }
    return true;  // probably in
  }
}

const bf = new BloomFilter(10000, 7);
bf.add('alice');
bf.has('alice');  // true (definitely)
bf.has('bob');    // false (definitely) 또는 true (probably)
```

### Size + false positive rate
```
n = expected items.
p = false positive rate (e.g. 0.01 = 1%).

m (bit) = -n * ln(p) / (ln 2)^2
k (hash) = m / n * ln 2

n = 10000, p = 0.01:
m ≈ 96000 bit (12 KB).
k ≈ 7 hash.
```

→ 1 KB = 1000 item @ 1% false positive.

### Use case: cache
```ts
// "이 user 가 가입 했나?" 빠른 check.
// Cache lookup 전에 bloom filter.

if (!bf.has(userId)) {
  return null;  // definitely not exist (skip DB).
}

// Probably exist → check DB.
const user = await db.users.findOne({ id: userId });
```

→ DB query 줄임.

### Use case: web crawler
```ts
// URL 가 이미 visited?
const seen = new BloomFilter(10_000_000, 7);

if (!seen.has(url)) {
  seen.add(url);
  await crawl(url);
}
```

→ Memory ↓ vs Set.

### Use case: malware DB
```ts
// 1B 의 malware hash.
// 1 GB bloom filter.
// 매 file → "probably malware?".
```

→ Antivirus / Chrome safe browsing.

### Distributed Bloom
```
N node 의 bloom filter.
- Union: bit 별 OR.
- Intersection: AND.

→ Cross-node deduplication.
```

### Counting Bloom
```
Bit → counter.
Add: counter++.
Remove: counter--.

→ Delete 가능. Memory N x.
```

### Cuckoo filter (modern)
```
Bloom 의 단점:
- Delete 안 됨.
- False positive rate 가 fixed.

Cuckoo:
- Delete OK.
- 비슷한 size + false positive.
- 더 좋은 cache locality.
```

```ts
class CuckooFilter {
  // 2 hash → 2 bucket.
  // Bucket 가 fingerprint (8 bit) store.
  // Insert 시 collision = 다른 element 'kick out'.
}
```

→ Bloom 보다 modern.

### Counting Cuckoo
```
Bucket 가 multiset (count).
→ True deduplication.
```

### Quotient filter (또 다른)
```
Hash 의 quotient + remainder.
- Sequential access 친화.
- Bloom 보다 30% 작은 (specific case).
```

### Redis bloom (RedisBloom)
```bash
BF.RESERVE myfilter 0.01 10000
BF.ADD myfilter alice
BF.EXISTS myfilter alice
# (integer) 1
```

```bash
CF.RESERVE myfilter 10000   # cuckoo
CF.ADD myfilter alice
CF.EXISTS myfilter alice
CF.DEL myfilter alice
```

→ Production 친화.

### HyperLogLog (다른 family)
```
Bloom: "이 element 가 in?".
HLL: "set 의 cardinality?" (count distinct).

→ 다른 problem.
```

→ [[CS_Probabilistic_Data_Structures]].

### Count-Min Sketch
```
"매 element 의 frequency?".
- Top-K element 추정.
- Heavy hitter detect.
```

### T-Digest / KLL (quantile)
```
"p99 latency 의 추정?".
- Streaming quantile.
```

→ 매 구조 가 다른 problem.

### Bloom 의 false positive 의 cost
```
1% false positive:
- 100 query → 1 가 잘못 'true' → DB query (cache miss).
- 100 false positive → 1 가 진짜 cache miss.

→ Total = 101 query (1% extra). Acceptable.
```

### 함정
```
- Bloom 의 false positive 무시: 잘못된 logic.
- Hash function 가 안 좋음: collision 폭발.
- Size 가 너무 작음: 모든 거 'probably in'.
- Count 안 함: bloom 가 size grows X.
- Delete 가 필요: counting / cuckoo.
```

### CDN (CloudFront / Cloudflare)
```
Edge cache 가 bloom filter:
- "이 URL 가 origin 에 있나?".
- Cache miss 가 빠름.

→ Internal optimization.
```

### Database (Cassandra)
```
Cassandra 의 SSTable 별 bloom filter.
- "이 row 가 SSTable 에 있나?".
- Disk read 줄임.
```

### Postgres
```sql
-- pg_bloom (extension)
CREATE EXTENSION bloom;
CREATE INDEX ON users USING bloom (email, name);

-- 매 column hash → bit.
```

→ Multi-column query 가 빠름.

### Browser (Safe Browsing)
```
Google 의 1M+ malicious URL.
- Bloom filter (1 MB) 가 client 에 download.
- Match → 정확 check (server).

→ Client-side privacy + 빠름.
```

### LSM tree 와 함께
```
LSM (RocksDB / LevelDB):
- 매 SSTable 가 bloom filter.
- Read 가 매 SSTable check → bloom 가 미리 skip.

→ I/O ↓.
```

### Production library
```
- redis bloom (RedisBloom)
- guava (Java)
- bloomfilter-rb (Ruby)
- bloom-filters (npm)
- pyprobables (Python)
```

### Python
```python
from pybloom_live import BloomFilter

bf = BloomFilter(capacity=10000, error_rate=0.01)
bf.add('alice')
print('alice' in bf)  # True
```

### Bit budget vs accuracy
```
100k item, 1 KB / 1k item:
- 1% FPR: 12 KB.
- 0.1% FPR: 18 KB.
- 0.01% FPR: 24 KB.

→ Linear improvement.
```

### Bloom 의 수학 (quick)
```
m bit, k hash, n inserted.
False positive rate ≈ (1 - e^(-kn/m))^k.
Optimal k ≈ (m/n) ln 2.
```

### When use?
```
✓ 큰 set membership (M+ items).
✓ Memory tight.
✓ Approximate OK.
✓ Read 가 비싼 (DB / disk / network).

✗ Exact answer 필요.
✗ 작은 set (<10k).
```

### Real-world
- **Akamai / CDN**: cache filtering.
- **Cassandra / RocksDB**: SSTable filter.
- **Bitcoin SPV**: transaction filter.
- **Chrome Safe Browsing**: URL.
- **Medium**: deduplication.

## 🤔 의사결정 기준
| 작업 | 추천 |
|---|---|
| Set membership | Bloom |
| Add + delete | Cuckoo / Counting Bloom |
| Cardinality | HLL |
| Frequency | Count-Min Sketch |
| Quantile | T-Digest / KLL |
| Random sample | Reservoir |
| Redis | RedisBloom |

## ❌ 안티패턴
- **Bloom 만 + 정확 가정**: false positive.
- **Bloom delete**: 안 됨 — Cuckoo.
- **Size 가짜 작음**: 'probably in' 모두.
- **Bad hash**: collision.
- **Bloom 만 모든 query**: cache 가 답.
- **Static size + grow**: capacity 폭발.

## 🤖 LLM 활용 힌트
- Bloom = bit + hash. False positive only.
- Cuckoo = modern alternative (delete OK).
- Cassandra / RocksDB / Chrome 가 production user.
- 1 KB = ~1000 item @ 1% FPR.

## 🔗 관련 문서
- [[CS_Bloom_Filter]]
- [[CS_Probabilistic_Data_Structures]]
- [[CS_Reservoir_Sampling]]
