확률적 자료구조를 이용한 추정 - 원소 포함 여부 판단(Membership Query)과 Bloom Filter

어느 글을 가져온 것인데, 어디서 가져온 것인지 기억이 나질 않는다.ㅠ

membership query란 어떤 집합  와 어떤 원소   가 '' 관계인지 묻는 것을 말합니다. java.util.Set 인터페이스의 boolean contains(Object e) 메서드가 대표적인 membership query의 예입니다. 정확한 membership query 결과 값을 도출하려면 Java Collection의 set나 STL의 set 같은 symbol table 구현체를 이용하거나, 모든 원소를 데이터베이스에 저장하여 존재 여부를 판단하게 할 수 있습니다. 그러나 메모리에 모든 원소를 저장하면 메모리를 너무 많이 사용하고, 데이터베이스를 이용해 조회하면 상대적으로 시간이 많이 소요된다는 단점이 있습니다.

"확률적 자료구조를 이용한 추정 - 유일한 원소 개수(Cardinality) 추정과 HyperLogLog"의 cardinality와 마찬가지로, membership query에도 확률적 자료구조를 이용할 수 있습니다. Bloom Filter는 메모리를 매우 적게 사용하면서 membership query 결과를 알 수 있는 방법으로, 데이터베이스를 구현할 때나 네트워크 보안 시스템을 사용할 때 이용합니다. 그러나 언제나 정확한 값(정해)을 얻는 것은 아니고 경우에 따라 false positive(실제 데이터가 없는데 있다고 판단하는 경우)가 발생할 수 있습니다. 그러나 false positive가 발생하는 경우 데이터베이스를 조회하여 데이터 존재 여부(원소 포함 여부)를 판단할 수 있기 때문에, 시스템 전체적으로는 항상 정해를 도출할 수 있습니다.

이 글에서는 Bloom Filter의 기본 원리를 간략하게 살펴보겠습니다.

Bloom Filter 동작 과정

Bloom Filter는 어떤 원소  가 어떤 집합  의 원소인지 확률적으로 판단하는 표시함수(indicator function, 

)이다. 그러나 Bloom Filter를 이용하여 어떤 원소  에 대한 membership query를 수행했을 때, 수행 결과가 '참'이라고 해도, 반드시  가   에 포함되는 것은 아니다(false positive). 하지만 실제로는 데이터가 있는데, 없다고 잘못 판단하는 경우(false negative)는 없다. 다시 말해, Bloom Filter를 이용한 membership query의 결과 값은 '아마도 해당 집합의 원소인 것 같다', 또는 '확실히 해당 집합에 포함된 원소가 아니다'를 뜻한다. 이런 특성 때문에 Bloom Filter는 단독으로 사용하는 것보다는 확률적인 방법이 아닌 다른 방법을 보조하는 역할로 사용하는 것이 적합하다. 그림 1은 Bloom Filter를 적용하는 대표적인 경우를 나타내고 있다.

그림 1 대표적인 Bloom Filter 적용 예

그림 1에서 알 수 있듯이, Bloom Filter의 주목적은 '데이터베이스가, 원소(키)가 존재하지 않는다는 것을 파악하는 데 소모되는 자원의 낭비를 줄이는 것'이다.

Bloom Filter는 m개의 원소로 이루어진 하나의 비트 배열 V와 k개의 서로 독립적인(independent) 종류의 이산 균등 분포(uniformly distributed) 해시 함수를 이용한 자료구조이다. 이때 해시 함수는 각각의 입력 값에 대해 0에서 m-1 중 하나를 반환하는 함수이다(

).

Bloom Filter에 원소를 삽입할 때에는 입력 원소에 대하여 k개의 해시 함수에 대한 각각의 결과 값을 배열 V에 대한 인덱스로 사용하여 해당 위치를 1로 설정한다(

).

원소 x가 Bloom Filter에 포함되어 있는지 확인하는 방법을 알아보자. 원소 x에 대해 k개의 모든 해시 결과를 V에 대한 배열 인덱스로 사용하였을 때 해당 배열 값이 모두 1이면 '아마도 해당 집합의 원소인 것 같다'라고 판단한다. 이때 단 하나라도 원소 배열 값이 1이 아니라면, '집합에 포함된 원소가 확실히 아니다'라고 판단할 수 있다(

).

