안녕하세요. 자바파커입니다.

데이터가 수억 건 있는 저장소에 어떤 키가 존재하는지 확인해야 한다고 생각해 보겠습니다. 매 요청마다 DB나 디스크를 읽으면 정확하지만 비쌉니다. 그렇다고 모든 키를 메모리에 보관하면 메모리가 커집니다.

블룸 필터(Bloom Filter)는 이 문제에 독특한 답을 냅니다.

없다고 판정하면 확실히 없습니다. 있다고 판정하면 실제로는 없을 수 있습니다.

정확한 집합 대신 작은 비트 배열과 여러 해시 함수를 사용하고, 약간의 **False Positive(거짓 양성)**를 허용해 메모리를 크게 아낍니다. 중요한 점은 블룸 필터가 원본 저장소를 대체하는 것이 아니라, 불필요한 조회를 앞에서 걸러내는 필터라는 것입니다.

블룸 필터의 구조

표준 블룸 필터에는 세 가지가 있습니다.

1. m개의 칸을 가진 비트 배열
2. 서로 다른 위치를 만드는 k개의 해시 함수
3. 저장할 원본 키

처음에는 모든 비트가 0입니다.

index  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bit    0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0

apple을 세 해시 함수에 넣은 결과가 1, 6, 12라면 해당 비트를 1로 바꿉니다.

H1(apple) → 1
H2(apple) → 6
H3(apple) → 12

bit    0 1 0 0 0 0 1 0 0 0  0  0  1  0  0  0

여기에 banana → 3, 6, 14를 추가합니다. 6번 비트는 이미 1이므로 그대로 둡니다.

bit    0 1 0 1 0 0 1 0 0 0  0  0  1  0  1  0

블룸 필터는 apple이나 banana라는 원문을 저장하지 않습니다. 어느 키가 어떤 비트를 켰는지도 기억하지 않습니다. 이 특성이 작은 메모리 사용량과 삭제의 어려움을 동시에 만듭니다.

조회: 하나라도 0이면 확실히 없다

kiwi의 해시 결과가 1, 7, 12라고 해보겠습니다.

H1(kiwi) → 1  = 1
H2(kiwi) → 7  = 0
H3(kiwi) → 12 = 1

7번 비트가 0입니다. 삽입된 키라면 세 위치를 모두 1로 만들었어야 하므로 kiwi는 확실히 없습니다.

이때는 실제 DB나 디스크를 읽지 않고 바로 끝낼 수 있습니다.

Bloom Filter: DEFINITELY NOT
Database:     조회 생략

Redis 공식 문서가 블룸 필터를 “존재하지 않는 항목을 확실히 걸러내고, 존재 가능성이 있는 항목만 추가 확인하는 확률적 자료구조”로 설명하는 이유입니다.

False Positive: 모두 1이어도 틀릴 수 있다

이번에는 넣지 않은 mango의 해시 결과가 1, 6, 14라고 하겠습니다.

세 위치는 모두 1입니다. 하지만 이 비트들은 apple과 banana가 각각 켠 것입니다.

Bloom Filter: MAYBE EXISTS
Database:     NOT FOUND
Result:       FALSE POSITIVE

블룸 필터는 “mango가 이 비트를 켰다”는 출처를 저장하지 않으므로 구분할 수 없습니다. 따라서 MAYBE EXISTS는 최종 답이 아니라 실제 저장소를 조회하라는 신호입니다.

표준 블룸 필터에는 다음 비대칭이 있습니다.

단, “False Negative가 없다”는 말은 표준 방식으로 삽입하고 비트를 임의로 지우지 않았을 때 성립합니다. 구현 오류, 동기화 누락, 안전하지 않은 삭제까지 면책하는 표현은 아닙니다.

용량과 오탐률을 먼저 정해야 한다

비트 배열이 많이 찰수록 서로 다른 키가 같은 비트를 공유할 확률이 커지고 False Positive가 늘어납니다. 그래서 운영에서는 자료구조를 만든 뒤 데이터를 무한히 넣는 것이 아니라 다음 두 값을 먼저 정합니다.

