블록 블룸 필터(Blocked Bloom Filter)는 캐시 효율성을 극대화하기 위해 고안된 확률적 자료 구조입니다. 표준 블룸 필터와 달리 전체 필터를 여러 개의 작은 블록으로 나누어 관리하며, 각 블록이 하나의 캐시 라인(cache-line)에 딱 맞도록 설계되어 캐시 미스를 크게 줄일 수 있다는 것이 핵심 아이디어입니다.
블록 블룸 필터의 주요 특징
- 먼저 하나의 메모리 블록을 선택합니다.
- 그다음 해당 블록 내부의 로컬 블룸 필터를 선택합니다.
- 메모리 블록 간에 불균형이 발생할 수 있습니다.
- 연산은 효율적이지만, 표준 블룸 필터에 비해 거짓 양성률(FPR, False Positive Rate)이 높아지는 경향이 있습니다.
- 이상적으로는 동일한 크기의 표준 블룸 필터와 같은 FPR을 가져야 합니다.
- 블록 블룸 필터는 표준 블룸 필터보다 작은 일련의 블록 b(Bloom filter blocks)로 구성되며, 각 블록은 하나의 캐시 라인에 들어갑니다.
- 각 비트를 서로 다른 블록에 삽입하는 파티션(partition) 방식과는 구별되는 방식입니다.
블록 블룸 필터는 다음과 같은 방식으로 구현할 수 있습니다.
1. 비트 패턴(Bit Patterns, pat)
이 방식은 사전 계산된 비트 패턴을 활용해 블록 블룸 필터를 구현하는 기법입니다. k개의 해시 함수를 평가하여 k개의 비트를 설정하는 대신, 단일 해시 함수가 너비 B의 무작위 k비트 패턴 테이블에서 하나의 패턴을 선택합니다.
이 테이블은 대부분의 경우 캐시 안에 들어갈 만큼 작습니다. 따라서 하나의 작은 해시 값(bit 단위로 매우 작음)만 필요하며, 소수의 SIMD(Single Instruction Multiple Data) 명령어만으로 연산을 구현할 수 있습니다. 또한 블룸 필터를 전송할 때 테이블을 데이터에 명시적으로 포함할 필요가 없으며, 시드(seed) 값만 있으면 언제든 재구성할 수 있습니다.
단점: 두 요소가 동일한 패턴으로 해시되면 테이블 충돌(table collision)이 발생하여 FPR이 증가한다는 점입니다.
2. 패턴 멀티플렉싱(Multiplexing Patterns)
앞선 아이디어를 한 단계 더 발전시킨 방법으로, 단일 테이블에서 더 다양한 패턴을 얻기 위해 x개의 패턴을 비트 OR(bitwise-or) 연산으로 결합합니다. 이렇게 하면 평균적으로 k/x개의 설정된(set) 비트를 가진 패턴을 만들어낼 수 있어, 패턴의 다양성을 높이고 충돌 가능성을 줄입니다.
3. 멀티 블로킹(Multi-Blocking)
FPR을 개선하는 또 다른 변형 기법으로 멀티 블로킹(multi-blocking)이 있습니다. 이 방식에서는 쿼리 연산이 X개의 블룸 필터 블록에 접근하도록 허용하고, 각 블록에서 k/X개의 비트를 각각 설정하거나 검사합니다. (k가 X로 나누어 떨어지지 않는 경우, 첫 번째 k mod X개의 블록에 추가 비트를 하나씩 설정합니다.)
멀티 블로킹은 단순히 블록 크기를 XB로 늘리는 것보다 더 나은 성능을 보입니다. 이는 블록을 여러 개 사용함으로써 더 많은 다양성(variety)이 도입되기 때문입니다. 설정된 비트들을 여러 블록에 분산시키면 블록당 1비트의 예상 개수는 동일하게 유지되지만, 요소에 접근할 때 각 참여 블록에서는 k/X개의 비트만 고려하게 됩니다.