블룸 필터

블룸 필터의 동작 방식은 크게 삽입과 조회 두 가지로 나뉜다. 핵심은 하나의 값을 여러 개의 해시 함수를 통해 변환하고, 그 결과를 하나의 비트 배열에 기록하는 것이다.

삽입 과정에서는 저장하려는 값을 k개의 서로 다른 해시 함수에 입력한다. 각 해시 함수는 0부터 m-1 사이의 정수 인덱스를 생성한다. 생성된 모든 k개의 인덱스에 해당하는 비트 배열의 위치를 1로 설정한다. 이 과정은 다른 값이 삽입되더라도 누적되어 적용되며, 기존에 1로 설정된 비트는 그대로 유지된다.

조회 과정에서는 확인하려는 값을 동일한 k개의 해시 함수에 입력하여 k개의 인덱스를 얻는다. 그런 다음 비트 배열에서 이 인덱스들에 해당하는 모든 비트가 1로 설정되어 있는지 검사한다. 모든 비트가 1이면 "아마도 존재함"으로 판단하며, 하나라도 0인 비트가 있으면 "절대 존재하지 않음"으로 판단한다. 이 "아마도 존재함" 판단에서 긍정 오류가 발생할 가능성이 있다.

블룸 필터는 확률적 자료 구조이기 때문에 오류 가능성을 내포한다. 가장 중요한 특징은 부정 오류(false negative)가 절대 발생하지 않는다는 점이다. 즉, 블룸 필터가 특정 원소가 집합에 "없다"고 판단했다면, 그 결과는 100% 정확하다. 이는 원소가 삽입될 때 설정된 비트들이 다른 원소 삭제 과정에서 0으로 되돌려지지 않기 때문이다. 따라서 한 번 설정된 비트는 계속 1로 유지되어, 해당 원소에 대한 조회 시 항상 "있을 수 있다"는 결과를 반환하게 된다.

반면, 긍정 오류(false positive)는 발생할 가능성이 있다. 이는 서로 다른 원소들이 해시 함수를 통과한 후, 테이블 내에서 동일한 비트 위치들을 가리키는 충돌이 발생했기 때문이다. 예를 들어, 집합에 없는 원소 A를 조회할 때, A의 해시값들이 가리키는 모든 비트들이 다른 원소들(B, C 등)의 삽입 과정에서 이미 1로 설정되어 있었다면, 블룸 필터는 A가 집합에 "있을 수 있다"고 잘못 보고하게 된다. 이러한 오류 확률은 사용된 해시 함수의 개수, 비트 배열의 크기, 그리고 저장된 원소의 수에 따라 결정된다.

이러한 오류 특성 때문에 블룸 필터의 결과 해석에는 주의가 필요하다. "없다"는 답변은 확실하지만, "있다"는 답변은 확률적일 뿐이다. 따라서 블룸 필터는 1차적인 빠른 필터링 도구로 사용되며, 긍정 오류가 발생하더라도 후속 확인 절차(예: 디스크에서의 정확한 조회)를 통해 최종적으로 정확성을 보장하는 방식으로 활용된다. 이는 메모리 사용량과 속도를 극대화하면서도 기능적 타협점을 찾은 설계이다.

블룸 필터의 근본적인 한계는 요소를 삭제할 수 없다는 점이다. 이는 블룸 필터의 핵심 동작 방식에서 비롯된다. 어떤 값을 삽입할 때, 그 값은 여러 개의 해시 함수를 거쳐 생성된 인덱스들에 해당하는 비트를 1로 설정함으로써 집합에 기록된다. 문제는 서로 다른 여러 값이 동일한 비트 위치를 공유할 수 있다는 점이다. 만약 특정 값을 삭제하기 위해 그 값에 대응되는 모든 비트를 0으로 되돌린다면, 공유된 비트를 사용하고 있던 다른 값들의 존재 여부 정보가 손상되어 부정 오류(false negative)가 발생할 수 있다. 즉, 실제로는 집합에 존재하는 값이 존재하지 않는다고 잘못 판단될 위험이 생긴다.

