Published 2023. 4. 11. 22:04

LSM-Tree는 왜 사용할까

728x90

이번 포스팅에서는 Patric O'Neil의 "The Log-Structured Merge-Tree" 논문을 읽고 LSM Tree가 등장한 이유, 특징, 그리고 동작 원리에 대해 살펴보겠습니다.

Abstract

해당 논문이 발표된 시기에는 "activity flow management system application"의 수요가 증가하고 있었습니다. 이 시스템은 일련의 활동을 관리하고 최적화하기 위해 사용되며 대표적인 기능으로는 task tracking, workflow automation 가 있습니다. 이러한 시스템은 애플리케이션 레벨에서 히스토리성 데이터를 저장하는 동시에 데이터베이스에서 시스템 복구를 위해 해당 데이터가 저장되는 시점에 로그성 데이터를 추가로 저장합니다(Write ahead log). 그러나 논문이 출판된 시점에 가장 많이 사용되던 B-tree는 쓰기 요청이 많을 때 이를 효율적으로 처리하지 못했습니다(B-tree의 구조상 디스크의 random I/O가 무수히 많이 발생할 수 있기 때문입니다). 이러한 문제점을 해결하기 위해 대안으로 저자는 LSM-tree를 소개합니다.

The Two Component LSM-tree Algorithm

다음으로는 Two Component LSM-Tree의 원리에 대해 설명합니다. Two component는 메모리에 위치한 tree와 디스크에 위치한 tree로 구성됩니다. LSM 트리는 2개 이상의 tree로 구성될 수 있는데 1개의 tree를 제외하고 나머지 tree는 디스크에 위치합니다. Two component 구조에서 메모리에 위치한 자료구조를 C0 tree라고 표현하고 디스크에 위치한 자료구조를 C1 tree라고 표현합니다. LSM-tree에서 쓰기 요청은 다음과 같이 처리됩니다.

쓰기 작업이 요청됩니다.
시스템 다운 시 복구를 위해 별도의 log성 파일에 데이터를 기록합니다(sequential log)
메모리의 C0 tree에 해당 쓰기 요청을 반영합니다. C0 tree는 메모리에서만 존재하기 때문에 디스크를 위한 최적화가 필요하지 않습니다.
C0 tree가 임계치 이상의 크기에 도달하면 rolling merge를 실시합니다. Rolling merge를 통해 C0 tree의 연속되는 메모리 영역을 디스크 상의 C1 tree와 병합합니다. 병합을 통해 C0이 사용할 수 있는 메모리 공간을 확보합니다.

Rolling merge에 대해 상세하게 살펴보겠습니다. Rolling merge의 시작은 디스크상의 C1 tree에 위치한 leaf node 데이터를 multi-page block 단위로 메모리에 적재합니다. 메모리에 적재된 C1 tree의 leaf node 데이터를 disk page 크기 단위로 읽고 이를 C0 tree의 left node데이터와 병합하여 새로운 leaf node를 생성합니다. 생성된 leaf node는 C1의 parent node가 가리킴으로써 병합과정이 완료됩니다. 메모리에서 병합된 데이터를 디스크로 플러쉬할 때 기존 데이터의 위치에 덮어쓰지 않고 새로운 위치에 저장합니다.

How a Two Component LSM-tree Grows

다음으로는 쓰기작업으로 인해 LSM-Tree가 어떻게 커져가는지를 살펴보겠습니다.

쓰기 요청은 C0 tree에서 처리하고 쓰기 요청을 처리할수록 C0 tree가 점점 커져갑니다.
C0 tree의 크기가 임계치를 넘어가면 C0 tree의 연속된 left most leaf nodes가 배치 작업을 통해 C1 tree의 leaf node로 변환됩니다(C1 leaf node를 저장하는 메모리의 버퍼에 저장됩니다).
C1 tree의 leaf node가 저장된 버퍼가 꽉 차면 해당 버퍼의 블록은 디스크로 플러쉬됩니다(디스크에 C1 tree가 생성됩니다). 디스크로의 플러쉬는 multi-page block 단위로 디스크의 새로운 위치에 저장됩니다.
1 ~ 3번 과정을 반복하며 "C0 -> C1 -> 디스크"의 데이터 이동이 반복됩니다. 여기서 메모리 상의 C1 tree의 directory node(leaf node가 아닌 노드)는 성능을 위해 최대한 오래 메모리에 적재된 상태로 유지됩니다.

Multi-page block 단위로 디스크의 새로운 위치에 저장되는 LSM-Tree의 특성은 높은 쓰기 성능을 가능하게 합니다. B-tree의 insert와 다르게 random I/O를 유발하지 않기 때문에 disk seek에 걸리는 속도도 최소화할 수 있습니다.

B-tree의 쓰기 작업을 LSM-tree의 쓰기작업과 비교했을 때 더 많은 random I/O가 발생하는 이유는 다음과 같습니다. B-tree는 기본적으로 정렬된 상태로 데이터를 저장합니다. 새로운 데이터가 이미 정렬된 B-tree의 leaf node 중간에 삽입되어야 할 경우, 주변의 데이터를 이동시켜야 하므로 많은 random I/O가 발생할 수 있습니다. 또한, 쓰기 작업 중에는 parent node를 분할하거나 병합해야 할 경우가 있으며, 이러한 작업도 random I/O를 유발할 수 있습니다.

Finds in the LSM-tree Index

LSM-Tree에서는 조회가 C0, C1, ... Cn 순서로 수행됩니다. C0 tree에서 원하는 데이터를 찾을 수 없다면 C1 tree를 찾고, 이후에도 데이터를 찾을 수 없다면 다음 tree를 확인합니다. C0를 제외한 나머지 tree는 디스크에 위치하기 때문에 다수의 tree를 탐색해야 한다면 B-Tree와 비교하여 조회 성능이 좋지 않을 수 있습니다. 이 논문에서는 LSM-Tree에서 조회 성능을 개선하기 위한 몇 가지 최적화 방법이 제시됩니다(저는 스킵하겠습니다). 최적화 방법으로 직접 언급되지는 않았지만, bloom filter를 활용하면 LSM-Tree에 존재하지 않는 데이터를 조회하는 요청을 빠르게 처리할 수 있을 것 같습니다.

Deletes, Updates and Long-Latency Finds in the LSM-tree

LSM-Tree에서의 삭제 작업은 C0 tree에 특정 노드를 삭제하도록 표시된 node entry를 생성하는 것으로부터 시작됩니다. 실제 데이터의 삭제는 rolling merge 과정에서 수행됩니다. 수정작업은 삭제 후 쓰기 작업의 조합으로 볼 수 있습니다. 이전 데이터에 대한 삭제를 수행하고 새로운 데이터를 쓰는 것으로 데이터에 대한 수정 작업이 이루어집니다.

Reference

https://www.cs.umb.edu/~poneil/lsmtree.pdf