LSM Tree in Flink

Apache Flink에서 주로 State Backend로 사용되는 RocksDB는 쓰기 속도가 빠르다고 알려져 있는데요, 그 동안 왜 빠른지에 대해서는 한 번도 찾아본 적이 없어 찾아보게 되었습니다.

정답부터 말하면 LSM Tree(Log-Structured Merge-Tree)를 선택했기 때문입니다.

 

이 글에서는 LSM Tree의 아키텍처와 동작 원리를 1996년 원본 논문을 기반으로 살펴보고, 이후 Flink에서 이걸 어떻게 활용하는지 간단히 정리합니다.

 

1. 왜 LSM Tree가 필요했을까?

B-Tree의 쓰기 비용 문제

LSM Tree를 이해하려면 먼저 B-Tree의 한계를 알아야 합니다.

1996년 Patrick O'Neil 등이 발표한 원본 논문 "The Log-Structured Merge-Tree (LSM-Tree)" 에서는 다음과 같은 문제를 제기합니다. (1p)

"Standard disk-based index structures such as the B-tree will effectively double the I/O cost of the transaction to maintain an index in real time, increasing the total system cost up to fifty percent."

B-Tree 인덱스를 실시간으로 유지하면 트랜잭션의 I/O 비용이 두 배가 되어, 전체 시스템 비용이 최대 50%까지 증가합니다. -> 흠 B-Tree가 이렇게나 비효율적인 자료구조였다는 게 이해가 되지 않습니다. 🤔

 

B-Tree에 레코드 하나를 삽입하는 과정을 보면 이해가 됩니다.

1. 해당 leaf 페이지(보통 4KB~16KB)를 디스크에서 읽고
2. 메모리에서 페이지를 수정한 뒤
3. 수정된 페이지 전체를 디스크에 다시 쓰고
4. WAL(Write-Ahead Log)에도 기록합니다

10바이트를 수정하는데 16KB 페이지 전체를 다시 쓰게 됩니다. 논문에서 언급되진 않지만, 이러한 현상을 Write Amplification(쓰기 증폭)이라고 종종 부릅니다.

핵심 원인은 B-Tree의 삽입이 랜덤 위치에 발생한다는 점입니다. 연속된 삽입이 트리의 이곳저곳에 흩어지면서, 매번 디스크 암이 물리적으로 이동해야 합니다. 여기서 랜덤 I/O는 디스크에서 가장 비싼 연산입니다.

 

순차 쓰기와 랜덤 쓰기

순차 쓰기 vs 랜덤 쓰기

택배 상하차로 비유해보자면 순차 쓰기는 들어오는 택배를 순서대로 쌓으면 되지만, 랜덤 쓰기는 들어오는 택배의 주소지를 알파벳 순으로 정렬해서 맞춰야 합니다. 쓰기 속도가 느릴 수밖에 없습니다.

 

논문이 제시한 해결 아이디어

논문의 핵심 아이디어는 한 문장으로 요약됩니다.

"The LSM-tree uses an algorithm that defers and batches index changes, cascading the changes from a memory-based component through one or more disk components in an efficient manner reminiscent of merge sort."

LSM 트리의 알고리즘은 인덱스 변경을 지연(defer)하고 일괄 처리(batch)해서, 메모리 컴포넌트에서 디스크 컴포넌트로 머지 소트와 유사한 방식으로 전파하는 것

 

간단히 말하면 "인덱스 변경을 즉시 반영하지 말고, 모아서 한꺼번에 순차적으로 쓰자"

-> 이것이 논문에서 제시한 LSM Tree의 근본 원리입니다.

---

2. 아키텍처

논문의 원래 설계: C0와 C1

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

원본 논문에서 LSM Tree는 두 개의 컴포넌트로 구성됩니다.

• C0 (메모리 컴포넌트): 메모리에 저장된 작은 트리. 모든 새 레코드는 먼저 여기에 삽입됩니다.
• C1 (디스크 컴포넌트): 디스크에 저장된 큰 트리. 완전히 채워진 페이지 노드들로 구성됩니다.

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

각 컴포넌트는 자기가 위치한 저장 매체의 특성에 맞게 최적화됩니다. C0는 메모리 접근 속도에, C1은 디스크의 순차 I/O에 맞춰 튜닝됩니다. (예를 들어, C0는 Red-Black Tree나 Skip List를 사용합니다)

C0가 임계값에 도달하면, Rolling Merge라는 프로세스가 C0의 데이터를 C1으로 병합합니다. 논문에서는 이 과정을 다음과 같이 묘사합니다.

