블룸 필터

이 사용자명은 이미 사용 중입니다.

회원가입할 때 흔히 보는 이 메시지를 띄우려면, 서버는 수억 개의 기존 사용자명 중에 입력값이 있는지 확인해야 합니다. 해시 테이블을 쓰면 정확하지만 메모리를 많이 먹고, 매번 DB를 조회하면 느립니다. 만약 "아마 있을 것 같다"는 대략적인 답이면 충분하다면 어떨까요?

1970년, Burton Howard Bloom이 정확히 이 질문에 답하는 자료구조를 제안했습니다. 이름은 블룸 필터(Bloom Filter). 거짓 양성(false positive)은 허용하되 거짓 음성(false negative)은 절대 발생하지 않는 확률적 자료구조입니다. 50년이 넘은 아이디어인데, 지금도 구글 빅테이블, 비트코인, 아파치 카산드라, 크롬 브라우저에서 현역으로 뛰고 있습니다.

원문: Bloom, B. H. (1970). "Space/time trade-offs in hash coding with allowable errors." Communications of the ACM, 13(7), 422–426.

핵심 아이디어

블룸 필터의 원리는 놀라울 정도로 단순합니다.

구조: 길이 m인 비트 배열(모두 0으로 초기화)과 k개의 해시 함수.

삽입: 원소를 k개의 해시 함수에 통과시켜 k개의 위치를 얻고, 해당 비트를 1로 설정합니다.

조회: 같은 k개의 해시 함수로 위치를 계산하고, 해당 비트를 확인합니다. - 하나라도 0이면 → 그 원소는 확실히 없습니다 - 모두 1이면 → 그 원소는 아마 있습니다 (거짓 양성 가능)

이게 전부입니다. 원소 자체를 저장하지 않고, 비트만 기록합니다. 그래서 메모리가 극도로 적고, 삽입과 조회 모두 O(k) — 저장된 원소 수에 무관한 상수 시간입니다.

왜 거짓 양성이 생기는가

비트 배열은 유한합니다. 원소를 계속 넣다 보면 점점 많은 비트가 1이 됩니다. 어느 순간, 집합에 없는 원소가 해시를 돌렸을 때 우연히 k개의 위치가 전부 1인 경우가 생깁니다. "다른 원소들이 켜둔 비트"와 우연히 겹치는 것입니다.

하지만 반대 방향은 불가능합니다. 집합에 있는 원소라면, 삽입 시 해당 비트를 전부 1로 켰으므로 조회 시에도 반드시 1입니다. 그래서 거짓 음성은 절대 없습니다.

수학: 얼마나 정확한가

거짓 양성 확률(FPP)은 다음 공식으로 근사합니다:

ε ≈ (1 - e^(-kn/m))^k

• m = 비트 배열 크기
• n = 삽입된 원소 수
• k = 해시 함수 개수

최적 해시 함수 개수

주어진 m과 n에서 거짓 양성을 최소화하는 k의 최적값:

k_opt = (m/n) × ln(2) ≈ 0.693 × (m/n)

필요한 비트 수

목표 거짓 양성률 ε을 달성하려면 원소당 필요한 비트:

m/n ≈ -1.44 × log₂(ε)

구체적으로 보면:

1%의 거짓 양성률을 위해 원소당 약 10비트면 됩니다. 1억 개의 원소를 저장해도 약 120MB — 해시 테이블로 원소 자체를 저장하는 것에 비하면 훨씬 작습니다.

블룸 필터의 특성

정리하면 블룸 필터는 이런 자료구조입니다:

삭제가 안 된다는 점이 가장 큰 제약입니다. 비트를 0으로 끄면 같은 비트를 공유하는 다른 원소까지 "없다"고 답하게 됩니다.

실제 사용 사례

블룸 필터가 50년 넘게 살아남은 이유는 실용성입니다. "아마 있다/확실히 없다"라는 답이면 충분한 상황이 의외로 많습니다.

데이터베이스: 불필요한 디스크 조회 차단

Apache Cassandra와 Google Bigtable은 LSM-tree 기반 저장 엔진을 사용합니다. 키를 조회할 때, 여러 SSTable 파일을 순서대로 확인해야 하는데, 대부분의 SSTable에는 해당 키가 없습니다. 블룸 필터를 각 SSTable에 달아두면, "이 파일에 확실히 없다"는 키에 대해 디스크 I/O를 건너뛸 수 있습니다. Apache HBase도 같은 방식을 씁니다.

웹 브라우저: 악성 URL 차단

Google Chrome은 악성 URL 목록을 블룸 필터로 관리했습니다. 사용자가 URL을 입력하면 먼저 로컬 블룸 필터로 확인합니다. "확실히 없다"면 바로 통과, "아마 있다"면 그때서야 서버에 정확한 확인을 요청합니다. 대부분의 정상 URL은 서버 왕복 없이 즉시 통과됩니다. Mozilla Firefox도 인증서 폐기 확인과 애드온 차단에 블룸 필터를 사용합니다.

CDN: 캐시 오염 방지

Akamai의 연구에 따르면, 일반적인 웹 캐시 URL의 약 75%가 "한 번만 요청되는(one-hit-wonder)" URL입니다. 이런 URL을 전부 캐시하면 캐시가 오염됩니다. 블룸 필터로 "두 번 이상 요청된 적 있는" URL만 캐시에 넣도록 필터링하면, 디스크 쓰기를 거의 절반으로 줄일 수 있었습니다.

블록체인: 지갑 동기화