그림 2 3개의 해시 함수와 비트 배열의 크기가 18인 Bloom Filter(원본 출처:http://en.wikipedia.org/wiki/Bloom_filter)

그림 2는 Bloom Filter를 이용해 어떻게 확률적인 membership query를 수행하는지를 잘 보여 준다. 집합 {x,y,z}의 원소에 대해 각각의 해시 함수(그림 2에서는 3개의 해시 함수)를 수행했을 때, 해시 함수 결과 값을 배열 인덱스로 한 값은 모두 1이다. 이 경우 x,y,z는 '아마도 해당 원소의 집합인 것 같다'라고 판단할 수 있다. 반면, w에 대해서는 해시 함수의 실행 결과 값이 가리키는 배열 V의 원소 값이 모두 1은 아니다. 따라서 w는 '집합에 포함된 원소가 확실히 아니다'라고 판단할 수 있다.

false positive가 일어날 확률

그림 1에서 확인할 수 있듯이 false positive가 일어날 확률이 줄어들수록 불필요한 데이터 조회를 줄일 수 있다. 따라서 false positive에 대한 기대 확률을 정하고 Bloom Filter를 적용할 필요가 있다.

Bloom Filter에 원소 x를 삽입할 때에는 각각의 해시 함수를 실행한 결과 값을 비트 배열 V에 대한 배열 인덱스로 하여 해당 비트를 1로 설정하기 때문에, 해시 함수를 한 번 실행한 후 V의 어떤 요소 값이 1로 설정될 확률은 

이다. 해시 함수를 한 번 실행한 후 특정 비트를 1로 설정하지 않을 확률은 당연히 

 이고, 이는 

로 표현할 수 있다. 해시 함수를 k개 실행하고 n개의 원소를 삽입했을 때 V 배열의 특정 비트가 1로 설정되어 있을 확률은 모든 경우에서 설정되어 있지 않은 확률을 뺀

이다. 각각의 해시 함수 수행 결과와 Bloom Filter에 값을 삽입하는 것은 모두 독립 사건이기 때문이다.

false positive는 x에 대하여 k개의 해시 함수 수행 결과를 인덱스로 하는 배열 V의 첨자 값이 모두 1일 때 발생한다. 해시 함수 실행 결과는 독립 사건이기 때문에, false positive 확률은 특정 비트가 1로 설정될 확률을 k번 곱한 

이다. 

이기 때문에 

으로 표현할 수 있다. 즉, false positive가 일어날 확률 

인데 k 값이 

일 때 

는 최솟값을 가진다. 즉 전체 원소의 개수 n, 비트 배열 V의 크기인 m, 해시 함수 개수 k, 이 셋 중 두 개의 값을 알거나 정하면, 

가 최소가 되도록 다른 변수 값을 구할 수 있다는 뜻이다.

수식으로 확인하지 않아도 직관적으로도 알 수 있겠지만, false positive가 일어날 확률은 비트 배열의 크기인 m이 클수록, 원소 개수인 n이 작을수록 낮다. 해시 함수 개수 k의 경우에는 일정 수준으로 증가할 때까지는 false positive가 일어날 확률이 낮아지지만, 일정 수준 이상 넘어서면 false positive가 일어날 확률이 높아진다. 게다가 해시 함수 수행 비용 또한 고려해야 하기 때문에 연산 비용을 고려한 k 값을 선택해야 한다.

이므로 

는 

으로 표현할 수 있다.

그림 3 역시 Wikipedia에서 인용한 것인데, 해시 함수 개수 k를 최적인 값 

로 했을 때, n과 m의 변화에 따른 

 변화를 파악할 수 있다.

그림 3 해시 함수 개수 k를 최적으로 했을 때, n과 m의 변화에 따른 

변화(원본 출처:http://en.wikipedia.org/wiki/Bloom_filter)

그림 3은 n의 변화량을 가로축에, 

를 세로축에 둔 

 변화량 그래프로, 각각의 급간은 

이다. 가장 왼쪽 

 변화량 그래프부터 차례대로 m 값에 따른 배열 V의 크기를 바이트 단위로 표현하면 32바이트, 512바이트, 8KB, 128KB, 2MB, 32MB, 512MB, 8GB이다.

가 충분히 낮은 상태를 유지하다가도(1% 이하) n이 10배 증가하면 

 값이 1에 수렴하여 사실상 membership query로서의 역할을 하지 못하는 경향을 확인할 수 있다. n의 값이 천만일 때는 32MB 크기의 V로 1% 미만의 

를 유지할 수 있으나, n의 값이 일억일 때에는 V의 크기가 512MB가 되어야 

를 1% 선에서 유지할 수 있다.

따라서, 만약 원소가 대소 구별이 가능한 형태인 경우에는(total ordering) 데이터 급간별로 Bloom Filter를 둔다면 메모리 사용량을 아낄 수 있다. 즉, 512MB 크기의 배열 V 하나를 두는 대신 32MB 크기의 V 배열 10개를 둘 수 있다.

마치며

Bloom Filter를 사용하는 대표적인 경우는 membership query에 대한 디스크 I/O 줄여야 할 때이다. 가령 화이트리스트와 블랙리스트 방식을 사용하는 보안 시스템의 경우, Bloom Filter를 사용하면 시스템의 성능과 처리량을 향상시킬 수 있다. 보안 시스템뿐만 아니라 Chrome의 경우에도 보안 위험이 있는 URL 접근인지 파악하는 목적으로 Bloom Filter를 사용한다.Hadoop, BigTable, Cassandra 같은 데이터베이스·저장소는 물론, Squid 같은 웹 캐시 시스템에서도 Bloom Filter를 사용하고 있다.

Bloom Filter는 상대적으로 구현하기 쉬운 편에 속하기 때문에, 언어별로 구현체를 찾기가 어렵지 않다. Java 개발 환경에서 자주 사용하는 라이브러리인 guava에도 Bloom Filter가 있다.

하지만 Bloom Filter는 치명적인 단점이 있다. 한 번 삽입한 원소를 삭제할 수 없다는 것이다. 서로 다른 x, y에 대하여 

 일 수 있기 때문이다. 따라서 값을 아예 삭제하지 않거나 거의 삭제하지 않는 데이터베이스에 Bloom Filter를 적용할 때 효과를 기대할 수 있다. Hadoop, BigTable, Cassandra는 주로 데이터 분석에 사용하기 때문에 모두 Bloom Filter를 적용하는 것이 유리한 데이터베이스·저장소이다.

참고

http://ko.wikipedia.org/wiki/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0

wh-oracle_BLOOM_FILTER.pdf

---

Cuckoo Filter

cuckoo-conext2014.pdf