컴퓨터공학 300 주제 시리즈의 058번째 글이다. 전체 지도는 여기.

한 줄 요약

블룸 필터는 비트 배열 하나와 해시 함수 k 개로 “이 원소가 집합에 있나?”에 답하는 확률적 자료구조로, “없다”는 답은 항상 정확하고 “있을 수도 있다”는 답만 일정 확률로 틀리며, 그 대가로 원소를 직접 저장하는 것보다 훨씬 적은 메모리를 쓴다.

왜 필요한가

데이터베이스가 디스크에 파일 수십 개를 두고 있다고 하자. 키 하나를 읽으려면 그 키가 어느 파일에 있는지 몰라 파일을 하나씩 열어 봐야 한다. 대부분의 파일에는 그 키가 없다. “없는 걸 확인하려고” 디스크를 읽는 것이 가장 아까운 비용이다.

파일마다 키 목록을 메모리에 들고 있으면 해결되지만, 키가 수십억 개면 메모리가 모자란다. 블룸 필터는 여기서 절충한다. 키 하나당 10비트 정도만 쓰고, “이 파일에 그 키는 확실히 없다”를 대부분의 경우 알려 준다. 가끔 “있을 수도 있다”고 잘못 말하면 그때만 디스크를 읽어 확인하면 된다. Burton Bloom 이 1970년 “허용 오류가 있는 해시 부호화의 공간·시간 절충”이라는 논문에서 제안한 이 구조는, 지금은 LSM 트리 기반 저장소(RocksDB, LevelDB, Cassandra), 웹 캐시, 네트워크 장비, 분산 조인 최적화에 두루 쓰인다.

핵심 개념

구조와 연산

크기 m 비트의 배열을 모두 0 으로 시작하고, 서로 독립인 해시 함수 k 개를 준비한다.

  • 추가(add): 원소를 k 개 해시에 넣어 나온 k 개 위치의 비트를 모두 1 로 만든다.
  • 조회(might_contain): 같은 k 개 위치를 본다. 하나라도 0 이면 확실히 없다. 모두 1 이면 있을 수도 있다.
m = 16, k = 3

add("apple")  → 위치 1, 6, 11
add("kiwi")   → 위치 3, 6, 14

bits: 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0
      0 1 2 3 4 5 6 7 8 9 ...      15

query("grape") → 위치 1, 3, 9  → 9 가 0 → 확실히 없음
query("melon") → 위치 3, 11, 14 → 모두 1 → "있을 수도" (사실은 없음: 거짓 양성)

“melon” 은 넣은 적이 없지만, 다른 원소들이 켜 놓은 비트들과 우연히 겹쳐 있다고 잘못 답했다. 이것이 거짓 양성(false positive) 이다. 반대로 넣은 원소는 그 비트들이 반드시 켜져 있으므로 거짓 음성(false negative)은 절대 없다.

거짓 양성률

원소 n 개를 넣은 뒤 특정 비트가 아직 0 일 확률은 (1 − 1/m)^(kn) ≈ e^(−kn/m) 이다. 없는 원소의 k 개 위치가 모두 1 일 확률, 즉 거짓 양성률은 근사적으로

p ≈ (1 − e^(−kn/m))^k

이다. m/n(키당 비트 수)이 정해지면 p 를 최소로 만드는 k 는

k* = (m/n) · ln 2

이고, 이때 p ≈ 0.6185^(m/n) 이다. 키당 비트를 약 4.8 비트 늘릴 때마다 거짓 양성률이 10분의 1 로 준다.

키당 비트 (m/n) 최적 k 거짓 양성률 (근사)
5 3 약 9%
10 7 약 0.8%
15 10 약 0.07%

원소 자체의 크기와 상관없다는 점이 중요하다. 키가 100바이트 URL 이든 8바이트 정수든 키당 10비트면 0.8% 다. 원소를 그대로 저장하는 해시 집합과 비교하면 수십 배 작다.

한계

  • 삭제가 안 된다. 비트를 0 으로 되돌리면 그 비트를 공유하던 다른 원소까지 “없음”이 되어 거짓 음성이 생긴다. 비트 대신 작은 카운터를 두는 카운팅 블룸 필터나, 삭제를 지원하는 쿠쿠 필터 같은 변형을 쓴다.
  • 원소를 꺼낼 수 없다. 무엇이 들어 있는지 나열할 수 없다. 오직 “있을 수 있나”만 묻는다.
  • 크기를 미리 정해야 한다. n 이 예상보다 커지면 거짓 양성률이 급격히 오른다. 넉넉하게 잡거나 필터를 여러 개 이어 붙인다.

해시 k 개를 어떻게 만드나

해시 함수를 k 개 따로 계산할 필요는 없다. 해시 두 개 h₁, h₂ 로 gᵢ(x) = h₁(x) + i · h₂(x) 를 만들어 써도 점근적 거짓 양성률이 같다는 것이 Kirsch 와 Mitzenmacher 의 결과다. 아래 실습도 이 방식이다.

직접 해 보기

이중 해싱 블룸 필터를 만들고, 10만 개를 넣은 뒤 넣지 않은 20만 개로 거짓 양성률을 잰다.

import hashlib, math

class BloomFilter:
    def __init__(self, m_bits, k):
        self.m, self.k = m_bits, k
        self.bits = bytearray((m_bits + 7) // 8)

    def _positions(self, item):
        # 해시 두 개로 k 개 위치를 만든다: g_i(x) = h1(x) + i*h2(x)  (이중 해싱)
        d = hashlib.blake2b(item.encode(), digest_size=16).digest()
        h1 = int.from_bytes(d[:8], "little")
        h2 = int.from_bytes(d[8:], "little") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for p in self._positions(item):
            self.bits[p >> 3] |= 1 << (p & 7)

    def might_contain(self, item):
        return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self._positions(item))

