블룸 필터의 오탐률 1%는 무슨 뜻일까? 조회 생략과 정합성의 조건

“이미 처리한 주문”을 건너뛰어도 될까

주문 이벤트를 처리하는 서비스가 처리 완료 ID를 블룸 필터에 넣는다고 하자. 새 이벤트의 ID를 조회했더니 양성이 나왔다. 이를 곧바로 “중복이니 버림”으로 바꾸면, 처음 도착한 주문까지 버릴 수 있다. 서로 다른 키들이 같은 비트를 사용하기 때문이다.

블룸 필터(Bloom filter)는 집합에 어떤 키가 들어 있는지 작은 공간으로 가늠하는 자료구조다. 응답은 없음 또는 있을 수 있음이다. 정확성이 필요한 업무에서는 후자를 원본 저장소에서 확인한다. “없음”을 이용해 비싼 조회를 건너뛰는 데 가치가 있다. RocksDB 공식 설명도 이 구조를 특정 SST 파일에 키가 있을 가능성을 판별하는 데 연결한다. 한 파일에 없다는 답이 DB 전체에 없다는 뜻은 아니다.

이 글은 2026년 10월 14일 확인한 공식 문서와 직접 만든 작은 실험을 바탕으로 한다. Redis·RocksDB 서버를 실행하거나 처리량을 측정하지 않았다. 제품에 넣기 전에 판단할 원리와 데이터 반영 조건을 다룬다.

비트는 켠 사람의 이름을 기억하지 않는다

처음에 모두 0인 비트 배열을 준비한다. 키를 넣을 때 여러 해시로 배열의 위치를 구하고 그 비트를 1로 만든다. 조회할 때도 같은 입력 표현과 해시를 사용한다. 확인한 위치 중 하나라도 0이면 그 키는 넣지 않았다. 모두 1이면 그 키가 켰는지 다른 키가 켰는지 구별할 수 없다. 이것이 오탐(false positive)의 원리다. 비트 설정·조회 구조 근거

아래는 해시 출력 대신 위치를 직접 정한 설명용 8비트 예제다. 실제 해시의 품질이나 오탐률을 측정하는 예제가 아니다.

키	확인할 위치	실제로 넣었나?	A·B 삽입 후 답
A	1, 4, 7	넣음	있을 수 있음
B	2, 4, 6	넣음	있을 수 있음
C	1, 2, 6	안 넣음	있을 수 있음 — 오탐
D	0, 2, 6	안 넣음	없음 — 0번 비트가 0

위치 0부터 7까지 배열은 0 1 1 0 1 0 1 1이다. C는 A·B가 켠 비트만 확인하므로 통과한다. 모든 해시값이 다른 키 하나와 완전히 같아야 오탐이 생기는 것은 아니다. 여러 키가 남긴 비트가 조합돼도 가능하다.

정상적인 삽입 전용 필터에서 A를 다시 조회하면 A가 켠 비트들이 남아 있다. 그래서 넣은 키를 없다고 하는 거짓 음성이 발생하지 않는다. 이 논리는 삽입 성공, 같은 키 표현·해시, 비트 보존을 전제로 한다. 동시 쓰기로 비트를 잃거나, 새 필터로 교체하면서 키를 빠뜨린 경우까지 보장하지 않는다.

오탐률의 분모는 전체 질의가 아니다

오탐률 1%는 필터에 넣지 않은 키를 물었을 때 양성이 나올 확률을 뜻한다. 양성 응답 100개 중 하나만 틀린다는 뜻이 아니다. RocksDB도 관측 오탐률의 분모를 해당 집합에 없는 키에 대한 질의로 정의한다. 관측 지표의 정의

가상 질의 1만 건 중 실제 존재하는 키가 100건, 없는 키가 9,900건이라고 하자. 없는 키에 대한 오탐률이 1%라면 양성은 다음과 같이 예상된다.

• 실제 존재하는 키의 양성: 100건.
• 없는 키의 오탐: 9,900 × 0.01 = 99건.
• 총 양성 199건 중 오탐의 비중: 99 / 199 ≈ 49.75%.

입력 비율과 확률을 정해 계산한 기댓값이며 실제 요청 수집 결과가 아니다. 같은 1% 필터라도 없는 키가 대부분인 업무에서는 양성의 상당 부분이 틀릴 수 있다. 그러므로 주문 중복, 파일 존재, 회원 가입 여부를 양성 하나로 확정하지 않는다.

