- Bloom Filter는 1970년 Burton Howard Bloom에 의해 고안된 공간 효율적인 확률적 데이터 구조로서, 어떤 요소가 집합에 속하는지를 테스트하는 데 사용된다.
- 이 구조의 핵심적인 특징은 false positive가 발생할 수 있지만, false negative는 발생하지 않는다는 점이다. 즉, Bloom Filter는 주어진 쿼리에 대해 “집합에 포함되어 있을 수도 있음” 또는 “집합에 확실히 포함되어 있지 않음” 중 하나의 결과를 반환한다.
- 요소는 필터에 추가할 수 있지만, 삭제는 일반적인 Bloom Filter에서는 불가능하며, 삭제 기능이 필요한 경우 Counting Bloom Filter와 같은 변형이 사용된다. 요소가 필터에 많이 추가될수록 false positive가 발생할 확률은 점차 증가하게 된다.
- 충분한 메모리가 있다면 오류 없는 인덱스 해시를 사용할 수 있겠지만, 메모리가 제한적일 경우 Bloom Filter를 사용하여 대부분의 디스크 접근을 불필요하게 만들 수 있다. 실제로 이상적인 오류 없는 해시가 요구하는 공간의 18%만 사용하는 Bloom Filter만으로도 전체 디스크 접근의 87%를 제거할 수 있다.
- 보다 일반적으로, 원소 하나당 약 10비트 미만의 공간만으로도 1%의 false positive 확률을 유지할 수 있으며, 이는 집합의 크기나 요소의 개수에 관계없이 유지된다. 이처럼 Bloom Filter는 낮은 오차를 감수하는 대신 메모리 사용량을 획기적으로 줄여주는 방식으로 동작한다.
동작 방식
-
빈 Bloom Filter는 길이가
m인 비트 배열로 구성되며, 모든 비트는 0으로 초기화된다. 이 필터에는 서로 독립적인k개의 해시 함수가 존재하며, 각 해시 함수는 입력된 요소를m개의 가능한 인덱스 중 하나로 매핑한다. 삽입 시에는 각 해시 함수로부터 도출된 인덱스의 비트를 모두 1로 설정한다. -
어떤 요소가 집합에 속하는지를 확인하려면, 해당 요소를 각 해시 함수에 넣어 인덱스를 얻고, 이 인덱스에 해당하는 비트들이 모두 1인지 확인한다. 하나라도 0이 있으면 그 요소는 “확실히 집합에 없다”고 판단할 수 있다. 모든 비트가 1이면 그 요소는 “있을 수도 있다”는 응답을 하게 되며, 이 경우 false positive가 발생할 수 있다. 단순한 Bloom Filter는 이 경우를 구분할 수 없으나, Counting Bloom Filter나 Xor Filter 등의 고급 구조에서는 보다 정교한 처리가 가능하다.
사례
- Akamai: 1회만 요청되는 웹 오브젝트(one-hit-wonder)를 캐시하지 않기 위해 Bloom Filter를 사용. 2회 이상 요청된 오브젝트만 디스크에 캐시하여, 디스크 접근을 절반 이상 줄이고 전체 캐시 효율을 향상.
- Google Bigtable / HBase / Cassandra / ScyllaDB: SSTable 또는 ColumnFamily 단위로 Bloom Filter를 저장하여, 존재하지 않는 row나 column에 대해 디스크 접근을 방지함으로써 데이터베이스 성능을 크게 향상.
- Grafana Tempo: 각 백엔드 블록에 대해 Bloom Filter를 저장하여 trace ID에 대한 빠른 필터링을 제공.
- PostgreSQL: 다중 열 인덱스에서 Bloom Index를 제공, 특정 필드 조합이 존재하는지를 빠르게 판단.
주의사항
- Bloom Filter는 false positive를 완전히 제거할 수 없으므로, 정확성이 중요한 로직에서는 보조 수단으로만 사용해야 한다.
- 예상되는 요소 수
n과 허용 가능한 false positive 비율ε에 따라 비트 배열 크기m과 해시 함수 수k를 적절히 조정해야 한다. - 요소 삭제가 필요한 경우 Counting Bloom Filter 또는 Cuckoo Filter 등 변형 구조를 사용할 것.
- 요소가 일정 주기를 넘어서거나 너무 많이 삽입되면 false positive 확률이 급격히 증가하므로, Bloom Filter를 회전하거나 재생성하는 정책이 필요하다.