블룸 필터 예제로 이해하기

• 블룸 필터는 큰 집합의 포함 여부를 적은 메모리로 빠르게 걸러내는 자료구조로, “확실히 없음”과 “있을 수도 있음”만 구분함
• 핵심은 비트 벡터와 여러 해시 함수이며, 삽입 시 해시 결과가 가리키는 위치의 비트를 1로 바꿈
• 조회 때 같은 위치들을 확인해 하나라도 0이면 제외할 수 있지만, 모두 1이어도 거짓 양성 가능성은 남아 있음
• 해시 함수는 독립적이고 균등 분포에 가까우면서 빨라야 하며, md5에서 murmur로 바꿔 약 800% 속도 향상을 얻은 사례가 있음
• 필터의 정확도와 비용은 예상 원소 수 n, 비트 수 m, 해시 수 k의 균형에 달려 있으며 삽입과 조회는 모두 O(k) 수준임

---

블룸 필터의 동작 방식

• 블룸 필터는 원소가 집합에 포함되는지 빠르고 메모리 효율적으로 판단하는 확률적 자료구조임
• 결과는 두 가지로 제한됨
  • 원소가 집합에 확실히 없음
  • 원소가 집합에 있을 수도 있음
• 내부 구조는 비트 벡터이며, 원소를 추가할 때 입력을 여러 해시 함수에 통과시킴
• 각 해시값이 가리키는 비트 인덱스를 1로 설정하면 삽입이 끝남
• 예시에서는 Fnv와 Murmur가 단순한 해시 함수로 사용됨

포함 여부 확인과 거짓 양성

• 조회도 삽입 때와 같은 해시 함수들을 사용함
• 해시값이 가리키는 비트 중 하나라도 0이면 해당 원소는 확실히 집합에 없음
• 관련 비트가 모두 1이면 해당 원소가 있을 수도 있음
  • 같은 비트들이 다른 원소 하나 또는 여러 원소의 조합으로 이미 설정됐을 수 있음
• 이 충돌 때문에 블룸 필터에는 거짓 양성(false positive) 가능성이 존재함

해시 함수 선택 기준

• 블룸 필터의 해시 함수는 독립적이고 균등 분포에 가까워야 하며, 가능한 한 빨라야 함
• sha1 같은 암호학적 해시는 널리 쓰이지만, 블룸 필터에는 항상 좋은 선택이 아닐 수 있음
• 빠르고 단순한 해시 예시는 다음과 같음
  • murmur
  • xxHash
  • fnv
  • HashMix
• 블룸 필터 구현을 md5에서 murmur로 바꾼 뒤 약 800% 속도 향상을 얻은 사례가 있음

실제 구현에서 쓰이는 해시

• 여러 구현체가 블룸 필터에 각기 다른 해시 함수를 사용함
  • Chromium: murmur 사용
  • Plan9: Mitzenmacher 2005에서 제안한 단순 해시 사용
  • Sdroege Bloom filter: fnv1a 사용
  • Squid: MD5 사용
  • RedisBloom: murmur 사용
  • Apache Spark: murmur 사용
  • influxdb: xxhash 사용
  • bloomd: 처음 두 해시는 murmur, 다음 두 해시는 SpookyHash, 이후 해시는 둘의 조합 사용
  • fleur, flor, bloom: fnv 사용
  • Sqlite: 분석 쿼리용 블룸 필터 추가
  • RocksDB: 설정 가능하며, 소스에서는 xxhash 계열의 xxh3가 가장 좋았다고 밝힘
  • ScyllaDB: murmur 사용

필터 크기와 해시 함수 수 정하기

• 블룸 필터는 거짓 양성률을 조정할 수 있음
  • 더 큰 필터는 거짓 양성이 줄어듦
  • 더 작은 필터는 거짓 양성이 늘어남
• 거짓 양성률은 대략 (1-e^-kn/m)^k로 계산됨
  • n: 삽입할 것으로 예상되는 원소 수
  • m: 필터의 비트 수
  • k: 해시 함수 수
