View

Bloom Filter로 DB 호출을 99% 차단해보았다 - set·dict·SQLite와 메모리 58MB→1.2MB 직접 비교

DevNinja 2026. 5. 5. 19:19

728x90

if user_id in user_ids 한 줄을 쓰려고 set에 100만 건을 올렸다가 메모리 60MB 가까이 날린 적이 있는가? 아니면 캐시 미스 때마다 DB로 가서 "없음" 답만 받아오는 네거티브 캐시 페널티 때문에 골치 아팠던 적은? 블룸 필터(Bloom Filter)는 이런 상황에서 메모리 1MB 남짓으로 DB 호출의 99%를 잘라내는 확률적 자료구조이다. 다만 인터넷에 떠도는 글들은 대부분 "1% false positive로 설정한다" 한 줄짜리 튜토리얼이거나, 위키백과식 원리 설명에 그치고 있어서 실제로 얼마나 이득인지 감이 잡히지 않는다.

각설하고, 직접 100만 사용자 ID 기준으로 set·dict·SQLite(:memory: PK 인덱스)·Bloom Filter 4종을 같은 조건에 박아놓고 빌드 시간, RSS 메모리, hit/miss 지연(p50·p99), FPR 이론값 vs 실측값, DB 차단량까지 모두 측정했다. python:3.12-slim 컨테이너에서 32.6초 만에 종료되었고 결과는 PASS이다. 이 글은 그 raw 데이터를 차트와 함께 풀어놓고, 언제 블룸 필터가 답이고 언제 그냥 set을 쓰는 편이 나은지 정리한 결과이다.

블룸 필터가 무엇이길래 모두 캐시 앞단에 깔자고 하는가

출처: System Design (131KB)

한 줄 정의는 "있을 수도 있음 / 확실히 없음" 두 답만 한다

블룸 필터는 1970년 Burton H. Bloom이 논문 "Space/Time Trade-offs in Hash Coding with Allowable Errors"에서 제안한 확률적 자료구조이다. 핵심은 두 가지 답만 한다는 점이다:

있을 수도 있음 (probably present) — false positive 가능성이 있다
확실히 없음 (definitely not present) — 100% 신뢰 가능하다

False positive(오탐, 없는데 있다고 답함)는 발생할 수 있지만 false negative(있는데 없다고 답함)는 절대 발생하지 않는다. 이것이 캐시 앞단 가드로 쓰기 좋은 이유이다. "없다"는 답은 무조건 신뢰하고 DB 호출을 스킵하면 되기 때문이다.

비트 배열 + k개 해시가 동작 방식의 전부이다

내부 구조는 단순하다:

크기 m의 비트 배열을 0으로 초기화한다
키를 추가할 때 k개의 해시 함수로 인덱스 k개를 뽑아 해당 비트들을 1로 세팅한다
키를 조회할 때 같은 k개 해시를 돌려 모두 1이면 "있을 수도 있음", 하나라도 0이면 "확실히 없음"으로 판정한다

해시 충돌 때문에 다른 키들이 같은 비트를 1로 세팅했을 수 있어 false positive가 생기는 것이다. 다만 false negative는 불가능하다 — 한 번 1로 세팅된 비트는 절대 0으로 돌아가지 않기 때문이다.

어디에 사용하는가

이미 거의 모든 대규모 시스템에 깔려 있다:

Cassandra SSTable — 디스크 IO를 일으키지 않고 "이 SSTable에 키가 있는가?"를 빠르게 체크한다
Google BigTable / LevelDB / RocksDB — LSM 트리 read amplification을 줄인다
Chrome Safe Browsing — 위험한 URL 리스트를 클라이언트에서 1차 필터링한다
Medium 추천 dedup — 이미 읽은 글을 다시 추천하지 않으려고 사용한다
PostgreSQL bloom 인덱스 — 다중 컬럼 동치 조건을 가속한다

다만 한국어권에서는 위 사례를 "어디서 들어봤다" 수준으로만 인용할 뿐, 직접 돌려서 "내 워크로드에서 얼마나 이득인지" 보여주는 글이 없어 이번 실험을 돌리게 되었다.

Bloom Filter 사이즈는 어떻게 잡는가? 공식부터 보자

출처: javamex.com

기본 공식은 두 줄이다

목표 false positive rate를 $p$, 키 개수를 $n$이라 두면:

m = -n * ln(p) / (ln 2)^2     # 비트 배열 크기 (비트)
k = (m / n) * ln 2            # 해시 함수 개수