n = 100_000
for bits_per_key in (5, 10, 15):
    m = n * bits_per_key
    k = max(1, round(bits_per_key * math.log(2)))          # 최적 k = (m/n)·ln 2
    bf = BloomFilter(m, k)
    for i in range(n):
        bf.add(f"user:{i}")
    assert all(bf.might_contain(f"user:{i}") for i in range(n))   # 거짓 음성 없음
    trials = 200_000
    fp = sum(bf.might_contain(f"other:{i}") for i in range(trials))
    theory = (1 - math.exp(-k * n / m)) ** k
    print(f"키당 {bits_per_key:>2}비트 (k={k}, {m/8/1024:.0f} KiB): "
          f"거짓 양성 실측 {fp/trials:.4%}  이론 {theory:.4%}")

키당  5비트 (k=3, 61 KiB): 거짓 양성 실측 9.0980%  이론 9.1849%
키당 10비트 (k=7, 122 KiB): 거짓 양성 실측 0.8325%  이론 0.8194%
키당 15비트 (k=10, 183 KiB): 거짓 양성 실측 0.0780%  이론 0.0744%

10만 개의 키를 122 KiB 로 표현하면서 거짓 양성은 0.83% 였다. 같은 키를 파이썬 set 에 문자열로 담으면 수 MiB 가 든다. 넣은 10만 개는 assert 로 모두 “있을 수도”가 나왔으니 거짓 음성은 없다. 이론식과 실측이 잘 맞는다는 것은 해시가 충분히 고르게 흩어졌다는 뜻이기도 하다.

현업에서는

  • LSM 트리 저장소. Cassandra 문서는 읽기 경로에서 요청한 파티션을 찾으려고 모든 SSTable 파일을 확인하지 않도록 블룸 필터를 쓰며, 테이블마다 bloom_filter_fp_chance 로 정확도와 메모리를 조절할 수 있다고 설명한다. 기본값은 LeveledCompactionStrategy 에서 0.1, 그 외에는 0.01 이다(Apache Cassandra — Bloom Filters). RocksDB 위키는 키당 약 10비트 설정이 많은 작업 부하에 잘 맞는다고 하고, 키당 9.9비트가 거짓 양성률 1% 에 해당한다는 표를 싣는다(RocksDB Bloom Filter).
  • 데이터베이스 인덱스. PostgreSQL 은 bloom 확장으로 블룸 필터 기반 인덱스를 제공한다. 문서는 이것이 손실 있는 서명(signature)을 써서 거짓 양성이 날 수 있으므로 인덱스 검색 결과를 실제 행에서 다시 확인해야 한다고 설명한다(PostgreSQL — bloom). 여러 열의 임의 조합으로 등호 검색을 하는 경우에 쓴다.
  • 캐시 앞단 필터. “한 번도 요청된 적 없는 키”로 캐시를 오염시키지 않으려고, 두 번째 요청부터 캐시에 넣는 정책을 블룸 필터로 구현하기도 한다. 존재하지 않는 키를 대량으로 조회해 DB 를 두드리는 요청을 앞단에서 걸러 내는 데도 쓴다.
  • 설계 질문. 블룸 필터를 쓸 때는 세 가지를 정한다. 예상 원소 수 n, 허용 거짓 양성률 p, 거짓 양성이 났을 때의 후속 비용. 이 셋으로 m 과 k 가 결정된다.

확인 문제

  1. 블룸 필터가 “없다”고 답했을 때와 “있을 수도 있다”고 답했을 때 각각 믿을 수 있는 정도는?
  2. 원소 100만 개, 키당 10비트면 필터 크기는 대략 몇 KiB 이고 최적 k 는?
  3. 블룸 필터에서 원소를 지우려고 비트를 0 으로 바꾸면 어떤 문제가 생기는가?
  4. 거짓 양성률을 1% 에서 0.1% 로 낮추려면 키당 비트를 대략 얼마나 늘려야 하는가?
  5. LSM 트리 저장소가 SSTable 마다 블룸 필터를 두는 이유는?

풀이

  1. “없다”는 항상 정확하다(거짓 음성 없음). “있을 수도 있다”는 거짓 양성률만큼 틀릴 수 있어 실제 확인이 필요하다.
  2. 1000만 비트 ≈ 125만 바이트 ≈ 약 1221 KiB(약 1.2 MiB). k = 10 · ln 2 ≈ 7.
  3. 그 비트를 공유하던 다른 원소의 조회가 “없음”으로 바뀌어 거짓 음성이 생긴다.
  4. p ≈ 0.6185^(m/n) 이므로 10배 줄이려면 약 4.8비트 더. (RocksDB 표로는 9.9 → 15.5 비트)
  5. 키가 없는 파일을 디스크에서 읽지 않고 메모리에서 바로 건너뛰려고. 대부분의 파일에는 찾는 키가 없기 때문이다.

더 읽을거리 (References)

  • Burton H. Bloom, “Space/Time Trade-offs in Hash Coding with Allowable Errors”, Communications of the ACM 13(7), 1970
  • Apache Cassandra Documentation, Bloom Filters
  • RocksDB Wiki, RocksDB Bloom Filter
  • PostgreSQL Documentation, bloom — bloom filter index access method
  • Adam Kirsch, Michael Mitzenmacher, “Less Hashing, Same Performance: Building a Better Bloom Filter”, ESA 2006 (LNCS 4168)