LSM Tree (Log-Structured Merge Tree) - 1

LSM 트리는 쓰기 성능 최적화를 위한 트리 기반 인덱싱 구조로, 로그 구조 병합 트리라는 이름을 갖습니다. 이 글에서는 LSM 트리의 개념, 구조, 구성 요소, 그리고 쓰기 최적화를 위한 다양한 방식들을 정리합니다.

LSM 트리란?

Log-Structured Merge Tree는 데이터를 메모리에 먼저 기록하고, 이후 디스크에 순차적으로 병합(merge)하여 저장하는 구조입니다. 랜덤 쓰기 대신 순차 쓰기를 활용함으로써 디스크 I/O를 줄이고, 쓰기 성능을 극대화합니다.

불변(Immutable) 자료구조란?

LSM 트리는 불변 자료구조입니다. 즉, 데이터를 수정할 때 기존 데이터를 덮어쓰지 않고 새로운 위치에 레코드를 추가합니다.

불변 자료구조의 장점

• 쓰기 효율 향상: 덮어쓰기가 아니라 새로운 위치에 기록 → 랜덤 I/O 최소화
• 단편화 방지: 고정된 크기의 레코드를 연속된 공간에 저장 가능
• 복구 용이성: 이전 상태 복원이 간단 (예: 툼스톤 기반 삭제)

가변 자료구조 예: B-트리

• 기존 위치에서 데이터를 수정하거나 삭제
• 무작위 접근(Random Access)이 많아 쓰기 I/O 부담 증가
• 블록 단편화 가능성 존재

LSM 트리의 구성 요소

1. 멤테이블 (Memtable)

위치	읽기	쓰기
메모리	O	O

• 메모리 상에 존재하는 정렬된 데이터 구조 (주로 SkipList, Red-Black Tree 등)
• 쓰기 작업은 이곳에 먼저 저장됨
• 임계 크기 도달 시 디스크로 플러시

2. SSTable (Sorted String Table)

위치	읽기	쓰기
디스크	O	X

• 디스크에 저장되는 읽기 전용 불변 테이블
• 멤테이블이 디스크로 내려오면 SSTable로 저장
• 정렬된 형태 유지, 검색 및 병합 최적화

3. Write-Ahead Log (WAL)

• 멤테이블보다 먼저 기록되는 로그
• 시스템 장애 복구 시 멤테이블 복원 가능

이중 컴포넌트 LSM 트리

구조

• C0: 메모리 기반 멤테이블
• C1: 단일 디스크 기반 컴포넌트 (읽기 전용, 100% 채워진 노드)

특징

• 디스크는 읽기 전용이며 쓰기 작업은 전부 멤테이블에
• 플러시 시 서브트리 단위 병합
• 병합 중에도 읽기/쓰기 가능
• 병합 종료 후 원자적으로 적용 & 불필요한 서브트리 제거

플러시 빈도에 따라 쓰기 증폭이 심해질 수 있어 실제 사용 사례는 없다고 합니다.

다중 컴포넌트 LSM 트리

계층 구조

• C0 (Memtable) → C1, C2 ... Cn (SSTable)
• 디스크 기반 테이블이 여러 개 존재
• 계층 간 병합 및 압축(compaction) 수행

컴포넌트 상태별 읽기/쓰기 여부

컴포넌트	읽기	쓰기
최신 멤테이블	O	O
플러시 대상 멤테이블	O	X
디스크 SSTable	O	X
압축 대상 SSTable	O	X
압축 완료 SSTable	O	X

삽입/수정/삭제 처리 방식

• 모든 연산은 멤테이블에 기록
• 중복 키는 최신 값만 읽기 시 반영

삭제 처리: 툼스톤(Tombstone)

• 삭제 요청 시 실제 삭제가 아닌 "삭제 표시" 레코드를 기록
• 이후 병합 과정에서 다른 테이블에 존재하지 않는지 확인 후 완전히 제거

압축(Compaction) 과정

왜 압축하는가?

• 테이블 수가 많아질수록 읽기 성능 저하
• 이를 방지하기 위해 계층 간 병합 및 중복 제거

방법

• 모든 SSTable은 정렬된 상태 유지
• 여러 SSTable의 최상위 항목을 우선순위 큐(PQ)로 병합
• 중복 키는 타임스탬프 기반 최신 값만 유지

PQ는 중복 키를 허용해야 하며, 최신 값을 선택해야 합니다.

정리

항목	LSM 트리
목적	쓰기 최적화, 순차적 디스크 접근
구조	불변 구조, 멤테이블 + SSTable 계층
쓰기	메모리 → WAL 기록 → 멤테이블 → 플러시
읽기	멤테이블 + SSTable 병렬 검색 (Bloom Filter 등 보조)
삭제	툼스톤으로 표시 후 병합 시 제거
병합	정렬 병합 + 중복 제거 + 최신 값 유지

본 정리는 Database Internals 도서를 기반으로 작성되었습니다.