블룸 필터
"이 값이 집합에 들어 있는가?"는 해시 테이블이나 데이터베이스가 늘 답하는 질문이지만, 원소가 수억 개이면 원소를 그대로 저장하는 것만으로 메모리와 디스크 읽기가 부담입니다. 블룸 필터(Bloom filter)는 원소를 저장하지 않고 비트 몇 개만 켜 두는 방식으로 "확실히 없다"와 "있을 수도 있다" 두 가지 답만 알려 주는 확률적 자료구조입니다. 대답이 가끔 틀리는 대신 메모리를 아주 적게 씁니다.
비트 배열 하나와 해시 함수 k개로 만듭니다. 원소를 추가하면 해시 함수 k개가 가리키는 칸을 모두 1로 켜고, 조회할 때는 같은 k개 칸이 모두 1인지 봅니다. 하나라도 0이면 추가한 적이 없다고 확신할 수 있고, 모두 1이어도 다른 원소들이 켠 칸일 수 있어 확실하지 않습니다. 이 토픽에서는 추가, 조회에서 생기는 거짓 양성, 삭제가 안 되는 이유를 단계별로 봅니다.
핵심 개념
비트 배열
길이 m의 비트 배열로, 처음에는 모두 0입니다. 원소 자체를 저장하지 않고 원소의 흔적만 이 배열에 남깁니다.
핵심 개념
해시 함수 k개
원소를 칸 번호 k개로 바꿉니다. 서로 독립에 가까운 해시 함수를 쓰거나, 해시 두 개를 조합하는 이중 해싱으로 k개를 만듭니다.
핵심 개념
추가
원소의 해시 위치 k칸을 모두 1로 켭니다. 이미 1인 칸은 그대로 두며, 이 칸을 여러 원소가 공유할 수 있습니다.
핵심 개념
조회
k칸 중 하나라도 0이면 "확실히 없다", 모두 1이면 "있을 수도 있다"입니다. 거짓 음성은 없고 거짓 양성만 있습니다.
핵심 개념
거짓 양성
추가한 적 없는 원소인데 k칸이 우연히 모두 1이어서 "있을 수도 있다"가 나오는 경우입니다. 켜진 칸이 많아질수록 확률이 올라갑니다.
핵심 개념
삭제 불가
한 칸을 여러 원소가 공유하므로 칸을 끄면 그 칸을 공유한 다른 원소의 흔적까지 지워 거짓 음성이 생길 수 있습니다. 삭제가 필요하면 칸에 카운터를 두는 변형을 씁니다.
블룸 필터의 배경
블룸 필터는 버튼 블룸(Burton H. Bloom)이 1970년 논문 "Space/Time Trade-offs in Hash Coding with Allowable Errors"에서 제안했습니다. 오류를 조금 허용하는 대신 해시 코딩의 공간을 크게 줄이는 방법으로, 대용량 데이터의 해시 영역이 주기억장치에 들어가지 않는 상황을 다뤘고, 논문의 예시는 하이픈 분리용 단어 사전이었습니다. 지금은 대규모 저장소가 디스크 읽기를 줄이는 용도로 널리 씁니다.
숫자로 확인하기
자주 하는 오해
면접에서 이렇게 물어요
면접 질문
블룸 필터는 무엇이고 언제 쓰나요?
원소 존재 여부를 적은 메모리로 근사해서 답하는 확률적 자료구조입니다. 비싼 조회(디스크, 네트워크) 앞에 두어 "확실히 없다"인 요청을 걸러 낼 때 씁니다.
면접 질문
거짓 양성과 거짓 음성은 어느 쪽이 있나요?
거짓 양성만 있습니다. 추가한 원소는 해당 칸이 켜져 있으므로 항상 "있을 수도 있다"가 나오고, 추가하지 않은 원소가 가끔 "있을 수도 있다"로 나옵니다.
면접 질문
왜 삭제가 안 되나요?
한 칸을 여러 원소가 공유해서, 칸을 끄면 그 칸을 쓰던 다른 원소가 지워진 것처럼 보이는 거짓 음성이 생길 수 있기 때문입니다. 카운터를 두는 카운팅 블룸 필터가 대안입니다.
면접 질문
크기와 오류율의 관계는?
원소 수 n, 목표 오류율 p가 정해지면 비트 수 m은 -n ln p / (ln 2)^2, 해시 수 k는 (m / n) ln 2 정도입니다. 오류율을 10분의 1로 줄이려면 원소당 약 4.8비트가 더 필요합니다.
실제 시스템에서는
함께 보면 좋은 토픽
참고 자료
Python — 블룸 필터 기본 구현
def djb2(s): h = 5381 for c in s.encode(): h = (h * 33 + c) & 0xFFFFFFFF return h def fnv(s): h = 0x811c9dc5 for c in s.encode(): h ^= c h = (h * 0x01000193) & 0xFFFFFFFF return h class BloomFilter: def __init__(self, m, k): self.m, self.k = m, k self.bits = [0] * m def _positions(self, item): a, b = djb2(item), fnv(item) | 1 # 이중 해싱: h_i = a + i*b return [(a + i * b) % self.m for i in range(self.k)] def add(self, item): for p in self._positions(item): self.bits[p] = 1 def might_contain(self, item): return all(self.bits[p] for p in self._positions(item)) bf = BloomFilter(16, 3) for w in ['apple', 'banana', 'cherry']: bf.add(w) print(bf._positions('apple'), sum(bf.bits)) # [7, 6, 5] 7 print(bf.might_contain('apple'), bf.might_contain('mango'), bf.might_contain('grape')) # True False True
비트 배열 하나와 해시 위치 k개를 구하는 함수만 있으면 됩니다. 여기서는 해시 함수를 k개 따로 만드는 대신, 서로 다른 해시 두 개(djb2와 FNV)로 a + i * b를 계산하는 이중 해싱으로 위치 3개를 만듭니다. b를 홀수로 만들어 칸 수가 2의 거듭제곱일 때 위치가 겹치지 않게 합니다. add는 위치의 칸을 1로 켜고, might_contain은 위치의 칸이 모두 1인지 확인합니다. 이름이 contain이 아니라 might_contain인 이유는 "모두 1"이어도 다른 원소가 켠 칸일 수 있기 때문입니다. apple, banana, cherry를 넣은 뒤 apple의 위치는 7, 6, 5이고 켜진 칸은 7개입니다. mango는 12와 1이 0이라 False(확실히 없음)이고, 추가한 적 없는 grape는 위치 4, 5, 6이 모두 켜져 있어 True가 나옵니다. 시각화의 조회 탭이 보여 주는 거짓 양성입니다.
Python — 크기 계산과 실제 거짓 양성률
import math def size(n, p): m = math.ceil(-n * math.log(p) / (math.log(2) ** 2)) # 비트 수 k = round(m / n * math.log(2)) # 해시 함수 수 return m, k m, k = size(1_000_000, 0.01) print(m, k, round(m / 8 / 1024)) # 9585059 7 1170 (약 1.14MiB) n = 10000 m, k = size(n, 0.01) bf = BloomFilter(m, k) for i in range(n): bf.add('item-%d' % i) print(all(bf.might_contain('item-%d' % i) for i in range(n))) # True (거짓 음성 없음) fp = sum(bf.might_contain('other-%d' % i) for i in range(100000)) print(m, k, fp / 100000) # 95851 7 0.00972
원소 수 n과 목표 거짓 양성률 p가 정해지면 필요한 비트 수는 m = -n ln p / (ln 2)^2, 최적의 해시 함수 수는 k = (m / n) ln 2로 계산합니다. 원소 100만 개를 1% 오류율로 담으려면 비트 약 958만 개, 즉 약 1.14MiB가 필요하고 해시 함수는 7개입니다. 원소 하나당 약 9.6비트입니다. 원소 1만 개로 실제로 만들어 확인하면, 넣은 원소는 모두 "있을 수도 있다"로 나오고(거짓 음성 없음), 넣지 않은 10만 개 가운데 0.97%가 거짓 양성으로 나왔습니다. 목표한 1%에 가깝습니다. 이 예의 문자열(item-숫자)을 그대로 저장하면 글자만 약 89KB이지만, 블룸 필터는 약 12KB면 됩니다. 원소 자체를 저장하지 않는다는 점이 공간 절약의 원천입니다.
Python — 삭제가 되는 Counting Bloom Filter
class CountingBloomFilter(BloomFilter): def add(self, item): for p in self._positions(item): self.bits[p] += 1 # 비트 대신 카운터를 올린다 def remove(self, item): for p in self._positions(item): self.bits[p] -= 1 # 지울 때는 카운터를 내린다 cbf = CountingBloomFilter(16, 3) for w in ['apple', 'banana', 'cherry']: cbf.add(w) cbf.remove('apple') print(cbf.might_contain('apple'), cbf.might_contain('banana')) # False True
Counting Bloom Filter는 칸마다 비트 하나 대신 작은 카운터를 두어 삭제를 지원합니다. add는 위치의 카운터를 1씩 올리고 remove는 1씩 내리며, might_contain은 카운터가 0보다 큰지 확인합니다. 파이썬 코드에서는 부모 클래스의 might_contain이 값이 0이 아닌지 검사하므로 그대로 쓸 수 있습니다. 앞에서 본 문제 상황과 같은 apple, banana, cherry에서 apple을 지워도, 칸 6과 7은 banana도 쓰고 있어 카운터가 2에서 1로 내려갈 뿐 0이 되지 않습니다. 그래서 banana는 여전히 True이고 apple은 False입니다. 비트 필터에서는 이 두 칸이 0이 되어 banana가 거짓 음성이 되었습니다. 대신 칸당 메모리가 비트 1개에서 카운터로 늘어납니다. 카운팅 블룸 필터를 제안한 Fan 등의 분석은 칸당 4비트면 오버플로 확률이 극히 낮아 충분하다고 봅니다. 같은 원소를 추가한 적 없이 remove하면 카운터가 음수가 될 수 있어서, 실제로 있었던 원소만 지운다는 전제가 필요합니다. 없던 원소를 지우면 공유한 칸의 카운터가 줄어 다른 원소의 거짓 음성이 생길 수도 있습니다.
Q1
블룸 필터가 "이 원소는 없다"라고 답했을 때의 의미는?
Q2
블룸 필터가 "이 원소는 있다"라고 답했을 때의 특징은?
Q3
표준 블룸 필터가 지원하지 않는 연산은?