블룸 필터 (Bloom Filter)
쉽게 풀면
수백만 개의 아이디가 이미 가입되어 있는지 확인해야 하는 서비스를 생각해봅시다. 모든 아이디를 통째로 저장해 놓고 하나씩 비교하면 정확하지만 메모리가 많이 필요합니다. 블룸 필터는 대신 작은 비트 배열 하나만 두고, 새 아이디가 들어올 때마다 몇 개의 해시 함수로 계산한 위치의 비트를 켜 둡니다. 나중에 어떤 아이디가 있는지 확인할 때도 같은 위치들을 계산해서, 그 비트가 전부 켜져 있으면 "아마 있을 것"이라고 답하고 하나라도 꺼져 있으면 "확실히 없다"고 답합니다. 즉, 있다는 답은 가끔 틀릴 수 있어도(오탐, false positive) 없다는 답은 절대 틀리지 않습니다.
왜 중요한가
대규모 시스템에서는 "이 값이 존재하는가"를 확인하는 연산이 초당 수없이 반복되는데, 매번 디스크나 네트워크를 거쳐 정확히 확인하면 전체 성능이 크게 떨어집니다. 블룸 필터는 아주 작은 메모리로 "확실히 없음"을 빠르게 걸러내 불필요한 무거운 조회를 사전에 차단할 수 있기 때문에, 분산 데이터베이스, 네트워크 라우팅, 캐시 설계, 대규모 그래프·집합 연산 등 메모리와 속도가 동시에 중요한 여러 시스템 논문에서 기본 구성요소로 반복해서 등장합니다. 이 때문에 새로운 시스템을 제안하는 논문에서도 기존 기법과의 비교 대상이나 최적화 도구로 자주 언급됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 시스템이 실제 데이터를 찾아보기 전에 블룸 필터로 먼저 "이 값이 아예 없을 가능성이 높은지"를 빠르게 걸러내, 느린 저장소 접근 횟수를 줄였다는 뜻입니다. 데이터베이스 인덱스나 캐시 시스템 앞단에서 자주 쓰입니다.
분산·P2P 네트워크 논문에서는 노드 간에 원본 데이터 전체를 주고받는 대신, 블룸 필터라는 압축된 요약본만 교환해 대역폭을 아끼는 용도로 쓰이는 경우가 많습니다.
분산 처리·빅데이터 시스템 논문에서는 여러 노드에 걸친 데이터를 합치기 전에 블룸 필터로 미리 걸러내어, 네트워크로 오가는 데이터 양 자체를 줄이는 최적화 기법으로 자주 등장합니다.
조금 더 깊게 보면
블룸 필터의 성능은 비트 배열의 크기, 저장할 원소 개수, 사용하는 해시 함수의 개수 사이의 관계에 따라 결정되며, 이 조합이 오탐률(false positive rate)을 좌우합니다. 해시 함수가 너무 적으면 비트가 서로 겹쳐 오탐이 늘고, 너무 많으면 비트 배열이 빨리 가득 차 버려 오히려 오탐이 늘어나므로, 논문에서는 목표 오탐률에 맞춰 이 값들을 설계했다고 밝히는 경우가 많습니다. 또한 원소 삭제를 지원하기 위해 비트 대신 카운터를 두는 카운팅 블룸 필터(Counting Bloom Filter)나, 메모리 효율을 더 높인 큐코 필터(Cuckoo Filter) 같은 변형이 함께 언급되기도 하므로, 논문을 읽을 때는 기본형인지 변형인지도 함께 확인하는 것이 도움이 됩니다.
주의할 점
블룸 필터는 저장된 원소를 나중에 다시 꺼내 보여줄 수 없고, "속해 있는가"만 답할 수 있는 자료구조입니다. 값 자체를 저장하는 해시테이블과는 목적이 다르며, 일반적인 구현에서는 한 번 켠 비트를 개별적으로 끌 수 없어 원소 삭제도 기본적으로 지원하지 않습니다.