블룸 필터

블룸 필터
[확률적 자료구조]
영문명	Bloom Filter
제안자	버튼 하워드 블룸 (Burton Howard Bloom)
제안 연도	1970년
분류	확률적 자료구조 (Probabilistic Data Structure)
공간 복잡도	[math]\displaystyle{ O(m) — m }[/math] 비트 배열의 크기
삽입 시간 복잡도	[math]\displaystyle{ O(k) — k }[/math] 해시 함수의 개수
조회 시간 복잡도	[math]\displaystyle{ O(k) }[/math]
오탐률 (False Positive)	존재 (튜닝 가능)
미탐률 (False Negative)	없음 (절대 발생하지 않음)
삭제 지원	기본형은 불가, 변형(Counting Bloom Filter)은 가능

개요

-
“	"어쩌면 존재할 수도, 확실히 존재하지 않는다."	”
	— 블룸 필터의 핵심 철학

블룸 필터(Bloom Filter)는 1970년 버튼 하워드 블룸(Burton Howard Bloom)이 고안한 공간 효율적인 확률적 자료구조(Probabilistic Data Structure)로, 어떤 원소가 집합에 속하는지 여부를 검사(membership test)하는 데 사용된다. 일반적인 해시 테이블과 달리, 블룸 필터는 실제 원소를 저장하지 않고 단지 비트 배열(bit array)만을 유지한다. 이로 인해 공간을 획기적으로 절약할 수 있지만, 특정 확률로 거짓 긍정(False Positive)을 반환할 수 있다는 트레이드오프가 존재한다.

즉, 블룸 필터는 다음 두 가지 답만 반환한다.

• "확실히 없다(Definitely Not)" — 이 경우는 100% 정확하다.
• "아마도 있다(Possibly Yes)" — 이 경우는 틀릴 수도 있다 (거짓 긍정 가능).

이 단순하면서도 강력한 특성 덕분에 블룸 필터는 데이터베이스, 네트워크, 캐시(Cache), 암호화, 분산 시스템 등 무수히 많은 분야에서 핵심 부품으로 사용된다.

개요 및 역사

탄생 배경

1970년, 버튼 하워드 블룸은 Communications of the ACM에 "Space/Time Trade-offs in Hash Coding with Allowable Errors"라는 논문을 발표했다. 이 논문의 제목에서도 알 수 있듯, 블룸 필터는 처음부터 공간(Space)과 시간(Time)의 트레이드오프에 오류(Allowable Errors)를 허용함으로써 기존 해시 코딩의 한계를 극복하고자 설계되었다.

당시의 문제의식은 간단했다. 하이픈 없는 단어(unhyphenated word) 목록과 하이픈이 들어간 단어(hyphenated word) 목록을 메모리에 올려두고, 입력된 단어가 어느 쪽에 속하는지 빠르게 판단해야 하는데, 메모리가 극히 제한적이었다. 모든 단어를 해시 테이블에 넣으면 정확하지만 메모리를 많이 쓰고, 메모리를 아끼면 속도와 정확성을 잃는다. 블룸은 여기서 "약간의 오류를 허용하면 메모리를 극적으로 줄일 수 있다"는 아이디어를 제안했다.

이름의 유래

블룸 필터의 이름은 단순히 발명자인 버튼 블룸(Burton Bloom)의 성(姓)을 딴 것이다. 꽃(bloom)과는 아무 관련이 없다. 영어권에서는 종종 "꽃처럼 피어나는 필터"라는 시적인 표현을 쓰기도 하지만, 이는 완전한 후세의 재해석이다.

위상과 중요성

블룸 필터는 컴퓨터 과학사에서 가장 우아하고 실용적인 자료구조 중 하나로 손꼽힌다. 제안된 지 50년이 넘었지만, 오늘날 Google Chrome, Apache Cassandra, PostgreSQL, Redis, Bitcoin, Ethereum 등 세계적인 소프트웨어들이 블룸 필터를 핵심 구성요소로 채택하고 있다. 이는 블룸 필터의 아이디어가 시대를 초월한 보편성을 가짐을 증명한다.

핵심 원리

구성 요소

블룸 필터는 두 가지 핵심 구성요소로 이루어진다.

비트 배열 (Bit Array)

크기 m인 비트 배열(또는 비트 벡터)을 유지한다. 초기에는 모든 비트가 0으로 설정된다.

초기 상태 (m = 10):
인덱스: [0][1][2][3][4][5][6][7][8][9]
값:      [0][0][0][0][0][0][0][0][0][0]

해시 함수들 (Hash Functions)

k개의 서로 다른(독립적인) 해시 함수들을 사용한다. 각 해시 함수는 임의의 원소를 입력으로 받아 {0, 1, ..., m-1} 범위의 인덱스를 반환한다. 이 해시 함수들은:

• 서로 독립적이어야 한다.
• 출력이 비트 배열 전체에 균일하게 분포해야 한다.
• 빠르게 계산될 수 있어야 한다.

실제로는 MurmurHash, FNV Hash, xxHash 같은 비암호화 해시 함수가 자주 쓰이며, 하나의 해시 함수에 서로 다른 시드(seed)를 주어 k개를 흉내내는 기법도 사용된다.

동작 원리

삽입 (Insert)

원소 x를 블룸 필터에 추가하려면:

