LSM 트리와 쓰기 증폭

LSM 트리는 순차 쓰기로 처리량을 높이지만, 컴팩션에서 데이터를 반복 기록하면 쓰기 증폭이 발생합니다.

순차 쓰기라는 선택

저장 장치는 같은 양을 써도 순차 쓰기를 랜덤 쓰기보다 효율적으로 처리합니다. 하드 디스크는 탐색 비용을 줄이고, SSD는 내부 쓰기와 가비지 컬렉션 부담을 줄일 수 있습니다. 이 물리적 특성이 스토리지 엔진의 쓰기 전략을 가릅니다.

B+트리(B+Tree)는 제자리 갱신(update-in-place)을 합니다. 행 하나를 바꿔도 그 키가 속한 페이지를 다시 씁니다. 읽기는 한 키가 한 곳에만 있어 빠르지만, 쓰기는 흩어진 페이지를 랜덤하게 건드립니다.

로그 구조 병합 트리(Log-Structured Merge-Tree, LSM 트리)는 쓰기를 메모리에 모았다가 한꺼번에 순차 기록합니다. 데이터 정리는 나중에 백그라운드에서 수행합니다. RocksDB, Cassandra, LevelDB가 이 구조를 사용합니다.

LSM 트리의 쓰기 경로

쓰기는 메모리에서 시작해 디스크 아래쪽으로 한 방향으로만 흐릅니다. 각 단계는 다음 그림처럼 이어집니다.

flowchart LR
  w[쓰기 요청<br/>키-값 한 쌍] --> wal[Write-Ahead Log<br/>장애 복구용 순차 로그]
  w --> mem[MemTable<br/>메모리 정렬 자료구조]
  mem -->|가득 참| imm[Immutable MemTable<br/>읽기 전용 전환]
  imm -->|flush| l0[SSTable L0<br/>불변 정렬 파일]
  l0 -->|compaction| l1[SSTable L1 이하<br/>병합·정리된 하위 레벨]

• MemTable: 메모리의 정렬 자료구조입니다. 보통 스킵 리스트(skip list)로 구현하며, 새 쓰기는 여기에 먼저 들어갑니다.
• Write-Ahead Log(쓰기 전 로그, WAL): MemTable은 휘발성이라, 같은 내용을 디스크에 순차로 덧붙여 장애 시 복구 근거로 씁니다.
• MemTable이 가득 차면 읽기 전용(immutable)으로 바꾸고 새 MemTable을 엽니다. 읽기 전용 MemTable은 SSTable로 flush됩니다.
• Sorted String Table(정렬된 문자열 테이블, SSTable): 불변 정렬 파일입니다. 블룸 필터와 인덱스를 함께 둬서 읽기 때 없는 키를 빠르게 건너뜁니다.

읽기는 MemTable에서 L0, L1 순으로 내려가며 키를 찾습니다. 블룸 필터가 해당 키가 없는 SSTable을 미리 걸러 디스크 접근을 줄입니다.

여기까지 쓰기는 전부 순차입니다. 문제는 SSTable이 불변이라는 데서 시작합니다. 갱신과 삭제도 새 레코드로 추가되므로, 같은 키의 옛 버전과 삭제 표식(tombstone)이 파일마다 쌓입니다.

쓰기 증폭이 생기는 자리

컴팩션(compaction)은 오래된 버전과 삭제 표식을 정리합니다. 여러 SSTable을 읽어 같은 키를 병합하고, 오래된 버전과 삭제 표식을 제거한 새 SSTable을 씁니다. 이 정리 과정에서 이미 기록한 데이터를 다시 읽고 씁니다.

쓰기 증폭 계수(Write Amplification Factor, WAF)는 실제 스토리지 기록 바이트를 애플리케이션이 요청한 바이트로 나눈 값입니다. 키는 최종 레벨에 도달할 때까지 여러 레벨에서 다시 기록됩니다. 일반적인 leveled compaction에서는 레벨 수와 인접 레벨 크기 비율이 커질수록 WAF도 증가합니다.

RocksDB 공식 튜닝 가이드는 500GB 데이터베이스와 10배 크기 비율을 둔 예에서 WAF를 약 33으로 계산합니다. 이는 제품 기본값의 보장이나 모든 워크로드의 실측 범위가 아니라, 각 레벨에서 다시 쓰는 바이트를 더한 예시입니다. 실제 값은 키 분포, 갱신 패턴, 압축, 채워진 레벨 수에 따라 달라집니다.

예시 WAF = 최초 L0 기록 1 + L0→L1 병합 2 + 하위 레벨 병합 10 + 10 + 10 = 33

