LSM Tree(Log Structured Merge)

LSM트리는 로그파일 기반으로 작성되는 방식의 파일 구조다. key-value형태로 관리되며, 로그파일 기반이란 LSM 트리에 쓰기작업시 항상 Append-only 방식으로 쓰여지고 로그파일에 먼저 쓰기작업을 진행하는 걸 뜻한다.

LSM 트리는 항상 끝에 데이터를 새로 쓰는 방식이어서(Append-only) 쓰기작업의 퍼포먼스가 좋다.

쓰기작업

LSM 트리는 쓰기작업을 바로 disk에 하지 않고 순차적으로 로그파일과 정렬된 메모리테이블(memTable)에 먼저 쓴다. 그리고 메모리테이블이 다 차면 disk로 flush 하게 되는데 이 때, disk에 저장되는 방식은 정렬된 순서로 저장되어 Sorted String table(SSTable)이라고 한다.

수정작업

LSM 트리는 Append-only 방식이어서 기존 데이터를 수정하지 않고 그냥 새로운 데이터를 추가하는 방식으로 적용되니 쓰기작업을 진행하는 거와 똑같다.

읽기작업

LSM 트리는 데이터를 SSTable에 저장할 때 일정 크기로 나눠서 저장한다.
따라서 항상 가장 마지막 SSTable이 최신의 데이터를 들고 있어 수정작업으로 중복된 key를 기준으로 읽기작업을 해도 마지막 데이터만 읽을 수 있다.

읽기 작업의 순서는 memtable -> SSTable 하위 -> SStable 상위 순서로 접근한다. SStable이 많을 때 제일 처음 SSTable의 데이터를 읽어야한다면 시간이 오래 걸릴 수 있다.

때문에 인덱스를 사용하여 필요한 SStable에 빠르게 접근하도록 하여 읽기 속도를 올린다.

Compaction(압축)작업

데이터가 많아져서 SSTable이 늘어나면 DISK에 여러번 접근해야 데이터를 가져 올 수 있으니 여러개의 SSTable을 합치는 작업을 Compaction작업이라 한다.

Compaction작업에서는 중복된 key값을 제거하고 삭제된 데이터를 정리하는 작업이 포함된다.

삭제 작업

LSM 트리의 삭제 작업은 marking만 해놓고 실제론 Compaction작업에서 데이터가 지워진다.

한 줄평 : LSM 트리는 읽기 작업에 비해 쓰기 작업량이 많을 때 유리하다고 한다.