블룸 필터(bloom filter)는 항목이 있는지 확정하는 대신, 없다는 답은 확실히 하고 있다는 답은 ‘그럴 수 있다’고 알려주는 확률적 자료구조다. 정확한 포함 여부보다 메모리 절약이 중요하고 오탐을 허용할 수 있는 상황에 쓸 수 있다.

작동 방식과 활용

블룸 필터는 비트 배열에 항목의 해시값을 반영한다. 항목을 확인할 때 관련 비트 중 하나라도 설정돼 있지 않으면 해당 항목은 없다고 확정할 수 있다. 비트가 모두 설정돼 있으면 항목이 있을 수도 있지만, 실제로 추가되지 않은 항목을 있다고 판단하는 오탐이 발생할 수 있다. 표준 블룸 필터에서는 실제로 들어 있는 항목을 없다고 판단하는 미탐은 발생하지 않는다.

원문은 악성 링크 100만 개를 각각 20자라고 가정해 일반 목록이 20MB를 차지하는 사례를 든다. 100만 번 중 한 번 오탐을 허용하면 블룸 필터는 3.59MB로 같은 데이터를 저장할 수 있고, 오탐률을 0.1%(1000번 중 한 번)로 설정하면 1.8MB가 든다고 설명한다. 구글 크롬은 2012년까지 악성 링크 확인에 블룸 필터를 사용했다. 오탐을 피하려면 블룸 필터가 ‘있을 수도 있다’고 답한 경우에만 서버의 전체 목록을 조회할 수도 있다.

원문은 또 Akamai가 한 번만 접근된 뒤 다시 방문되지 않는 웹 페이지의 캐싱을 줄이는 데 블룸 필터를 이용한다고 소개한다. 구글의 BigTable은 키가 데이터베이스에 있는지 확인할 때 메모리의 블룸 필터를 먼저 검사한다. 키가 없다는 답이 나오면 디스크를 읽지 않고 응답할 수 있으며, 필터가 있다고 답했지만 실제로는 없는 경우 디스크 접근으로 확인한다.

크기와 오탐률 조정

설정된 비트의 비율이 커질수록 오탐률도 높아진다. 해시 함수를 3개 쓰고 비트의 절반이 설정된 경우, 각 해시 함수가 설정된 비트를 가리킬 확률이 같다고 가정하면 오탐률은 0.5³, 즉 12.5%다. 해시 함수를 늘리면 오탐률을 낮출 수 있지만 항목마다 더 많은 비트가 설정돼 필터가 빨리 차고, 해시 계산 비용도 커진다.

저장할 고유 항목 수와 허용할 오탐률을 미리 알면 필요한 비트 수와 최적 해시 함수 수를 계산할 수 있다. 원문은 다음 자바스크립트 함수를 제시한다.

function bits(items, fpr) { const n = -items * Math.log(fpr); const d = Math.log(2) ** 2; return Math.ceil(n / d); }

bits 함수는 최적 개수의 해시 함수를 사용한다고 가정한다. 필요한 비트 수를 구한 뒤 다음 함수로 해시 함수 수를 계산한다.

function hashFunctions(bits, items) { return Math.ceil((bits / items) * Math.log(2)); }

예상 항목 수가 늘면 사용할 해시 함수 수는 줄고, 블룸 필터가 커지면 더 많은 해시 함수를 사용할 수 있다. 적절한 설정은 예상 항목 수와 허용 가능한 오탐률에 달려 있다. 이 추정이 불확실하다면 원문은 필요한 것보다 더 큰 필터를 쓰는 편이 나을 수 있다고 설명한다. 블룸 필터의 수학적 배경

삭제할 때의 주의점

표준 블룸 필터에서는 항목을 삭제할 수 없다. 항목이 설정한 비트를 0으로 바꾸면 다른 항목의 존재 정보도 지울 수 있기 때문이다. 카운팅 블룸 필터는 비트 대신 카운터 배열을 사용해 삭제를 지원하지만, 카운터 크기만큼 메모리를 더 쓰며 카운터가 최댓값에 도달하면 데이터가 손상될 위험이 있다. 또한 삭제 과정에서 다른 항목의 카운터까지 줄어들면 표준 블룸 필터에는 없는 미탐이 생길 수 있다.

블룸 필터는 메모리를 줄이는 대신 오탐을 감수하는 선택이 필요한 경우 유용하다. 다만 삭제가 필요한지, 예상 항목 수와 허용 오탐률을 얼마나 정확히 추정할 수 있는지 먼저 따져야 한다.

원문 참고 자료: 해시 함수 설명, Akamai 기술 논문, BigTable 논문