Bloom Filter란 무엇인가
Bloom Filter(블룸 필터)는 ‘어떤 데이터가 집합에 존재하는지’를 아주 빠르게, 그리고 매우 적은 메모리로 확인할 수 있는 확률적 자료구조입니다. 일반적인 자료구조는 데이터를 직접 저장해두고 비교하지만, 블룸 필터는 데이터 자체를 저장하지 않고 ‘있을 수도 있다’ 또는 ‘절대 없다’라는 두 가지 답만 내놓습니다. 특이한 점은 ‘없다’는 답은 100% 확실하지만, ‘있다’는 답은 실제로는 없는데 있다고 잘못 판단하는 거짓 양성(False Positive)이 발생할 수 있다는 것입니다. 반대로 실제로 있는데 없다고 판단하는 거짓 음성(False Negative)은 절대 발생하지 않습니다.
동작 원리와 예시
블룸 필터는 내부적으로 비트 배열(bit array)과 여러 개의 해시 함수를 사용합니다. 데이터를 추가할 때는 여러 해시 함수로 계산한 위치의 비트를 모두 1로 켭니다. 조회할 때는 같은 해시 함수로 위치를 계산해 해당 비트가 모두 1인지 확인합니다. 하나라도 0이면 ‘확실히 없음’이고, 모두 1이면 ‘있을 가능성이 있음’이라고 판단합니다.
비유하자면 도서관 입구에 여러 개의 감지 센서가 있고, 책을 등록할 때마다 관련 센서 몇 개를 켜둔다고 생각하면 됩니다. 어떤 책을 찾을 때 관련 센서가 하나라도 꺼져 있으면 ‘이 책은 등록된 적 없다’고 100% 확신할 수 있지만, 센서가 모두 켜져 있다고 해도 다른 책들 때문에 우연히 켜졌을 수 있어 ‘아마 있을 것’이라고만 말할 수 있습니다.
- 비트 배열 크기와 해시 함수 개수를 늘리면 거짓 양성 확률은 줄어듭니다.
- 대신 메모리 사용량은 늘어나므로 정확도와 공간 사이의 트레이드오프가 존재합니다.
- 한 번 저장된 데이터는 삭제할 수 없다는 한계도 있습니다. 비트를 끄면 다른 데이터에 영향을 줄 수 있기 때문입니다.
실무에서는 왜 사용할까
블룸 필터는 실제 데이터를 조회하기 전에 ‘미리 걸러내는 필터’ 역할로 많이 쓰입니다. 예를 들어 대용량 데이터베이스나 캐시 시스템에서 ‘이 키가 존재하지 않는다’는 사실을 디스크 접근 없이 빠르게 확인할 수 있다면, 불필요한 디스크 I/O를 크게 줄일 수 있습니다. 대표적으로 구글의 빅테이블, 아파치 카산드라, 레벨DB 같은 시스템은 특정 키를 조회하기 전에 블룸 필터로 먼저 확인해 ‘없는 키’에 대한 조회를 사전에 차단합니다. 또한 스팸 URL 필터링, 회원가입 시 중복 아이디 체크, 캐시 미스 방지 등에서도 널리 활용됩니다.
정리하면 블룸 필터는 완벽한 정확도 대신 속도와 메모리 효율을 택한 자료구조입니다. ‘있다/없다’를 정확히 구분해야 하는 상황이 아니라, ‘없는 것을 빠르게 걸러내고 싶은’ 상황에서 강력한 힘을 발휘합니다.