LSM 트리와 쓰기 증폭

순차 쓰기로 번 처리량을 컴팩션이 도로 비싸게 만드는 지점이 쓰기 증폭입니다.

순차 쓰기라는 선택

저장 장치는 같은 양을 써도 순차 쓰기가 랜덤 쓰기보다 빠릅니다. 하드 디스크는 순차 접근이 랜덤 접근보다 대략 100배 빠르다고 알려져 있고, SSD도 순차 쓰기가 수명과 처리량에서 유리합니다. 이 물리적 특성이 스토리지 엔진의 쓰기 전략을 가릅니다.

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

로그 구조 병합 트리(Log-Structured Merge-Tree, LSM 트리)는 반대 전략을 택합니다. 들어오는 쓰기를 메모리에 모았다가 통째로 순차 기록하고, 정리는 나중에 백그라운드로 미룹니다. RocksDB, Cassandra, LevelDB가 이 구조를 씁니다.

LSM 트리의 쓰기 경로

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

• 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)은 그 대가를 수치로 본 것입니다. 쓰기 증폭 계수(Write Amplification Factor, WAF)는 스토리지에 실제 기록된 바이트를 애플리케이션이 요청한 바이트로 나눈 값입니다. 키 하나가 최종 레벨에 닿기까지 여러 레벨을 거치며 재기록됩니다. 그래서 쓰기 증폭은 레벨 수 L과 레벨당 팬아웃 T에 비례해 O(L·T)까지 커집니다.

RocksDB 기본 설정은 레벨 6단계, 레벨당 팬아웃 10배 정도입니다. 이 구성에서 실측 쓰기 증폭은 대략 1030배 범위로 알려져 있습니다(워크로드 의존, 대략값). 사용자가 1바이트를 쓰면 디스크에는 그 1030배가 기록될 수 있다는 뜻입니다.

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

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

위 수치는 공개 측정과 문서 기준의 대략값입니다. ScyllaDB 측정 기준으로 레벨드는 티어드보다 공간 효율이 약 5배 높지만 쓰기 증폭은 약 2배 큽니다. 레벨드가 SSTable 한 개를 컴팩션할 때 다음 레벨에서 키 범위가 겹치는 파일을 최대 10여 개 함께 병합하기 때문입니다.

티어드는 같은 크기끼리만 병합해 한 번에 다시 쓰는 범위가 작습니다. 대신 같은 키의 옛 버전이 여러 파일에 흩어져 남아 공간 증폭과 읽기 증폭이 커집니다. 쓰기 증폭을 낮춘 만큼 다른 축에서 비용이 되돌아옵니다.

이 상충은 우연이 아닙니다. 읽기(Read)·갱신(Update)·메모리(Memory) 비용을 동시에 최소화할 수 없다는 RUM 추측(RUM Conjecture)이 한계를 요약합니다. 세 증폭(쓰기·읽기·공간)은 상충하므로, 한 축을 누르면 다른 축이 부풀어 오릅니다.

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

증폭을 줄이는 방법

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

키-값 분리(Key-Value separation)는 큰 값을 별도 Blob 영역에 두고 LSM 트리에는 키와 포인터만 남깁니다. WiscKey(FAST 2016 논문)가 제안했고, RocksDB의 BlobDB와 TiKV Titan이 이를 구현했습니다. 값이 4KB 이상일 때 쓰기 증폭을 대략 50~80% 줄인다고 보고됩니다(WiscKey 계열 보고값).

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

다만 Blob은 컴팩션처럼 자동으로 정리되지 않습니다. 유효 키를 역추적하는 가비지 컬렉션(garbage collection, GC)이 따로 돌아야 하고, 그 비용이 공간 증폭으로 되돌아옵니다. 쓰기 증폭을 줄인 자리를 GC 부담이 채우는 구조입니다.

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

어떤 파라미터를 먼저 조정할지는 워크로드가 정합니다. SSD 수명 예산이 빠듯하면 쓰기 증폭을 먼저 누릅니다. 검색·온라인 분석 처리(OLAP)처럼 읽기가 중요하면 읽기 증폭을, 스토리지 비용이 제약이면 공간 증폭을 우선합니다.

정리

LSM 트리는 랜덤 쓰기를 순차 쓰기로 바꿔 쓰기 처리량을 얻고, 그 대가로 컴팩션이 같은 데이터를 반복 재기록하는 쓰기 증폭을 떠안습니다. 쓰기 증폭은 레벨 수와 팬아웃에 비례해 O(L·T)까지 커지며, RocksDB 기본 구성에서 대략 10~30배로 알려져 있습니다. 컴팩션 전략 선택은 이 증폭을 쓰기·읽기·공간 사이에 분배하는 결정이고, RUM 추측대로 세 축을 동시에 최소화할 수는 없습니다. 키-값 분리와 RocksDB 파라미터 조정은 쓰기 증폭을 실질적으로 줄이지만, 줄인 비용이 GC나 다른 증폭으로 되돌아온다는 점을 함께 봐야 합니다.