Bloom Filter(블룸 필터)

Bloom Filter(블룸 필터)

블룸 필터(Bloom filter)는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조입니다. 1970년 Burton Howard Bloom에 의해 개발되었습니다. 그 당시 컴퓨터의 저장 공간은 매우 부족하였습니다. 사용자가 입력하는 password의 보안을 올리고자, 영어 사전에 나오는 단어에 해당하는지 검사를 개발하였습니다. 코딩을 해보자면 hash-table이나 binary-search-tree로 구현할 수 있겠으나, 그 당시의 적은 저장 공간과 메모리로 어떻게 개발할 수 있을까요? 모든 단어를 집합의 원소로 생각하고 입력으로 들어온 패스워드가 집합에 속해있는지 검색을 하는 방식으로 구현할 수 있습니다.

여기서 membership checking(원소가 집합에 속해있는지 확인)에서 발생하는 오류에서 FP와 FN을 살펴봅시다.

FP(False Positive)는 집합에 원소가 속하지 않는데(member가 아님), 있다고 잘못 판단한 경우입니다.

FN(False Negative)는 집합에 원소가 속해 있는데(member), 아니라고 판단한 경우입니다.

모든 단어를 집합(set)으로 모아놓고, 간결하게 표현합니다. m개의 단어 개수 만큼 m개의 크기를 가지고, 있는지 없는 지 여부를 0과 1의 bitmap으로 표현합니다. 그리고 x라는 원소가 집합(s)에 속하는지(member) 확인합니다. hash 함수를 k개만큼(h1, h2, …, hk) 사용하여 원소가 있는지 검색합니다.

Encoding은 입력으로 들어온 값(x)에 대하여 k개의 hash 함수에서 나온 k개의 위치(position)에 1을 채워 넣습니다.

Decoding에서는 있는지 없는지 여부를 판단합니다. hash 함수 k개의 위치에서 모두 1이 있는 경우에는 member라고 판단합니다. 하나라도 1이 없다면, non-member라고 판단합니다.

다음의 경우 x는 3개의 hash 함수에서 1로 되어있기 때문에 member라고 판단하며, 입력값 y의 경우에는 2번째 hash 함수에서 0으로 되어 있기 때문에 집합에 포함되어 있지 않다 즉, non-member라고 판단합니다.

hash 함수를 여러 개로 두는 것에 따라, 병렬 처리도 가능해집니다. hash 함수를 인덱스 위치로 지정해서 구간에 따라 처리가 가능해지며, 시간과 공간 복잡도가 향상 됩니다.

공간 절약을 통해 DRAM에 있을 데이터를 SRAM으로 올릴 수 있습니다. 또한 시간 복잡도는 상수인 O(k)로 처리 시간이 절약됩니다. 그러나 FP(False Positive)가 용납이 되지 않는 application에서 사용하면 안됩니다.

S의 집합 개수는 m개, hash 함수는 k개가 있다면, n*k의 인덱스가 생성됩니다.

특정 elements가 선택될 확률은 1/m이며, 선택되지 않은 확률은 1에서 빼면 됩니다.

이를 통해서 특정 elements가 0으로 남아 있을 확률은 p의 수식과 같습니다.

동시 확률에 따라서 선택되지 않은 확률에 n*k승 하면 됩니다.

특정 elements가 1로 남아 있을 확률은 1-p입니다.

이에따라, FP에 대한 확률도 다음의 수식으로 계산할 수 있습니다.

모두가 1일 확률은 hash 함수 k개이므로 k승을 하면 됩니다. exp(지수)과 ln(자연 로그)로 표현 가능합니다.

일반적으로 n(입력의 크기), m(집합의 크기 : 영단어장), k 값에 따라 FP에 대한 변화가 생깁니다. n과 m은 일반적으로 고정되어 있으며, k 값을 최적화 하기 위해 최소값을 구해야 합니다. g는 f를 미분한 값입니다. g가 0이 되는 지점을 찾으면 됩니다.

hash 함수 개수인 k를 최적화 해봅시다. 미분에 따라 m과 n으로 k를 구할 수 있습니다. FP를 구한 f함수도 m/n에 대해서 정리할 수 있습니다.

