Bloom filter [1편] - 기본 개념, Double Hashing

Aekiori·2026년 5월 6일

목록 보기

1/1

"이 데이터 있어?" 라는 질문에
"확실히 없어" 또는 "아마 있을 걸?"로만 대답하는 자료구조.

Bloom filter

블룸 필터(Bloom filter)는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조이다.
1970년 Burton Howard Bloom에 의해 고안되었다.

블룸 필터에 의해 어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능하지만,
반대로 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다는 특성이 있다.

집합에 원소를 추가하는 것은 가능하지만,
집합에서 원소를 삭제하는 것은 불가능하다.
집합 내 원소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가한다.

활용 사례

블룸 필터는 불필요한 고비용 작업(I/O, Network, DB 조회)에 대해 메모리 단에서 미리 입구컷 하는데 쓰인다.

중복 가입 방지

이메일/ID 중복 확인 시 DB를 조회하기 전 필터링하여 DB 부하 절감

대규모 크롤링

수십억 개의 방문 URL을 문자열 그대로 저장하는 대신, 최소한의 메모리로 중복 방문을 체크

Cache Penetration 방지

DB에 존재하지 않는 키 조회가 캐시를 우회해 DB로 직접 유입되는 것을 막음. 악의적인 요청뿐 아니라 단순 오요청 반복도 DB 커넥션을 고갈시킬 수 있음.

LSM Tree 기반 DB (Cassandra, HBase, RocksDB)

수많은 저장 파일(SSTable) 중 찾는 데이터가 "확실히 없는 파일"은 읽지 않고 건너뛰게 하여 읽기 성능을 향상

False Positive vs False Negative

이게 Bloom Filter의 핵심이다.

케이스	설명	Bloom Filter에서 발생여부
False Positive	없는데 있다고 함	발생 가능 (확률적)
False Negative	있는데 없다고 함	발생 안 함 (보장)

false negative가 없다는 게 왜 중요하냐면,
"없다"고 판단하면 진짜 없다.
DB 조회 없이 넘겨도 안전하다는 뜻이다.

단, 이는 Bloom Filter가 현재 데이터셋을 제대로 반영하고 있다는 전제에서 성립한다.
warm-up 전이거나, 여러 인스턴스가 각자 로컬 Bloom Filter를 들고 있는 환경에서는
필터가 최신 상태가 아닐 수 있으므로 DB fallback이나 동기화 전략 등이 필요하다.

반대로 "있다"고 판단하면 실제로 있을 수도 있고,
false positive일 수도 있다.
이 경우엔 DB로 최종 확인한다.

결국 Bloom Filter는 DB 조회를 완전히 대체하는 게 아니라, 불필요한 조회를 줄이는 필터다.

상세

zzzzz@example.com은 실제로 존재하지 않는다.
그러나 뽀록으로 3개의 비트가 모두 1이라 Bloom Filter는 "아마 있을 수도 있다"고 판단한다.
이러한 케이스 때문에 mightContain() == true일 때는 반드시 DB 조회로 최종 확인해야 한다.

Bloom Filter의 구조는 두 가지다.

bit array: m개 크기의 비트 배열, 처음엔 전부 0
k개의 해시 함수: 입력 데이터를 bit array의 k개 인덱스로 매핑

개념적으로는 k개의 해시 함수를 사용한다고 설명하지만,
실제 구현에서는 해시 함수를 k개 독립적으로 계산하지 않는 경우가 많다.
예를 들어 Guava BloomFilter는 Murmur3 128-bit 해시를 한 번 계산한 뒤,
이를 두 개의 해시값으로 나누고 Double Hashing 방식으로 k개의 인덱스를 만든다.

삽입 (put)

"aekiori@example.com" → [해시1 → 3번 비트, 해시2 → 17번 비트, 해시3 → 42번 비트]

해시 결과로 나온 인덱스들을 전부 1로 바꾼다.

조회 (mightContain)

"aekibunhongi@example.com" → [해시1 → 3번 비트, 해시2 → 9번 비트, 해시3 → 42번 비트]

해시 결과로 나온 인덱스들을 전부 본다.

하나라도 0이면 → 확실히 없다 (false negative 없음)
전부 1이면 → 아마 있을 수도 있다 (false positive 가능)

주의점

삭제가 안 된다. (더 정확하게는, 삭제를 지원하지 않는다.)
비트는 공유 자원이라 누구의 것 인지 모른다.
비트를 0으로 돌리면 다른 데이터가 공유하던 비트까지 날라간다!

회원 탈퇴 이메일을 Bloom Filter에서 제거할 수 없는 이유다.

이게 필요하면 Counting Bloom Filter를 쓴다.

정합성 보장은 Bloom Filter가 아니라 DB가 한다

Bloom Filter가 "없다"고 해도 동시에 가입 요청이 여러 개 들어오면 race condition이 생길 수 있다.
그래서 최종 중복 보장은 항상 DB의 unique constraint와 예외 처리가 담당한다.
Bloom Filter는 성능 최적화 레이어지, 정합성 보장 장치가 아니다.

메모리 사용량

$m = -\frac{n \ln p}{(\ln 2)^2}$

n : 예상 데이터 수
p : 허용 오진 확률

예시: 이메일 1000만 개, fpp 1% 기준

m ≈ -10,000,000 * ln(0.01) / (ln 2)^2
  ≈ 95,850,600 bit
  ≈ 약 12MB

1000만 이메일을 12MB로 커버한다.
이메일 문자열 자체를 저장하면 수백 MB 이상인데.

최적 해시 함수 개수는:

$k = \frac{m}{n} \ln 2 \approx 7$

Double Hashing

Double Hashing은 해시 테이블의 open addressing에서 사용되던 고전적인 해싱 기법이다.
두 개의 해시 함수 $h₁$ , $h₂$ 만으로 다음과 같이 k개의 인덱스를 생성한다.

g_i(x) = (h_1(x) + i \cdot h_2(x)) \pmod m \quad (i = 0,1,\dots,k-1)

이 방식으로 만들어진 $g_i(x)$ 들은 완전히 독립적인 k개의 해시 함수 결과는 아니다.
하지만 Kirsch와 Mitzenmacher의 논문 Less Hashing, Same Performance 는
Bloom Filter에서 이 방식을 사용해도 이론적으로는 표준 Bloom Filter와 동일한 asymptotic fpp를 얻을 수 있음을 보였다.

즉, k개의 독립적인 해시 함수를 매번 계산하지 않아도
fpp 측면에서 손실 없이 Bloom Filter를 구현할 수 있다.

코드로 간단히 보면:

m = BIT_SIZE
k = HASH_COUNT
bits = array of m bits, all set to 0

function put(value):
    h1 = hash1(value)
    h2 = hash2(value)

    for i from 0 to k - 1:
        index = (h1 + i * h2) mod m
        bits[index] = 1


function mightContain(value):
    h1 = hash1(value)
    h2 = hash2(value)

    for i from 0 to k - 1:
        index = (h1 + i * h2) mod m
        
        if bits[index] == 0:
            return false
            
    return true

Aekiori

애기오리