• 예상 삽입 개수 n
• 허용할 False Positive 확률 p

필요한 비트 수 m과 적절한 해시 함수 수 k는 다음과 같이 계산할 수 있습니다.

m = -n × ln(p) / (ln 2)²
k = (m / n) × ln 2

키 하나당 필요한 대략적인 비트 수는 다음과 같습니다.

오탐률을 낮추면 메모리와 해시 계산량이 늘어납니다. “낮을수록 좋다”가 아니라 불필요한 원본 조회 비용과 필터 비용을 함께 측정해 정해야 합니다.

Redis에서 사용하는 방법

Redis Bloom 모듈에서는 예상 용량과 오탐률을 명시해 필터를 예약할 수 있습니다.

BF.RESERVE seen:users 0.001 1000000
BF.ADD seen:users user:42
BF.EXISTS seen:users user:42
BF.EXISTS seen:users user:999

위 설정은 100만 개 항목과 0.1% 오탐률을 목표로 합니다.

애플리케이션 코드는 BF.EXISTS 결과를 이렇게 해석해야 합니다.

const maybeExists = await redis.call("BF.EXISTS", "seen:users", userId)

if (!maybeExists) {
  return null // 확실히 없음: DB 조회 생략
}

return database.users.findById(userId) // MAYBE: 실제 저장소 확인

예상 용량을 넘을 수 있다면 Redis의 확장 가능한 필터가 하위 필터를 추가할 수 있지만, 필터 수와 메모리·조회 비용도 함께 늘어납니다. 용량 추정과 관찰을 생략해도 된다는 뜻은 아닙니다.

RocksDB에서는 어디에 효과가 있을까

RocksDB는 SST 파일을 실제로 읽기 전에 “이 파일에 키가 없다는 것을 알 수 있는가?”를 판단하는 데 블룸 필터를 활용합니다.

GET user:42
  ↓
Bloom Filter: 이 SST에는 확실히 없음
  ↓
파일 읽기 생략

이 방식은 특정 키를 찾는 point lookup에서 효과가 큽니다. 반면 범위를 순서대로 읽는 range scan은 많은 키를 실제로 순회해야 하므로 같은 이점을 기대하기 어렵습니다. RocksDB 문서도 블룸 필터를 point lookup 중심의 튜닝 항목으로 설명합니다.

왜 일반 블룸 필터는 삭제가 어려울까

banana를 삭제하면서 6번 비트를 0으로 바꾸면 어떻게 될까요? 6번은 apple도 사용하고 있었습니다. 그러면 실제로 존재하는 apple 조회가 0을 만나 False Negative가 됩니다.

apple  → bit 6 사용
banana → bit 6 사용

banana 삭제 → bit 6을 0으로 변경
apple 조회  → 잘못된 NOT FOUND

삭제가 필요하다면 선택지는 다음과 같습니다.

• Counting Bloom Filter: 비트 대신 작은 카운터를 사용
• Cuckoo Filter: 항목의 fingerprint를 bucket에 저장해 삭제 지원
• 세대 교체: 일정 주기로 새 필터를 만들어 원본에서 재구축

카운터와 fingerprint는 삭제를 가능하게 하지만 메모리와 구현 복잡도가 늘어납니다. 삭제 요구가 없다면 표준 블룸 필터가 더 단순합니다.

실무 적용 체크리스트

1. 원본 저장소를 진실의 원천으로 둔다

블룸 필터의 MAYBE를 실제 존재로 취급하면 안 됩니다. 캐시, 권한, 결제처럼 정확성이 필요한 판단은 반드시 원본에서 확인합니다.

2. 필터 갱신 순서를 설계한다

원본 저장은 실패했는데 필터만 갱신되면 False Positive가 늘어나는 것으로 끝날 수 있습니다. 반대로 원본은 저장됐는데 필터 갱신이 빠지면 False Negative 성격의 운영 장애가 생깁니다. 재시도, 이벤트 기반 동기화, 재구축 절차를 마련해야 합니다.