m/n이 8로 고정되었을 때 hash 함수 k는 5.45로 값이 나오며, 일반적으로 소수점을 버린 값을 취하여 5를 사용하면 적절합니다.

Bloom Filter의 사용 예는 다음과 같습니다. 패스워드 검사, 그리고 Google의 BigTable이나 Apache Hbase, Cassandra에서 존재하지 않는 row와 column를 위한 디스크 IO를 줄이기 위해 사용됩니다. 또한 의심스러운 URL을 검사하기 위해 사용됩니다.

Bloom Filter는 네트워크에서도 사용됩니다. 원본 데이터의 길이가 길수록 Bloom Filter를 사용하는 것이 좋습니다.

IP Address를 확인하는 라우팅 테이블(routing table)을 검사하기 위해서도 사용됩니다. 네트워크를 통한 파일 전송에서는 패킷(packet)으로 라우터에서 목적지 주소로 전달이 됩니다. 복잡한 라우팅 테이블에 액세스하지 말고, Bloom Filter로 간단하게 표현합니다. 라우터에 대한 port를 목적지의 주소들을 집합으로 표현합니다. 그리고 이 여러 개의 집합에서 값이 있는 지 없는 지 확인합니다. IPv4의 경우 A, B, C, D 클래스 별로 4개의 그룹으로 만들어 Bloom Filter로 검사합니다.

기존의 FP(False Positive)를 낮추고자 hash 함수의 개수를 늘리고, 메모리 액세스가 많아져 처리하는 시간이 길어지게 됩니다.

현대로 넘어오면서 운영체제(OS : 32bit/64bit)에 따라 한 번의 메모리 엑세스(access)로 가져오는 크기가 커졌습니다. 이에 따라 한번의 메모리 액세스로 Bloom Filter의 응용을 접목하였습니다.

밑의 예시는 m = 24bit라고 가정했을 경우, word size는 8bit로 3개의 word로 이루어집니다.

현대의 컴퓨터인 32/64bit OS에서는 word size가 64bit로 메모리에서 CPU로 가져올 때 너무 많은 bit를 가져오면서 낭비가 발생이 됩니다. 그래서 한 번의 메모리 액세스로 Bloom Filter로 구현 하였습니다.

word의 크기에 따라 n/m에 따른 FP 비율을 볼 수 있습니다. word에 따른 bit수가 달라져도 일정한 FP의 ratio를 볼 수 있습니다.

Bloom-1 Filter를 사용함에 따라 기존의 k의 개수가 1로 바뀌며 비슷한 성능을 보이게 됩니다.

Counting Bloom Filter

이전의 Bloom Filter에서는 0과 1로 이루어져 있어, delete 삭제 연산이 불가능했습니다. Hash 함수가 가르키는 값이 중첩이 된다면 다른 입력값에 대해 영향을 미치게 되어 문제가 발생해 delete 연산은 불가했습니다. Counting Bloom Filter는 bitmap이 아닌 카운트된 숫자값으로 되어 있어 IntegerMap으로 삭제 연산을 가능하도록 하였습니다. 하지만 Integer로 표현하기 위해서는 크기가 커지는 단점이 있습니다.

Encoding 시에 hash 함수에 중첩되면 1을 증가합니다. 삭제 시에는 1을 감소시킵니다.

Counter overflow가 발생합니다. 즉 counter의 최대 카운팅 수가 현저히 적다면 FP가 높아집니다. 이에 따라 카운터의 개수가 충분히 커야합니다.

Counter overflow에 대한 확률을 계산해봅시다. n개의 입력에 hash 함수 k개에, 카운터가 m개인 경우로 고려합니다.

c(i)는 i번째 counter의 count 값입니다.

k를 고르기 위해서는 m/n * ln2 보다 작아야합니다.

4 bit(0~15)로 표현하면 16이상이 되는 것이 에러가 발생하지만 그 에러값은 상당히 낮습니다.

cell 하나 당 4 bit를 유지하면, 안정적으로 운영이 가능합니다.

이처럼 Bloom Filter는 다양한 곳에서 응용이 되고, 더 발전한 Bloom Filter로 사용되고 있습니다.