1. k개의 해시 함수 h₁, h₂, ..., hₖ 각각에 x를 입력한다.
2. 각 해시 함수가 반환하는 인덱스 h₁(x), h₂(x), ..., hₖ(x)에 해당하는 비트를 모두 1로 설정한다.

예시: m=10, k=3, 원소 "apple" 삽입
h1("apple") = 2  →  비트[2] = 1
h2("apple") = 5  →  비트[5] = 1
h3("apple") = 8  →  비트[8] = 1

인덱스: [0][1][2][3][4][5][6][7][8][9]
값:      [0][0][1][0][0][1][0][0][1][0]

이어서 "banana"를 삽입하면:

h1("banana") = 1  →  비트[1] = 1
h2("banana") = 5  →  비트[5] = 1  (이미 1)
h3("banana") = 7  →  비트[7] = 1

인덱스: [0][1][2][3][4][5][6][7][8][9]
값:      [0][1][1][0][0][1][0][1][1][0]

조회 (Query / Lookup)

원소 y가 집합에 있는지 확인하려면:

1. k개의 해시 함수 각각에 y를 입력한다.
2. h₁(y), h₂(y), ..., hₖ(y)에 해당하는 비트를 모두 확인한다.
3. 하나라도 0이면 → "확실히 없다(Definitely Not)" 반환.
4. 모두 1이면 → "아마도 있다(Possibly Yes)" 반환.

"apple" 조회:
h1("apple") = 2  →  비트[2] = 1 ✓
h2("apple") = 5  →  비트[5] = 1 ✓
h3("apple") = 8  →  비트[8] = 1 ✓
→  결과: "아마도 있다" (실제로 삽입했으므로 정확)

"cherry" 조회 (삽입 안 함):
h1("cherry") = 1  →  비트[1] = 1 ✓
h2("cherry") = 5  →  비트[5] = 1 ✓
h3("cherry") = 9  →  비트[9] = 0 ✗
→  결과: "확실히 없다" (정확)

"grape" 조회 (삽입 안 함):
h1("grape") = 1  →  비트[1] = 1 ✓
h2("grape") = 5  →  비트[5] = 1 ✓
h3("grape") = 7  →  비트[7] = 1 ✓
→  결과: "아마도 있다" (거짓 긍정! 실제로는 없음)

"grape"의 경우처럼, 우연히 다른 원소들에 의해 해당 비트들이 모두 1이 되어 있으면 거짓 긍정(False Positive)이 발생한다. 이것이 블룸 필터의 본질적인 한계이자, 공간을 아끼기 위해 치르는 대가다.

삭제 불가

기본 블룸 필터는 원소를 삭제할 수 없다. 만약 특정 원소에 해당하는 비트를 0으로 되돌리면, 같은 비트를 공유하던 다른 원소의 정보도 손상되기 때문이다. 예를 들어 위 예시에서 비트[5]는 "apple"과 "banana" 둘 다 사용하고 있는데, "apple"을 삭제하겠다고 비트[5]를 0으로 만들면 "banana"도 조회되지 않게 된다.

이 문제를 해결한 변형이 카운팅 블룸 필터다.

거짓 긍정률 (False Positive Rate) 수학적 분석

단일 비트가 0일 확률

크기 m인 비트 배열에 k개의 해시 함수로 n개의 원소를 삽입했을 때, 특정 비트가 여전히 0일 확률을 계산한다.

하나의 해시 함수가 특정 비트를 설정하지 않을 확률 = [math]\displaystyle{ (1 - 1/m) }[/math]

k개의 해시 함수가 모두 해당 비트를 설정하지 않을 확률 = [math]\displaystyle{ (1 - 1/m)^k }[/math]

n개의 원소를 삽입한 후에도 해당 비트가 0일 확률:

[math]\displaystyle{ P(bit = 0) = (1 - 1/m)^(kn) ≈ e^(-kn/m) }[/math]

거짓 긍정률 계산

새 원소를 조회할 때, [math]\displaystyle{ k }[/math]개의 비트가 모두 1일 확률 (즉 거짓 긍정률 ε):

[math]\displaystyle{ ε ≈ (1 - e^(-kn/m))^k }[/math]

이 식에서 중요한 사실을 알 수 있다.

• m이 클수록 (비트 배열이 클수록) → ε 감소 (오탐 줄어듦)
• n이 클수록 (원소 수가 많을수록) → ε 증가 (오탐 늘어남)
• k가 너무 작으면 → 구별력이 없어짐 → ε 증가
• k가 너무 크면 → 비트가 빠르게 포화됨 → ε 증가
• k에 최적값이 존재함

최적 해시 함수 개수

[math]\displaystyle{ ε }[/math]를 최소화하는 최적의 [math]\displaystyle{ k }[/math] 값은 미분을 통해 구할 수 있다:

[math]\displaystyle{ k_opt = (m/n) × ln(2) ≈ 0.693 × (m/n) }[/math]

이 최적 [math]\displaystyle{ k }[/math]를 사용하면 거짓 긍정률이:

[math]\displaystyle{ ε_opt ≈ (1/2)^k = 0.5^k = (0.6185)^(m/n) }[/math]

비트 배열 크기 설계

원하는 오탐률 [math]\displaystyle{ ε }[/math]와 예상 원소 수 [math]\displaystyle{ n }[/math]이 주어졌을 때 필요한 최소 비트 배열 크기 m:

[math]\displaystyle{ m = -(n × ln(ε)) / (ln(2))² ≈ -(n × ln(ε)) / 0.4805 }[/math]

실용적인 수치 예시:

원소 수 (n)	오탐률 (ε)	비트 배열 크기 (m)	해시 함수 수 (k)	원소당 비트 수
1,000,000	1%	9,585,060 bit (~1.14 MB)	7	약 9.58 bit
1,000,000	0.1%	14,377,590 bit (~1.71 MB)	10	약 14.38 bit
1,000,000	0.01%	19,170,120 bit (~2.28 MB)	13	약 19.17 bit
1,000,000	0.001%	23,962,650 bit (~2.85 MB)	17	약 23.96 bit
10,000,000	1%	95,850,584 bit (~11.4 MB)	7	약 9.58 bit

일반적인 해시 테이블에서 백만 개의 문자열을 저장하면 수백 MB가 필요한 것과 비교하면, 블룸 필터의 공간 절약 효과가 극적임을 알 수 있다.

구현

Python 구현

import math
import hashlib
from bitarray import bitarray

class BloomFilter:
    """
    기본 블룸 필터 구현
    """
    def __init__(self, n: int, fp_rate: float = 0.01):
        """
        Parameters
        <hr>
        n       : 예상 원소 개수
        fp_rate : 허용 거짓 긍정률 (기본값 1%)
        """
        self.n = n
        self.fp_rate = fp_rate

        # 최적 비트 배열 크기 계산
        self.m = self._optimal_m(n, fp_rate)
        # 최적 해시 함수 개수 계산
        self.k = self._optimal_k(self.m, n)

        self.bit_array = bitarray(self.m)
        self.bit_array.setall(0)
        self.count = 0

        print(f"BloomFilter 초기화: m={self.m} bits, k={self.k} hash functions")

    @staticmethod
    def _optimal_m(n: int, fp_rate: float) -> int:
        """최적 비트 배열 크기"""
        m = -(n * math.log(fp_rate)) / (math.log(2) ** 2)
        return int(math.ceil(m))

    @staticmethod
    def _optimal_k(m: int, n: int) -> int:
        """최적 해시 함수 개수"""
        k = (m / n) * math.log(2)
        return max(1, int(round(k)))

    def _hash_indices(self, item: str):
        """k개의 해시 인덱스 생성 (double hashing 기법)"""
        # SHA-256으로 두 개의 기본 해시 생성
        h = hashlib.sha256(item.encode('utf-8')).digest()
        h1 = int.from_bytes(h[:8], 'big')
        h2 = int.from_bytes(h[8:16], 'big')

        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item: str):
        """원소 추가"""
        for idx in self._hash_indices(item):
            self.bit_array[idx] = 1
        self.count += 1

    def contains(self, item: str) -> bool:
        """
        원소 포함 여부 조회
        Returns
        <hr>
        False : 확실히 없음
        True  : 아마도 있음 (거짓 긍정 가능)
        """
        return all(self.bit_array[idx] for idx in self._hash_indices(item))

    def __contains__(self, item: str) -> bool:
        return self.contains(item)

    def estimated_fp_rate(self) -> float:
        """현재 채워진 상태에서의 추정 오탐률"""
        return (1 - math.exp(-self.k * self.count / self.m)) ** self.k

    def fill_ratio(self) -> float:
        """비트 배열에서 1인 비율"""
        return self.bit_array.count(1) / self.m


# === 사용 예시 ===
if __name__ == "__main__":
    bf = BloomFilter(n=1_000_000, fp_rate=0.01)

    # 데이터 삽입
    words = ["apple", "banana", "cherry", "date", "elderberry"]
    for word in words:
        bf.add(word)

    # 조회 테스트
    test_cases = ["apple", "banana", "grape", "mango", "cherry"]
    for word in test_cases:
        result = "아마도 있음" if word in bf else "확실히 없음"
        print(f"  '{word}': {result}")

    print(f"\n현재 추정 오탐률: {bf.estimated_fp_rate():.6%}")
    print(f"비트 배열 충전률: {bf.fill_ratio():.4%}")

Java 구현

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

public class BloomFilter {
    private final int m;          // 비트 배열 크기
    private final int k;          // 해시 함수 개수
    private final BitSet bitSet;
    private int count;

    public BloomFilter(int n, double fpRate) {
        this.m = optimalM(n, fpRate);
        this.k = optimalK(m, n);
        this.bitSet = new BitSet(m);
        this.count = 0;
        System.out.printf("BloomFilter: m=%d bits, k=%d hash functions%n", m, k);
    }

    private static int optimalM(int n, double fpRate) {
        return (int) Math.ceil(-(n * Math.log(fpRate)) / (Math.log(2) * Math.log(2)));
    }

    private static int optimalK(int m, int n) {
        return Math.max(1, (int) Math.round(((double) m / n) * Math.log(2)));
    }

    private int[] hashIndices(String item) {
        int[] indices = new int[k];
        try {
            MessageDigest md = MessageDigest.getInstance("SHA-256");
            byte[] digest = md.digest(item.getBytes(StandardCharsets.UTF_8));

            long h1 = bytesToLong(digest, 0);
            long h2 = bytesToLong(digest, 8);

            for (int i = 0; i < k; i++) {
                indices[i] = (int) Math.floorMod(h1 + (long) i * h2, m);
            }
        } catch (NoSuchAlgorithmException e) {
            throw new RuntimeException(e);
        }
        return indices;
    }