3. 실제 False Positive 비율을 측정한다

observed_fpr = Bloom이 MAYBE였지만 원본에는 없던 건수
               / Bloom이 MAYBE였던 전체 건수

목표보다 높아지면 용량 초과, 잘못된 파라미터, 키 분포·해시 품질을 확인합니다.

4. 비트 점유율과 삽입 개수를 관찰한다

점유율이 계속 올라가면 오탐도 증가합니다. 현재 필터가 설계한 용량에 근접했는지 대시보드와 알림으로 확인해야 합니다.

5. 복구 가능하게 만든다

블룸 필터는 원본 데이터에서 다시 만들 수 있는 파생 자료구조로 운영하는 편이 안전합니다. 필터 손상이나 버전 변경 시 원본에서 재구축할 수 있어야 합니다.

언제 사용하고 언제 피할까

잘 맞는 경우:

• 존재하지 않는 키 조회가 많고 원본 조회 비용이 비쌀 때
• URL 중복 검사, 크롤링 방문 여부, 캐시 관통 방지
• LSM 기반 저장소의 불필요한 파일 읽기 감소
• 약간의 False Positive는 허용되지만 False Negative는 허용하기 어려울 때

피해야 하는 경우:

• 정확한 존재 여부를 필터 하나로 끝내야 할 때
• 항목 삭제가 빈번한데 표준 블룸 필터만 사용하려 할 때
• 데이터가 작아 정확한 Set을 메모리에 보관해도 충분할 때
• 범위 검색이나 정렬 결과가 필요한 경우

마무리

블룸 필터의 가치는 “있다”를 맞히는 데 있지 않습니다. “없다”를 아주 작은 메모리로 빠르게 확정해 비싼 조회를 없애는 것에 있습니다.

하나라도 0 → DEFINITELY NOT → 조회 생략
모두 1     → MAYBE EXISTS   → 원본 확인

그리고 실전에서는 자료구조의 이름보다 세 가지가 더 중요합니다.

• 예상 삽입 개수
• 허용할 False Positive 비율
• 원본과 필터를 다시 맞추는 운영 절차

블룸 필터를 확률적 캐시처럼 막연하게 두지 않고, 측정 가능한 사전 필터로 다뤄야 효과를 얻을 수 있습니다.

자주 묻는 질문

블룸 필터와 HashSet은 무엇이 다른가요?

HashSet은 원본 키 또는 키를 구분할 충분한 정보를 보관해 정확한 존재 여부와 일반적인 삭제를 지원합니다. 블룸 필터는 비트 배열만 보관해 훨씬 작지만, MAYBE 판정과 False Positive를 허용합니다. 데이터가 작고 정확한 판정이 필요하면 Set이 더 단순합니다.

정말 False Negative는 없나요?

표준 블룸 필터가 정상적으로 삽입되고 비트가 임의로 지워지지 않았다는 조건에서는 없습니다. 삽입한 키의 해시 위치는 모두 1이기 때문입니다. 원본 저장과 필터 갱신이 어긋나거나 공유 비트를 잘못 삭제하면 운영상 False Negative가 생길 수 있으므로 동기화 절차는 별도로 보장해야 합니다.

항목을 삭제하려면 어떻게 해야 하나요?

공유 비트를 바로 0으로 만들면 다른 키까지 사라진 것으로 판정할 수 있습니다. 삭제가 필요하면 Counting Bloom Filter, Cuckoo Filter, 세대별 필터 교체 중 요구사항에 맞는 방식을 선택합니다.

목표 False Positive 비율은 얼마나 낮춰야 하나요?

무조건 가장 낮게 잡지 않습니다. False Positive 한 건이 만드는 원본 조회 비용, 예상 키 수, 메모리 예산, 해시 계산량을 함께 측정해 정합니다. 설정한 목표와 실제 관측 오탐률을 비교하는 운영 지표도 필요합니다.

참고 자료

• Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors
• Redis Bloom Filter 공식 문서
• Redis 확률적 자료구조와 Bloom Filter
• RocksDB Setup Options and Basic Tuning