"The rolling merge process has a conceptual cursor which slowly circulates in quantized steps through equal key values of the C0 tree and C1 tree components, drawing indexing data out from the C0 tree to the C1 tree on disk."

개념적인 커서가 C0와 C1의 동일한 키 범위를 순환하면서, C0에서 데이터를 꺼내 C1의 디스크로 병합하는 것입니다. 이때 multi-page block 단위로 I/O를 수행하기 때문에 seek time이 거의 발생하지 않습니다.

다중 컴포넌트 확장

논문은 여기서 멈추지 않고, K+1개의 컴포넌트로 일반화합니다. C0(메모리), C1, C2, ..., CK(디스크) 순으로 크기가 커지고, 인접한 컴포넌트 쌍마다 Rolling Merge가 동작합니다. (C1-C2, C5-C6 ...)

• C0 (Memory): 가장 작지만 가장 빠른 메모리
• C1, C2, ..., Ck (Disk): 뒤로 갈수록 용량이 커지는 디스크. Ck가 가장 큰 최종 저장소가 된다.

논문의 Theorem 3.1에 따르면, 모든 인접 컴포넌트의 크기 비율이 동일한 값 r일 때 전체 I/O가 최소화됩니다. 즉 S1/S0 = S2/S1 = ... = SK/SK-1 = r이 되어야 합니다.

현대적 구현: MemTable + SSTable + Level

현대의 LSM Tree 구현체(RocksDB, LevelDB 등)는 논문의 아이디어를 따라가지만, 용어와 구조가 좀 더 구체화되었습니다.

용어 정리로 앞에 WAL 부분은 생략했습니다. 밑에 나올 예정

논문 용어	현대 용어	설명
C0	MemTable	메모리의 정렬된 버퍼 (Skip List / Red-Black Tree)
C1, C2, ...	Level 0, 1, 2, ...	디스크의 SSTable 파일 계층
Rolling Merge	Compaction	하위 레벨 → 상위 레벨로 데이터 병합

MemTable

쓰기 요청이 들어오면 먼저 MemTable에 기록됩니다. MemTable은 메모리 내의 정렬된 자료구조로, 보통 Skip List로 구현됩니다. 삽입과 검색 모두 O(log N)입니다.

MemTable은 반드시 WAL(Write-Ahead Log)과 함께 동작합니다. (⭐️)

모든 쓰기는 MemTable에 넣기 전에 WAL에 먼저 기록되어, 프로세스 crash 시 복구할 수 있습니다.

 

SSTable (Sorted String Table)

MemTable이 임계값(보통 64MB)에 도달하면, 내용 전체를 디스크에 정렬된 상태로 flush합니다. (순차 쓰기)

이렇게 만들어진 파일이 SSTable입니다.

 

SSTable의 핵심 특성 세 가지:

• 불변(Immutable): 한 번 쓰면 절대 수정하지 않습니다
• 정렬(Sorted): 키 순서대로 정렬되어 있습니다
• 순차 쓰기(Sequential Write): 디스크에 처음부터 끝까지 순서대로 씁니다

SSTable 내부는 다음과 같이 구성됩니다.

https://medium.com/@dwivedi.ankit21/lsm-trees-the-go-to-data-structure-for-databases-search-engines-and-more-c3a48fa469d2

 

---

3. 동작 원리

쓰기

쓰기의 흐름을 따라가 보겠습니다.

1. 쓰기 연산 발생
2. WAL에 Append 수행 (순차 쓰기, 1회 디스크 I/O)
3. MemTable 삽입 (메모리 연산)
4. 완료

디스크 I/O는 WAL의 순차적 append 딱 1회입니다. B-Tree가 매번 랜덤 위치의 페이지를 읽고-수정하고-다시 쓰는 것과 비교하면, 이 차이가 LSM Tree를 쓰는 가장 큰 이유라고 볼 수 있습니다.

논문에서는 이 효율성을 Batch-Merge Parameter M이라는 개념으로 정량화합니다. C0와 C1의 크기 비율이 클수록 한 번의 디스크 페이지에 더 많은 항목을 배치 병합할 수 있어 효율이 높아진다는 것입니다.

읽기

쓰기를 최적화한 대가로, 읽기는 조금 복잡해집니다.

최신 데이터가 어디에 있는지 모르기 때문에 위에서부터 아래로 순서대로 찾아야 합니다. (C0, C1, ..., Ck)

1. MemTable 검색
2. Level 0 SSTable 검색
3. Level 1 SSTable 검색
4. Level 2, 3, ...

최악의 경우 모든 레벨을 탐색해야 합니다. LSM Tree의 최대 단점입니다.

 

다만, 실제로는 몇 가지 장치가 이 비용을 크게 줄여줍니다.

