bloom filter

java library인 guava document를 보다가 bloom filter라는 게 있어서 찾아봤다.

https://github.com/google/guava/wiki/HashingExplained#bloomfilter

모든 데이터에 대해서 바로 데이터가 있는지 체크하려고 하면 데이터가 클 수록 비용이 많이 들게 든다.

그래서 bloom filter 에서 데이터가 있는지 한번 체크하고, 데이터에 실제로 접근하도록 하는 모델을 많이 쓴다. 

bloom filter는 완벽한 searching table을 제공하는게 아니라 서치 비용(space and time)을 줄이기 위함이다.

cassandra, base, bigtable, hbase, ip filtering, router, 웹 검색 등 아주 많은 곳에서 사용되고 있다.

https://en.wikipedia.org/wiki/Bloom_filter

블룸필터 튜토리얼(동작 구경): http://llimllib.github.io/bloomfilter-tutorial/

영어에 당황하지 않고 그림 위주로 하나씩 살펴보자.

bloom filter 를 위해 byte array를 하나 생성한다.

[x, y, z]의 값이 있고, hash function 3개를 채택하면 위와 같은 그림을 그릴 수 있다. 

x 에 대해 hash function 이 3개 적용되므로 byte array에는 3개의 값이 true로 넣어진다.

y, z에 대해서도 마찬가지로 하면 위와 같은 byte array가 남게된다.

이 상태에서 w를 조회하려고 하면 hash function 3개를 다시 계산하고 하나라도 0을 리턴하면 그 값은 존재하지 않는다라는 것을 빨리 알 수 있다.

이 때 실제로 존재하지 않는 값인데, true를 리턴하는 false Positive가 발생할 수 있지만, 이 경우에는 실제 db등에 다시 확인을 했을 때 값이 없음이 나온다. 

하지만 false Positive가 많아질 수록 다시 비용이 증가하게 될 것이므로 false Positive를 얼마나 허용할 것인지 염두해두어야한다.

hash  function 최적 갯수, k = m/n * ln2 (m은 bloom filter bit size, n = size of data)

bloom filter의 단점은 한번 insert한 것은 remove할 수 없는 단점이 있다. byte array에 넣은 값들이 몇번이나 count되었는지 알 수 없기 때문에 remove시 함부로 byte array값을 초기화 할 수 없다. 그래서 이런 단점을 극복한 counter filter가 나왔다.

guava의 bloom filter를 살펴보면 아래와 같이 선언되어있다. 

첫번째 Funnel은 list<hash function>로, 두번째 인자는 넣으려는 전체 데이터 갯수, falsePositive을 얼마나 허용할 것인지에 대한 값을 넣어주면 bloom filter를 생성할 수 있다.

BloomFilter.create(Funnel funnel, int expectedInsertions, double falsePositiveProbability)

example: BloomFilter.create(someFunnel, 500, 0.1)