이러한 제거 불가능성은 블룸 필터가 확률적 자료 구조로서 절대적인 부정 오류를 허용하지 않는다는 원칙과 직접적으로 연결된다. 블룸 필터는 "없다"고 답할 때는 100% 확신할 수 있어야 하며, 이를 보장하기 위해서는 한 번 설정된 비트를 함부로 지워서는 안 된다. 따라서 블룸 필터는 주로 요소의 추가와 조회만 필요한 응용 분야, 예를 들어 캐시 시스템에서의 중복 데이터 확인이나 네트워크 라우터에서의 패킷 필터링 등에 적합하다.

제거 기능이 필요한 경우에는 블룸 필터의 변형인 카운팅 블룸 필터(Counting Bloom Filter)를 사용할 수 있다. 이 구조는 각 비트 대신 작은 카운터(counter)를 사용하여, 삽입 시 해당 인덱스의 카운터를 증가시키고 삭제 시 감소시킨다. 그러나 이 방식은 추가적인 메모리 오버헤드가 발생하며, 긍정 오류(false positive)로 인해 실제로 삽입되지 않은 값을 삭제하려 시도하는 등의 새로운 문제를 야기할 수 있다.

삽입 알고리즘은 블룸 필터의 핵심 동작으로, 새로운 요소를 필터에 추가하는 과정이다. 이 과정은 매우 직관적이고 간단하여 효율적이다. 먼저, 삽입할 데이터를 미리 정의된 여러 개의 해시 함수에 입력한다. 각 해시 함수는 입력값을 고정된 크기의 비트 배열 내 특정 인덱스 위치로 변환한다. 이후, 이렇게 계산된 모든 인덱스에 해당하는 비트 배열의 값을 1로 설정한다. 이 작업이 삽입의 전부이다.

이 알고리즘의 특징은 데이터 자체를 저장하지 않고, 그 데이터의 존재 여부를 나타내는 '흔적'만 비트 배열에 남긴다는 점이다. 따라서 해시 테이블과 달리 원본 데이터를 복원할 수 없으며, 저장 공간을 매우 적게 사용한다. 여러 개의 해시 함수를 사용하는 이유는 단일 해시 함수만 사용할 경우 발생할 수 있는 충돌 확률을 줄이고, 긍정 오류율을 낮추기 위함이다.

삽입 과정에서 서로 다른 데이터가 동일한 인덱스 위치를 가리킬 수 있다. 이는 해시 충돌의 일종으로, 이후 조회 시 긍정 오류의 원인이 된다. 그러나 한 번 1로 설정된 비트는 다른 데이터의 삽입으로 인해 다시 0으로 되돌아가지 않는다. 이러한 '한 방향성' 덕분에 블룸 필터에서는 절대 부정 오류가 발생하지 않는다. 즉, 필터가 '없다'고 판단한 요소는 절대로 삽입된 적이 없는 요소임이 보장된다.

이 간단한 알고리즘은 맞춤법 검사기나 웹 브라우저의 안전 검사와 같이 빠른 속도와 적은 메모리 사용이 중요한 대규모 데이터 필터링 작업에 적합하다. 다만, 비트를 1로만 설정할 수 있어 기존 요소의 제거는 기본적으로 불가능하며, 이 제약을 극복하기 위해 카운팅 블룸 필터와 같은 변형 자료구조가 개발되었다.

블룸 필터에서 특정 요소의 존재 여부를 확인하는 조회 알고리즘은 매우 간단하고 빠르게 동작한다. 조회를 수행하려면, 확인하고자 하는 값을 블룸 필터에 삽입할 때 사용한 것과 동일한 여러 개의 해시 함수에 순차적으로 통과시킨다. 각 해시 함수는 입력값을 처리하여 비트 배열 내의 특정 인덱스 위치를 가리키는 해시값을 생성한다.

알고리즘의 핵심은 이렇게 생성된 모든 인덱스 위치에 대응되는 비트 배열의 값이 1로 설정되어 있는지를 검사하는 것이다. 만약 모든 인덱스의 비트 값이 1이라면, 해당 값은 "아마도 집합 내에 존재한다"고 판단한다. 반면, 하나라도 0인 비트가 발견되면, 그 값은 "절대로 집합 내에 존재하지 않는다"고 확정적으로 결론지을 수 있다. 이 과정에서 발생할 수 있는 긍정 오류는 모든 해시 인덱스가 다른 요소들에 의해 우연히 모두 1로 설정되어 있을 때 일어난다.