• 해시 함수가 많을수록 조회와 삽입이 느려지고 필터도 더 빨리 채워짐
• 반대로 해시 함수가 너무 적으면 거짓 양성이 지나치게 많아질 수 있음
• 주어진 m과 n에서 최적의 k는 (m/n)ln(2)로 선택할 수 있음
• 필터 크기는 다음 순서로 맞춰 볼 수 있음
  • 예상 n 값을 대략 정함
  • m 값을 선택함
  • 최적의 k 값을 계산함
  • 선택한 n, m, k로 오류율을 계산함
  • 오류율을 받아들이기 어렵다면 m을 바꿔 다시 계산함

성능과 적합한 사용 조건

• m비트와 k개 해시 함수를 가진 블룸 필터에서 삽입과 포함 여부 확인은 모두 O(k) 임
• 원소를 추가하거나 조회할 때는 원소를 k개 해시 함수에 통과시키고 해당 비트를 설정하거나 확인하면 됨
• 공간 효율은 허용 가능한 오류율에 따라 달라짐
• 삽입 가능한 원소의 범위가 매우 제한적이면 결정적 비트 벡터가 더 나을 수 있음
• 삽입될 원소 수를 대략이라도 추정할 수 없다면 해시 테이블이나 scalable Bloom filter가 더 적합할 수 있음

참고 자료와 활용 예

• 블룸 필터 활용 예시는 Wikipedia의 Bloom filter 예시에서 볼 수 있음
• C. Titus Brown의 발표는 생물정보학에서 블룸 필터를 쓰는 사례를 다룸
• 주요 참고 자료
  • Network Applications of Bloom Filters: A Survey
  • Wikipedia - Bloom filter
  • Less Hashing, Same Performance
  • Scalable Bloom Filters

[GN⁺]

Hacker News 의견들

• 이 글은 딱 나 같은 사람을 겨냥한 글임. Bloom 필터라는 이름은 들어봤고, 언급될 때마다 찾아봐야겠다고 생각만 하다가 이 글을 보고 드디어 찾아봤는데, 내가 원하던 입문서로 완벽했음 :)

  • 10년도 더 전에 iBooks 검색 기능용으로 구현하라는 일을 받으면서 Bloom 필터를 알게 됨
  • 정말 재미있는 구조임. Bloom 필터가 필요한 문제가 나타나면 신나는데, 안타깝게도 분야에 따라 그런 경우가 드물 수 있음

• 2009년에 대학에서 CUDA로 Bloom 필터를 만들었고, 지도교수는 전 Nvidia 출신이었음. 그런데 이후 커리어에서는 GPU 프로그래밍을 전혀 하지 않게 됨
  그때 다른 선택을 했으면 1억 달러는 벌 수 있었을지도 모름

  • 나도 비슷함. 2009년에 호기심으로 GeForce 8에서 CUDA v1을 써서 GPU 최적화 생물정보학 툴킷 중 아주 초기 형태를 만들었던 것 같음
    그러고는 다른 일을 하러 갔고, 큰돈을 놓침
  • 1970년에 나온 컴퓨터과학 아이디어라는 점을 생각하면 그럴 가능성은 낮아 보임. 범용 GPU에서 시도할 만한 아이디어는 이미 다들 노려볼 수 있었을 것임
    10년 전에 GPU로 hashcash 구현을 만들었는데, 지금은 거의 가치가 없을 것 같음
  • 학부 우등 프로젝트로 기계학습 알고리즘을 CUDA로 포팅한 뒤, 그냥 어깨를 으쓱하고 임베디드 프로그래밍으로 갔음
  • Bitcoin을 샀어도 훨씬 더 많이 벌 수 있었을 것임

• 저자에게 남기는 메모: 인터랙티브 부분이 정말 좋음. 핵심을 더 확실히 보여주려면 해시 충돌이 나는 두 문자열 예시를 주고, 하나는 첫 번째 입력칸에 넣게 한 뒤 다른 하나를 두 번째 칸에서 검사하게 하면 좋겠음
  그러면 답이 왜 항상 “집합에 있을 수도 있음”이지 “있다”가 아닌지 보여줄 수 있음

  • "bloom"과 "demonstrators "가 충돌함. 뒤쪽 문자열 끝의 공백 문자에 주의해야 함
    둘 다 fnv: 7, murmur: 12로 충돌함

