블룸 필터(Bloom Filter)는 "이 원소가 집합에 있는가?"라는 질문에, 아주 적은 메모리로 확률적으로 답하는 자료구조입니다. 특징이 독특합니다. "없다"는 100% 확신할 수 있지만, "있다"는 아주 낮은 확률로 틀릴 수 있습니다. 이 비대칭성만 이해하면 쓸 곳이 확 넓어집니다.
처음 블룸 필터를 실무에 넣은 건, 회원가입 아이디 중복 체크 때문이었습니다. 수천만 개의 이미 쓰인 아이디를 매번 DB로 조회하니 부하가 컸죠. 대부분의 신규 아이디는 당연히 안 겹치는데도요. 여기에 블룸 필터를 앞단에 두니, "확실히 안 겹치는" 요청은 DB를 아예 안 건드리고 통과시킬 수 있었습니다.
동작 원리 — 비트 배열과 여러 해시
블룸 필터는 m개의 비트로 된 배열과 k개의 서로 다른 해시 함수로 구성됩니다. 원소를 추가할 때는 k개의 해시로 얻은 k개의 위치 비트를 모두 1로 켭니다. 조회할 때는 같은 k개 위치를 확인해서, 하나라도 0이면 "없음"이 확실합니다. 전부 1이면 "아마 있음"입니다.
bits = [0] * m
def add(x):
for i in range(k):
bits[hash_i(x, i) % m] = 1
def maybe_contains(x):
return all(bits[hash_i(x, i) % m] for i in range(k))왜 "아마"일까요? 서로 다른 원소들이 우연히 같은 비트들을 켜놓았을 수 있기 때문입니다. 한 번도 넣은 적 없는 값인데, 그 값의 k개 비트가 다른 원소들 때문에 이미 다 1이 되어 있으면 "있음"으로 잘못 답합니다. 이게 거짓 양성(false positive)입니다. 반대로 거짓 음성은 절대 없습니다. 넣은 원소의 비트는 반드시 1이니까요.
거짓 양성률은 조절할 수 있다
다행히 거짓 양성률은 설계로 통제됩니다. 넣을 원소 개수 n, 원하는 오류율 p를 정하면 최적의 비트 수 m과 해시 개수 k가 공식으로 나옵니다.
| 목표 오류율 p | 원소당 비트 수 | 1천만 원소 기준 크기 |
|---|---|---|
| 1% | 약 9.6 bit | 약 11.4 MB |
| 0.1% | 약 14.4 bit | 약 17.1 MB |
| 0.01% | 약 19.2 bit | 약 22.9 MB |
1천만 개 아이디를 오류율 1%로 담는 데 11MB 남짓입니다. 실제 문자열을 전부 저장하면 수백 MB가 들 텐데, 그것과 비교하면 압도적으로 작죠. 이 "메모리 대 정확도"의 맞교환이 블룸 필터의 본질입니다.
가장 많이 하는 오해와 함정
- 원소를 삭제할 수 없습니다. 비트를 0으로 되돌리면 그 비트를 공유하던 다른 원소까지 지워버립니다. 삭제가 필요하면 카운팅 블룸 필터(비트 대신 카운터)나 다른 구조를 써야 합니다.
- 원소 개수를 잘못 잡으면 오류율이 무너집니다. n을 100만으로 잡고 설계했는데 실제로 500만을 넣으면, 비트가 대부분 1로 포화되어 "있음" 오답이 폭증합니다.
- 실제 값을 되찾을 수 없습니다. 블룸 필터는 존재 여부만 답하지, 무엇이 들었는지는 모릅니다.
블룸 필터는 "빠르게 거를 수 있는 대부분의 부정 케이스"를 값싸게 쳐내는 앞단 필터로 쓸 때 빛납니다. "있음" 판정이 나오면 그때 비싼 진짜 조회로 확인하면 됩니다.
어디에 실제로 쓰이나
생각보다 도처에 있습니다. Cassandra와 HBase는 SSTable에 키가 없을 때 디스크를 안 읽으려고 블룸 필터를 씁니다. 크롬은 악성 URL 목록의 1차 체크에, CDN은 "한 번만 요청된 콘텐츠는 캐시하지 않기(one-hit-wonder)" 판단에, 비트코인 경량 지갑은 관련 트랜잭션 필터링에 활용했습니다. 공통점은 전부 "값비싼 조회 앞에 값싼 거름망"이라는 패턴입니다.
구현할 때의 현실 팁
직접 만들 일은 많지 않지만, 만들 때 알아두면 좋은 게 있습니다. k개의 독립적인 해시 함수를 진짜로 k번 계산하면 느립니다. 실무에선 이중 해싱(double hashing) 트릭을 씁니다. 좋은 해시 하나를 계산해 상위·하위 절반을 각각 h1, h2로 삼고, h1 + i·h2로 i번째 해시를 값싸게 만들어내는 방식이죠. 이론적으로도 오류율에 거의 영향이 없다는 게 알려져 있어, 널리 쓰입니다.
또 하나, 비트 배열이라 스레드 안전에 신경 써야 합니다. 여러 스레드가 동시에 비트를 켜는 건 원자적 OR라 대체로 안전하지만, 언어·자료구조에 따라 원자성 보장이 다르니 확인이 필요합니다. 대개는 Redis SETBIT이나 검증된 라이브러리(Guava의 BloomFilter 등)를 쓰는 편이 마음 편합니다. 직접 손으로 짠 비트 배열보다 실수가 훨씬 적습니다.
자주 묻는 질문
블룸 필터는 언제 쓰면 안 되나요?
거짓 양성이 치명적인 곳, 즉 오답 하나가 돈이나 안전에 직결되는 최종 판정에는 단독으로 쓰면 안 됩니다. 항상 "있음" 판정 뒤에 정확한 검증을 두거나, 오답을 감내할 수 있는 필터링 용도로만 쓰세요.
해시 함수는 몇 개가 적당한가요?
공식상 최적 k는 (m/n)·ln2 근처입니다. 보통 5~10개 사이가 흔합니다. 실무에선 한 개의 좋은 해시(예: MurmurHash) 결과를 두 조각으로 나눠 여러 해시를 흉내 내는 이중 해싱 기법을 자주 씁니다.
Cuckoo 필터와 뭐가 다른가요?
Cuckoo 필터는 삭제를 지원하고 특정 오류율 구간에선 공간 효율도 더 좋습니다. 대신 구현이 복잡하고 삽입이 실패할 수 있습니다. 삭제가 꼭 필요하면 Cuckoo나 카운팅 블룸 필터를 검토하세요.
분산 환경에서 여러 노드가 공유할 수 있나요?
비트 배열이라 병합(OR 연산)이 쉽습니다. 노드별 필터를 만든 뒤 비트 OR로 합치면 전체 집합의 필터가 됩니다. 이 성질 덕에 분산 집계에도 잘 맞습니다.
댓글 0