의미가 비슷한 문서를 찾는 하이브리드 검색과도 질문이 다르다. 여기서 확인하는 것은 “이 정확한 키를 넣었는가”이며, 연관 문서나 유사 항목을 반환하지 않는다.

메모리는 작지만 용량 가정은 남는다

기본 블룸 필터에서 비트 수를 m, 넣을 서로 다른 키 수를 n, 조회할 해시 위치 수를 k라고 하자. 균등하고 독립적인 해시를 이상화한 흔한 근사는 다음과 같다.

오탐률 p ≈ (1 − exp(−k × n / m))^k
목표 p에 필요한 비트 수 m ≈ −n × ln(p) / (ln(2))²
그때 k ≈ (m / n) × ln(2)

첫 식은 해시가 찍는 위치의 분포와 비트들의 독립성을 단순화한 근사다. 정수 k, 배열 반올림, 구현의 해시·캐시 배치에 따라 실제 값은 다르다. Redis의 크기 계산 설명은 목표 오탐률에서 필요한 비트 수와 해시 수를 제시한다.

서로 다른 키 100만 개를 넣는다는 가정으로 비트 배열만 계산하면 다음과 같다. 1 MiB = 1,048,576바이트다.

목표 오탐률	키당 비트 근삿값	배열 크기 근삿값	해시 수 예시¹
1%	9.585	1.143 MiB	7
0.1%	14.378	1.714 MiB	10

¹ Redis 문서의 ceil(−ln(p)/ln(2)) 방식으로 정수화했다. 표는 Redis 전체 프로세스 메모리나 실제 BF.RESERVE 할당량이 아니다. 메타데이터·추가 필터·할당 오버헤드는 제외했다.

고정된 배열에 예상보다 훨씬 많은 서로 다른 키를 넣으면 1인 비트가 늘어 오탐도 커진다. 이번 자체 코드에서는 9,586비트·해시 7개를 고정하고, 넣은 키와 별개의 absent:0부터 absent:9999까지 1만 개를 조회했다.

직접 실행한 유한 입력	오탐 수 / 부재 질의	관측 비율
item:0~item:999 삽입	80 / 10,000	0.80%
같은 배열에 item:1999까지 추가	1,627 / 10,000	16.27%

처음 넣은 1천 키의 재조회에는 거짓 음성이 없었고, 같은 키를 다시 넣어도 배열은 바뀌지 않았다. 결과는 고정 입력·교육용 SHA-256 probe의 관측이다. “목표 1%보다 성능이 좋다”는 평가나 일반 오탐률 보장이 아니다. 두 번째 입력 수를 첫 식에 넣은 약 15.74% 역시 근삿값이라 관측값과 일치할 의무가 없다.

이 실험을 Redis의 용량 초과 동작으로 읽으면 안 된다. 자체 코드는 계속 비트를 켜지만, BF.RESERVE 명령 계약은 NONSCALING 용량 도달 시 오류를 설명한다. 확장형은 추가 하위 필터를 만든다. 개념 문서의 NONSCALING 설명에는 용량 이후 오탐 증가라는 문구도 있어, 명령 문서와 고정 소스의 full 오류 분기를 대조했다. 삽입 실패를 무시하고 “전부 반영됐다”고 간주해서는 안 된다.

가장 위험한 “없음”은 필터 밖에서 생긴다

상품 DB 앞에 필터를 놓고 음성이면 “상품 없음”을 반환한다고 하자. 다음 순서는 블룸 필터 자체의 수학적 성질을 깨지 않고도 잘못된 응답을 만든다.

순서	원본 DB	필터	사용자가 받는 결과
1	새 상품 P를 커밋	P는 아직 미반영	아직 질의 없음
2	P가 존재함	P 조회가 음성	DB를 생략하면 잘못된 “없음”
3	P가 존재함	비동기 작업이 P를 추가	이후 질의는 원본 확인 가능

2번은 DB를 기준으로 한 누락이다. 필터를 기준으로는 넣지 않은 키를 없다고 답했을 뿐이다. 이 글의 설계 기준은 다음 포함 관계다.

조회가 볼 수 있는 원본 키 집합 ⊆ 해당 필터에 성공적으로 반영한 키 집합