컴팩션 전략의 트레이드오프

같은 컴팩션이라도 SSTable을 어떻게 묶어 병합하느냐가 증폭의 분배를 정합니다. 크게 레벨드(Leveled)와 티어드(Tiered) 두 갈래입니다. 레벨드는 레벨마다 키 범위가 겹치지 않게 유지하고, 티어드는 비슷한 크기의 파일이 N개 모이면 묶어 병합합니다.

이 비교는 RocksDB 컴팩션 문서의 구조적 성질을 요약합니다. Leveled는 다음 레벨에서 겹치는 파일을 다시 쓰므로 공간을 아끼는 대신 WAF가 커집니다. Tiered는 기존 run을 덜 다시 쓰는 대신 여러 run과 임시 공간을 남깁니다.

티어드는 같은 크기의 파일끼리 병합하므로 한 번에 다시 쓰는 범위가 작습니다. 대신 같은 키의 오래된 버전이 여러 파일에 남아 공간 증폭과 읽기 증폭이 증가합니다. 쓰기 비용을 줄이는 대신 다른 비용이 늘어납니다.

RUM 추측(RUM Conjecture)은 읽기(Read)·갱신(Update)·메모리(Memory) 비용을 동시에 최소화할 수 없다고 설명합니다. 쓰기·읽기·공간 증폭은 서로 영향을 줍니다. 하나를 줄이면 다른 비용이 증가할 수 있습니다.

레벨드에서 L0가 너무 빨리 쌓이면 RocksDB는 쓰기 스톨(write stall)을 걸어 유입을 일부러 늦춥니다. 컴팩션이 유입 속도를 따라잡지 못한다는 신호입니다. 이 지점에서 쓰기 증폭이 처리량 저하로 직접 이어집니다.

증폭을 줄이는 방법

쓰기 증폭은 컴팩션이 키와 값을 함께 옮기는 데서 크게 나옵니다. 값이 크면 재기록 비용도 그만큼 불어납니다. 그래서 큰 값을 컴팩션 경로에서 빼는 접근이 효과적입니다.

키-값 분리(Key-Value separation)는 큰 값을 별도 Blob 영역에 두고 LSM 트리에는 키와 포인터만 남깁니다. WiscKey 논문은 키 16바이트, 값 1KB, 키 쪽 WAF 10을 가정한 계산에서 전체 WAF가 1.14가 된다고 설명합니다. 이 값은 해당 가정의 계산 결과이며, 실제 감소 폭은 키와 값의 크기 및 가비지 컬렉션 비용에 따라 달라집니다.

다음 그림은 키와 포인터만 LSM 트리에 남기고 값은 Blob 저장소에 따로 두는 배치를 보여줍니다.

flowchart LR
  subgraph lsm["LSM 트리 (키와 포인터)"]
    k1["k1 → 0x10"]
    k2["k2 → 0x20"]
  end
  subgraph blob["Blob 저장소 (값 본문)"]
    v1["0x10: large-value-A"]
  end
  k1 -->|포인터 참조| v1

Blob은 SSTable 컴팩션으로 자동 정리되지 않습니다. 유효한 키를 추적하는 가비지 컬렉션(garbage collection, GC)이 별도로 필요합니다. 따라서 쓰기 증폭을 줄이는 대신 GC와 공간 관리 비용이 생깁니다.

운영 단계에서는 RocksDB 파라미터로 증폭 지점을 조절합니다. 다음은 공식 옵션 중 자주 쓰는 항목입니다.

워크로드에 따라 먼저 조정할 파라미터가 달라집니다. SSD 수명 예산이 부족하면 쓰기 증폭을 우선 줄입니다. 검색·온라인 분석 처리(OLAP)처럼 읽기가 중요하면 읽기 증폭을 우선합니다. 스토리지 비용이 제약이면 공간 증폭을 우선합니다.

정리

LSM 트리는 랜덤 쓰기를 순차 쓰기로 바꿔 처리량을 얻고, 컴팩션 과정에서 같은 데이터를 반복 기록합니다. WAF는 레벨 구성과 워크로드에 따라 달라지므로 하나의 범위를 제품 기본값처럼 적용할 수 없습니다. 실제 운영에서는 RocksDB 통계나 디스크 쓰기량을 사용해 직접 측정해야 합니다.

컴팩션 전략은 쓰기, 읽기, 공간 비용을 나눠 배치합니다. 키-값 분리는 큰 값을 컴팩션에서 빼지만 별도 가비지 컬렉션을 요구합니다. 파라미터를 바꾸기 전에는 현재 병목과 세 증폭을 함께 측정해야 합니다.