• 내가 좋아하는 요령이 하나 있음. 가끔 작을 가능성이 있는 집합에서 멤버십 검사를 많이 해야 한다면, 64비트 Bloom 필터를 아주 단순한 해시 함수와 함께 추측적으로 붙일 수 있음
  엄청 멍청하게 들리지만 비용이 너무 작아서 도박처럼 해볼 만함. 잘 안 맞아도 삽입과 멤버십 검사에 대략 10ns를 더하는 정도인데, 잘 맞으면 엄청난 작업량을 줄일 수 있음

  • Chromium도 여러 곳에서 이렇게 함. 글에서는 Safe Browsing이 murmur를 쓰는 예만 링크했지만, 렌더러인 Blink는 보통 rapidhash를 쓰고 이런 마이크로 필터를 여러 곳에 사용함
    예를 들면 특정 경우의 querySelector(), CSS 버킷에서 해시 조회 사전 필터링, 접근성용으로 특정 Aria 속성을 찾을 때 요소를 빠르게 거부하는 데 쓰임. 32비트나 64비트짜리 아주 작은 필터가 동작한다는 게 놀랍지만 실제로는 자주 효과가 있음. 더 큰 Bloom 필터들도 일부 있음. 이 중 몇 개는 내가 추가했음

• ChatGPT에게 Python으로 하나 만들어 달라고 해서, 기본 md5 다이제스트를 잘라 여러 해시처럼 쓰는 방식을 사용했음. 중요하지 않은 용도라면 괜찮을 것 같음

• Bloom 필터의 또 다른 시각화는 이 페이지 끝에서 볼 수 있음:
  https://www.chrislaux.com/hashtable.html

• 전에 본 적이 있다고 생각했는데, 실제로는 이 다른 페이지였음: https://bdupras.github.io/filter-tutorial/
  이 페이지는 Bloom 필터와 cuckoo 필터를 비교해서 정보가 조금 더 추가됨

• 최근에 Bloom 필터로 로그 메시지 스팸 방지 기능을 구현함. 로거에서 메시지를 해시해 필터에 넣고, 항목이 있으면 메시지를 출력하지 않았음
  몇 초마다 필터를 순회하면서 모든 비트를 지웠는데, 필터의 모든 비트를 원자적으로 지우는 문제를 신경 쓰지 않아도 돼서 잘 맞았음. 메시지가 들어오는 중에 그중 일부 비트가 지워지기만 해도 다시 로그에 찍히기에 충분했음. 이전 구현은 본 메시지 수를 세다가 N에서 포화되는 방식이었고, 특정 메시지가 반복해서 찍히면 필터가 지워지는 속도 이하로만 보이게 되는 효과가 있었음
  Bloom 필터를 알고만 있다가 이렇게 자연스럽게 실제 용도를 찾아 큰 개선을 만든 것이 꽤 만족스러웠음

• 더 읽고 싶다면 Eli Bendersky의 Bloom 필터 글도 좋았음:
  https://eli.thegreenplace.net/2025/bloom-filters/

• Bloom 필터, 집합, 해시 테이블을 이해하는 데 필요한 개념은 체감상 95%쯤 겹침. 집합은 값이 아니라 키만 신경 쓰는 멤버십 검사용 해시 테이블이고, Bloom 필터는 다대일 해싱이 충돌로 키 공간을 “압축”한다는 사실을 활용하는 집합임
  의도적으로 충돌이 많이 나는 해시 함수를 쓰는 셈임. 특정 키가 한 번이라도 해시됐다면 반드시 맞다고 나오지만, 같은 해시를 만든 다른 키가 있을 수도 있음. 버그가 아니라 기능임

  • Bloom 필터를 실제 데이터는 추적하지 않고 데이터가 있는 버킷만 추적하는 해시 테이블로 이해하는 사람이 나뿐이 아니라서 반가움
  • 이 설명에서 빠진 핵심은 Bloom 필터가 충돌을 줄이기 위해 여러 해시 함수를 쓴다는 점임. 예를 들어 해시가 3개라면, 어떤 키가 집합에 있다고 판단되려면 세 해시가 모두 맞아야 함
    이렇게 하면 거짓 양성 충돌 가능성을 줄이면서도 거짓 음성이 없다는 보장은 유지됨
  • Bloom 필터를 제대로 이해했다면, 무작위 사영과 지역성 민감 해시의 일부 구현도 이해하는 데 거의 다 온 것임