위키원
블룸필터
블룸필터(Bloom Filter)는 특정 원소가 집합에 속하는지 검사하는데 사용할 수 있는 확률형 자료 구조이다.[1]
개요
블룸필터(Bloom Filter)는1970년 Burton Howard Bloom에 의해 고안되었다. 블룸 필터에 의해 어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능하지만, 반대로 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다는 특성이 있다. 집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능하다. 집합 내 원소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가한다.[2]
등장배경
블룸필터(Bloom Filter)는 1970년도에 Burton H. Bloom이 고안한 것으로 공간 효율적인 probabilistic data structure이며 구성요소가 집합의 구성원인지 점검하는데 사용된다.[3]
특징
집합의 크기가 굉장히 크거나 집합의 속해있는 원소의 크기가 커서 원소가 집합에 속해있는지 정확히 판단하는데 시간이 오래걸리는 경우 이 과정의 전처리 과정으로 Bloom Filter를 이용해서 아예 집합에 속할 일이 없는 원소를 미리 걸러낼 수 있다. Google Chrome은 위험한 사이트 검사에 Bloom Filter를 사용한다고 알려져 있다. Bloom Filter를 사용해서 빠르게 대충 검사한 다음, 의심이 가는 사이트인 경우 데이터베이스에 다시 정확하게 검사하는 것이다. 아마 위험 사이트 데이터베이스의 크기가 크고, 검사 요청이 굉장히 빈번하게 일어나기 때문에 Bloom Filter를 전처리 과정으로 사용해서 데이터베이스 요청 부하를 줄이는 것으로 보인다. 비트코인도 내부적으로 Bloom Filter를 사용하는 것으로 알려져 있다. 보통은 Disk IO를 줄이기 위한 최적화 방법으로 많이 사용한다.[1]
활용
- 스펠링체크, 사전, 웹 검색, IP Filtering, Router 등에 활용되고 Squid Web, Venti Storage System, SPIN model checker, Google Chrome Browser 등에도 활용되고 있다.
- Cassandra : SSTable 생성시(Index용으로 활용) - Read 성능 향상(Disk IO를 줄임).
- SMHasher & MurmurHash hash 함수 사용 : http://code.google.com/p/smhasher/
- HBase : HFile안에 로우와 컬럼이 존재하는 지 검사하기 위해 사용.
- Bigtable : 불필요한 디스크 접근을 피하기 위해.
- Oracle
- Parallel Join시 Slave간의 communication 데이터량을 줄이기 위해.(10gR2) - Join-Filter Pruning 사용시.(11gR1) - Result Cache 지원 (11gR1).
- Guava Bloom Filter : http://code.google.com/p/guava-libraries/issues/detail?id=12
- pyreBloom = Python + Redis + Bloom Filter
- bloomfilter-rb = Ruby + Redis + Bloom Filter[3]
- 블룸 필터는 비트코인 언리미티드 팀(Bitcoin Unlimited Team)이 노드에 알려지지 않은 거래를 식별하는 데 도움을 주고 있다.[4]
장.단점
장점
- 블룸필터는 많은 양의 데이터를 중여서 공간 효율적으로 빠르게 검색 할 수 있다.[5]
- 처리능력대비 적은 메모리 공간만을 필요하다.[6]
- Bloom Filter 는 (Join Filter Pruning) Hash Join 이나 Merge Join 을 하기에 앞서 조인 대상건수를 미리 줄임 으로써 Join 의 부하 를 감소 시킨다.
- Parallel Processing 의 경우 Slave 에서 조인을 하기 위해 Co or dinate 로 전송하는 통신양을 감소 시키고 , 조인의 부하까지 감소 시킨다.[7]
단점
- 동적으로 원소를 추가하기에 효율적이지 않다.
- 원소의 개수가 동적으로 계속 변경된다면 블룸필터를 구성하는 시점에 최적의 hash 함수 개수, 메모리 사이즈를 결정할 수가 없게 된다. 또한 원소가 예상보다 훨씬 많아지게 된다면 FPP 가 너무 커져서 문제가 생길 수 있다.
- 원소의 삭제가 불가능하고 원소의 개수가 많아질수록 false positive 의 확률이 높아진다.[8]
동영상
각주
- ↑ 1.0 1.1 , 〈알아두면 좋은 자료 구조, Bloom Filter〉, 《steemit》, 2017
- ↑ 〈블룸 필터〉, 《위키백과》
- ↑ 3.0 3.1 , 〈Bloom Filter 개요〉, 《개인 블로그》, 2013-05-13
- ↑ jo Yujin, 〈블룸 필터(Bloom Filter)는 무엇이며, 어떻게 사용되는가?〉, 《Dash》, 2019-02-19
- ↑ itbrain, 〈BLOOM FILTER(블룸 필터)〉, 《티스토리》, 2009-12-16
- ↑ 임지홍, 〈BloomFilter는 언제 쓰나요?〉, 《toast meetup》, 2019-07-25
- ↑ 한국데이터산업진흥원, 〈데이터 기술 자료〉, 《한국데이터산업진흥원》
- ↑ Taeguk, 〈Bloom Filter 자료구조〉, 《개인 블로그》, 2019-05-18
참고자료
- 〈알아두면 좋은 자료 구조, Bloom Filter〉, 《steemit》, 2017
- 미물,〈Bloom Filter 개요〉, 《개인 블로그》, 2013-05-13
- tbrain, 〈BLOOM FILTER(블룸 필터)〉, 《티스토리》, 2009-12-16
- jo Yujin, 〈블룸 필터(Bloom Filter)는 무엇이며, 어떻게 사용되는가?〉, 《Dash》, 2019-02-19
- 임지홍, 〈BloomFilter는 언제 쓰나요?〉, 《toast meetup》, 2019-07-25
- 한국데이터산업진흥원, 〈데이터 기술 자료〉, 《한국데이터산업진흥원》
- Taeguk, 〈Bloom Filter 자료구조〉, 《개인 블로그》, 2019-05-18