이러한 조회 방식은 부정 오류가 절대 발생하지 않음을 보장한다. 값이 실제로 존재했다면 삽입 과정에서 해당하는 모든 비트가 1로 설정되었을 것이므로, 조회 시 0이 발견되는 경우는 원천적으로 불가능하기 때문이다. 이 알고리즘의 강점은 복잡한 계산 없이 고정된 수의 해시 연산과 메모리 접근만으로 결과를 도출할 수 있어, 대규모 데이터베이스의 사전 필터링이나 웹 브라우저의 안전 검사와 같이 속도가 중요한 맥락에서 매우 효율적으로 활용될 수 있다.

블룸 필터의 성능, 즉 긍정 오류 확률은 비트 배열의 크기(m), 사용하는 해시 함수의 개수(k), 그리고 삽입될 원소의 예상 개수(n)라는 세 가지 매개변수에 의해 결정된다. 설계 시 주어진 예상 원소 개수(n)와 허용 가능한 긍정 오류율(p)을 기준으로 최적의 비트 배열 크기(m)와 해시 함수 개수(k)를 계산하여 설정한다.

최적의 매개변수는 수학적 모델을 통해 도출된다. 긍정 오류 확률을 최소화하기 위한 이론적 최적 해시 함수 개수(k)는 k = (m/n) * ln(2)로 근사된다. 이를 바탕으로 필요한 최소 비트 배열 크기(m)는 m = - (n * ln(p)) / (ln(2))^2 공식으로 계산할 수 있다. 이는 특정 오류율을 보장하기 위해 각 원소당 필요한 비트 수가 대략 1.44 * log2(1/p)임을 의미한다.

실제 구현에서는 계산된 최적의 해시 함수 개수(k)가 정수가 아닐 수 있으므로, 가장 가까운 정수로 반올림하여 사용한다. 또한 독립적인 k개의 해시 함수를 생성하는 것은 비용이 클 수 있으므로, 두 개의 기초 해시 함수를 조합하여 여러 개의 해시 값을 만들어내는 기법이 널리 사용된다. 매개변수 최적화를 통해 메모리 사용량과 계산 속도, 정확도 사이의 균형을 효율적으로 맞출 수 있다.

블룸 필터는 웹 브라우저의 안전 검사 기능에서 중요한 역할을 한다. 특히 구글 크롬은 사용자가 접속하려는 URL이 악의적인 사이트나 멀웨어를 배포하는 사이트인지 빠르게 확인하기 위해 블룸 필터를 활용한다. 이는 수억 개에 달할 수 있는 악성 URL 목록을 효율적으로 관리하고 검색하기 위한 방법이다.

전체 악성 데이터베이스를 로컬에 저장하거나 매번 서버에 질의하는 것은 메모리 사용량과 응답 시간 측면에서 비효율적이다. 블룸 필터는 매우 적은 메모리만으로 특정 URL이 '안전하지 않을 가능성'이 있는지를 순식간에 걸러낼 수 있다. 블룸 필터의 검사 결과 '없음'이 나오면 해당 URL은 절대 악성 목록에 포함되지 않았음을 의미하므로, 브라우저는 안전하게 접속을 허용한다.

반면, 블룸 필터의 검사 결과 '있을 수 있음'이 나오면, 이는 긍정 오류의 가능성을 내포한다. 이 경우 브라우저는 더 정확한 판단을 위해 전체 악성 코드 목록을 가진 원격 서버에 추가 확인 요청을 보내거나, 사용자에게 경고 페이지를 표시하는 등의 후속 조치를 취한다. 이렇게 2단계 검증 방식을 채택함으로써, 사용자 경험을 저해하지 않으면서도 보안 수준을 유지할 수 있다.

이러한 방식은 네트워크 트래픽을 줄이고 브라우저의 성능을 높이는 데 기여하며, 클라우드 기반의 실시간 보안 서비스와 결합되어 광범위하게 사용된다.

