# 블룸 필터 — "없다"고 싸게 확신하기 위한 확률적 자료구조

> **한 줄 요지:** 블룸 필터는 원소를 저장하지 않고 멤버십만 판정하는 확률적 자료구조로, false negative는 절대 없고 false positive만 허용한다. "없음을 싸게 확신"해서 비싼 조회(디스크·네트워크)를 건너뛰는 게 존재 이유다.

**메타** — 백엔드 > CS 기초 > 확률적 자료구조: 블룸 필터 · 2026-07-14 · 깊이: 실무
**페르소나** — 정우(LSM 스토리지 시니어) · 지민(정합성 신봉 DBA·회의론) · 현수(주니어 질문자) · 세영(신형 자료구조 옹호)

---

## 1. 배경 — 왜 이 논의가 필요한가

대규모 시스템에서 "이 원소가 집합에 있나?"는 초당 수십만 번 던지는 질문이다.

- **캐시 관통(cache penetration):** 캐시에 없는 키를 반복 조회하면 캐시를 뚫고 DB로 직행한다.
- **LSM 스토리지(RocksDB/Cassandra):** 키 하나 찾으려고 여러 SSTable을 디스크에서 뒤진다.
- **크롤러:** "이 URL 방문했나?"를 수십억 번 묻는다.

이걸 **정확하게** 답하려면 전체 집합을 메모리에 들고 있어야 하는데, 그게 불가능한 규모가 존재한다. 그런데 많은 경우 진짜 필요한 답은 "**확실히 없음**"이다. 없음을 싸게 확신하면 비싼 조회 자체를 건너뛴다 — 블룸 필터가 특화된 지점.

## 2. 동작 원리 (선행 개념)

- **비트 배열** m개 + 서로 독립인 **해시 함수 k개**.
- **삽입:** 원소를 k개 해시에 통과 → 나온 k개 위치의 비트를 1로.
- **조회:** 같은 k개 위치가 **모두 1인지** 확인.
  - 하나라도 0 → **확실히 없음** (false negative 불가)
  - 전부 1 → **아마 있음** (false positive 가능)
- 답은 항상 `없음(확정)` 또는 `아마 있음` 둘 중 하나. 이 **비대칭**이 핵심.

## 3. 쟁점 요약

- HashSet 대신 왜? → **규모**. 블룸은 원소를 저장하지 않아 원소당 수 비트로 끝난다(문자열 길이 무관).
- 오탐을 어떻게 감당? → **폴백이 있어야** 쓴다. "있음"이 뜨면 진짜 소스로 재확인. 블룸은 게이트키퍼지 최종 심판이 아니다.
- 오탐률은 어떻게 정하나? → **설계값.** m, n, k로 결정. 원하는 오탐률을 정하고 역산.
- k는 많을수록 좋은가? → **아니다.** 최적 k = (m/n)·ln2. 넘으면 비트가 빨리 차 오탐이 다시 오른다.
- 삭제/확장은? → 원판은 **삭제 불가·리사이즈 불가.** → Counting/Cuckoo/Scalable 변형.
- 언제 쓰면 안 되나? → 데이터 작을 때 / 오탐이 곧 사고이고 폴백 없을 때 / 카운트·열거가 목적일 때.

## 4. 입장별 정리

- **정우 (스토리지):** 규모의 문제다. 10억 URL을 1% 오탐으로 담아도 원소당 9.6비트(≈1.2GB). RocksDB가 SSTable마다 블룸을 붙이는 이유 = 없는 키 조회 시 디스크 I/O를 통째로 스킵. SSTable은 불변이라 삭제 문제가 애초에 안 생긴다("도구가 놓이는 자리가 맞아야 한다").
- **지민 (DBA·회의론):** 블룸이 성립하는 건 **오탐 시 안전 폴백이 있을 때뿐.** 돈·권한 판정에 단독 사용 금지. 사이징은 n을 미리 안다는 전제인데 예측이 빗나가 포화되면 오탐 폭발. 게다가 **삭제 불가.** 단순·예측가능성은 원판의 장점이기도.
- **현수 (질문자):** "HashSet이 정확한데 왜?"로 전제를 드러내고, "없음만 믿고 있음은 재확인하는 구조"로 핵심을 정리. 마지막에 "쓰면 안 되는 경우"를 끌어냄.
- **세영 (신형 자료구조):** 삭제 필요 → Counting Bloom/Cuckoo, 크기 모름 → Scalable Bloom. 단, Counting은 메모리 3~4배, Cuckoo는 포화 시 insert 실패 — 공짜 개선은 없음(지민도 인정).

## 5. 트레이드오프 표

| 항목 | 얻는 것 | 잃는 것 |
|------|---------|---------|
| 공간 | 원소당 수 비트, 원본 저장 안 함(길이 무관) | 원소 복구·열거 불가 |
| 정확성 | false negative 절대 없음("없음"=확정) | false positive 존재("있음"=확률) |
| 속도 | 조회·삽입 O(k), 데이터 크기 무관 | 모든 조회가 항상 k번 해시 |
| 수정 | 삽입 자유 | 삭제 불가(원판) → Counting/Cuckoo |
| 확장 | 크기 알면 예측 가능 | 포화 시 오탐 폭발, 리사이즈 불가 → Scalable |
| 운영 | 단순·예측가능·병합 가능(OR) | n·오탐률 목표를 미리 정해야 함 |

**핵심 공식**
- 오탐률: `P = (1 − e^(−kn/m))^k`
- 최적 해시 개수: `k = (m/n)·ln2`
- 목표 오탐률 p에 필요한 비트: `m = −n·ln p / (ln2)²` (원소당 약 `−1.44·log2(p)` 비트, 1%면 ≈9.6비트)

## 6. 결론 / 의사결정 가이드

- **원판 블룸 필터** — 데이터 크고, "없음"으로 비싼 조회를 걸러내는 게 목적, 오탐은 폴백으로 검증, 삭제 불필요. (LSM SSTable, 캐시 관통 방어, 크롤러 dedup)
- **삭제 필요** → Counting Bloom(메모리↑) 또는 **Cuckoo Filter**(삭제+낮은 오탐 효율↑, 포화 시 insert 실패).
- **개수 모름** → **Scalable Bloom Filter** 또는 주기적 재구축.
- **오탐이 곧 사고이고 폴백 없음** → 단독 사용 금지, 게이트로만.
- **데이터 작음** → HashSet/인덱스. 블룸은 규모의 도구.
- **카운트·유일값 개수 목적** → 블룸이 아니라 **HyperLogLog**(멤버십이 아닌 카디널리티 문제).

## 7. 추가 학습 키워드

Counting Bloom Filter · Cuckoo Filter · Scalable Bloom Filter · Quotient Filter · HyperLogLog · Cache Penetration · LSM-Tree/SSTable · double hashing으로 k개 해시 생성