Bloom filter란 무엇이며, 어떤 트레이드오프를 하나요?

Question

Accepted Answer

**Bloom filter(블룸 필터)**는 한 가지 묘미를 가진, 공간 효율적인 **확률적(probabilistic)** 구조로 집합 멤버십에 답합니다. **거짓 양성(false positive)**은 있을 수 있지만 **거짓 음성(false negative)**은 절대 없습니다. "분명히 없음"은 확실하고, "있을 수도 있음"은 실제 확인이 필요합니다.

## 동작 방식

`m` 비트의 비트 array와 `k`개의 해시 함수. 항목을 **추가**하려면 그것이 해싱되는 `k`개의 비트를 1로 설정합니다. **질의**하려면 그 `k`개의 비트를 확인합니다. 하나라도 0이면 그 항목은 분명히 없습니다.

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": 1,3,6으로 해싱 -> bit 3이 0 -> 분명히 없음
query "cat": 1,4,6 모두 설정됨 -> "아마 있음"
```

## 코드

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # 해시 함수의 리스트
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = 확실; True = 어쩌면
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| 연산 | 시간 | 공간 |
|---|---|---|
| add | O(k) | O(m) 비트 |
| query | O(k) | — |

거짓 음성 없음; 거짓 양성률은 `m`(과 조정된 `k`)이 커질수록 떨어집니다.

## 트레이드오프

- **강점:** 전체 key를 저장하는 것 대비 아주 작은 메모리 사용량; 상수 시간 연산.
- **약점:** 거짓 양성; **삭제 불가**(표준 Bloom filter); 멤버를 나열할 수 없음.

## 왜 중요한가

Bloom filter는 비싼 작업을 저렴하게 건너뜁니다. 데이터베이스(예: Cassandra, HBase)는 디스크에 **분명히** 없는 key에 대한 디스크 읽기를 피하는 데 이를 사용합니다.

이들은 고전적인 시스템 트레이드오프를 구현합니다. 작고 제한된 오류율을 받아들이는 대가로 메모리와 I/O를 크게 줄입니다.