이것이 전부이다. 키 개수와 허용 오탐률만 정하면 비트 배열 크기와 해시 개수가 자동으로 결정된다.

100만 키, FPR 1%를 대입하면

$n = 1{,}000{,}000$
$p = 0.01$
$m \approx 9{,}585{,}059$ 비트 ≈ 1.14 MiB ≈ 1,170 KB
$k \approx 7$

즉 키 한 건당 약 9.6비트를 쓰고 7번 해시한다. 100만 키를 1.2MB 안에 모두 욱여넣는 것이 가능한 이유이다.

"7번 해싱하는데 dict보다 빠를 수 있는가?" — 솔직히 아니다

이 부분이 자주 오해되는데, 블룸 필터가 dict보다 in-memory 조회는 빠르지 않다. dict는 한 번만 해시하면 되지만 블룸은 7번 해싱과 7번 비트 체크를 수행한다. 실험에서도 dict p50 hit 0.4μs vs Bloom p50 hit 3.1μs로 약 8배 느렸다.

블룸 필터의 진짜 이점은 메모리와 DB 왕복 차단이다. 7번 해시해서 3μs를 쓰는 것 vs DB로 가서 5ms를 날리는 것을 비교하면 1,500배 이득이다. 핫 패스 in-memory 조회만 보면 set/dict 승, 캐시·DB 앞단이면 Bloom 승이다.

실험 설계 - 100만 사용자 ID, 4종 자료구조를 동일 조건으로 비교한다

런타임과 리소스를 모두 공개한다

항목	값
런타임	python:3.12-slim
리소스	메모리 1024MB, CPU 2.0, 타임아웃 480s
네트워크	allow
결과	PASS, exit 0, 32.60s
데이터셋	정수 사용자 ID 100만 건
조회 횟수	hit 1만 + miss 1만

비교 대상 4종 + Bloom sweep 4단계

비교 대상은 다음과 같다:

Python set — 정확한 멤버십, 빠른 조회
Python dict — set과 비슷하나 value 슬롯이 들어가서 더 크다
SQLite(:memory: PK 인덱스) — 디스크를 쓰지 않는 메모리 모드, id 컬럼에 PRIMARY KEY 적용
Bloom Filter (목표 FPR 1%) — 비트 배열 + 7개 해시

여기에 Bloom Filter는 0.1% / 1% / 5% / 10% 4단계로 sweep을 돌려 메모리-정확도 트레이드오프 곡선까지 추출했다.

측정 항목

빌드 시간 (wall-clock 초)
RSS 메모리 증가량 (MB)
hit 1만 건 조회 p50 / p99 지연 (μs)
miss 1만 건 조회 p50 / p99 지연 (μs)
Bloom Filter false positive 건수 + 실측 FPR
DB 왕복 차단량 (= 1만 - false positive)

stdout 마지막에 깔끔하게 정리되어 출력된다:

name             build_s    mem_MB  p50_hit_us  p99_hit_us  p50_mis_us  p99_mis_us     FPs
set                0.154     32.44        0.30        1.00        0.20        0.80       0
dict               0.281     57.62        0.40        1.30        0.30        1.00       0
sqlite             1.179     20.00        2.30        4.80        1.50        1.70       0
bloom_1pct         3.352      0.00        3.10        6.30        1.70        3.40     106

메모리 결과: dict 58MB → Bloom 1.2MB로 약 50배 줄였다

차트를 먼저 박는다.

100만 정수 ID 기준 RSS 증가량은 다음과 같다:

자료구조	메모리	빌드 시간
set	32.44 MB	0.154초
dict	57.62 MB	0.281초
SQLite (:memory: PK)	20.00 MB	1.179초
Bloom Filter (FPR 1%)	1.14 MB	3.352초

브리프에는 "80MB → 1.2MB"라고 적혀 있었으나 실제 측정은 dict 기준 58MB이다. 그래도 Bloom 대비 약 50배 차이라 인상은 그대로이다. 이것이 의미하는 바는, 운영 메모리 1GB짜리 컨테이너 워커 기준 dict는 약 5.7%를 차지하지만 Bloom은 0.1%로 떨어진다는 점이다. 워커 100개를 띄우면 5.6GB → 120MB로 딱 그만큼 메모리 여유가 생기는 것이다.