    private long bytesToLong(byte[] bytes, int offset) {
        long val = 0;
        for (int i = 0; i < 8; i++) {
            val = (val << 8) | (bytes[offset + i] & 0xFF);
        }
        return val;
    }

    public void add(String item) {
        for (int idx : hashIndices(item)) {
            bitSet.set(idx);
        }
        count++;
    }

    public boolean mightContain(String item) {
        for (int idx : hashIndices(item)) {
            if (!bitSet.get(idx)) return false;
        }
        return true;
    }

    public double estimatedFpRate() {
        return Math.pow(1 - Math.exp(-(double) k * count / m), k);
    }

    // 사용 예시
    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(1_000_000, 0.01);

        bf.add("hello");
        bf.add("world");
        bf.add("java");

        System.out.println(bf.mightContain("hello")); // true
        System.out.println(bf.mightContain("python")); // false (높은 확률로)
        System.out.printf("추정 오탐률: %.6f%%%n", bf.estimatedFpRate() * 100);
    }
}

JavaScript / TypeScript 구현

import * as crypto from 'crypto';

class BloomFilter {
  private readonly m: number;
  private readonly k: number;
  private readonly bitArray: Uint8Array;
  private count: number = 0;

  constructor(n: number, fpRate: number = 0.01) {
    this.m = BloomFilter.optimalM(n, fpRate);
    this.k = BloomFilter.optimalK(this.m, n);
    this.bitArray = new Uint8Array(Math.ceil(this.m / 8));
    console.log(`BloomFilter: m=${this.m} bits, k=${this.k} hash functions`);
  }

  private static optimalM(n: number, fpRate: number): number {
    return Math.ceil(-(n * Math.log(fpRate)) / (Math.LN2 ** 2));
  }

  private static optimalK(m: number, n: number): number {
    return Math.max(1, Math.round((m / n) * Math.LN2));
  }

  private getBit(index: number): boolean {
    return (this.bitArray[index >> 3] & (1 << (index & 7))) !== 0;
  }

  private setBit(index: number): void {
    this.bitArray[index >> 3] |= (1 << (index & 7));
  }

  private *hashIndices(item: string): Generator<number> {
    const hash = crypto.createHash('sha256').update(item, 'utf8').digest();
    const h1 = hash.readBigUInt64BE(0);
    const h2 = hash.readBigUInt64BE(8);
    for (let i = 0; i < this.k; i++) {
      yield Number((h1 + BigInt(i) * h2) % BigInt(this.m));
    }
  }

  add(item: string): void {
    for (const idx of this.hashIndices(item)) {
      this.setBit(idx);
    }
    this.count++;
  }

  has(item: string): boolean {
    for (const idx of this.hashIndices(item)) {
      if (!this.getBit(idx)) return false;
    }
    return true;
  }

  estimatedFpRate(): number {
    return Math.pow(1 - Math.exp(-this.k * this.count / this.m), this.k);
  }
}

// 사용 예시
const bf = new BloomFilter(1_000_000, 0.01);
bf.add("TypeScript");
bf.add("BloomFilter");
console.log(bf.has("TypeScript"));    // true
console.log(bf.has("JavaScript"));   // 아마도 false
console.log(`오탐률: ${(bf.estimatedFpRate() * 100).toFixed(6)}%`);

변형 및 확장

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

기본 블룸 필터의 삭제 불가 문제를 해결하기 위해, 1998년 Li Fan 등이 제안한 변형이다. 비트(0/1) 대신 각 슬롯에 카운터(counter)를 저장한다.

동작	기본 블룸 필터	카운팅 블룸 필터
삽입	비트를 1로 설정	해당 카운터 +1
삭제	불가능	해당 카운터 -1 (0 미만이면 무시)
조회	비트가 모두 1인지 확인	카운터가 모두 0 초과인지 확인
공간	m bits	m × (카운터 비트 수), 보통 4~8배

카운터 오버플로우(overflow) 문제가 있어 보통 4비트(최대 15까지 카운트) 카운터를 사용하며, 오버플로우 발생 시 더 이상 감소시키지 않는 처리가 필요하다.

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

기본 블룸 필터의 단점 중 하나는 미리 원소 수(n)를 알아야 m과 k를 결정할 수 있다는 점이다. 스케일러블 블룸 필터는 여러 개의 블룸 필터를 계층적으로 쌓아, 현재 필터가 가득 차면 새 필터를 추가하는 방식으로 동적 확장을 지원한다.

• 각 단계마다 오탐률 목표를 tighter하게 설정 (예: 0.01, 0.001, 0.0001...)
• 전체 오탐률은 각 단계 오탐률의 합으로 bounded됨
• 공간 효율은 약간 감소하지만, 사전 크기 지정 불필요

압축 블룸 필터 (Compressed Bloom Filter)

마이클 미첸마허(Michael Mitzenmacher)가 2002년 제안한 변형으로, 블룸 필터의 비트 배열을 산술 부호화(Arithmetic Coding)나 Golomb 부호화로 압축하여 네트워크 전송 효율을 높인다. 비트 배열이 희소(sparse)하거나 조밀(dense)할수록 압축률이 높아진다.

블룸 필터의 집합 연산

