Bloom filter

Table of Contents

• Bloom filter 란?
• 어디에 쓰이고 있는지?
• References

Bloom filter 란?

얼마 전에, 자료구조 관련 공부를 하다가 bloom filter에 대해서 알게 되었다.
조금 더 공부해보니 확률적 자료구조라고 하던데 자료구조면 자료구조지 ‘확률적’ 자료구조는 또 뭐지? 싶어서 구글링을 해보았다.

Wikipedia에는 다음과 같이 적혀있다.

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not – in other words, a query returns either “possibly in set” or “definitely not in set”. Elements can be added to the set, but not removed (though this can be addressed with the counting Bloom filter variant); the more items added, the larger the probability of false positives.

요약해보자면 Burton Howard Bloom 이라는 분이 고안했고, 어떤 set에 특정 요소가 포함되는지 여부를 판단하는(이걸 membership query라고 부름)데에 사용된다고 한다.

몇가지 주요한 특징이라고 한다면,

• 모든 요소를 메모리에 적재하지 않고도 membership test를 할 수 있다.
• 요소를 bloom filter에 더할 순 있어도, 뺄 순 없다.
• 어떤 요소가 집합에 속한다는 것은 확실하게 알 수 없지만, 속하지 않는다는 것은 확실하게 알 수 있다. 즉, false positive는 존재하나 false negative는 존재하지 않는다.

이 정도가 아닐까 한다.

‘확률적’ 자료구조라고 이름 붙은 것은 아마 false positive가 존재하기 때문이지 않을까 생각한다. 특정 집합에 속하는 것을 확실히 알 수 있다면 ‘확률적’ 이 아니라 ‘결정적’ 일 테니까?

bloom filter에 관한 자세한 설명은 Naver D2 블로그에 잘 정리되어 있어서 링크로 갈음해둔다.
Hash function에 관한 기본적인 이해와 이과 고등수학 정도 알고 있으면 이해하는 데에 큰 어려움은 없는 아티클이다.

어디에 쓰이고 있는지?

확률적 자료구조라는 개념이 재미있기는 해도 실제 엔지니어링 필드에서 쓰임이 없다면 공부하는 의미가 별로 없었을 테지만, 이미 여러 도메인에서 활발히 사용되고 있는 자료구조였다.

실무에서 흔히 볼 수 있는 Redis에서도 사용하고 있고, Kafka 같은 데이터 처리 툴에서도 사용하고 있다고 한다.
NHN Cloud라는 조직에서도 bloom filter 활용기를 포스팅으로 만들어 두었다.

나는 아무래도 프론트엔드 엔지니어다 보니 여러 use-case들 중에서 Chrome Browser 에서의 use-case에 관심이 갔는데, 이 use-case에 관해 조금 더 깊게 살펴보고 글을 마칠까 한다.

우선, 내가 Chrome 개발자라고 생각해보자. Chrome은 Browser 시장에서 60%가 넘는 점유율을 기록하고 있는 애플리케이션이니 DAU는 말도 안되게 높을 것이다. 이런 상황에서 Chrome에 악성 URL을 filtering 하는 기능을 탑재하려는 시도를 한다고 가정해보자(이미 있는 기능이지만).

가장 쉽게 떠올릴 수 있는 solution은 다음과 같을 것이다. 유저가 주소창에 URL을 입력하면 해당 URL이 악성 URL인지 아닌지를 판단하는 HTTP request를 Chrome 서버에 보내서 확인하는 방법.
하지만 이 방법은 조금만 생각해봐도 굉장한 비효율을 발생시킬 것이라는 것을 client-server 아키텍쳐를 활용한 개발을 해본 개발자라면 쉽게 예측할 수 있다. 당장 생각나는 비효율을 몇 가지 적어보면 다음과 같다.

1. 기본적으로, 네트워크 통신 비용(HTTP request/response round trip time)은 비싸다. 여기에 Chrome의 DAU까지 고려하면 이 비용은 기하급수적으로 치솟을 것이다.
2. 이렇게나 많은 트래픽을 감당하기 위한 서버를 안정적으로(high availability를 확보) 유지하기 위한 비용도 만만치 않을 것이다.

이런 경우에 활용할 수 있는 것이 바로 bloom filter이다.
정확히 Chrome에서 bloom filter를 활용하는 로직은 알 수 없지만, 아마 다음과 같은 형태이지 않을까?

1. Chrome 애플리케이션을 설치할 때, 악성 URL과 관련한 blacklist data를 유저의 local machine에 다운로드 받아둔다.
2. 유저가 Chrome을 통해 새로운 URL에 접근할 때, 유저의 machine에 존재하는 blacklist data를 활용하여 만든 bloom filter로 악성 URL인지 여부를 판단한다.
3. 만약 bloom filter에 URL을 통과시킨 결과가 참이라면, 악성 URL인지 확실치 않다는 뜻이므로 이 경우에만 서버에 HTTP request를 보내서 악성 URL인지 여부를 판단한다. 결과가 거짓이라면, 악성 URL임이 확실하므로(bloom filter 자료구조에는 false negative인 경우가 없으므로) 해당 URL로의 접근을 차단해준다.

References

• https://d2.naver.com/helloworld/749531
• https://meetup.nhncloud.com/posts/192
• https://stackoverflow.com/questions/18447874/google-chrome-usage-of-bloom-filter