[논문] The Log-Structured Merge-Tree (LSM-Tree)

 

 

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

 

ABSTRACT

논문이 발표된 당시에는 고성능 트랜잭션 시스템에서 activity flow를 추적하기 위한 히스토리 데이터의 저장과 시스템 복구를 위한 로그 레코드의 저장이 동시에 요구되고 있었습니다. 예를 들어 TPC-A 벤치마크와 같은 애플리케이션에서는 계정별 활동 이력을 효율적으로 조회하기 위해 계정 ID에 기반한 인덱스가 필요했습니다. 하지만 전통적인 디스크 기반 인덱스 구조인 B-tree는 insert 성능이 낮아, 인덱스를 유지하는 데 디스크 I/O 비용이 두 배 가까이 증가하여 전체 시스템 비용을 50%까지 상승시킬 수 있었습니다.

이러한 문제를 해결하기 위해, 해당 논문은 Log-Structured Merge-Tree (LSM-tree)를 제안합니다. LSM-tree는 insert/ delete가 빈번한 워크로드에 적합한 디스크 기반 인덱스 구조로, 변경 사항을 메모리에서 먼저 처리한 뒤, 배치 방식으로 디스크에 병합하는 전략을 사용합니다. 이를 통해 디스크 암(arm) 이동을 최소화하고, 디스크 I/O 병목을 줄일 수 있습니다. 또한, 삽입과 삭제뿐 아니라 다양한 인덱싱 연산에 일반화 가능하며, 조회 빈도가 낮고 삽입 빈도가 높은 시나리오에서 특히 효과적입니다.

 

---

 

1. Introduction

 

the five minute rule

데이터베이스 시스템을 설계하다 보면 자주 마주하는 질문이 있다. "이 데이터를 디스크에 둘까, 아니면 메모리에 둘까?" 단순한 질문처럼 보이지만, 이 선택은 시스템의 성능과 비용 효율성에 큰 영향을 미친다. 이 질문에 답하기 위한 기준 중 하나가 바로 The Five Minute Rule이다.

The Five Minute Rule은 1987년 Jim Gray와 Gianfranco Putzolu가 발표한 논문에서 처음 제안된 개념이다. 이 규칙은 다음과 같은 사실에 기반한다:

• 디스크 I/O는 느리고 비싸다.
• 메모리는 빠르지만 상대적으로 용량 대비 비용이 높다.
• 따라서 어떤 데이터가 일정 시간 안에 자주 접근된다면, 디스크에서 계속 읽어오는 것보다는 메모리에 올려놓는 것이 더 경제적이다.

그리고 이 일정 시간의 기준이 바로 5분이었다. 즉, "5분 안에 한 번 이상 접근되는 데이터는 메모리에 두는 것이 이득이다" 라는 것이다.

(논문이 나올 시점에서 메모리 가격이 싸져서 5분에서 1분으로 변동되었다)

 

LSM-tree가 등장하게 된 배경은, 기존의 B-tree 인덱스가 너무 많은 디스크 I/O를 유발하기 때문이었다. 특히 TPC-A 같은 벤치마크 워크로드에서는 초당 수천 건의 insert가 발생하는데, B-tree로 인덱스를 유지하려면 매번 디스크 페이지를 읽고 쓰는 작업이 필요하다.

이때 The Five Minute Rule을 적용해보면, 자주 업데이트되는 데이터라도 insert 위치가 랜덤하다면, 해당 페이지가 다시 버퍼에 남아 있을 확률은 매우 낮다. 

 

 

 

Two Component LSM-Tree Algorithm

앞서 살펴본 The Five Minute Rule을 통해, 자주 접근되지 않는 데이터를 무조건 메모리에 상주시켜두는 것은 비용 낭비일 수 있다는 점을 확인했다. 이러한 데이터를 효율적으로 관리하기 위해  LSM-tree을 제시한다.

LSM-tree(Log-Structured Merge-Tree)는 기본적으로 삽입 작업이 매우 빈번한 환경에서 디스크 I/O를 줄이기 위한 구조다. 이 구조는 여러 개의 계층적 트리로 구성되며, 각 트리는 메모리 또는 디스크 상에 존재한다.

이번에는 그 중에서도 가장 기본적인 형태인 Two Component LSM-tree의 구조와 원리를 살펴보자.