맞춤법 검사기는 블룸 필터의 빠른 속도와 적은 메모리 사용량이라는 장점을 활용하는 대표적인 사례이다. 맞춤법 검사기는 사용자가 입력한 단어가 사전에 등재된 올바른 단어인지 빠르게 판단해야 하며, 이 과정에서 사전에 없는 단어(오타)를 걸러내는 것이 핵심이다.

이때 블룸 필터는 올바른 단어들의 거대한 사전을 압축하여 메모리에 저장하는 데 사용된다. 모든 올바른 단어를 블룸 필터에 삽입해 두면, 사용자가 입력한 단어에 대해 블룸 필터를 조회하여 결과를 즉시 얻을 수 있다. 블룸 필터의 특성상, 사전에 없는 단어가 '있을 수도 있다'는 긍정 오류는 발생할 수 있지만, 사전에 있는 단어를 '없다'고 판단하는 부정 오류는 절대 발생하지 않는다.

이는 맞춤법 검사 시나리오에서 매우 유리한 특성이다. 긍정 오류가 발생하면, 실제로는 사전에 없는 잘못된 단어를 올바른 단어로 오인할 수 있다. 그러나 이는 사용자에게 '이 단어는 맞는 것 같다'고 안내하는 수준의 오류이며, 애플리케이션의 치명적 결함으로 이어지지 않는다. 반면, 만약 부정 오류가 발생해 올바른 단어를 계속 오타로 표시한다면 사용자 경험을 크게 해칠 것이다. 블룸 필터는 이러한 부정 오류 가능성을 원천적으로 차단하면서도, 전통적인 해시 테이블을 사용할 때보다 훨씬 적은 메모리로 수백만 개의 단어 사전을 처리할 수 있게 해준다.

블룸 필터는 메모리 사용량이 적고 검색 속도가 매우 빠르다는 특성 덕분에 대규모 데이터베이스 시스템에서 효율적인 사전 필터링 도구로 널리 활용된다. 특히 디스크나 네트워크와 같은 상대적으로 느린 저장 매체에 접근하기 전에, 특정 데이터가 절대 존재하지 않음을 빠르게 판단하여 불필요한 비용이 큰 조회를 제거하는 데 유용하다. 예를 들어, 분산 데이터베이스나 키-값 저장소에서 존재하지 않는 키에 대한 조회 요청을 최소화하거나, 데이터 웨어하우스에서 특정 조건을 만족하지 않는 데이터 블록을 쿼리 단계에서 조기에 배제하는 데 사용될 수 있다.

구체적인 활용 사례로는 카산드라나 HBase와 같은 NoSQL 데이터베이스에서, 실제 데이터 파일을 읽기 전에 블룸 필터를 검사하여 해당 키가 특정 SSTable에 존재할 가능성이 있는지 먼저 판단한다. 만약 블룸 필터가 "없음"을 반환하면, 해당 데이터 파일에는 절대 키가 존재하지 않으므로 즉시 조회를 중단할 수 있어 디스크 I/O를 크게 줄인다. 이는 수십억 개의 레코드를 처리하는 환경에서 시스템 성능을 향상시키는 핵심 기법 중 하나이다.

이러한 필터링은 긍정 오류가 발생할 수 있지만, 부정 오류는 절대 발생하지 않는다는 보장이 전제된다. 즉, 블룸 필터가 "있을 수 있다"고 답한 경우에만 비로소 정확한 확인을 위한 본격적인 조회를 수행하면 되므로, 전체적인 처리 효율을 극대화할 수 있다. 대규모 데이터베이스의 인덱스나 메타데이터 관리, 그리고 조인 연산 전의 후보 집합 필터링과 같은 다양한 최적화 작업에 이 원리가 적용된다.

카운팅 블룸 필터는 기본 블룸 필터의 가장 큰 제약 중 하나인 요소 삭제가 불가능하다는 점을 해결하기 위해 고안된 변형 자료 구조이다. 기존 블룸 필터는 각 위치를 1비트로 표현하여 특정 값의 존재 여부만을 표시하기 때문에, 한 번 설정된 비트를 다른 값이 공유하고 있을 가능성이 있어 안전한 삭제가 불가능했다. 카운팅 블룸 필터는 이 문제를 해결하기 위해 각 위치를 단순한 1비트가 아닌 여러 비트로 이루어진 카운터로 대체한다.