같은 m과 k를 공유하는 두 블룸 필터 A, B에 대해:

• 합집합(Union): A OR B — 두 비트 배열을 비트 OR 연산 → [math]\displaystyle{ A ∪ B }[/math]를 나타내는 블룸 필터
• 교집합(Intersection) 근사: A AND B — 두 비트 배열을 비트 AND 연산 → [math]\displaystyle{ A ∩ B }[/math]를 근사

단, 교집합 연산은 오탐률이 증가하는 단점이 있다.

스펙트럼 블룸 필터 (Spectral Bloom Filter)

원소의 존재 여부뿐만 아니라 빈도수(multiplicity)까지 추정할 수 있는 확장형이다. 카운팅 블룸 필터를 기반으로 하며, 각 원소의 최소 카운터 값을 빈도수 추정값으로 사용한다. 스트리밍 알고리즘의 Count-Min Sketch와 개념적으로 유사하다.

쿠쿠 필터 (Cuckoo Filter)

2014년 Fan et al.이 제안한 자료구조로, 블룸 필터의 직접적인 경쟁자다. 쿠쿠 해싱 기반으로 구현되며:

특성	블룸 필터	쿠쿠 필터
삭제 지원	기본형 불가	가능
조회 성능	[math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(1) }[/math] (최적)
공간 효율	우수	비슷하거나 약간 더 우수
구현 복잡도	간단	복잡
최대 부하율	~50% (1개 버킷)	~98% (2개 버킷)

낮은 오탐률(< 3%)에서는 쿠쿠 필터가 공간 효율적으로 블룸 필터를 능가한다고 알려져 있다.

XOR 필터 (XOR Filter)

2019년 Graf and Lemire가 제안한 최신 변형. 정적(static) 집합에 대해 구성되며, 쿼리 시 XOR 연산만 사용하여 매우 빠르고 메모리 효율적이다. 단, 집합이 변경되면 필터를 완전히 재구성해야 한다.

Ribbon 필터

2021년 발표된 가장 최신 변형 중 하나. Random Linear Systems를 기반으로 하며 이론적으로 매우 높은 공간 효율을 보인다. RocksDB 같은 실용 시스템에 채택되기 시작하고 있다.

Learned Bloom Filter

2018년 Google Brain의 Tim Kraska 등이 제안한 머신러닝 기반 변형. 신경망 모델이 원소의 패턴을 학습하여 더 작은 공간으로 낮은 오탐률을 달성한다. 모델이 "아마도 있다"고 판단하는 원소에 대해서만 전통적인 블룸 필터로 재확인하는 하이브리드 구조다.

실제 활용 사례

블룸 필터는 수많은 실제 시스템에서 핵심 구성요소로 사용된다. 아래는 대표적인 사례들이다.

데이터베이스

Apache Cassandra

Apache Cassandra는 LSM 트리(Log-Structured Merge Tree) 기반 스토리지 엔진을 사용한다. 데이터를 조회할 때 해당 키가 어떤 SSTable에 있는지 알아야 하는데, SSTable이 수십~수백 개일 수 있다. 블룸 필터를 각 SSTable마다 유지함으로써, 해당 키가 없는 SSTable은 디스크 I/O 없이 즉시 건너뛴다.

효과: 읽기 연산의 불필요한 디스크 접근을 수십~수백 배 줄임.

Apache HBase

HBase에서도 유사하게 StoreFile(HFile)마다 블룸 필터를 생성하여 읽기 성능을 향상시킨다. Get 연산과 존재하지 않는 키 조회 시 특히 효과적이다.

PostgreSQL

PostgreSQL 13부터 Bloom Index를 정식 지원한다. 여러 컬럼에 대한 동등 조건(equality condition) 쿼리에서 불필요한 힙 페이지 접근을 줄이는 데 사용된다. 다중 컬럼 동등 조건이 많은 데이터 웨어하우스 쿼리에서 유용하다.

LevelDB / RocksDB

Google이 개발하고 Meta가 확장한 키-값 스토어. SST 파일마다 블룸 필터를 유지하며, 최신 RocksDB는 블룸 필터 대신 Ribbon 필터도 선택할 수 있다.

네트워크

패킷 라우팅

고속 네트워크 라우터에서 이미 처리한 패킷 ID를 블룸 필터에 기록하여 중복 패킷 처리를 방지한다. 메모리가 제한적인 네트워크 장비에서 특히 유용하다.

P2P 네트워크

BitTorrent 같은 P2P 네트워크에서 피어(peer)가 어떤 청크(chunk)를 보유하고 있는지 블룸 필터로 광고함으로써, 불필요한 데이터 요청을 줄인다. 전체 보유 목록을 전송하는 것보다 훨씬 적은 대역폭을 소비한다.

CDN과 캐시

Akamai 등의 CDN에서 단 한 번만 요청된 객체(one-hit wonder)를 식별하여 캐시 오염(cache pollution)을 방지한다. 블룸 필터에 요청 URL을 기록하고, 두 번째 요청 시에만 실제 캐시에 저장하는 방식이다. 이 기법으로 Akamai는 캐시 효율을 크게 향상시켰다고 발표했다.

웹 브라우저

Google Chrome의 Safe Browsing

Google Chrome은 악성 URL 목록(피싱, 멀웨어 배포 등)을 블룸 필터로 로컬에 저장한다. 사용자가 URL을 방문하려 할 때:

