블룸 필터의 정의
블룸 필터는 ‘특정 데이터가 집합에 존재하는가?’를 아주 빠르고 적은 메모리로 확인할 수 있는 확률적 자료구조입니다. 일반적인 해시셋(HashSet)과 달리 정확한 값을 저장하지 않고, 비트 배열(bit array)만으로 존재 여부를 판단합니다. 그래서 결과가 ‘확실히 없음(No)’ 또는 ‘있을 수도 있음(Maybe)’으로만 나옵니다. 즉 없다고 하면 100% 없는 것이지만, 있다고 해도 실제로는 없을 가능성(False Positive)이 존재합니다. 반대로 있는데 없다고 판단하는 False Negative는 절대 발생하지 않는 것이 핵심 특징입니다.
동작 원리와 예시
블룸 필터는 크기가 m인 비트 배열과 서로 다른 해시 함수 k개로 구성됩니다. 데이터를 추가할 때는 k개의 해시 함수로 각각 인덱스를 계산해 해당 위치의 비트를 1로 바꿉니다. 조회할 때도 동일하게 k개의 인덱스를 계산해서, 모든 위치가 1이면 ‘있을 수도 있다’, 하나라도 0이면 ‘확실히 없다’고 판단합니다.
예를 들어 도서관 회원증 대신 특정 숫자 칸에 도장을 찍는 방식을 떠올려보세요. 여러 회원이 같은 칸에 도장을 찍을 수 있기 때문에, 도장이 찍혀 있다고 해서 그 사람이 정말 회원인지 확신할 수는 없습니다. 하지만 도장이 하나도 없는 칸이 있다면, 그 사람은 절대 회원이 아니라는 것을 확실히 알 수 있습니다. 블룸 필터도 이와 같은 원리로 동작합니다.
실무에서 왜 사용할까?
블룸 필터는 정확도보다 속도와 메모리 효율이 중요한 상황에서 빛을 발합니다. 대표적인 활용 사례는 다음과 같습니다.
- 데이터베이스(예: Cassandra, HBase)에서 디스크 조회 전 ‘이 키가 존재할 가능성이 있는지’ 먼저 확인해 불필요한 디스크 I/O를 줄임
- 웹 크롤러에서 이미 방문한 URL인지 빠르게 체크
- CDN이나 캐시 시스템에서 캐시 미스가 확실한 요청을 사전에 걸러내기
- 스팸 필터, 악성 URL 차단 리스트 검사
이처럼 블룸 필터는 ‘없는 것을 빠르게 걸러내는’ 용도로 매우 유용하며, False Positive 비율은 비트 배열 크기와 해시 함수 개수를 조절해 원하는 수준으로 낮출 수 있습니다. 정확한 판별이 필요한 경우에는 블룸 필터로 1차 필터링을 한 뒤, 실제 데이터 조회로 최종 확인하는 방식이 일반적입니다.