---

Two Component 구조란?

Two Component LSM-tree는 메모리에 위치한 트리(C₀ tree)와 디스크에 위치한 트리(C₁ tree)로 구성된다.

• C₀ tree (Memory-resident): 메모리에 상주하며 빠른 삽입을 처리한다. AVL-tree나 2-3 트리와 같이 CPU 효율이 높은 자료구조를 사용할 수 있다.
• C₁ tree (Disk-resident): 디스크에 저장되는 트리로, B-tree처럼 디렉토리 구조를 가지지만 순차적 접근에 최적화되어 있다.

 

쓰기 요청 처리 방식

LSM-tree에서의 쓰기 작업은 다음과 같은 순서로 처리된다:

1. 쓰기 요청이 들어온다.
2. 복구(log recovery)를 위해 요청 내용을 별도의 순차 로그(sequential log)에 먼저 기록한다.
3. C₀ 트리에 요청을 반영한다. C₀는 메모리 전용 트리이므로 디스크 I/O가 발생하지 않는다.
4. C₀ 트리가 설정된 임계 크기(threshold)를 넘어서게 되면, 디스크에 위치한 C₁ 트리로 데이터를 옮기기 위한 rolling merge 작업이 시작된다.

---

Rolling Merge란?

Rolling merge는 C₀의 데이터를 디스크에 있는 C₁으로 점진적으로 병합하는 과정이다. 이 병합은 다음과 같이 진행된다:

1. C₁ 트리의 leaf 노드들을 multi-page block 단위로 메모리에 읽어들인다.
   • 일반적으로 256KB 정도의 블록 크기를 사용하여 디스크 arm 움직임을 줄인다.
2. C₁의 leaf node와 C₀의 정렬된 데이터 일부를 병합하여 새로운 leaf node를 생성한다.
   • 이 병합은 보통 disk page 단위(예: 4KB)로 수행되며, 각 노드는 100% 채운다.
3. 새로운 leaf node들은 ‘filling block’에 기록되며, 일정 크기에 도달하면 디스크의 새로운 위치에 저장된다.
   • 기존의 leaf node는 덮어쓰지 않고, 새로운 위치에 쓰인다. 이로써 복구 시 데이터를 잃지 않도록 한다.
4. 병합된 leaf node의 참조 정보는 C₁의 parent directory node에 반영된다.

이러한 과정을 반복하면서 C₀ 트리의 크기를 줄이고, 디스크에 있는 C₁ 트리는 점차 새로운 데이터를 포함하게 된다.

---

왜 overwrite하지 않는가?

Rolling merge의 또 다른 중요한 특징은 디스크 상의 데이터를 기존 위치에 덮어쓰지 않는다는 점이다. 새로 병합된 데이터는 항상 새로운 위치에 저장되며, 기존 데이터는 무효화(invalidate) 처리만 된다. 이는 시스템이 예기치 않게 중단되었을 때에도 복구가 가능하도록 설계된 방식이다. 또한, 이러한 설계를 통해 동시성(concurrency) 제어와 체크포인트(checkpoint) 작성도 용이해진다.

---

---

 

 

 

 

 

3. How a Two Component LSM-tree Grows 

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

 

1단계: 쓰기 요청이 C₀ Tree에 저장된다

쓰기 요청은 가장 먼저 메모리에 있는 C₀ tree에 반영된다. 이 구조는 디스크 I/O를 발생시키지 않으므로 매우 빠른 성능을 낸다. C₀ tree는 B-tree 구조일 필요도 없다. AVL-tree나 (2-3)-tree와 같은 CPU 효율 중심의 메모리 트리를 자유롭게 사용할 수 있다.

시간이 지나고 쓰기 요청이 반복되면, C₀ tree는 점점 커지게 된다. 하지만 메모리는 한정되어 있기 때문에, 일정 임계치를 초과하게 되면 데이터를 디스크로 넘겨야 한다.

 

2단계: C₀의 leftmost 데이터를 C₁으로 병합

C₀ tree의 크기가 임계치를 넘어서면, C₀의 leftmost leaf nodes 일부가 삭제되고, 해당 데이터는 배치로 병합되어 C₁ tree의 leaf node로 변환된다. 이 작업은 C₁ tree의 leaf node 블록을 위한 메모리 내 multi-page buffer에서 수행된다.