1. 로컬 블룸 필터를 조회한다.
2. 확실히 없음 → 안전한 URL, 네트워크 요청 불필요.
3. 아마도 있음 → Google 서버에 실제 확인 요청.

전체 악성 URL 목록이 수천만 건임에도, 로컬 블룸 필터는 수 MB에 불과하다. 네트워크 요청을 대부분 생략할 수 있어 프라이버시도 보호되고 성능도 향상된다.

블록체인 및 암호화폐

Bitcoin SPV (Simplified Payment Verification)

Bitcoin BIP-37에 정의된 블룸 필터 프로토콜은 경량 클라이언트(SPV 클라이언트)가 전체 블록체인을 다운로드하지 않고도 자신과 관련된 트랜잭션만 필터링하여 받을 수 있도록 한다. 클라이언트는 관심 있는 주소들로 구성된 블룸 필터를 풀 노드에 전송하고, 풀 노드는 해당 필터를 통과하는 트랜잭션만 전달한다.

단, 블룸 필터가 지갑 주소를 어느 정도 노출한다는 프라이버시 우려로 인해 이후 Compact Block Filters(BIP-157/158)로 대체 추세다.

스팸 필터링

이메일 스팸 필터에서 알려진 스팸 발신자 주소나 스팸 키워드 목록을 블룸 필터에 저장하여 빠른 선별 처리가 가능하다. 거짓 긍정(정상 메일을 스팸으로 오인)이 발생할 수 있으나, 오탐률을 충분히 낮게 설정하면 실용적이다.

분산 시스템

캐시 관통(Cache Penetration) 방지

Redis, Memcached 같은 분산 캐시 앞단에 블룸 필터를 두어 캐시 관통(Cache Penetration)을 방지한다. 데이터베이스에도 없는 키에 대한 요청이 반복될 때, 블룸 필터가 "확실히 없음"을 반환하여 DB까지의 불필요한 요청을 차단한다.

Google Bigtable

Google Bigtable의 SSTable 구현에서 블룸 필터를 사용하여 읽기 성능을 향상시킨다. 이는 후에 Cassandra, HBase 등이 채택한 패턴의 원형이다.

생물정보학 (Bioinformatics)

DNA 염기서열 분석에서 대규모 k-mer 집합(게놈 데이터에서 추출한 길이 k의 부분 문자열)의 존재 여부를 빠르게 확인하는 데 블룸 필터가 사용된다. 단일 게놈의 k-mer 수가 수십억 개에 달할 수 있어, 메모리 효율이 결정적이다. Jellyfish, Khmer, Squeakr 같은 생물정보학 도구들이 블룸 필터를 핵심으로 사용한다.

추천 시스템

이미 사용자에게 추천한 아이템을 블룸 필터에 기록하여, 중복 추천을 방지한다. 수억 명의 사용자 × 수억 개의 아이템 조합을 모두 정확히 저장하면 엄청난 공간이 필요하지만, 블룸 필터를 사용하면 몇 MB 수준으로 관리할 수 있다.

성능 비교

공간 복잡도 비교

자료구조	100만 항목 저장 시 메모리	오탐률
HashSet (Java)	~50 MB	0% (완전 정확)
HashSet (Python)	~100~200 MB	0% (완전 정확)
트라이(Trie)	~10~50 MB (문자열 길이 의존)	0%
블룸 필터 (1% 오탐)	~1.14 MB	1%
블룸 필터 (0.1% 오탐)	~1.71 MB	0.1%
블룸 필터 (0.01% 오탐)	~2.28 MB	0.01%

시간 복잡도 비교

자료구조	삽입	조회	삭제
블룸 필터	O(k)	O(k)	불가 (기본형)
해시 테이블	O(1) 평균	O(1) 평균	O(1) 평균
BST/RBT	O(log n)	O(log n)	O(log n)
트라이	O(L) (L: 길이)	O(L)	O(L)

블룸 필터의 k는 보통 7~17 사이의 작은 상수이므로, 실질적으로 O(1)에 가깝다.

한계점 및 주의사항

거짓 긍정의 불가피성

블룸 필터는 구조적으로 거짓 긍정을 피할 수 없다. 오탐률을 0으로 만들려면 m을 무한히 크게 해야 하는데, 그러면 블룸 필터의 의미가 없다. 따라서 오탐이 허용되는 상황에서만 사용해야 한다. 오탐이 허용되지 않는 금융 거래 원장, 의료 기록 등에는 부적합하다.

삭제 불가 (기본형)

기본 블룸 필터는 원소를 삭제할 수 없다. 삭제가 필요하다면 카운팅 블룸 필터나 쿠쿠 필터를 고려해야 한다.

원소 개수 사전 추정 필요

비트 배열 크기 m을 결정하려면 예상 원소 수 n을 미리 알아야 한다. n을 과소추정하면 오탐률이 급격히 증가한다. 동적으로 성장하는 집합에는 스케일러블 블룸 필터를 사용해야 한다.

원소 열거 불가

블룸 필터는 어떤 원소가 삽입되었는지 열거(enumerate)할 수 없다. 비트 배열에서 원래 데이터를 복원하는 것은 불가능하다.

해시 함수 품질 의존성

나쁜 해시 함수(클러스터링, 편향된 분포)를 사용하면 실제 오탐률이 이론값보다 훨씬 높아진다. 균일하고 독립적인 해시 함수의 선택이 중요하다.