⚠️ 표에 Bloom_1pct RSS가 0.00 MB로 찍힌 이유는 다음과 같다. 비트 배열 자체는 1,198,133 바이트 (약 1.14 MiB)인데 인터프리터가 이미 잡아놓은 페이지 안에 흡수되어 RSS 측정 단위(MB) 미만으로 잡혔기 때문이다. result.json의 extra.size_bytes 값이 실제 자료구조 크기이다.

빌드 시간은 Bloom이 가장 느리다 (3.35초 vs set 0.15초). 키 한 건당 7번 해싱하니 당연한 결과이다. 한 번 빌드해서 오래 쓰는 시나리오라면 무시해도 되는 비용이고, 매 요청마다 빌드해야 한다면 Bloom을 쓰지 않는 편이 맞다.

지연 시간 결과: Bloom이 set보다 8배 느린데도 캐시 앞단으로는 압승이다

다음 차트는 hit/miss 1만 건씩 조회한 p50·p99 마이크로초 분포이다.

자료구조	p50 hit	p99 hit	p50 miss	p99 miss
set	0.30μs	1.00μs	0.20μs	0.80μs
dict	0.40μs	1.30μs	0.30μs	1.00μs
SQLite	2.30μs	4.80μs	1.50μs	1.70μs
Bloom (FPR 1%)	3.10μs	6.30μs	1.70μs	3.40μs

set/dict가 가장 빠르다. nanosecond 단위에 거의 들어간다. SQLite는 메모리 모드라도 PK 인덱스 lookup + Python <-> C 경계 비용으로 μs 단위가 된다. Bloom은 7번 해시 비용 때문에 set 대비 약 8배 느리다.

여기서 자주 나오는 잘못된 결론이 "그러면 Bloom을 쓰지 않는 편이 빠르다"인데, 블룸 필터의 비교 대상은 set이 아니라 DB 왕복이다. 같은 워크로드에서:

in-memory set 조회: ~0.3μs
in-memory Bloom 조회: ~3μs
DB(Postgres/MySQL) 단순 PK 조회: 1~10ms = 1,000~10,000μs
네트워크 캐시(Redis) 조회: 100~500μs

미존재 키를 Bloom이 차단하여 DB로 가지 않게 만들면 1만 μs → 3μs로 약 3,000배 빨라진다. 블룸 필터는 in-memory 자료구조 사이의 경쟁이 아니라 "in-memory vs network/disk" 경쟁에서 의미가 있다.

블룸 필터 FPR 이론 vs 실측, DB 호출 99% 차단까지 검증한다

FPR 4단계 sweep 결과

목표 FPR 0.1% / 1% / 5% / 10% 4단계로 비트 배열 크기를 다르게 잡고 돌렸다. 공식이 실제로 맞는지 확인하는 것이 목적이다.

목표 FPR	m(비트)	k(해시)	크기(KB)	이론 FPR	실측 FPR	DB 차단(/10,000)	차단율
0.10%	14,377,588	10	1,755.1	0.100%	0.090%	9,991	99.91%
1.00%	9,585,059	7	1,170.1	1.004%	1.060%	9,894	98.94%
5.00%	6,235,225	4	761.1	5.027%	5.040%	9,496	94.96%
10.00%	4,792,530	3	585.0	10.071%	10.240%	8,976	89.76%

이론 FPR과 실측 FPR이 거의 일치한다. 공식대로 사이즈를 잡으면 예측대로 동작한다는 뜻이라 운영 관점에서 매우 중요하다. SLA를 잡고 가도 된다.

DB 호출 차단량 시각화

미존재 키 1만 건을 조회했을 때 Bloom이 "확실히 없음" 답을 하여 DB 호출 자체를 일으키지 않게 만든 건수이다.

FPR 1% 설정으로 메모리 1.17MB만 쓰고도 1만 건 미존재 조회 중 9,894건을 차단하여 DB 호출을 98.94% 잘라낸다. 0.1% 설정이면 9,991건을 차단하여 99.91%까지 올라가고, 메모리는 1.76MB 정도이다. 트레이드오프 곡선이 거의 정확하게 공식을 따라간다.

트레이드오프 정리: 메모리 vs 차단율

차단율 99.9%를 원하면: 메모리 ~1.8MB, 해시 10번
차단율 99%를 원하면: 메모리 ~1.2MB, 해시 7번
차단율 95%를 원하면: 메모리 ~750KB, 해시 4번
차단율 90%를 원하면: 메모리 ~600KB, 해시 3번

