[System Design] Bloom Filter

 

Bloom Filter 는 어떤 멤버가 집합에 속하는 지를 판단할 때 사용하는 자료구조다. Bloom Filter는 확률형 자료구조기 때문에, 집합에 속한 멤버를 확인하려고 할 때 틀린 답을 내뱉을 수 있다. 하지만 없는 멤버를 있다고는 말할 수 있지만(False Positive) / 있는 멤버를 없다고 말하지는 않는다(False Negative). 

 

어떻게 동작할까?

 

 

Bloom Filter는 0으로 셋팅되어 있는 bit array를 사용한다. 그리고, 두 개의 멤버(star, moon)를 이 Bloom Filter에 넣는다면 k개의 hash function을 사용한 후 modulo 연산을 해서 bit를 1로 채워넣는다.

 

 

어떤 문자(mars)가 이 집합에 속하는 지를 확인할 때 이렇게 만들어진 bit array를 사용한다. 마찬가지로 k개의 hash function을 수행한 후 modulo연산을 진행해서 해당 문자의 bit의 값들이 모두 1이면, 해당 문자는 이 집합에 속한다고 판단한다. 이 과정에서 hash collision이 발생하면 집합에 없는 문자인데도, 집합에 있다고 판단할 수 있는 문제가 발생하기도 한다.

 

 

어디서 사용할까?

 

Bloom Filter의 장점은 아무리 많은 데이터가 담겨 있는 집합이라고 해도 O(k)의 시간 복잡도로 문자가 집합에 속해있는지 확인할 수 있다는 점이다. 집합에 있는 것을 없다(False Negative) 는 이루어지지 않기 떄문에, 집합에 절대 속할 일 없는 원소를 걸러내는 전처리 용도로 사용한다고 한다.

 

Google 같은 경우, 유해 사이트를 검증할 때 Bloom Filter를 통해 1차적으로 전처리를 거치고 그 후에 DB에 접근하는 방식으로 DB 부하를 줄이는데 사용하고 있다고 한다.