블룸 필터는 원본 집합을 대체하는 색인이 아니라 “원본 조회를 생략해도 안전한 음성”을 제공하는 압축된 보조 구조입니다. 따라서 메모리와 DB 부하를 줄이는 계산은 필터 자체의 확률만이 아니라 삽입 반영 시점, 삭제 정책, 동시 갱신, 원본 조회의 최종 권위를 함께 전제로 합니다.
부재 키의 DB 조회 생략 조건
등록된 상품은 백만 개인데 존재하지 않는 상품 ID 요청이 계속 들어온다고 합시다. 모든 요청을 DB까지 보내기 전에 작은 자료구조로 “이 키는 저장된 집합에 없다”고 걸러낼 수 있다면 조회 비용을 줄일 수 있습니다.
블룸 필터는 원소 자체 대신 여러 해시 위치의 비트를 저장합니다. 올바르게 삽입된 집합에서는 없다는 답을 신뢰할 수 있지만, 있다는 답은 “있을 수 있다”는 뜻입니다. 양성 결과는 원본을 다시 확인해야 합니다. 원본 DB와 필터의 반영 시점이 다르다면 이 수학적 보장과 실제 서비스의 부재 응답도 구분해야 합니다.
8비트 배열의 해시 위치 충돌과 거짓 양성
설명을 위해 키별 두 해시 위치를 아래처럼 정합니다. 실제 추천 해시 함수가 아니라 충돌을 보기 위한 작은 예입니다. 비트 번호는 0~7입니다.
| 키 | 해시 위치 | 삽입 여부 |
|---|---|---|
| A | 1, 4 | 삽입 |
| B | 4, 6 | 삽입 |
| C | 1, 6 | 삽입 안 함 |
| D | 2, 4 | 삽입 안 함 |
A와 B를 넣으면 1·4·6번 비트가 켜집니다. C를 조회하면 두 위치가 모두 켜져 있으므로 필터는 양성이라고 답합니다. 하지만 C는 넣은 적이 없습니다. 여러 키가 켠 비트가 우연히 조합되어 생긴 거짓 양성입니다. D는 2번 비트가 꺼져 있어 부재로 판정할 수 있습니다.
그림을 글로 읽기
- 켜진 비트 1 · 4 · 6: 삽입 집합: A, B
- C 조회: 1 · 6: 모두 1 → 원본 확인
- D 조회: 2 · 4: 2가 0 → 집합에 없음
- DB에서 C 조회: 없음: 거짓 양성 확인
- 켜진 비트 1 · 4 · 6 → C 조회: 1 · 6: 양성
- 켜진 비트 1 · 4 · 6 → D 조회: 2 · 4: 음성
- C 조회: 1 · 6 → DB에서 C 조회: 존재 확인
삽입·조회 연산의 비트 비삭제 원칙
insert(key):
for position in hashPositions(key):
bits[position] = 1
mayContain(key):
for position in hashPositions(key):
if bits[position] == 0:
return false
return true
동시 삽입에서는 서로 다른 비트라도 같은 기계어를 공유할 수 있습니다. 비원자적인 읽기·수정·저장으로 OR하면 한 스레드의 변경이 사라져 거짓 음성이 생길 수 있으므로 원자 OR나 잠금 등 실제 비트 저장의 동시성 계약이 필요합니다.
A를 삭제한다고 1·4번 비트를 끄면 B의 4번 비트도 사라집니다. B가 원본에 있는데 필터가 없다고 답하므로 잘못입니다. 삽입 전용 필터에서는 삭제된 키가 양성으로 남는 비용을 받아들이거나 새로 구축합니다. counting Bloom filter는 비트 대신 카운터를 사용하지만 정확한 삽입·삭제 횟수, 카운터 넘침·언더플로를 추가로 관리해야 합니다. 원본에 없는 키를 잘못 삭제하면 counting 방식도 안전하지 않습니다.
비트 용량·원소 수·해시 수 산정
비트 수 m, 삽입 원소 수 n, 해시 수 k에 대해 독립·균등 해시를 가정한 거짓 양성률 근사는 다음과 같습니다.
p ≈ (1 - exp(-k*n/m))^k
m ≈ -n*ln(p) / (ln(2)^2)
k ≈ (m/n)*ln(2)
원소 1,000개에 목표 거짓 양성률 1%라면 약 9,586비트, 약 1.2KB와 해시 7개가 출발점입니다. 실제 배열·객체·해시 상태의 부가 메모리는 포함하지 않은 계산입니다. 같은 필터에 2,000개를 넣으면 비트가 포화되어 위 근사에서 오류율이 약 15.7%로 커집니다.
해시 수를 무조건 늘리면 더 좋은 것은 아닙니다.
수치를 따라가면 n=1,000, p=0.01에서 m≈9,586, k≈7이지만 n이 2,000으로 늘어난 뒤에도 배열을 바꾸지 않으면 같은 k에서 비트 점유가 증가해 거짓 양성이 급격히 커집니다. 이때 양성 요청이 DB로 가는 비율은 올라갈 수 있지만, 진짜 존재 키가 음성으로 차단되면 안 된다는 안전 조건이 먼저입니다. 용량 경보는 원소 수뿐 아니라 실제 거짓 양성률과 필터 반영 lag를 함께 기준으로 둡니다.
재현 실습은 8비트 예를 코드로 옮겨 A·B를 삽입하고 C·D를 조회하는 것입니다. 예상 결과는 C=true 뒤 원본에서 없음, D=false 뒤 원본 조회 생략입니다. 여기에 A 삭제를 비트 clear로 추가하면 B가 false가 되는 반례가 재현되어, 삭제 지원 없이 일반 Bloom filter를 사용하는 설계 오류를 구분할 수 있습니다. 해시 계산이 늘고 비트도 더 빨리 켜집니다. 정수 반올림한 여러 k와 실제 키 분포를 비교하고, 원소 증가에 따라 필터를 교체할 시점을 정해야 합니다.
DB 커밋과 필터 반영 지연
DB에 새 상품 K를 먼저 커밋했다고 하겠습니다. 필터 갱신이 실패하면 K의 해시 위치를 새로 켜는 동작은 일어나지 않습니다. 현재 비트 중 K의 위치가 하나라도 꺼져 있으면 mayContain(K)=false가 되어 서비스가 DB 조회를 생략할 수 있지만, 다른 키의 충돌로 위치가 우연히 모두 켜져 있으면 양성이 나올 수도 있습니다. 블룸 필터의 “삽입된 키에는 거짓 음성이 없다”는 명제는 필터에 실제로 삽입된 집합에 대한 말이므로, DB가 최신 커밋까지 필터에 반영됐다는 운영 전제와 분리해서 읽어야 합니다.
필터가 원본의 어느 커밋 위치까지 따라갔는지 저장하고, 그 위치보다 새로 들어온 키의 조회는 원본으로 보내는 식으로 일관성 경계를 둡니다. 필터를 먼저 갱신한 뒤 DB 쓰기가 실패하면 없는 키가 양성으로 남는 방향이지만, 갱신 중 오류·삭제·여러 writer에서도 같은 순서가 지켜지는지 확인해야 합니다. 필터는 권한 검사나 보안상의 존재 비공개를 대신하지 않습니다.
Snapshot과 증분 삽입을 반영하는 필터 재구축
원본의 기준 위치 S에서 snapshot을 읽어 새 필터를 만들었다고 해 보겠습니다. 구축 중 추가된 키 K가 증분 기록에만 있다면 snapshot만으로 새 필터를 활성화할 때 K를 놓칩니다.
- snapshot의 기준 위치와 변경 로그 시작 위치를 일치시킵니다.
- snapshot의 모든 키를 새 필터에 넣습니다.
- S 이후의 신규 삽입을 재생하고 전환 경계까지 따라잡습니다.
- 새 필터 활성화와 이후 쓰기의 갱신 대상 전환을 연결합니다.
- 옛 필터를 읽는 작업이 끝난 뒤 회수합니다.
구축 중 두 필터 중 하나라도 양성이면 원본을 조회하는 보수적 방식은 도움이 됩니다. 하지만 둘 다 신규 키를 놓쳤다면 OR로도 복구되지 않습니다. 갱신이 불확실하면 음성 차단을 잠시 끄고 원본으로 보내되, 그때 늘어나는 DB 부하에도 상한이 필요합니다.
거짓 양성률·부재 응답 오류율의 구분
| 지표 | 분모 | 뜻 |
|---|---|---|
| 거짓 양성률 | 실제 부재 키 전체 | 없는 키 중 필터를 통과한 비율 |
| 양성 중 부재 비율 | 필터 양성 전체 | 원본 조회 중 낭비 비율, 요청 분포에 영향 |
| 잘못된 부재 응답 | 실제 존재 키 전체 | 반영 지연·잘못된 삭제·동시성 오류 가능성 |
작은 A·B·C·D 예에서 C 양성, D 음성, A·B 양성을 확인합니다. A 삭제 비트를 지운 잘못된 구현은 B를 놓쳐야 반례가 재현됩니다. 대규모 시험은 삽입 집합과 별도의 부재 집합을 보관해 오류율을 계산하고, 재구축 중 새 키·동시 비트 갱신·필터 복원 실패도 따로 시험합니다.