또한 sweep마다 빌드 시간과 hit p99도 함께 측정했는데, 해시 개수 k가 줄수록(10→3) 둘 다 단조 감소한다. k=10일 때 빌드 4.5초·p99 hit 15μs, k=3일 때 빌드 2.1초·p99 hit 4.1μs이다. 키 한 건당 k번 해시하니 그저 비례 관계이다. 본인 워크로드에서 SLA가 빡빡하다면 FPR 5% 정도까지 풀어 hit 지연을 줄이는 것이 합리적인 선택일 수 있다.

그러면 언제 Bloom을 쓰고 언제 set을 쓰면 되는가?

이제 케이스를 분류한다. 실험 데이터를 그대로 보고 결정 기준을 정리했다.

set/dict가 답인 경우

정확한 멤버십이 절대적으로 필요하다 (false positive 0)
메모리에 여유가 있다 (수십 MB를 써도 무방)
키 개수가 ~수십만 ~ 백만 단위이다
핫 패스 in-memory 조회이다 (μs도 아까운 상황)

SQLite/RDB 인덱스가 답인 경우

정확성과 영구 저장 둘 다 필요하다
키마다 부가 정보(value)도 함께 보관해야 한다
메모리 모드 SQLite는 set보다 느리고 무거우니 굳이 쓰지 않는다

Bloom Filter가 답인 경우

"없음" 답만 빠르게 받으면 되는 시나리오이다 (멤버십 게이트)
메모리가 빡빡하다 (워커 수백 개 / 엣지 노드 / 모바일 클라이언트)
키 개수가 수백만 ~ 수억 단위이다
캐시·DB 앞단의 네거티브 캐시 가드이다
가끔 false positive가 떠도 "한 번 더 DB로 확인" 정도는 허용된다

안티 패턴: "있음" 답을 그대로 신뢰하기

블룸 필터에서 가장 자주 나오는 사고가 이것이다. "있음" 답은 false positive 가능성이 있어 100% 신뢰할 수 없다. 반드시 다음 단계가 있어야 한다:

key in bloom?
├─ 확실히 없음 → 즉시 "없음" 응답 (DB 안 감)
└─ 있을 수도 있음 → 캐시/DB로 가서 실제 확인

이 구조로 짜면 "없는 키"는 99% 차단되고 "있는 키"는 항상 정확하게 처리된다. 반대로 "있음" 답을 그대로 응답으로 쓰면 1% 확률로 잘못된 데이터가 내려가는 사고가 터진다.

Python 라이브러리 추천

직접 비트 배열을 짜는 것도 어렵지는 않으나, 검증된 라이브러리를 쓰는 편이 낫다:

pybloom-live — 순수 파이썬 구현, scalable bloom filter도 지원한다
pybloomfiltermmap3 — C 구현, mmap 기반이라 더 빠르다
redisbloom — Redis 모듈, 분산 환경에서 공유 가능하다

요청량이 많다면 RedisBloom으로 가서 워커 간 필터를 공유하는 패턴이 정석이다.

블룸 필터 실험 데이터 정리: 캐시 앞단에 깔면 거의 무조건 이득이다

직접 돌려본 데이터로 정리하면 다음과 같다:

메모리: dict 58MB → Bloom 1.2MB, 약 50배 절감
차단율: FPR 1% 설정으로 미존재 키 98.94% 차단, 0.1% 설정이면 99.91%
이론 vs 실측: 공식대로 잡으면 거의 정확하게 일치한다 → SLA를 잡고 가도 된다
지연: in-memory에서 set 대비 8배 느리지만 DB 왕복 대비 1,000배 이상 빠르다
트레이드오프: 메모리를 600KB까지 줄이면 차단율은 90%로 떨어진다, 본인 워크로드에 맞춰 선택한다

캐시 앞단에 블룸 필터 한 줄을 깔면 백엔드 DB 호출의 90~99%가 잘린다. 메모리는 MB 단위로 끝나고, 코드 한 줄짜리 트레이드오프이다. 핫 패스 in-memory 자료구조 자리에는 쓰지 마라 — 그곳은 set이 답이다. 다만 미존재 키 차단이 목적이라면 블룸 필터가 거의 무조건 이득이다.

result.json과 차트 4종을 모두 첨부했으니 본인 워크로드에서 키 개수와 허용 FPR을 바꿔 그대로 sweep을 돌려보면 된다. 공식 신뢰도까지 검증한 1차 데이터라 의사결정 자료로 그대로 활용해도 무방하다.