본문 바로가기
Programming/JAVA

BloomFilter를 이용해서 데이터 찾기.

by 유주원 2018. 10. 30.

map-reduce, 혹은 spark를 사용함에 있어서 가장 비용을 많이 차지하는 부분은 map-reduce의 reduce, spark에서는 join 부분일 것이다.

join을 할때는 되도록 데이터 셋을 최대한 줄인 후에 join을 하는 게 가장 바람직하다.


만약에 실제 내가 사용할 데이터는 2억건인데 input으로 들어온 데이터가 400억 건이면 400억 건에 대해 일단 2억건으로 줄인 후 join을 진행하는게 맞다.


그럼 400억 건을 2억건으로 어떻게 줄일까??


물론 2억건을 메모리로 다 올린 후에 for문으로 찾아도 된다.


그러나 지금 설명하려고 하는 내용은 bloomFilter를 활용해서 데이터를 줄이는 방법을 말하려고 한다.


일단 BloomFilter에 대해 간략히 설명하자면, 해시 테이블을 활용해서 현재 url이 찾고자 하는 데이터 인지를 찾아내는 방법이다.

(Bloom이란 사람이 만들어서 이름이 BloomFilter 임)


예를 한 번 들어보자.


해시 테이블이 20개 있다고 가정하고, 우리는 두 개의 단어 ['apple', 'banana']를 해시 함수를 적용해서 테이블에 적용할 것이다. 

해시 함수는 1개 이상 적용할 수가 있다. 

즉, 해시 테이블에 masking을 1개 이상 할 수 있다는 의미가 된다.


여기서는 해시 함수를 2개를 적용해 보도록 하자. 

apple을 해시 함수 1에 통과 시켰을 때, 17을 리턴한다면 해시 테이블 17번째에 1을 masking 해주자.

apple을 해시 함수 2에 통과 시켰을 때, 3을 리턴한다면 해시 테이블 3번째에 1을 masking 해주자.




이런 식으로 banana에도 같이 masking을 해 준다. banana는 3, 15에 각각 1이 masking 되었다고 가정하자.




이제 단어를 찾아보자.

apple을 입력하니 해시 함수 1에서 3,17을 각각 리턴해줬고, 해당 결과가 해시 테이블에 존재한다면(masking이 1), apple이란 단어는 목표 값에 존재한다고 생각할 수가 있다.


만약에 orange를 입력하고 결과 값 3, 13을 리턴받았다면, 3은 1이지만 13은 0이기 때문에 존재 안 함으로 판단할 수가 있다.


이런 식으로 처리를 함으로써 20개 이상의 많은 단어가 유입 된다고 하더라고 해시 테이블 20개만 써서 20개 이상의 단어에 대한 존재 유무를 판단 할 수가 있다.


물론 20개 테이블 전부 masking이 1이 된다거나 했을 경우에는 정상적인 동작을 한다고 판단 되지는 않을 것이다. 즉, 모든 해시 테이블이 masking 1이 되지 않도록, 또한 해시 충돌을 최소한으로 줄일 수 있도록 해시 테이블 크기와 해시 함수 개수 등의 적절한 조합이 필요하다.


bloomFilter 같은 경우에는 false positive 요소는 있을 수 있으나, (해당 단어가 없는데 있다고 판단한 경우) false negative는 확실히 걸러낸다. (해당 단어가 있는데 없다고 판단한 경우)


해시 값 충돌이나 masking이 일치하는 경우 없는 단어도 있다고 판단할 수 있겠으나, 있는 단어인 경우는 확실히 매칭시키기 때문에 bloom Filter를 통해 한번 거르게 되면 많은 양의 데이터를 줄일 수가 있다.




아래는 BloomFilter를 활용한 Java code를 나타낸다.