비트 배열 포화 (Saturation)

n을 크게 초과하여 원소를 삽입하면 비트 배열이 거의 모두 1이 되어(포화 상태), 오탐률이 100%에 가까워진다. 이 경우 블룸 필터는 완전히 무용지물이 된다.

보안 취약성

일반 해시 함수를 사용할 경우, 공격자가 블룸 필터의 내부 상태를 이용하여 거짓 긍정을 의도적으로 유발하는 HashDoS 공격을 시도할 수 있다. 보안이 중요한 환경에서는 SipHash 같은 키드(keyed) 해시 함수를 사용하거나 무작위 시드를 적용해야 한다.

설계 가이드라인

파라미터 결정 순서

실제로 블룸 필터를 설계할 때의 권장 순서:

1. 예상 원소 수(n) 추정: 최대치로 넉넉하게 잡을 것. 나중에 넘기면 오탐률 폭등.
2. 허용 오탐률(ε) 결정: 애플리케이션 특성에 따라. 캐시 보조용이면 1~5%, 안전 여부 확인이면 0.01% 이하.
3. 공식으로 m 계산: [math]\displaystyle{ m = -(n × ln ε) / (ln 2)^2 }[/math]
4. 공식으로 k 계산: [math]\displaystyle{ k = (m/n) × ln 2 }[/math]
5. 메모리/성능 절충 확인: k가 너무 크면 해시 계산 비용 증가.
6. 여유 마진 추가: n을 20~50% 더 크게 잡으면 안전.

오탐률과 공간의 트레이드오프

오탐률을 10배 낮추면(예: 1% → 0.1%) 필요한 비트 배열 크기는 약 1.5배 증가한다. 오탐률 ε와 비트 수 m/n 사이의 관계는 로그적(logarithmic)이므로, 오탐률을 극단적으로 낮추려 할수록 필요한 공간이 빠르게 증가한다.

해시 함수 선택 가이드

실무에서 자주 쓰이는 해시 함수:

해시 함수	속도	분포 품질	암호화 여부	주요 용도
MurmurHash3	매우 빠름	우수	X	일반 목적, 비보안
xxHash	최고 속도	우수	X	고성능 시스템
FNV-1a	빠름	양호	X	임베디드, 간단 구현
SipHash	중간	우수	보안 해시	DoS 방지 필요 시
SHA-256	느림	완벽	O (암호화)	보안 중요 환경

블룸 필터에서 k개의 해시 함수를 별도로 구현하는 대신, 하나의 해시로 두 개의 64비트 값을 만들고 이중 해싱(double hashing) 기법으로 k개를 파생시키는 것이 일반적이다:

[math]\displaystyle{ h_i(x) = (h1(x) + i × h2(x)) mod m }[/math]

이 기법은 실제로 k개의 완전히 독립적인 해시 함수와 유사한 성능을 내면서 구현이 훨씬 간단하다.

블룸 필터 관련 이론

정보 이론적 하한

n개의 원소로 이루어진 집합을 u개의 가능한 원소 공간에서 표현하되, 거짓 긍정률 ε를 허용할 때, 필요한 최소 비트 수는 정보 이론적으로:

[math]\displaystyle{ n × log₂(1/ε) bits }[/math]

블룸 필터의 최적 m은 이 값의 약 1/ln(2) ≈ 1.44배다. 즉, 블룸 필터는 이론적 하한 대비 약 44% 더 많은 공간을 사용한다. 이 비효율은 블룸 필터가 비적응적(non-adaptive) 구조이기 때문이며, 최적 부호화를 사용하는 이론적 구조로는 하한에 도달할 수 있지만 실제 구현은 훨씬 복잡해진다.

로딩 팩터(Loading Factor)와 오탐률의 관계

비트 배열에서 1인 비트의 비율을 로딩 팩터(f)라 할 때:

[math]\displaystyle{ f ≈ 1 - e^(-kn/m) }[/math]

최적 k에서 [math]\displaystyle{ f ≈ 0.5 }[/math], 즉 절반의 비트가 1로 설정된다. 이는 직관적으로도 납득 가능하다: 비트가 너무 드물면(낮은 f) 해시 충돌이 적어 좋지만 공간 낭비, 너무 촘촘하면(높은 f) 거짓 긍정 폭증. 최적은 50% 충전이다.

독립성 가정과 현실

블룸 필터의 이론적 오탐률 계산은 해시 함수들이 완전히 독립적이고 균일하게 분포한다고 가정한다. 실제 해시 함수들은 이 조건을 완벽히 만족하지 않으므로, 실제 오탐률이 이론값과 약간 다를 수 있다. 그러나 좋은 품질의 해시 함수를 사용하면 이 차이는 무시할 만한 수준이다.

관련 자료구조와 비교

블룸 필터 vs 해시 테이블

항목	블룸 필터	해시 테이블
목적	멤버십 테스트만	저장 + 조회 + 수정
공간	매우 작음	큼 (실제 데이터 저장)
정확도	거짓 긍정 가능	완전 정확
원소 열거	불가	가능
삭제	기본형 불가	가능
원소 복원	불가	가능

블룸 필터 vs Count-Min Sketch

Count-Min Sketch는 블룸 필터와 비슷한 개념의 확률적 자료구조로, 원소의 빈도수(frequency)를 근사 추정한다.

