블룸 필터 (Bloom Filter)

블룸필터는 해시테이블의 특이한 변종이라 할 수 있는 자료구조다.
1970년에 Burton Howard Bloom에 의해 처음 고안되었다. 그래서 블룸 필터다.

이건 데이터 집합에 특정 값이 존재하는지 여부만 확인할 수 있는 아주 단순한 기능만을 가진다.
게다가 그 확인도 부분적으로 실패 가능성이 있기 때문에 특수한 경우에만 사용된다.

구조와 원리

블룸필터도 일반적인 해시테이블과 같이 테이블의 형태로 구현이 된다.
다만 값은 0 or 1, boolean이다.

특이한 점은, 여러개의 해시함수를 쓴다는 것이다.
여기서는 해시함수를 3개 쓴다고 가정하겠다.

만약 값을 하나 필터에 넣는다면, 해시함수 3개를 돌려서 해시값 3개에 해당하는 테이블 인덱스에 값 1을 할당한다.
여기서 해시 충돌은 고려하지 않는다. 다른 값이 새로 들어와서 기존에 1로 할당되어있는 테이블 인덱스에 또 1을 쓰더라도 신경쓰지 않는다.

red와 blue가 같은 인덱스를 점유해도 신경쓰지 않음

특정 값의 존재여부를 확인할 때는, 마찬가지로 해시함수 3개를 돌려서 그 해시값 3개가 테이블에 다 존재하는지 확인한다.
3개가 전부 있다면 존재한다고 판단하고, 0-2개라면 없다고 판단한다.

여기서 유의할 점은, "존재한다"고 나온 것은 틀릴 수 있다는 것이다. 다른 값에서 해시 충돌이 잔뜩 발생해서 있는 것처럼 보일 수 있으니까!
이를 false positive라고 한다.
그리고 해시 함수가 많을수록 실패 확률은 떨어진다.

반대로 "존재하지 않는다"고 나온 것은 정확하다. 해시 충돌이고 자시고 없으면 진짜 없는 것이기 때문이다.

그리고 값을 넣는건 되는데 빼는게 안된다. 해시충돌을 신경쓰지 않기 때문에 막 빼버렸다간 다른 값까지 빼버리는 결과가 날 수 있기 때문이다.

장단점

이 알고리즘의 가장 큰 장점은 매우 가볍고 빠르다는 것이다.

해시테이블은 그 특성상 해시 충돌로 인해 최악 O(N)의 성능 저하가 발생할 수 있는 반면에, 블룸필터는 O(k)가 보장된다. 여기서 k는 해시함수의 개수다. 거의 상수시간인 셈이다.

게다가 단편적인 boolean list라서 메모리도 적게 먹고 구현도 간단하다.

하지만 여러모로 범용성이 떨어지는게 단점이다. 추가만 가능하고 삭제가 불가능하며, 결과가 항상 정확하지도 않다.

그래서 뭔가 대량의 데이터셋에서 빠르게 비존재를 확인할 때, 혹은 존재를 확인하되 가끔 틀려도 괜찮을 때 사용하곤 한다.

사용처

사용례는 생각보다 다양하다.

URL 필터링 등에도 곧잘 사용되는데, 대표적으로 크롬 브라우저에서 악성 URL을 판단할 때 사용한다고 한다.

빅데이터를 다룰 때도 응용된다.
빅데이터 DB 시스템인 GCP BigTable이나 Apache Hbase, Cassandra, 그리고 PostgreSQL에서는 블룸필터 매커니즘을 활용해 존재하지 않는 row나 column 등을 빠르게 식별, 무시해서 disk I/O를 최적화하는 기법을 사용한다.

low level로 내려가서 네트워크 수준에서도 블룸필터가 자주 사용된다.
패킷을 전달할때, 무거운 라우팅 테이블을 일일히 확인하는 대신에 블룸필터를 띄워서 빠르게 존재여부를 확인해서 전달하는 식이다.

블록체인에서도 꽤 많이 쓰더라.
이더리움에서 로그를 빨리 찾기 위해서 블룸필터를 쓰고, 비트코인도 지갑 동기화 속도를 늘리기 위해서 블룸필터를 썼다고 한다. 그게 취약점이 되긴 했지만.

이외에도 사용사례는 꽤 많은 편이다.

참조
https://ko.m.wikipedia.org/wiki/%EB%B8%94%EB%A3%B8_%ED%95%84%ED%84%B0
https://velog.io/@chlvlftn22/%EB%B8%94%EB%A3%B8%ED%95%84%ED%84%B0
https://stackoverflow.com/questions/54280508/can-bloom-filters-in-bigtable-be-used-to-filter-based-only-on-row-id
https://stackoverflow.com/questions/4282375/what-is-the-advantage-to-using-bloom-filters
https://en.m.wikipedia.org/wiki/Bloom_filter
https://systemdesign.one/bloom-filters-explained/