[Kakao Tech] Radix Tree + 블룸 필터

https://khs20010327.tistory.com/82

[논문]히트율에 따른 LevelDB 블룸 필터 최적화

학회에서 작성한 논문에 대한 발표를 진행하였다.

 

 

 

 

https://tech.kakao.com/2022/08/18/radix-tree-for-object-storage/

Object Storage 구현을 위한 분산 Radix Tree

그리고 학회에서 제공되는 다양한 강의를 추가로 들었는데,

카카오 tech workshop에서 object storage 구현에 블룸 필터를 사용하였단 사실에 흥미를 갖고 

이에 대해 정리해보고자 한다.

 

 

카카오의 metakage에 저장된 파일의 개수는 수천억개로, 

이러한 대규모 데이터베이스에 range query를 수행하기 위해 LSM-Tree를 사용하는 것은 overhead가 너무 크다

 

 

in-place update를 수행하는 B Tree의 경우 range scan에 상대적으로 유리하지만,

이 역시 root node에 월등히 많은 접근이 발생하는, 병목 현상이 발생하게 된다.

 

그렇기에 카카오는 radix tree와 bloom filter를 사용하는 것으로

range scan과 병목 2가지 issue를 해결하였다.

 

 

 

root node의 key는 '/'이고,

해당 노드 밑에는 '/1'과 '/foo'가 존재,

'/1'밑에는 '/12345', '/foo' 밑에는 '/foo/abc'가 존재하는 등,

radix tree는 파일 주소와 유사한 형태의 node key를 사용한다.

 

위와 같은 prefix한 자료 구조를 사용할 경우,

scan(/12345)를 수행할 때

/  ->  /1  ->  /12345  ->    /12345/89  +  /1234567

5번의 get으로 range scan을 수행할 수 있다.

 

또한 이러한 radix tree는 split에 유리한데,

/foo가 꽉 차 공간이 부족하다면

/foo와 /fooc 2개의 노드를 만들어 split하면 된다.

 

위 경우 2번에 /foo+ccc와 /fooc+cc 2개가 중복하여 존재하지만,

/fooc+cc로 접근 가능한 포인터가 없으므로 중복 오류는 발생하지 않는다.

그렇기에 radix tree의 split은 별도의 트랜잭션 없이 수행되며,

주기적으로 끊어진 노드를 찾아 삭제하는 로직만 돌려주면 된다.

 

 

 

그리고 결정적으로, 

이러한 radix tree의 경우 bloom filter를 사용하여 root node에 대한 병목 현상을 줄일 수 있는데,

찾으려는 노드에 대한 모든 상위 노드의 경우의 수를 블룸 필터에서 탐색하면 된다.

 

만약 /foo/abcd를 scan할 경우,

/foo/abcd, /foo/abc, /foo/ab, /foo/a  ...   / 까지 모든 상위 노드 경우의 수를 bloom filter에서 찾는다.

블룸 필터를 통해 /foo와 같은 상위 노드의 존재를 확인했을 경우,

root 노드 대신 해당 노드부터 탐색을 시작하면 되므로

root 노드에 대한 병목을 없앨 수 있다.

 

그리고 그 다음부턴 블룸 필터에 /foo/abc 존재가 설정되므로,

해당 노드부터 더 빠르 탐색이 가능하다.