비트코인 SPV(Simplified Payment Verification) 클라이언트는 전체 블록체인을 다운로드하지 않습니다. 자신의 지갑 주소에 해당하는 트랜잭션만 받으면 되는데, 블룸 필터를 사용해서 관심 있는 주소 집합을 풀 노드에 전달합니다. 풀 노드는 블룸 필터에 매칭되는 트랜잭션만 전송합니다. 이더리움도 블록체인 로그 검색에 블룸 필터를 활용합니다.

추천 시스템: 중복 방지

Medium은 사용자에게 이미 읽은 글을 다시 추천하지 않기 위해 블룸 필터를 사용합니다. 사용자별로 "이미 본 글" 블룸 필터를 유지하면, 추천 후보를 빠르게 필터링할 수 있습니다.

검색 엔진: 인덱싱

Microsoft Bing의 검색 엔진 BitFunnel은 블룸 필터 기반 인덱스 구조를 사용합니다. 문서가 특정 단어를 포함하는지 빠르게 확인하는 데 활용됩니다.

변형: 한계를 극복하려는 시도들

표준 블룸 필터의 가장 큰 한계는 삭제 불가입니다. 이를 해결하려는 다양한 변형이 등장했습니다.

카운팅 블룸 필터 (Counting Bloom Filter)

각 비트 대신 카운터를 사용합니다. 삽입 시 카운터를 증가, 삭제 시 감소. 삭제가 가능해지지만 공간이 3~4배 늘어납니다. 또한 카운터 오버플로우 위험이 있습니다.

쿠쿠 필터 (Cuckoo Filter)

2014년 카네기멜론의 Bin Fan 등이 제안한 구조입니다. 블룸 필터의 실질적 대안으로 주목받고 있습니다.

쿠쿠 필터는 핑거프린트(fingerprint)를 저장하고, 해시 충돌 시 기존 항목을 다른 위치로 밀어내는(cuckoo hashing) 방식을 씁니다. 카운팅 블룸 필터 대비 공간을 약 50% 절감합니다.

스케일러블 블룸 필터 (Scalable Bloom Filter)

표준 블룸 필터는 용량이 고정입니다. 예상보다 많은 원소가 들어오면 거짓 양성률이 급증합니다. 스케일러블 블룸 필터는 용량이 차면 새 필터를 추가하는 방식으로 동적 확장을 지원합니다.

Xor 필터 (Xor Filter)

비교적 최근 등장한 구조로, 정적 집합(한 번 구축하고 변경 없이 조회만)에 최적화되어 있습니다. 원소당 약 1.23 × log₂(1/ε) 비트로, 블룸 필터의 1.44 × log₂(1/ε)보다 공간 효율이 좋습니다.

구현 예시

블룸 필터의 구현은 놀라울 정도로 간단합니다. 파이썬으로 핵심 로직만 보면:

import hashlib

class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size
        self.num_hashes = num_hashes
        self.bit_array = [0] * size

    def _hashes(self, item):
        positions = []
        for i in range(self.num_hashes):
            h = hashlib.md5(f"{item}{i}".encode()).hexdigest()
            positions.append(int(h, 16) % self.size)
        return positions

    def add(self, item):
        for pos in self._hashes(item):
            self.bit_array[pos] = 1

    def might_contain(self, item):
        return all(self.bit_array[pos] for pos in self._hashes(item))

might_contain이라는 이름이 핵심입니다. "포함한다"가 아니라 "포함할 수도 있다"입니다. True가 나와도 100% 확신은 아닙니다. 하지만 False가 나오면 100% 확실합니다.

블룸 필터를 쓸지 말지 판단하기

블룸 필터가 적합한 상황: - "없다"는 확실히 알아야 하지만, "있다"는 대략적이어도 괜찮을 때 - 메모리가 제한적이고, 정확한 멤버십 테스트에 필요한 공간이 너무 클 때 - 비싼 연산(디스크 I/O, 네트워크 요청) 전에 빠른 사전 필터가 필요할 때

블룸 필터가 부적합한 상황: - 거짓 양성을 허용할 수 없을 때 (100% 정확성 필요) - 삭제가 빈번할 때 (쿠쿠 필터를 고려) - 저장된 원소를 열거해야 할 때

50년이 넘은 자료구조가 아직도 최전선에서 쓰이는 경우는 드뭅니다. 블룸 필터가 살아남은 이유는 "완벽하지 않아도 된다"는 트레이드오프를 명시적으로 받아들였기 때문입니다. 정확성을 약간 포기하는 대신 공간과 시간을 극적으로 절약합니다.

흥미로운 점은 이 아이디어가 처음 등장한 맥락입니다. Bloom의 1970년 논문 제목이 "Space/Time Trade-offs in Hash Coding with Allowable Errors"인데, 당시에는 메모리가 킬로바이트 단위였고, 디스크 접근이 극도로 비쌌습니다. 지금은 메모리가 기가바이트 단위이지만, 데이터가 페타바이트 단위가 되면서 같은 트레이드오프가 여전히 유효합니다. 규모만 바뀌었을 뿐, 문제의 본질은 그대로입니다.

쿠쿠 필터나 Xor 필터 같은 후속 구조가 특정 영역에서 블룸 필터를 개선하고 있지만, 블룸 필터의 단순함은 여전히 강력한 장점입니다. 구현이 쉽고, 동작을 이해하기 쉽고, 분석하기 쉽습니다. 시스템 설계에서 "충분히 좋은 해결책"의 가치를 보여주는 교과서적 사례라고 할 수 있습니다.