Bloom Filter 오탐률과 메모리 계산: Redis 적용 전 알아둘 함정

Bloom Filter의 1% 오탐률은 모든 요청의 1%가 틀린다는 뜻이 아닙니다. 실제로 없는 항목을 조회했을 때 ‘있을 수도 있다’고 답하는 확률입니다. 이 차이를 놓치면 메모리를 줄였는데 데이터베이스 부하가 기대만큼 줄지 않거나, 잘못된 조회 생략으로 실제 데이터를 놓칠 수 있습니다.

자료구조의 기본 동작은 Bloom Filter 입문에서 볼 수 있습니다. 여기서는 캐시 앞단에 적용할 때의 오탐률, 메모리, 데이터 동기화 문제를 숫자로 풀어봅니다.

‘없다’와 ‘있을 수도 있다’를 구분

일반적인 삽입 전용 Bloom Filter는 정상적으로 삽입된 항목을 없다고 판정하지 않습니다. 반면 없던 항목이 다른 항목과 비트 위치를 공유하면 양성으로 나올 수 있습니다. 따라서 양성 결과는 원본에서 확인하고, 음성 결과는 필터가 최신이라는 조건 아래 원본 조회를 줄이는 데 활용합니다. Redis Bloom Filter 설명

이 보장은 자료구조의 성질입니다. 실제 시스템에서 DB에 새 항목을 넣고 필터 업데이트를 빠뜨리면 그 항목을 음성으로 볼 수 있습니다. 필터를 다른 키로 조회하거나 인코딩 규칙을 바꿔도 마찬가지입니다. ‘false negative가 없다’는 문장을 전체 애플리케이션의 동기화 보장으로 확대하면 안 됩니다.

100만 항목이면 메모리가 얼마나 필요할까요?

최적 해시 개수를 가정할 때 필요한 비트 수의 근사는 다음과 같습니다. n은 항목 수, p는 목표 오탐률입니다.

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

Redis의 BF.RESERVE 문서도 항목당 비트 수와 오탐률의 관계를 설명합니다. BF.RESERVE 메모리 계산

이 용량은 m / 8 / 1,048,576으로 계산한 이론적 비트 배열이며 실제 Redis 메모리 사용량이 아닙니다. 객체와 서브필터 관리 비용, 구현상 반올림, 자동 확장 등이 추가됩니다. 목표 오탐률을 10배 낮춘다고 메모리가 10배가 되는 것도 아닙니다.

직접 계산하려면 Python 표준 라이브러리로 아래 예시를 실행할 수 있습니다.

import math

n = 1_000_000
for p in (0.01, 0.001, 0.0001):
    bits = -n * math.log(p) / math.log(2) ** 2
    hashes = bits / n * math.log(2)
    print(f"p={p:g}, MiB={bits / 8 / 2**20:.2f}, k≈{hashes:.2f}")

오탐률 1%가 DB 호출을 얼마나 남길까요?

가상의 10만 요청 중 실제 존재하는 항목이 1만, 없는 항목이 9만이라고 합시다. 양성은 항상 DB로 확인하고 음성은 조회를 생략할 수 있는 정확한 동기화 조건을 가정합니다.

존재하는 항목 확인: 10,000회
없는 항목 중 예상 오탐: 90,000 × 0.01 = 약 900회
남는 원본 조회: 약 10,900회

오탐률을 0.1%로 낮추면 약 10,090회입니다. 이 예에서는 810회의 차이를 줄이려고 메모리와 필터 비용을 더 씁니다. 반대로 요청 대부분이 실제 존재하는 항목이면 필터가 생략할 조회 자체가 적습니다. 필터 추가 전 없는 ID 조회 비중과 DB 호출 비용을 측정해야 하는 이유입니다. 이 수치는 기대값 계산이며 실측 성능이 아닙니다.

Redis에서 먼저 확인할 명령

