LSM tree 는 주기적인 compaction 을 통해 꾸준히 증가하는 disk 의 table 수를 줄이며, 중복된 키에 대한 조정 작업을 수행한다.
compaction 은 병합과 조정 알고리즘을 사용해 전체 record 를 순회하고 결과를 새로 생성한 테이블에 저장한다.
LSM tree 의 구조상 disk 에 쓰여져 있는 SSTable 의 record 는 정렬되어 있고, merge sort algorithm 의 특성상 iterator 의 head 만 memory 에 저장하기 때문에 memory 사용량 상한이 존재한다.
이러한 compaction 과정을 최적화 하기 위해 널리 알려진 방법중에 하나가 leveled compaction 이다.
Merge - Interation
Leveled Compaction 의 구조를 보기 전에 우선 기본적인 병합 과정을 LSM tree 가 어떻게 처리하는지 확인해보자.
LSM tree 구조에서 disk table (SSTable) 은 정렬되어 있기 때문에 다방향 병합 정렬 (multiway merge sort) 를 사용할 수 있다.
예를 들어, 아래 이미지와 같이 3개의 source table 이 있다고 가정해보자.
각 테이블은 정렬되어 있는 상태이기 때문에 Iterator 가 각 테이블의 head 값만 참조하고 있다면, 각 테이블의 최소값을 모두 확인할 수 있다는 것을 알 수 있다.
때문에 이 head 값을 참조하고 있을때 겹치는 key 값이 없다면, 다음 element 에 겹치는 값이 존재할 수는 없다는 것이 보장된다.
Leveled Compaction
LSM tree 구조에서 가장 많이 사용하는 compaction 기법으로 RocksDB 가 사용하는 방식이다.
leveled compaction 은 disk 를 여러 level 로 추상화 하여 나눈다.
각각의 level 에서 허용되는 테이블의 총 크기는 제한되며, 각 level 을 나타내는 index 번호가 있다.
(직관적이지는 않지만 가장 큰 index 가 최하위 level 을 가리킨다.)
memtable 을 최초 flush 하면 0번 level 의 SStable 이 생성된다. 이때 0번 level 의 table 의 key 의 범위는 겹칠 수 있다.
0번 level 의 테이블 수가 일정 수에 도달하면 데이터를 병합해 1번 level table 을 생성한다.
(compaction 시 0 번 level table 을 여러 key range 로 partition 하고 같은 범위의 table 끼리 병합하게 된다.)
결과적으로 1번 level 내에서 table 간의 key 범위는 겹치지 않게 조절된다.
또한 1 번 level 이상의 level 로 데이터가 compaction & merge 될 때에도 역시 key 범위는 겹치지 않게 조절된 후 이동하게 된다.
아래 그림은 level 사이에 compaction 과 데이터를 옮기는 작업을 나타낸다.
이렇게 table 마다 서로 다른 key 범위를 저장하면 읽기 중에 접근해야 하는 테이블 수가 줄어든다. 테이블의 meta-data 를 확인해 범위에 검색 키가 포함되지 않은 테이블은 필터링한다.
level 간 크기는 level 이 커질수록 증가하게 된다. 각 level 의 table 크기는 이전 level 의 table 의 크기보다 월등히 크기 때문이다.
가장 최신 데이터는 항상 index 가 낮은 level 에 있고, 상대적으로 오래된 데이터는 점차 높은 level 로 이동한다.