삽입 연산 시, 값은 여러 해시 함수를 통해 여러 인덱스를 생성하고, 이 인덱스에 해당하는 모든 카운터의 값을 1씩 증가시킨다. 조회 연산은 기존과 동일하게 해당 인덱스들의 카운터 값이 모두 0보다 큰지를 확인한다. 삭제를 수행할 때는 삽입의 역과정으로, 해당 인덱스들의 카운터 값을 1씩 감소시킨다. 이 방식을 통해 여러 값이 동일한 인덱스를 공유하더라도, 카운터 값을 관리함으로써 특정 값의 삭제가 다른 값의 존재 여부 판단에 영향을 미치지 않도록 한다.

그러나 카운팅 블룸 필터에는 새로운 문제점이 존재한다. 가장 큰 문제는 긍정 오류가 발생한 값, 즉 실제로는 집합에 없지만 필터가 있다고 잘못 판단하는 값을 삭제하려고 시도할 수 있다는 점이다. 이렇게 잘못된 삭제가 수행되면, 해당 인덱스들의 카운터 값이 부정확하게 감소하여 이후의 조회나 삭제 연산에 오류를 일으킬 수 있다. 이러한 오류를 방지하기 위해서는 삭제 요청이 들어온 값이 실제로 집합에 존재하는지를 확인할 별도의 메커니즘, 예를 들어 별도의 해시 테이블을 유지하는 것이 필요하다.

또한, 카운터의 비트 수를 제한적으로 사용하기 때문에 많은 삽입과 삭제가 반복되면 카운터가 오버플로될 위험이 있다. 이는 다시 부정 오류가 발생할 가능성을 만들어낼 수 있다. 따라서 카운팅 블룸 필터는 삭제 기능이 반드시 필요한 특정 데이터베이스나 네트워크 응용 분야에서 주로 사용되며, 카운터의 크기와 해시 함수의 수를 신중하게 설계해야 한다.

블룸 필터의 기본적인 제한 사항을 극복하거나 특정 응용 분야에 더 적합하도록 다양한 변형이 제안되었다. 카운팅 블룸 필터 외에도 성능, 기능, 또는 보안을 개선한 여러 확장 형태가 존재한다.

블룸 필터의 공간 효율성을 더욱 높이기 위해 설계된 변형으로는 블록 블룸 필터와 압축 블룸 필터가 있다. 블록 블룸 필터는 비트 배열을 작은 블록으로 나누어 각 블록을 독립적으로 관리함으로써 캐시 효율성을 높인다. 압축 블룸 필터는 생성된 블룸 필터를 압축하여 전송하거나 저장하는 기법으로, 네트워크 통신에서 유용하게 활용된다. 또한, 스케치 기반의 확률적 자료구조인 쿠 필터는 블룸 필터와 유사한 기능을 제공하면서도 더 나은 공간 효율성을 목표로 한다.

특정 연산을 지원하기 위한 변형도 개발되었다. 삭제 가능 블룸 필터는 카운팅 방식 외에도 다른 메커니즘을 통해 요소의 삭제를 가능하게 한다. 동적 블룸 필터는 저장해야 할 요소의 수가 예측 불가능하게 증가하더라도 성능을 유지할 수 있도록 필터의 크기를 동적으로 조정하는 기능을 추가한다. 공간 효율적 블룸 필터는 거짓 긍정률을 최소화하면서도 메모리 사용량을 줄이는 데 중점을 둔다.

분산 컴퓨팅 환경을 위해 설계된 분산 블룸 필터는 여러 노드에 걸쳐 데이터를 분산 저장하고 질의할 수 있도록 한다. 보안 강화 블룸 필터는 저장된 데이터의 프라이버시를 보호하기 위해 암호학적 기법을 도입한 변종들로, 민감한 정보를 처리하는 시스템에서 고려된다.