오른쪽에 원본에 없는 키가 조금 더 있어도 추가 조회가 생기는 방향이다. 왼쪽의 키가 오른쪽에서 빠지면 정상 데이터를 숨길 수 있다. 이 비대칭 때문에 “조금 늦어도 되는 캐시”라는 말만으로 정책을 정하기 어렵다.

특히 Redis BF.EXISTS는 필터 키 자체가 없는 경우에도 부정 값을 반환할 수 있다. 응답 0 하나로 “정상 필터가 이 상품의 부재를 증명했다”고 판단하면, 필터 만료·삭제·잘못된 키 선택을 정상 부재와 혼동할 수 있다. 확인한 소스의 조회 분기도 함께 볼 수 있다. 오류나 타임아웃을 음성으로 변환하는 애플리케이션 처리 역시 피해야 한다.

조회를 생략할 권한은 어떻게 주나

다음은 특정 제품이 제공하는 자동 보장이 아니라, 위 포함 관계에서 도출한 설계 선택표다.

상황	음성으로 생략할 수 있는 조건	불확실할 때의 행동
변경 없는 파일·스냅샷	그 파일의 모든 키로 만든 필터를 같은 버전에 연결	필터가 없거나 버전 불일치면 파일 조회
계속 쓰는 서비스	해당 조회가 볼 새 키까지 반영 완료하는 프로토콜	반영 지연·실패 구간은 원본 조회
필터 재생성·교체	스냅샷 이후 변경까지 따라잡고 완성 세대로 전환	구축 중 세대는 조회 생략에 사용하지 않음
필터 장애·만료	정상 상태·데이터 범위를 함께 확인	한도 있는 원본 조회 또는 명시적 일시 오류

정적인 집합이 관리하기 쉬운 이유는 “무엇을 모두 넣었는가”가 고정돼 있기 때문이다. 여러 파일을 읽는 저장소라면 각 파일에 대한 판단을 합쳐야 한다. 한 필터의 음성만으로 다른 파일·메모리 계층의 데이터까지 제외하지 않는다.

계속 쓰는 서비스에서 필터를 먼저 갱신하고 DB에 쓰는 순서를 생각할 수 있다. DB 쓰기가 실패해도 필터에 남은 키는 불필요한 조회를 유발하는 쪽이다. 하지만 두 호출의 순서만으로 정합성이 완성되지는 않는다. 이후 필터 유실, 읽기 복제본의 지연, 키 정규화 차이, 다른 배치 쓰기 경로를 포함해 같은 조건을 지켜야 한다. 이 글에서는 이런 분산 쓰기 프로토콜을 구현·검증하지 않았다.

비동기 반영을 택했다면 DB 커밋 순서를 대표하는 위치와 필터가 반영한 위치를 비교하거나, 새 데이터 구간은 원본으로 보내는 정책 등을 설계할 수 있다. 단순히 “마지막 동기화 5초 전”이라는 시각만으로 모든 커밋을 반영했다고 증명할 수는 없다. 메타데이터와 필터 자체를 다른 순간에 읽어서 생기는 경합도 처리해야 한다.

원본 조회로 우회하면 정확성의 근거는 회복되지만 부하가 늘어난다. 이때 동시 처리 한도와 일시 오류 정책도 함께 둬야 필터 장애가 DB 장애로 번지는 것을 막을 수 있다. 필터 상태가 불명확한 요청에 정상적인 “없음”을 답하는 것과, 조회를 완료하지 못했다는 오류를 답하는 것은 다르다.

삭제와 중복 방지는 원본의 책임을 남겨 둔다

앞의 8비트 예제에서 A를 지운다며 1·4·7번 비트를 0으로 바꾸면 어떻게 될까. B도 사용하던 4번이 꺼져, 아직 남은 B를 없다고 답한다. 자체 코드에서 이 반례를 확인했다. 따라서 기본 비트 배열에서 개별 키의 비트를 그대로 지우지 않는다. 원본에서만 지우고 필터를 유지하면 불필요한 양성이 남지만, 조회로 삭제 여부를 확인할 수 있다. 누적 비용이 커지면 원본 기준 재구축이 필요하다.

삭제가 핵심인 업무에는 다른 자료구조를 검토할 수 있다. Redis의 개념 문서도 삭제를 지원하는 Cuckoo filter를 대안으로 언급한다. 그렇다고 자료구조를 바꾸면 삭제 대상 확인과 동기화 책임까지 사라지는 것은 아니다. 대안 비교 근거