환경이 Bloom 명령을 지원하는지 확인하고, 운영 데이터와 분리된 테스트 키를 사용하세요. 아래는 초기 용량 100만, 목표 오탐률 0.1%의 예시입니다.

redis-cli COMMAND INFO BF.RESERVE
redis-cli BF.RESERVE demo:products:bf 0.001 1000000
redis-cli BF.ADD demo:products:bf product:42
redis-cli BF.EXISTS demo:products:bf product:42
redis-cli BF.INFO demo:products:bf

삽입된 product:42 조회는 정상 상태에서 1을 반환합니다. 다른 ID가 1을 반환했다고 필터 오류로 결론내리지 마세요. 양성은 확정 존재 여부가 아닙니다. BF.INFO로 크기, 삽입 항목 수, 서브필터 관련 정보를 확인할 수 있습니다. BF.EXISTS, BF.INFO

BF.RESERVE는 이미 존재하는 키에 다시 실행하면 오류가 납니다. 자동 확장 여부와 NONSCALING 옵션도 설계에 영향을 주므로 공식 명령 문서로 확인하세요. 용량을 넘는 항목을 넣은 뒤 처음 설정한 비트 배열 하나의 가정으로 계산하면 실제 동작과 달라질 수 있습니다.

DB와 필터 사이에 새 데이터가 들어오는 순간

가장 위험한 구현은 DB 저장 성공 직후 필터 등록이 실패했는데도 모든 음성을 ‘없는 데이터’로 응답하는 방식입니다. 새 데이터가 실제로 있는데 사용자는 못 찾게 됩니다.

안전 조건은 시스템마다 다르지만 다음을 명시해야 합니다.

• 필터 생성 중·재구축 중·장애 중에는 음성으로 원본 조회를 생략하지 않는 경로.
• 새 항목 업데이트 순서와 실패 시 재시도·복구 방식.
• 필터 준비 완료 상태와 버전 확인.
• ID 인코딩·대소문자·테넌트 범위를 일관되게 적용하는 규칙.

중요한 존재 확인에서는 음성이라도 DB를 조회하도록 두고, 필터를 부하 완화의 보조 신호로만 사용할 수 있습니다. 처음부터 정확성을 희생해 조회를 생략할 필요는 없습니다. 중복 결제나 보안 권한 같은 정확한 판정에는 원본 제약과 권한 검사가 필요합니다.

삭제는 어떻게 처리하나요?

일반 Bloom Filter에서 특정 항목의 비트를 임의로 지우면 다른 항목까지 음성으로 바뀔 수 있습니다. 삭제가 필요하면 재구축·시간 구간별 필터·삭제를 지원하는 다른 자료구조 등을 비교하세요. ‘삭제된 항목이 필터에는 남아 양성으로 나오지만 DB에서 없음으로 확인된다’는 경우와, ‘존재하는 항목이 음성으로 누락된다’는 경우의 위험은 다릅니다.

자주 묻는 질문

Bloom Filter가 1을 반환하면 DB 조회를 생략해도 되나요?

양성은 존재 가능성일 뿐입니다. 정확한 존재 확인이나 실제 값을 얻으려면 원본을 확인해야 합니다.

오탐률을 아주 낮추면 항상 더 빠른가요?

메모리와 해시·필터 조회 비용도 달라집니다. 없는 요청 비중, DB 비용, 실제 서브필터 수를 포함해 비교해야 합니다.

Redis가 재시작되면 그대로 믿어도 되나요?

영속화·복구 설정과 DB 업데이트 동기화 상태를 검증해야 합니다. 필터 키가 있다는 사실만으로 원본과 일치한다고 볼 수는 없습니다.

참고 자료

• Redis Bloom Filter.
• BF.RESERVE, BF.EXISTS, BF.INFO.

2026년 10월 8일 문서 확인. 메모리와 조회 횟수는 명시한 가정의 계산값입니다.