Bloom Filter와 확률적 자료구조 완전 가이드

개요

Bloom Filter는 원소가 집합에 속하는지 여부를 확률적으로 검사하는 공간 효율적 자료구조입니다. “없다(No)“는 확실하지만 “있다(Yes)“는 거짓 양성(False Positive) 가능성이 있습니다. 해시 셋보다 수십 배 적은 메모리로 같은 기능을 수행합니다.

---

1. 동작 원리

삽입(Insert):
  k개의 해시 함수로 m비트 배열에서 k개의 위치를 선택
  → 해당 비트를 1로 설정

검사(Query):
  k개의 해시 함수로 k개의 위치 확인
  → 모두 1이면 "아마 있음"
  → 하나라도 0이면 "확실히 없음"

---

2. C++ 구현

#include <vector>
#include <functional>
#include <string>
#include <cmath>

class BloomFilter {
    std::vector<bool> bits;
    int numHashes;
    size_t size;

    // k번째 해시 (FNV + 시드 조합)
    size_t Hash(const std::string& key, int seed) const {
        size_t h = 14695981039346656037ULL;
        for (char c : key) h = (h ^ c) * 1099511628211ULL;
        h ^= seed * 2654435761ULL; // 시드 혼합
        return h % size;
    }

public:
    // n: 예상 원소 수, fp: 거짓 양성률 (0~1)
    BloomFilter(int n, double fp = 0.01) {
        // 최적 비트 수: m = -n*ln(p) / (ln2)^2
        size = std::ceil(-n * std::log(fp) / (std::log(2) * std::log(2)));
        // 최적 해시 수: k = (m/n) * ln2
        numHashes = std::round((double)size / n * std::log(2));
        bits.assign(size, false);
    }

    void Insert(const std::string& key) {
        for (int i = 0; i < numHashes; i++)
            bits[Hash(key, i)] = true;
    }

    // false: 확실히 없음, true: 아마 있음 (fp 확률로 오류)
    bool Contains(const std::string& key) const {
        for (int i = 0; i < numHashes; i++)
            if (!bits[Hash(key, i)]) return false;
        return true;
    }

    double GetFPRate(int inserted) const {
        double exponent = -(double)numHashes * inserted / size;
        return std::pow(1 - std::exp(exponent), numHashes);
    }

    size_t MemoryBytes() const { return (size + 7) / 8; }
};

---

3. 거짓 양성률

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

거짓 양성률 p ≈ (1 - e^(-kn/m))^k

예시:
  n = 100만, m = 10MB = 80M 비트, k = 5
  p ≈ (1 - e^(-5*1M/80M))^5 ≈ 0.78%

메모리 절약:
  HashSet: 100만 × 40B = 40MB
  BloomFilter: 10MB = 1/4 크기, 오류율 0.78%

---

4. Counting Bloom Filter (삭제 지원)

class CountingBloomFilter {
    std::vector<int> counters; // bool 대신 int 카운터
    int numHashes;
    size_t size;

    size_t Hash(const std::string& key, int seed) const;

public:
    CountingBloomFilter(int n, double fp = 0.01) {
        size = std::ceil(-n * std::log(fp) / (std::log(2) * std::log(2)));
        numHashes = std::round((double)size / n * std::log(2));
        counters.assign(size, 0);
    }

    void Insert(const std::string& key) {
        for (int i = 0; i < numHashes; i++)
            counters[Hash(key, i)]++;
    }

    void Remove(const std::string& key) {
        if (!Contains(key)) return;
        for (int i = 0; i < numHashes; i++)
            if (counters[Hash(key, i)] > 0)
                counters[Hash(key, i)]--;
    }

    bool Contains(const std::string& key) const {
        for (int i = 0; i < numHashes; i++)
            if (counters[Hash(key, i)] == 0) return false;
        return true;
    }
};

---

5. 실전 활용

5.1 캐시 필터링 (Cache Stampede 방지)

// DB에 없는 키를 Bloom Filter로 빠르게 거부
class CacheLayer {
    BloomFilter existsFilter;  // DB에 있는 키 집합

public:
    CacheLayer(int expectedKeys) : existsFilter(expectedKeys) {}

    std::optional<Data> Get(const std::string& key) {
        // DB에 없는 키는 즉시 거부 (DB 조회 없음)
        if (!existsFilter.Contains(key))
            return std::nullopt;

        return QueryDatabase(key); // 있을 가능성이 있는 경우만 DB 조회
    }

    void Put(const std::string& key, const Data& data) {
        existsFilter.Insert(key);
        StoreToDatabase(key, data);
    }
};

5.2 중복 URL 방지

// 웹 크롤러: 방문한 URL 추적
class WebCrawler {
    BloomFilter visited;  // 수억 URL도 수백 MB로 관리

public:
    WebCrawler() : visited(100'000'000, 0.001) {} // 1억 URL, 0.1% 오류율

    bool ShouldVisit(const std::string& url) {
        if (visited.Contains(url)) return false; // 이미 방문
        visited.Insert(url);
        return true;
    }
};

5.3 게임 서버 스팸 방지

// 최근 N분 내 같은 메시지 중복 전송 차단
class AntiSpamFilter {
    BloomFilter recentMessages;

public:
    AntiSpamFilter() : recentMessages(1'000'000) {}

    bool IsSpam(const std::string& message) {
        if (recentMessages.Contains(message)) return true;
        recentMessages.Insert(message);
        return false;
    }
};

---

6. HashSet과 비교

항목	HashSet	Bloom Filter
메모리	O(N × 원소크기)	O(m 비트)
삽입	O(1)	O(k)
탐색	O(1)	O(k)
삭제	O(1)	X (기본 버전)
거짓 양성	없음	있음 (설정 가능)
거짓 음성	없음	없음

---

정리

• “없다”는 확실, “있다”는 거짓 양성 가능성 존재
• m (비트 크기)과 k (해시 수)로 오류율과 메모리 트레이드오프
• 캐시 필터, 중복 제거, 스팸 방지, 네트워크 라우팅에 활용
• Counting Bloom Filter로 삭제 지원 (메모리 증가)
• HashSet 대비 수십 배 메모리 절약, 소량의 오류 허용 시 적합

참고 자료

• Wikipedia — Bloom filter