• Bloom Filter: 각 SSTable에 존재하며 "이 키가 여기 없다"는 것을 O(1)에 판별
• Block Cache: 자주 읽히는 블록은 메모리에 캐싱
• Index Block: SSTable 내 binary search 지원

Compaction

시간이 지나면 SSTable 파일이 계속 쌓입니다. 같은 키에 대한 여러 버전이 여러 파일에 흩어지게 됩니다. 이걸 정리하는 과정이 Compaction이고, 논문에서의 Rolling Merge에 해당합니다.

Compaction 전:
  Level 0:  [a:1, c:3, f:6]  [b:2, c:5, d:4]   ← 같은 키 c가 두 파일에
                    │
                    ▼  merge sort + 중복 제거
Compaction 후:
  Level 1:  [a:1, b:2, c:5, d:4, f:6]            ← 최신값(c:5)만 유지

 

삭제는 어떻게?

개인적으로 이 부분이 꽤 재미있었는데요, LSM Tree와 같은 불변 구조에서는 파일을 수정할 수 없으니 삭제도 "쓰기"로 처리합니다.

 

DELETE(id=1) 요청이 오면, MemTable에 (id=1, TOMBSTONE)이라는 특수한 마커를 삽입합니다. 이후 읽기 시 tombstone을 만나면 "이 키는 삭제되었다"고 판단합니다. 실제 물리적 삭제는 compaction 때 일어납니다. INSERT, UPDATE, DELETE 모두 결국 같은 쓰기 경로를 탄다는 점이 중요합니다.

---

Flink에서 사용하는 LSM Tree

Flink에서는 상태 저장소로 RocksDB(LSM Tree 기반)를 사용합니다.

Flink + RocksDB

Flink의 EmbeddedRocksDBStateBackend은 operator state를 RocksDB에 저장합니다. 스트림 처리에서 이 조합이 잘 맞는 이유는 세 가지입니다.

 

1. 스트림 처리는 쓰기 중심입니다.

// 이벤트마다 상태를 읽고 쓴다
public void processElement(Event event, Context ctx, Collector<Result> out) {
Long count = countState.value();   // 1회 읽기
    countState.update(count + 1);      // 1회 쓰기
}

초당 수십만 이벤트가 들어오면, 상태 쓰기 횟수도 초당 수십만 회입니다. 이는 Flink 상태 처리에서 매우 일반적인 상황입니다.

 

2. 메모리보다 큰 상태를 다룰 수 있습니다.

HashMapStateBackend은 모든 상태를 JVM 힙에 올립니다. 상태가 수십 GB를 넘으면 GC 지옥에 빠져 헤어나오지 못합니다. 😱 RocksDB는 MemTable과 Block Cache만 메모리에 두고 나머지는 디스크에 두기 때문에, TB 규모의 상태도 안정적으로 처리할 수 있습니다.

 

3. Incremental Checkpoint와 궁합이 좋습니다.

SSTable은 불변이기 때문에, 마지막 체크포인트 이후 새로 생긴 SSTable 파일만 업로드하면 됩니다. Flink에서 RocksDB를 쓰는 가장 큰 이유입니다.

 

LSM Tree를 사용하는 다른 시스템들

LSM Tree를 사용하는 다른 시스템들에는 아래가 있습니다. 이 밖에도 엄청 많습니다.

시스템	사용 맥락	LSM 구현체
Apache Cassandra	분산 NoSQL DB	자체 구현
Apache HBase	대용량 칼럼형 스토어	자체 구현
Kafka Streams	상태 저장소	RocksDB

 

---

마치며

LSM Tree에 대해 찾아보기 전까지는 단순히 옆에 메모리 하나 더 두는 개념으로 생각했었는데요, 그 안에서는 WAL로 데이터를 먼저 쓰고, MemTable에 데이터를 모으고, SSTable로 flush하고, Compaction으로 정리하는 일을 반복하고 있었습니다.

결국 핵심은 "랜덤 쓰기를 순차 쓰기로 변환한다"는 아이디어를 바탕으로 쓰기 속도를 극단적으로 높였고, 블룸 필터 등으로 읽기 속도를 개선했다고 볼 수 있습니다. 특히 최근 NoSQL, 시계열 데이터베이스가 성장하면서 이렇게 쓰기 효율을 높이는 방법이 많이 등장하고 있다고 합니다.

---

참고 자료

• O'Neil, Cheng, Gawlick, O'Neil. "The Log-Structured Merge-Tree (LSM-Tree)", Acta Informatica, 1996 (PDF)
• Log-structured merge-tree - Wikipedia
• RocksDB Wiki
• Apache Flink - State Backends