주문 중복 방지로 돌아가 보자. 양성이면 처리 완료 저장소를 확인하고, 음성이어도 같은 이벤트가 동시에 처리될 수 있으므로 최종 기록에는 유일성 제약이나 원자적인 중복 제어가 필요하다. 필터 조회와 삽입 사이를 업무 잠금으로 간주하지 않는다. DB 규칙과 동시성, 이벤트 전달과 중복 효과는 그 다음 판단에 해당한다.

도입 전에는 “없는 키를 얼마나 묻는가”부터 센다

같은 오탐률이어도 대부분 존재하는 키를 조회하면 생략할 기회가 적다. 전체 질의 중 부재 비율을 q, 부재 질의에 대한 오탐률을 p라 하고, 양성은 원본 조회·음성은 생략한다고 가정하자.

원본 조회 비율 = (1 − q) + q × p
원본 조회 생략 비율 = q × (1 − p)

이는 포함 관계가 유지되고 필터 장애가 없다는 모델이다. 질의 1만 건·p=1%에서 비교하면 다음과 같다.

부재 질의 비율	실제 존재 질의	예상 오탐	예상 원본 조회	예상 생략
90%	1,000	90	1,090	8,910
5%	9,500	5	9,505	495

두 번째 행에서는 모든 요청에 필터 확인을 추가하면서 4.95%의 원본 조회만 줄인다. 원본의 부재 조회 한 건을 생략해 아끼는 평균 비용을 Cmiss, 필터 확인 평균 비용을 Cf라 하면, 단순 직렬 모델의 유리한 조건은 Cf < q × (1−p) × Cmiss다. 원본의 존재 조회와 부재 조회가 같은 비용이라고 가정할 필요는 없다.

가령 Cf=0.2ms, Cmiss=1ms라는 가상 값을 넣으면 부재 90%일 때 0.891ms를 아끼는 대신 0.2ms를 추가한다. 부재 5%일 때는 0.0495ms를 아끼기 위해 0.2ms를 추가한다. 이는 설명용 비용 계산이다. 원격 필터의 왕복 지연, 원본 캐시 적중, 장애 우회, 유지 비용과 꼬리 지연을 측정한 결과가 아니다.

실제 도입에서는 부재 질의 비율, 필터 양성 뒤 원본에서 발견하지 못한 비율, 필터 지연, 반영 지연·삽입 실패, 원본으로 우회한 건수를 함께 본다. 음성은 평소 원본을 읽지 않으므로 모든 원본 누락을 직접 관측할 수 없다. 별도 대조 표본이나 구축 검증으로 누락을 확인해야 하며, 표본에서 문제가 없었다는 사실도 전체 포함 관계의 증명은 아니다.

필터만으로 주문을 버려도 되는가, 데이터가 없다고 답해도 되는가, 조회를 추가할 가치가 있는가는 서로 다른 결정이다. 팀에서 먼저 합의할 것은 목표 오탐률보다 잘못된 답을 어디에서 막을지다.

직접 확인하고 설계에 옮기기

교육용 Python 코드와 실행 결과·계산값을 내려받아 같은 디렉터리에 둘 수 있다. Python 3.11 이상에서 외부 패키지·서버 없이 다음처럼 실행한다.

python3 bloom-filter-lab.py

확인 환경은 Python 3.11.12다. 코드는 8비트 오탐·잘못된 삭제, 삽입 키 재조회·중복 삽입, 1천/2천 키의 오탐 대조, 반영 누락 시 원본 우회, 본문의 가정 계산을 출력한다. 해시는 재현성을 위한 교육용 구성으로 제품 구현과 다르다. 동시 쓰기·복제·복구·실제 데이터의 분포는 실험하지 않았다.

적용 검토에는 아래 네 줄을 채워 두면 된다. 다음에 용량이나 배포 구조를 바꿀 때 같은 기준으로 다시 판단할 수 있다.

필터가 대표하는 집합: 파일/세대/테넌트/원본 범위와 키 표현
음성을 믿는 조건: 전체 반영 증거, 새 쓰기·재구축·복구 규칙
불확실할 때: 원본 조회 한도, 일시 오류, 재활성화 조건
비용 대조: 부재 비율, 오탐, 필터 지연, 원본 부재 조회 비용

이 기준표는 본문의 저장 버튼으로 다시 찾을 수 있다. 자료구조와 서비스 설계의 후속 글은 소프트웨어 주제 모음과 RSS에서 이어 볼 수 있다.