쿠팡·네이버급 트래픽에서 "이 원소가 집합에 있나?"는 초당 수십만 번 던지는 질문이다.
상품 캐시에 없는 키를 계속 조회당하면 그 요청은 캐시를 뚫고 DB로 직행한다(캐시 관통, cache penetration). RocksDB 같은 LSM 스토리지는 키 하나 찾으려고 디스크의 여러 SSTable을 뒤진다. 웹 크롤러는 "이 URL 방문했나?"를 수십억 번 묻는다. 이 질문을 정확하게 답하려면 전체 집합을 메모리에 들고 있어야 하는데 — 그게 불가능한 규모가 존재한다.
비트 배열 하나 + 서로 다른 해시 함수 k개. 원소를 넣으면 k개 위치를 1로 켠다. 조회할 땐 그 위치가 모두 1인지 본다.
파란 테두리 = 조회 시 확인한 비트(모두 1). 빨간 테두리 = 0이라서 "확실히 없음"으로 판정된 비트. 넣지 않았는데 "있을 수도 있음"이 뜨면 그게 false positive다 — 다른 원소들이 우연히 같은 비트를 켜둔 것.
"없음(확정)" 또는 "아마 있음" 둘 중 하나다.
스토리지 실무자 · 정합성 신봉 DBA · 주니어 질문자 · 신형 자료구조파가 붙었다.
● 정우 — RocksDB/LSM 스토리지 다뤄온 시니어 (단정형)
● 지민 — 정합성 신봉 DBA·회의론자 (신중형)
● 현수 — 주니어, 전제를 캐묻는 질문자 (질문형)
● 세영 — Cuckoo/Scalable 등 신형 자료구조 옹호 (도전형)
솔직히 이해가 안 돼요. 그냥 HashSet에 다 넣어두면 100% 정확하잖아요. 왜 굳이 틀릴 수도 있는 걸 써요?
규모 때문이야. URL 10억 개를 HashSet에 넣으면 문자열 원본 + 포인터 + 버킷 오버헤드로 수십 GB 간다. 블룸 필터는 원소를 저장하지 않아. 비트만 켜지. 10억 개를 1% 오탐으로 담아도 약 1.2GB — 원소당 딱 9.6비트야. 문자열 길이랑 무관하게.
RocksDB가 왜 SSTable마다 블룸 필터를 붙이겠어? 없는 키를 조회하면 원래는 여러 레벨의 파일을 디스크에서 다 뒤져야 해. 블룸이 "이 파일엔 확실히 없음"이라고 잘라주면 그 디스크 I/O를 통째로 건너뛴다. 이게 읽기 성능의 핵심이야.
맞는 말인데, 조건이 붙어. 그 구조가 성립하는 건 false positive가 나도 안전하게 폴백할 곳이 있을 때뿐이야. RocksDB는 블룸이 "있을 수도"라고 하면 실제 파일을 확인하니까 오탐은 그냥 "헛수고 한 번"으로 끝나. 정확성은 뒤의 진짜 데이터가 보장하지.
근데 폴백이 없거나, 오탐이 곧 사고인 도메인이면? "이 사용자 이미 쿠폰 받았나?"를 블룸으로만 판정해서 false positive가 나면, 받을 자격 있는 사람을 막아버려. 돈·권한이 걸린 판정에 블룸을 단독으로 쓰면 안 돼. 블룸은 "게이트키퍼"지 "최종 심판"이 아니야.
아 그럼 항상 "없음"만 믿고, "있음"이 뜨면 진짜인지 한 번 더 확인하는 구조군요. 근데 오탐률은 어떻게 정해요? 그냥 운인가요?
운 아니야, 설계값이야. 비트 수 m, 넣을 원소 수 n, 해시 개수 k 세 개로 오탐률이 결정돼. 원하는 오탐률을 먼저 정하고 역산해서 m과 k를 뽑는 거야. 아래 계산기로 직접 만져봐 — k를 너무 늘리면 오히려 비트가 빨리 차서 오탐이 다시 올라가는 지점이 보일 거야.
바로 그 n이 함정이야. 사이징은 "넣을 원소 수"를 미리 안다는 전제로 해. 실제로 트래픽 예측이 빗나가서 계획보다 3배 넣으면? 비트가 포화되고 오탐률이 설계값을 훌쩍 넘겨. 그리고 블룸 필터는 원소를 뺄 수가 없어. 한 번 켠 비트는 다른 원소도 쓰고 있을지 몰라 함부로 못 끈다.
그래서 요즘은 대안이 있어. 삭제가 필요하면 Counting Bloom Filter(비트 대신 카운터) 아니면 Cuckoo Filter를 써. Cuckoo는 삭제도 되고, 낮은 오탐률 구간에선 공간 효율도 블룸보다 나아. 크기를 모르면 Scalable Bloom Filter가 포화되면 필터를 계층으로 덧붙여.
그건 인정. 근데 Counting Bloom은 카운터 때문에 메모리 3~4배 먹고, Cuckoo는 너무 꽉 채우면 insert가 실패해서 리사이즈가 필요해. 공짜 개선은 없어. "삭제 안 되고 리사이즈 안 되는" 원판 블룸이 가장 단순하고 예측 가능하다는 것도 장점이야. 버릴 수 있는 필터라면 그냥 새로 만드는 게 제일 깔끔할 때도 많고.
실제로 그렇게 써. LSM에서 SSTable은 불변(immutable)이라 삭제가 필요 없어 — 컴팩션 때 파일이 통째로 새로 써지니까 블룸도 새로 만들면 돼. 삭제 문제가 애초에 안 생기는 구조에 얹은 거지. 도구가 아니라 도구가 놓이는 자리가 맞아야 한다는 얘기야.
정리되네요. "없음을 싸게 확신 + 오탐은 폴백으로 흡수 + 삭제 필요 없는 자리"면 원판 블룸, 삭제가 필요하면 Cuckoo/Counting, 크기를 모르면 Scalable. 근데 반대로 쓰면 안 되는 경우는요?
세 가지. ① 데이터가 작으면 그냥 HashSet이 더 빠르고 정확해 — 블룸은 규모의 도구야. ② 오탐이 곧 사고이고 폴백이 없으면 금지. ③ "정확히 몇 개 있나(카운트)"나 "무엇무엇 들었나(열거)"가 필요하면 블룸은 답을 못 해. 그건 HyperLogLog(개수 추정)나 다른 구조의 영역이야. 블룸은 오직 멤버십, 그것도 한 방향으로만 정확한 멤버십이야.
지민의 지적("사이징이 함정")과 정우의 반론("k를 너무 늘리면 오히려 나빠짐")을 직접 확인해보자.
"계획보다 많이 넣으면?" — 지민이 말한 실패 모드. 고정된 필터에 원소를 계속 부으면 오탐률이 어떻게 폭발하는지 본다.
| 항목 | 블룸 필터가 주는 것 | 대가로 잃는 것 |
|---|---|---|
| 공간 | 원소당 수 비트. 원본 저장 안 함(길이 무관) | 원소 자체는 복구·열거 불가 |
| 정확성 | false negative 절대 없음 ("없음"은 확정) | false positive 존재 ("있음"은 확률) |
| 속도 | 조회·삽입 O(k), 데이터 크기와 무관 | 모든 조회가 항상 k번 해시 계산 |
| 수정 | 삽입은 자유 | 삭제 불가(원판). Counting/Cuckoo 필요 |
| 확장 | 사전에 크기 알면 예측 가능 | 포화 시 오탐 폭발, 리사이즈 안 됨(→Scalable) |
| 운영 | 구현 단순, 예측 가능, 병합 가능(OR) | n·오탐률 목표를 미리 정해야 함 |
PFCOUNT.