논문에서는 이 과정을 rolling merge라고 부르며, merge는 다음과 같은 과정을 따른다:

• 디스크에 존재하는 C₁ tree의 leaf-level 블록들을 메모리로 로딩
• C₀ tree의 leaf-level 데이터와 병합
• 새롭게 병합된 leaf node들을 새로운 multi-page 블록에 저장

 

3단계: C₁ Tree의 메모리 버퍼가 가득 차면 디스크로 Flush

C₁ tree의 leaf node들이 저장되는 filling block이 가득 차면, 해당 블록은 디스크로 플러쉬된다. 이때 주의할 점은 기존 데이터를 덮어쓰지 않고, 디스크의 새로운 위치에 블록 단위로 저장된다는 점이다.

이러한 방식은 디스크 seek나 rotational delay를 거의 유발하지 않으며, random I/O가 주를 이루는 B-tree와는 전혀 다른 방식이다.

• Emptying block: 이전 C₁ 데이터가 존재하는 블록
• Filling block: 새롭게 병합된 데이터가 저장되는 블록
• 병합이 끝나면 filling block이 디스크에 쓰이고, C₁ 디렉토리는 새 블록을 가리키도록 갱신됨

 

왜 이 방식이 빠른가?

LSM-tree의 핵심 설계는 디스크의 random I/O를 피하는 데 있다. B-tree는 삽입 시마다 leaf 노드를 읽고 수정한 후 디스크에 다시 써야 하므로, 디스크 arm이 무수히 움직이며 성능이 저하된다. 반면 LSM-tree는 일정량의 삽입을 모은 뒤, 한 번에 병합하여 multi-page block 단위로 순차 쓰기를 수행한다.

• Random I/O 없이 순차적으로만 디스크를 쓰기 때문에 seek time이 거의 발생하지 않는다.
• C₁의 leaf-level은 항상 100% 채워서 저장하므로 디스크 공간 활용률도 높다.

이러한 이유로, 쓰기 성능은 B-tree에 비해 수십 배 이상 빠를 수 있다.

 

---

 

LSM-tree vs. B-tree: I/O 비용 비교

데이터베이스에서 인덱스를 유지하려면 디스크에 지속적으로 데이터를 쓰고 읽는 작업이 필요하다. 그렇다면 기존의 대표적인 인덱스 구조인 B-tree와, LSM-tree는 디스크 입출력(I/O) 측면에서 어떤 차이를 보일까?

 

 

B-tree의 I/O 비용

B-tree에서 새로운 인덱스 항목을 삽입하려면 보통 다음의 작업이 필요하다:

1. 디렉토리 노드를 따라 leaf node까지 탐색한다.
2. leaf node를 수정하고 디스크에 다시 쓴다.

이때 디스크에 존재하는 node들을 읽고 쓰는 작업은 대부분 random I/O를 발생시킨다. 특히 삽입할 위치가 무작위로 분포돼 있는 경우, 같은 leaf node가 다시 사용될 확률이 낮아 버퍼 히트율도 떨어진다.

평균적으로 한 번의 삽입당 3번의 random I/O가 발생할 수 있다

 

LSM-tree의 I/O 비용

LSM-tree는 쓰기 요청이 들어오면 메모리(C₀)에 우선 저장하고, 이후 일정량이 쌓이면 디스크(C₁)로 batch로 병합(merge)한다. 이때 디스크 접근은 multi-page block 단위로 순차 접근하므로, random I/O에 비해 훨씬 효율적이다.

한 번의 삽입이 병합 시점에서 여러 엔트리와 함께 처리되므로 삽입당 I/O 비용이 매우 낮다.

 

LSM-tree의 I/O 비용은 B-tree 대비 약 1/75 수준으로, 두 자릿수 이상 차이가 날 수 있다

 

 

 

예시: 1000 TPS 시스템에서의 비용 차이

논문에서는 TPC-A 벤치마크를 기반으로 다음과 같은 시나리오를 제시한다:

• 하루 8시간, 20일 동안 초당 1000건의 트랜잭션 발생
• 각 트랜잭션은 16바이트짜리 인덱스 항목을 1개 생성
• 총 인덱스 엔트리 수: 약 5.76억 개 → 9.2GB
• B-tree는 leaf node 당 1개씩 I/O가 발생하므로 2000 IOPS 요구
• 디스크 한 대가 40 IOPS를 처리한다고 가정하면 50개의 디스크 arm 필요

반면 LSM-tree를 사용하면 병합 단위가 커지므로, 단 1~2개의 디스크 arm으로도 충분하다는 결과가 나온다.

 

---

 

 

LSM-tree에서의 동시성 처리 (Concurrency in the LSM-tree)

LSM-tree는 설계상 쓰기 성능을 극대화하기 위한 구조이지만, 다중 사용자 환경에서는 동시성(concurrency) 문제를 반드시 고려해야 한다.  LSM-tree에서 동시성 이슈가 발생하는 주요 지점은 다음과 같다:

1. 쓰기 요청이 들어와 C₀ tree를 갱신할 때
2. rolling merge 중에 C₁ tree의 leaf node를 읽거나 쓸 때
3. 조회(find) 작업이 C₀, C₁ tree를 순회할 때

이러한 상황에서 중요한 것은 데이터 정합성과 일관성(consistency)을 유지하면서도 병렬 처리 성능을 확보하는 것이다.

 

쓰기 작업 중 동시성 처리

쓰기 작업은 메모리에 있는 C₀ tree에만 반영되기 때문에, 병목은 크지 않다. 다만 여러 쓰기 요청이 동시에 들어오면 다음과 같은 방법으로 처리할 수 있다:

• C₀ tree 자체에 대해 lock-based 접근 제어를 두거나,
• 병렬 쓰기를 허용하는 thread-safe 자료구조(예: concurrent AVL-tree)를 사용할 수 있다.

논문에서는 C₀ tree가 비교적 작고 메모리에 있으므로, 복잡한 concurrency control 없이도 효율적인 처리가 가능하다고 설명한다.

 

 

Merge 중 병행 처리: Rolling Merge의 동시성

rolling merge는 C₀의 데이터를 C₁으로 병합하는 작업이다. 이 과정에서 주의할 점은 다음과 같다:

1. merge 대상인 C₁ tree의 leaf node는 메모리로 불러와진 상태이며,
2. 병합 결과는 디스크의 새로운 위치에 쓰여야 하며,
3. 기존의 leaf node는 무효화(invalidate)되지만, 바로 삭제되진 않는다.

이 구조에서 동시성 처리는 이렇게 이뤄진다:

• merge가 진행 중인 C₁의 leaf node는 잠시 동안 lock이 걸린다.
• 그 외의 node들은 merge와 무관하므로 읽기/쓰기 작업이 병렬로 진행 가능하다.
• 병합 결과는 항상 디스크의 새로운 위치에 저장되므로, overwrite가 발생하지 않고 읽기/쓰기 충돌을 회피할 수 있다.
• merge는 점진적으로 진행되기 때문에, 전체 시스템의 latency에 미치는 영향은 작다.

 

조회 작업 중 동시성 처리

조회 작업(예: find, range scan 등)은 C0 tree, C1 tree 두 컴포넌트를 순차적으로 조회한다:

조회 작업에서 중요한 것은 데이터가 아직 merge되지 않았더라도 최신 결과를 반환해야 한다는 점이다. 이를 위해 LSM-tree는 다음과 같은 정책을 사용한다:

• 항상 C₀ → C₁ → C₂ 순으로 조회를 수행하며,
• 더 앞선 컴포넌트에서 해당 key를 찾으면, 뒤에 있는 컴포넌트는 건너뛴다.
• C₀에는 삭제(tombstone) 정보도 포함되어 있으므로, 오래된 값이 C₁에 존재하더라도 걸러낼 수 있다.

이 방식은 복잡한 동기화 없이도 조회 시 정확한 최신 결과를 보장할 수 있도록 도와준다.

 

 

 

 

---

 

 

LSM-tree는 단순히 새로운 트리 구조를 제안한 것이 아니다. 그것은 디스크의 물리적 한계와 현실적인 비용 모델을 반영하여, 대규모 트랜잭션 시스템에서도 실용적으로 적용 가능한 대안을 제시한 인덱싱 전략 제시한다.