블룸 필터(Bloom Filter)

서버 메모리에 대용량 데이터를 올려야하는 작업이 있었다

단순하게 Map 형태로 올릴까 생각하다가 크기가 너무 커질까봐 걱정이 들기 시작

하지만 O(1)의 속도를 보장하는 Key-Value 형태의 자료구조를 포기할 수는 없었다

그러다가 검색해보니 동일한 O(k)를 보장하면서 공간을 더 적게 사용하는 Bloom Filter을 알게되었다

무엇인지 한번 알아보자

1. 블룸 필터란? 🌸

블룸 필터(Bloom Filter)는 1970년 Burton Howard Bloom이 제안한 확률적 자료 구조이다

이 구조는 주어진 원소가 집합에 속하는지 여부를 검사하는 데 사용된다

블룸 필터의 주요 특징은 매우 적은 메모리를 사용하면서도 빠른 검색 속도 O(k)을 제공한다는 점이다

블룸 필터의 주요 특징은 다음과 같다:

공간 효율성: 매우 적은 메모리로 대규모 데이터셋을 표현할 수 있다.
빠른 검색 속도: O(k) 시간 복잡도로 검색이 가능하다. (k는 해시 함수의 개수)
확률적 결과: 거짓 양성(false positive)이 발생할 수 있지만, 거짓 음성(false negative)은 절대 발생하지 않는다.
원소 삭제 불가: 기본적인 블룸 필터에서는 원소를 삭제할 수 없다.

블룸 필터의 작동 방식은 다음과 같다:

초기화: m 비트 길이의 비트 배열을 모두 0으로 초기화한다.
원소 추가:
- 추가할 원소에 k개의 서로 다른 해시 함수를 적용한다.
- 각 해시 함수의 결과값에 해당하는 비트 배열의 위치를 1로 설정한다.
원소 검색:
- 검색할 원소에 동일한 k개의 해시 함수를 적용한다.
- 모든 해시 함수의 결과값에 해당하는 비트가 1이면 원소가 '아마도' 존재한다고 판단한다.
- 하나라도 0이 있다면 원소가 '확실히' 존재하지 않는다고 판단한다.

블룸 필터는 생가보다 다양한 분야에서 활용된다:

물론 장점만 있는 자료구조는 아니다

거짓 양성 (False-positive): 블룸 필터가 확률형 자료구조라고 불리는 가장 큰 이유. 실제로는 집합에 없는 원소를 있다고 잘못 판단할 수 있다. 하지만 없는 원소를 없다고(False-negative) 판단하지는 않는다.
원소 삭제 불가: 기본 구조에서는 원소를 제거할 수 없다. (Counting Bloom Filter 등의 변형으로 해결 가능)
원소 목록 불가: 블룸 필터는 집합에 어떤 원소들이 있는지 나열할 수 없다.
최적 파라미터 설정: 효율적인 사용을 위해 적절한 비트 배열 크기와 해시 함수 개수를 선택해야 한다.

기존 Map 형태와 비교했을때는 분명히 trade-off들이 존재한다

각 자료구조의 장담점을 분명히 인지하고 상황에 알맞게 선택해서 사용하는것이 좋아보인다

블룸 필터는 그 단순함에도 불구하고 매우 강력하고 유용한 자료 구조이다. 특히 대규모 데이터를 다루는 현대의 컴퓨팅 환경에서 메모리 사용량과 검색 속도의 trade-off를 효과적으로 조절할 수 있는 도구로 각광받고 있다.

False-positive의 가능성이라는 단점이 있지만, 많은 응용 분야에서 이는 큰 문제가 되지 않는다. 오히려 공간 효율성과 빠른 검색 속도로 인한 퍼포먼스 향상이라는 장점이 더 중요하게 여겨진다.

블룸 필터의 이해와 적절한 활용은 효율적인 시스템 설계에 큰 도움이 될 것이다. 향후 빅데이터, 분산 시스템, 네트워크 보안 등 다양한 분야에서 블룸 필터의 활용이 더욱 증가할 것으로 예상된다.