블룸필터(Bloom Filter) 동작 방식, 특징

 

 

💡블룸 필터(Bloom Filter)란?

 

블룸필터란 특정 원소가 집합에 속하는지 검사하는데 사용할 수 있는 확률형 자료 구조이다. 확률적 검색 필터로 원하는 패턴이 무엇인지 정확하게 규정할 필요 없이 원하는 패턴을 설명하는 방식이라 할 수 있으며, 즉 통계적 특성을 보였다고 할 수 있다. 또한 많은 양의 데이터를 줄여서 공간 효율적으로 빠르게 검색을 할 수 있다. 블룸필터는 프라이버시를 보호하면서 검색 패턴을 구현하기 위한 효율적인 방법을 제공한다. 또한 블룸빌터는 비트코인 언리미티드 팀이 노드에 알려지지 않은 거래를 식별하는데 도움을 주고 있다. SPV 노드가 블룸필터를 사용해 이웃 노드들에게 특정 거래를 제공해 달라고 요청하는데 이때 노드는 검색중인 주소가 정확히 어떤 주소인지 밝힐 필요는 없다.

 

 

✓ 블룸 필터 동작 방식

 

블랙 리스트 기반의 IP 주소 검색 및 차단의 예를 가지고 동작 방식을 살펴보자. x, y, z라고 하는 IP를 블랙리스트에 저장하고, 방화벽에서 이러한 블랙 리스트의 IP를 차단하려고 등록한다고 가정해보자. 블랙 리스트에 어떻게 IP주소가 저장되는지, 그리고 패킷이 들어올 때, 어떻게 블랙 리스트와 IP 주소 비교를 어떻게 하는지를 살펴보자. 

 

먼저 N비트 크기의 비트 배열, 그리고 J개의 해싱 함수가 필요하다. 여기서는 N 이 18이고 J 는 3이다.

 

[블랙 리스트에 IP 주소 저장 순서]

1. x 라는 IP를 저장한다. x 라는 IP에 대해 3개의 해싱함수를 돌린다. 그리고 각 출력값에 해당하는 배열 인덱스 값을 1로 수정한다.

2. y 라는 IP를 저장한다. 1번과 같은 방식으로 진행한다.

3. z 라는 IP를 저장한다. 1, 2번과 같은 방식으로 진행한다.

 

 

[블랙 리스트에 IP 주소 비교 순서]

 

1. w라는 IP를 가진 패킷을 받는다. 

2. w라는 IP에 대해 3개의 해싱함수를 돌린다.

3. 4, 13 인덱스 값은 1이지만 15의 인덱스 값은 0이므로 w라는 IP는 블랙 리스트 IP가 아니다.

 

만약, 4/13/15 모두 1이라면 블랙리스트 IP 이다.

 

 

✓ 블룸 필터 특징

 

블룸필터는 길이 N의 이진 배열과 1부터 N까지의 출력값을 갖는 J개의 해시함수를 가지고 있다고 했는데 이 N과 J를 조절함으로써 정확도와 프라이버시 보호 수준을 조절할 수 있다. 오탐지율이 존재하기 때문에 결정적 결과 대신 부정확한 결과를 얻을 수 있다. False Negative(거짓 - 부정) 는 존재하지 않는다고 보장할 수 있다. 하지만 False Positive (거짓 - 긍정) 가 존재할 수 있다. 즉, 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면, 이 원소는 확실하게 없다고 할 수 있다. 해시 함수들을 기본적으로 여러 개를 가지는데 임의의 테이블 크기, 넣어야 하는 자료의 크기와 해시 함수의 수를 정하는 편이다. 또한 있는지 없는지만을 보는 그 특성 때문에 삽입만 가능하고 제거가 되지는 않는다. 위 블랙 리스트 IP를 예로 들면 리스트에 IP 가 추가될 때마다 비트 배열을 초기화하는 것이 아니라 그 위에 덮어쓰는 것이기 때문이다. 따라서, 위 블랙 리스트를 예로 들면, 정상 IP 를 블랙 리스트로 판단하여 차단할 확률이 존재한다.

 

✓ 블룸 필터 사용 예시

 

블룸필터는 처리능력 대비 적은 메모리 공간을 필요로 하는 장점 때문에 데이터베이스 의외에도 많은 곳에서 사용되고 있다.

 

1. IP 주소 검색 및 차단 필터링

2. 문자열 맞춤법 교정

3. 가상화폐

4. 라우터

5. 크롬 브라우저

6. 빅데이터 환경