[개발생각] Bloomfilter에서 삭제가 가능하다면?

BloomFilter는 확률적으로 원소가 존재하는지를 확인하는 확률기반 알고리즘이다. 작은 메모리로 원소 존재여부를 확인할수있다.

 

 

BloomFilter는 많은곳에서 활용이 가능하다.

공지/글등의 읽음표시여부에 사용할수도 있고 (내가 적용했지 후후..),

디비의 조회를 줄이기위한 필터링으로도 사용가능하다 (HBASE가 정말 BloomFilter를 적극적으로 사용했지..)

 

하지만 이런 좋은 기능이지만, 단점이 하나있다.

바로!!! 한번 저장한 원소(값)은 삭제를 할수없다는 것이다.

이게 당연한것이,

BloomFilter는 해시값을 비트버킷에 저장을 하는 방식이기에,  원본 데이터를 저장하지 않는다.

따라서 원본 데이터를 알수없기에 삭제도 할수없는 것이다.

따라서, 삭제가 필요하다면,

BloomFilter 버킷을 새롭게 만들고 다시 마이그레이션하는 방법을 써야한다.

 

이런 단점을 해결한 알고리즘이 하나 있다.

Cuckoo Filter

일명 뻐꾸기 필터이다.

CuckooFilter는 BloomFilter와 동일하게 확률적기반으로 원소 존재여부를 확인해준다.

더불어, 원소(값)의 Fingerprint 즉 해시일부값을 저장하고 있기때문에 원본 데이터를 알수가 있고

(물론, 해시 일부이기에 중복 조회될수있다), 해당 원본 데이터를 삭제할수가 있다.

 

엄청난 장점!!

더불어 성능이나 메모리도 크게 BloomFilter와 차이가 없다.

 

간단하게 동작하는 방식은 아래와 같다.

원소(값)이 A라고 하면, 

fp = hash(A) substring 0, x //해시값의 일부만 핑커프린트를 사용 (메모리 효율)



여러개의 bucket들이 존재한다. (List<Bucket>)

그중에 fp가 들어갈수있는 bucket는 2개이다.

bucketA

bucketB

둘중에 하나의 bucket에 fp를 저장함.

 

fp를 bucketA 또는 bucketB에서 찾는다! 

삭제는 fp가 있는 bucket에서 해당 fp를 삭제처리해준다.

 

여기서 정말 중요한부분이 있다.

왜 fp를 저장할 bucket를 굳이 2개의 bucket후보를 선정하고 그중에 하나에 넣는가?

해시 충돌을 최대한 없애기 위함이다.

원소값의 해시의 일부만을 저장하기에 하나의 버킷에 많은 원소의 핑거프린트값을 저장하게 되면,

해시 충돌이 급속도로 늘어나게 된다.

따라서 버킷을 2개로 분산하여 해시 충돌을 없애는 방법을 사용한것이다. (미쳤다...만든사람)

 

그리고 버킷후보 2개중에 한쪽에 데이터가 저장되기에,

bucketA를 통해 bucketB의 원소를 찾을수있어야한다.

또한 bucketB를 통해 bucketA의 원소를 찾을수있어야한다.

해당 후보 bucket들의 관계는 XOR hash(원소) 로 만들어 한쪽의 버킷으로 다른쪽 버킷을 찾을수 있게 한다.

즉, 원소 존재여부를 확인할때, 2개의 버킷을 조회할때 효율이 늘어나게 된다.

 

그리고 해당 버킷의 사이즈가 모두 차면, 기존에 있던 원소를 다른 여유있는 버킷으로 이동을 시키게한다 (캐시만료 정책 LRU 느낌??!)

 

여기서 Cuckoo라고 이름을 지은 이유가 나온다.

(뻐꾸기가 남의 둥지에 알을 낳을때, 기존 알을 밖으로 밀어내서 없애버린다는 의미,

버킷이 가득찼을때, 기존 원소값을 다른 버킷으로 이동 시킨다는 의미)

 

프로젝트에서 EV자동차연동을 한 유저가 홈에 접근했는지 여부를 현재는 BloomFilter를 사용하고 있는데,

현재는 일정시간간격으로 BloomFilter를 매번 새로 만들게 구현을 했다 (삭제가 안되니 ㅠ)

 

이걸 CuckooFilter를 사용하면, 매번 필터를 만들 필요없이 사용이 가능할것 같다.

좀더 고민을 해보고, 적용을 해볼지 결정을 해봐야겠다!

(UserId + 필터가 존재해야하는 시간간격값 => Key로 하면, 딱인듯!!!)