항목	블룸 필터	Count-Min Sketch
질문 유형	"있냐 없냐" (멤버십)	"몇 번 나왔냐" (빈도)
오류 유형	거짓 긍정 (과대 추정)	빈도 과대 추정
공간	O(m) 비트	O(d × w) 정수
주요 용도	집합 멤버십	스트림 빈도 추정

블룸 필터 vs HyperLogLog

HyperLogLog는 집합의 원소 개수(cardinality)를 근사 추정하는 자료구조다. 블룸 필터가 "이 원소가 집합에 있는가?"를 묻는다면, HyperLogLog는 "이 집합에 몇 개의 원소가 있는가?"를 묻는다.

블룸 필터 vs MinHash

MinHash(=MinWise Hashing)는 두 집합의 자카드 유사도(Jaccard Similarity)를 추정하는 자료구조다. LSH(Locality-Sensitive Hashing)의 기반이 된다. 블룸 필터와는 목적이 다르다.

구현 라이브러리

Python

• pybloom-live — 기본 블룸 필터 + 스케일러블 블룸 필터
• bloom-filter2 — 파이썬 블룸 필터 구현
• probables — 블룸 필터, 카운팅 블룸 필터, Count-Min Sketch 등을 포함한 확률적 자료구조 라이브러리

Java

• Google Guava — com.google.common.hash.BloomFilter 클래스 내장
• Orestes-Bloomfilter — Redis 연동 분산 블룸 필터 지원
• Apache Commons Collections — 블룸 필터 구현 포함

Go

• bloom (willf/bloom) — 표준적인 Go 블룸 필터 구현
• cuckoofilter — 쿠쿠 필터 구현

Rust

• bloomfilter crate — Rust 블룸 필터
• cuckoofilter crate — Rust 쿠쿠 필터

C++

• Boost C++ Libraries — boost::bloom_filter 내장
• libbloom — C 라이브러리 (C++에서도 사용 가능)

Redis (RedisBloom / Redis Stack)

Redis의 공식 모듈 RedisBloom은 블룸 필터, 카운팅 블룸 필터, 쿠쿠 필터, Count-Min Sketch, Top-K, HyperLogLog 등을 Redis 명령어로 제공한다.

# RedisBloom 사용 예시
BF.ADD myfilter "hello"        # 삽입
BF.EXISTS myfilter "hello"     # 조회 → 1 (아마도 있음)
BF.EXISTS myfilter "world"     # 조회 → 0 (확실히 없음)
BF.MADD myfilter "a" "b" "c"   # 다중 삽입
BF.INFO myfilter               # 필터 정보 조회

기타

• 블룸 필터는 1970년에 제안되었지만, 그 진가를 인정받은 것은 인터넷과 빅데이터 시대가 온 이후다. 50년이 지난 지금도 현역이다.

• 블룸 필터는 "거짓말쟁이 필터"라고도 불린다. "있다"고 할 때는 거짓말일 수 있지만, "없다"고 할 때는 절대 거짓말하지 않기 때문이다.

• Google Chrome의 Safe Browsing 기능 덕분에 전 세계 수십억 명의 브라우저에 블룸 필터가 탑재되어 있다. 아마 블룸 필터는 세계에서 가장 많이 배포된 자료구조 중 하나일 것이다.

• Bitcoin의 SPV 클라이언트에서 블룸 필터가 사용되었지만, 프라이버시 문제(지갑 주소 노출 가능성)가 있어 개선된 방식으로 대체되고 있다. 이는 블룸 필터의 확률적 특성이 때로는 의도치 않은 정보 누출로 이어질 수 있음을 보여준다.

• 블룸 필터의 비트 배열이 최적 상태(50% 충전)일 때, 외부에서 보면 완전한 무작위 비트 열처럼 보인다. 이는 어떤 원소가 들어있는지 비트 배열만 보고는 알 수 없음을 의미한다(물론 해시 함수를 알고 있다면 다르다).

• 확률적 자료구조 계열로 블룸 필터(멤버십), Count-Min Sketch(빈도), HyperLogLog(카디널리티), MinHash(유사도)가 있으며, 이 네 가지를 합쳐서 빅데이터 4총사라고 비공식적으로 부르기도 한다.

• 블룸 필터는 역설적으로 완벽하지 않기 때문에 완벽하다. 정확성을 조금 희생하는 대신 수백 배의 공간을 아끼는 이 철학은, 공학에서 "완벽한 것이 좋은 것의 적"이라는 교훈을 잘 보여준다.

• 아마존 AWS의 DynamoDB도 내부적으로 블룸 필터를 사용하여 존재하지 않는 항목에 대한 불필요한 디스크 I/O를 줄인다.

관련 문서

• 해시 테이블 (Hash Table)
• 확률적 자료구조 (Probabilistic Data Structure)
• Count-Min Sketch
• HyperLogLog
• MinHash
• 쿠쿠 해싱 (Cuckoo Hashing)
• LSM 트리 (Log-Structured Merge Tree)
• Apache Cassandra
• Redis
• 암호화 해시 함수
• MurmurHash
• 분산 시스템 (Distributed Systems)
• 캐시 (Cache)
• 비트 조작 (Bit Manipulation)
• 정보 이론 (Information Theory)
• 생물정보학 (Bioinformatics)