블룸 필터 (Bloom Filter)
비트와 해시로 존재 여부를 걸러내고, Redis에서 불필요한 DB 조회 줄이기
알고리즘 복잡도
개요
블룸 필터는 원문 대신 비트 배열과 여러 해시 위치 를 사용하는 확률적 자료구조다. 적은 메모리로 집합 포함 여부를 검사하지만, 결과는 “없음”과 “있을 수 있음”으로 나뉜다. Redis 상품 캐시 앞에서 존재하지 않는 상품 ID를 걸러내는 상황으로 원리를 살펴본다.
비트 배열에 기록하는 방법
- 초기화: m개 비트를 모두 0으로 설정.
- 삽입: 같은 입력을 k개 해시로 계산하고, 각 결과를 m으로 나눈 나머지 위치를 1로 설정.
- 조회: 동일한 해시 위치를 확인. 하나라도 0이면 집합에 추가되지 않은 값. 모두 1이면 존재할 가능성.
- 불변식: 정상적으로 추가된 값의 k개 위치는 이후에도 모두 1. 기본 블룸 필터는 비트를 지우지 않음.
| 조회 결과 | 의미 | 상품 조회 예제의 처리 |
|---|---|---|
| 하나라도 0 | 필터에 추가된 적 없는 값 | 필터가 최신·정상일 때 DB 조회 생략 |
| 모두 1 | 추가된 값이거나 해시 충돌 | 일반 캐시 확인 후, MISS면 DB 조회 |
“거짓 음성이 없다”는 성질은 삽입이 완료된 집합 에 대한 보장이다. DB에만 생성되고 필터에는 아직 반영되지 않은 상품까지 자동으로 보장하지 않는다.
시각화의 입력과 오탐 추적
교육용 필터는 m = 24비트, k = 3 이며, 상품 101·202·303이 먼저 반영되어 있다. 숫자는 0부터 시작하는 인덱스다. 화면의 해시는 결정적인 교육용 함수이며 Redis 내부 해시·비트 배치와 다르다.
| 입력 ID | 해시 위치 | 관찰할 결과 |
|---|---|---|
| product:101 | 9, 15, 17 | 이미 삽입한 상품. 존재 가능 → DB에 실제 존재 |
| product:202 | 19, 7, 22 | 오탐에 사용되는 19번 비트를 설정 |
| product:303 | 17, 22, 21 | 다른 상품과 비트 공유 |
| product:404 | 17, 17, 13 | 삽입 시 이미 1인 17은 유지하고 13만 새로 설정 |
| product:500 | 13, 21, 3 | 초기 필터의 13이 0 → 검사 중단 |
| product:506 | 19, 9, 15 | 삽입하지 않았지만 세 비트가 모두 1 → 오탐 |
오탐은 가짜 데이터를 생성하는 현상이 아니다. 필터가 DB 확인을 한 번 더 허용하는 현상이다. 506의 비트는 202와 101이 각각 설정했으며, DB 조회 결과는 상품 없음이다. 각 시나리오는 동일한 초기 필터에서 독립적으로 시작한다.
Redis에서 캐시 관통 줄이기
여기서는 DB의 전체 상품 ID 집합 을 필터에 반영한다. 캐시에 현재 들어 있는 상품 ID만 반영하면 캐시 MISS와 실제 상품 부재를 혼동하게 된다.
- 애플리케이션이 요청한 상품 ID로 Redis 블룸 필터 조회.
- 필터가 정상·최신이고 결과가 0이면 없는 상품으로 응답. 일반 상품 캐시와 DB 접근 생략.
- 결과가 1이면 일반 Redis 상품 캐시 GET. HIT면 캐시 데이터 반환.
- 캐시 MISS면 DB SELECT로 실제 존재 여부 확인. 상품이 있으면 반환하고 캐시 저장, 없으면 404 응답.
시각화의 존재 가능·오탐 예시는 모두 캐시 MISS 를 가정한다. 블룸 필터 자체는 상품 본문을 저장하지 않으며, 일반 캐시를 대체하지 않는다. 존재하지 않는 ID가 반복 유입되어 DB까지 내려가는 캐시 관통 을 줄일 수 있지만, 정상 상품의 캐시 만료나 동시 MISS를 모두 해결하지는 않는다.
Redis 명령으로 확인하기
Redis 8 배포에는 블룸 필터 자료형이 통합되어 있다. 이전 버전은 Redis Stack 또는 RedisBloom을 제공하는 환경인지 확인한다. 관리형 서비스는 해당 명령 지원 여부를 별도로 확인한다.
아래 명령은 새 키를 사용하는 redis-cli 예제다. 실제 Redis가 비트 수와 해시 수를 선택 하므로 위 24비트 교육용 시각화와 충돌 결과가 같지는 않다.
# 예상 상품 ID 100만 개, 목표 오탐률 1%
BF.RESERVE demo:products:ids 0.01 1000000
# OK
BF.MADD demo:products:ids product:101 product:202 product:303
# 각 항목의 추가 결과 반환
BF.EXISTS demo:products:ids product:101
# 1: 존재 가능 (이 값은 실제로 추가했음)
BF.EXISTS demo:products:ids product:506
# 0 또는 1: 실제 해시 충돌 여부에 따라 달라짐
BF.INFO demo:products:ids
# 용량·메모리 크기·서브필터 등 운영 정보
- BF.EXISTS = 1: 존재 가능. 데이터 존재를 확정하는 응답이 아님.
- BF.ADD = 0: 이미 추가되었을 가능성. 정확한 중복 여부나 유일성 보장으로 사용하지 않음.
- 원자성의 경계: 개별 Redis 명령의 원자성이 Redis와 DB의 변경을 하나의 트랜잭션으로 만들지는 않음.
메모리와 오탐률의 절충
독립적이고 균등한 해시를 가정한 근사식은 다음과 같다. n은 삽입한 서로 다른 값의 수, m은 비트 수, k는 해시 수다.
- 오탐률: p ≈ (1 − exp(−kn/m))^k
- 목표 오탐률을 위한 비트 수: m ≈ −n × ln(p) / (ln 2)^2
- 최적 해시 수: k ≈ (m/n) × ln 2
100만 개·목표 1%라면 원시 비트 배열은 약 959만 비트 = 1.20 MB (1.14 MiB), 해시는 약 7개다. Redis 실제 사용량에는 메타데이터·할당 단위·확장 서브필터 등이 추가되므로 BF.INFO로 확인한다.
오탐률 1%는 모든 양성 응답 중 1%가 틀린다는 뜻이 아니다. 집합에 없는 값을 조회했을 때 약 1%가 존재 가능으로 판정된다는 뜻이다. 트래픽의 실제 상품 비율에 따라 양성 응답의 정확도는 달라진다. 작은 교육용 필터의 선택된 예시 몇 개로 운영 오탐률을 추정하지 않는다.
운영에서 보장을 유지하는 조건
| 상황 | 발생할 수 있는 문제 | 설계 시 고려할 처리 |
|---|---|---|
| 최초 적재·재구축 | 아직 반영되지 않은 실제 상품을 차단 | 전체 적재와 변경분 반영 검증 후 ready 전환. 준비 전에는 필터로 차단하지 않고 기존 조회 경로 사용 |
| 상품 생성 | DB와 필터 사이 반영 시간차 | 필터 반영과 읽기 공개 순서를 조율. 실패 시 차단 기능을 우회하거나 공개 보류. 단순 비동기 반영만으로 무누락 보장 불가 |
| 키 유실·만료·장애 | 빈 필터의 0을 상품 부재로 오인 | 별도 준비 상태·세대 검증. 키 유실, 타임아웃, 오류는 “없음”으로 해석하지 않고 폴백. DB 부하 보호 병행 |
| 상품 삭제 | 공유 비트를 0으로 지우면 다른 상품 누락 | 기본 블룸 필터는 개별 삭제 금지. 오래된 양성은 DB에서 확인. 필요 시 재구축 또는 삭제 지원 자료구조 검토 |
| 용량 초과 | 오탐 증가 또는 추가 실패 | 예상 용량 예약, BF.INFO 관찰. Redis 확장형은 서브필터가 늘어 조회 비용도 증가할 수 있음 |
필터 장애 때 DB로 우회하면 정확성은 유지할 수 있지만 DB 부하는 증가한다. 요청 제한·동시성 제한 등 보호 정책도 함께 설계한다. 블룸 필터는 조회 비용을 줄이는 보조 인덱스 이며, 권한 확인이나 결제·재고·회원 ID의 정확한 유일성 검증을 대신하지 않는다.
시간·공간 복잡도 읽기
단일 필터에서 삽입은 k개 위치를 설정하므로 O(k), 조회는 첫 0에서 종료하면 최선 O(1), 끝까지 확인하면 O(k)다. 저장 공간은 O(m)비트다. 이는 해시 계산을 단위 비용으로 본 분석이며, 문자열 길이가 L이면 실제 해시 계산 비용도 고려한다. k를 고정했을 때 흔히 O(1)이라고 부르지만 해시 수에 따른 비용이 사라지는 것은 아니다.
학습 목표
- 비트 배열 변화로 삽입·조회·오탐을 설명하고, 존재 가능과 실제 존재를 구분한다.
- Redis 블룸 필터, 일반 캐시, 원본 DB의 역할과 장애 시 우회 조건을 구분한다.
자주 하는 오해
- BF.EXISTS가 1이라고 실제 상품이 존재한다고 확정하지 않는다.
- 거짓 음성 없음은 필터에 정상 반영된 집합에 대한 보장이다. DB와의 동기화 누락까지 보장하지 않는다.
- 여러 상품이 비트를 공유하므로 삭제할 상품의 해시 위치를 0으로 초기화하지 않는다.
핵심 정리
- 0 하나면 확실한 미등록, 모두 1이면 존재 가능. 오탐은 후속 확인 비용을 늘린다.
- 메모리를 더 쓰면 목표 오탐률을 낮출 수 있다. 실제 사용량과 용량은 BF.INFO로 관찰한다.
- Redis 연동에서는 최신성·준비 상태·키 유실을 관리하고 실제 데이터는 캐시 또는 DB에서 확인한다.
학습 확인
핵심 단계
- 1
상품 ID를 동일한 k개 해시로 계산하고 m으로 나눈 나머지를 비트 인덱스로 사용.
- 2
삽입은 해당 비트를 모두 1로 설정. 다른 값과 위치가 겹쳐도 1 유지.
- 3
조회는 같은 위치를 검사. 0을 만나면 중단하고 미등록 판정.
- 4
모두 1이면 존재 가능으로 판정. 캐시 MISS 시 DB에서 실제 존재 확인.
- 5
DB에 값이 없으면 오탐. 404를 반환하며 필터의 공유 비트는 그대로 유지.
핵심 개념 및 실무 적용 분야
참고 자료
개념과 기술 규격을 추가로 확인할 수 있는 외부 자료입니다. 시각화는 교육 목적에 맞게 일부 절차를 단순화할 수 있습니다.