블룸 필터의 세 가지 성능 지표
블룸 필터(Bloom Filter)에서는 서로 절충(trade-off) 관계에 있는 세 가지 성능 지표를 고려해야 합니다.
- 연산(실행) 시간 — 해시 함수의 개수 k에 해당
- 필터 크기 — 비트 수 m에 해당
- 오류 확률 — 거짓 양성(false positive) 비율 f = (1 − p)k에 해당
오류 허용과 네 가지 결과 유형
블룸 필터(BF)는 조회(lookup) 성능과 공간 효율성을 높이기 위해 의도적으로 오류 허용(error tolerance)을 도입한 자료 구조입니다. 블룸 필터는 true 또는 false만을 반환하며, 그 결과는 항상 다음 네 가지 범주 중 하나에 속합니다.
- 참 양성(True Positive): 실제로 원소가 존재하고, 필터도 true를 반환하는 경우
- 거짓 양성(False Positive): 실제로 원소가 존재하지 않는데도 필터가 true를 반환하는 경우
- 참 음성(True Negative): 실제로 원소가 존재하지 않고, 필터도 false를 반환하는 경우
- 거짓 음성(False Negative): 실제로 원소가 존재하는데도 필터가 false를 반환하는 경우
블룸 필터는 거짓 양성이 발생할 수 있다는 점이 가장 큰 특징이며, 이 거짓 양성의 최대 허용 한계를 설계 단계에서 결정하게 됩니다. 거짓 양성과 거짓 음성은 모두 불필요한 재확인 작업 등 시스템에 추가적인 오버헤드를 유발합니다. 블룸 필터는 내부적으로 배열(array)을 사용해 원소의 정보를 저장하며, 확률적 판단을 수행한다는 점에서 확률적 자료 구조(probabilistic data structure)로 분류됩니다.
필터 크기와 해시 함수 개수 결정하기
블룸 필터의 크기가 너무 작으면 비트 배열의 대부분이 금방 '1'로 채워지게 되어, 입력되는 모든 값에 대해 '거짓 양성'을 반환하게 됩니다. 따라서 블룸 필터의 크기는 설계 시 매우 신중하게 결정해야 할 중요한 요소입니다. 필터가 클수록 거짓 양성은 줄어들고, 작을수록 늘어나는 경향이 있습니다.
결국 블룸 필터의 크기는 '거짓 양성 오류율(false positive error rate)'에 따라 결정된다고 정리할 수 있습니다.
또 하나 중요한 파라미터는 사용할 해시 함수의 개수입니다. 해시 함수를 많이 사용할수록 블룸 필터의 연산 속도는 느려지고, 필터는 더 빨리 차오릅니다. 반대로 해시 함수가 너무 적으면 많은 거짓 양성으로 인해 오히려 성능 저하를 겪을 수 있습니다. 즉, 속도와 정확도 사이에서 균형점을 찾는 것이 핵심입니다.
거짓 양성 오류율 계산 공식
필터 크기 m, 해시 함수 개수 k, 삽입된 원소의 개수 n을 바탕으로 거짓 양성 오류율 p를 다음 공식으로 계산할 수 있습니다.
p ≈ (1 − e(−kn/m))k
실제 설계 과정에서는 주로 m과 k의 값을 정해야 하는 경우가 많습니다. 오류 허용치 p와 삽입할 원소의 개수 n을 직접 설정했다면, 아래 두 공식을 활용해 필요한 파라미터를 손쉽게 계산할 수 있습니다.
m = −n·ln(p) / (ln 2)2
k = (m / n) × ln 2