LSM 트리는 쓰기를 어떻게 모아 디스크에 정리할까? SSTable과 컴팩션

B-트리는 디스크 페이지 안에서 정렬된 키를 찾고 필요하면 노드를 제자리에서 나누거나 갱신한다. 쓰기가 매우 많을 때는 흩어진 페이지를 자주 바꾸는 비용이 커질 수 있다. LSM 트리는 쓰기를 메모리에 모은 뒤 정렬된 파일로 순차 기록하는 쪽을 택한다.

LSM 트리(Log-Structured Merge-tree: 변경을 메모리와 여러 단계의 정렬 파일에 쌓고 나중에 병합하는 저장 구조)는 쓰기를 빠르게 받아들이는 대신 읽을 위치와 백그라운드 정리 작업이 늘어난다.

쓰기는 WAL과 메모리 테이블에 먼저 들어간다

새 키와 값을 받으면 먼저 WAL에 복구 기록을 남기고 memtable(memory table: 최근 변경을 키 순서로 보관하는 메모리 자료구조)에 넣는다.

put("user:7", "active")
  → WAL에 추가
  → memtable에 정렬 상태로 저장
  → 쓰기 완료 응답

memtable만 사용하면 재시작 때 내용을 잃으므로 WAL이 필요하다. 반대로 WAL만 있으면 매번 전체 로그를 뒤져 읽어야 하므로 memtable이 최신 값을 빠르게 제공한다.

memtable이 정해진 크기에 도달하면 더 이상 바꾸지 않는 immutable memtable(불변 메모리 테이블: 디스크로 내리는 동안 새 변경을 받지 않는 메모리 구조)로 전환하고 새 memtable에서 쓰기를 이어 간다.

SSTable은 정렬된 채로 한 번 기록된다

immutable memtable은 SSTable(Sorted String Table: 키 순서로 정렬되어 한 번 만들어진 뒤 내용이 바뀌지 않는 디스크 파일)로 내려간다.

memtable
  a → 3
  c → 9
  f → 2
       ↓ flush
SSTable 파일
  [a:3][c:9][f:2]

파일 안에서 키가 정렬되어 있으므로 범위를 찾거나 인덱스로 위치를 좁힐 수 있다. 파일을 만든 뒤 제자리 수정하지 않아 쓰기는 큰 순차 기록으로 모인다.

flush(flush: 메모리의 정렬된 변경 묶음을 새 SSTable로 기록하는 과정)가 끝나면 해당 변경을 복구하는 데 필요했던 WAL 구간을 정리할 수 있다. 다만 복제나 백업이 필요로 하는 범위는 별도다.

읽기는 최신 구조부터 여러 곳을 확인한다

같은 키가 memtable과 여러 SSTable에 있을 수 있다. 조회는 최신 변경이 있는 곳부터 확인한다.

get("c")
  1. 현재 memtable 확인
  2. immutable memtable 확인
  3. 최신 SSTable부터 후보 파일 확인
  4. 가장 최신 버전 반환

파일이 늘면 읽기 증폭(read amplification: 하나의 값을 찾기 위해 여러 자료구조나 파일을 확인해야 하는 추가 읽기)이 커진다. 각 SSTable의 최소·최대 키, 희소 인덱스, 캐시를 사용해 볼 필요가 없는 파일을 줄인다.

블룸 필터(Bloom filter: 어떤 키가 집합에 절대 없다는 사실은 확실히 말하고 있을 가능성은 작게 틀릴 수 있는 확률적 자료구조)는 디스크 파일을 열기 전에 키가 없음을 빠르게 거르는 데 유용하다. “있을 수 있다”는 답은 실제 존재를 보장하지 않으므로 해당 SSTable을 다시 확인한다.

삭제도 즉시 모든 파일에서 지우지 않는다

이미 만들어진 SSTable은 수정하지 않는다. 삭제 요청은 tombstone(삭제 표식: 해당 키의 이전 값이 논리적으로 삭제됐음을 나타내는 새 기록)으로 남긴다.

오래된 SSTable: user:7 → active
최신 SSTable  : user:7 → TOMBSTONE

조회 결과: 없음

오래된 파일만 보면 값이 남아 있지만 최신 삭제 표식이 가린다. 모든 관련 파일을 즉시 고쳐 쓰지 않아 빠른 쓰기를 유지하는 대신, tombstone을 언제 실제로 제거할지 컴팩션이 맡는다.

복제 지연이나 스냅샷이 오래된 버전을 필요로 한다면 삭제 표식을 너무 일찍 없앨 수 없다. 그렇지 않으면 오래된 값이 다시 살아나는 것처럼 보일 수 있다.

컴팩션은 파일을 병합해 최신 상태를 남긴다

컴팩션(compaction: 여러 SSTable을 읽어 키 순서로 병합하고 오래된 값과 불필요한 삭제 표식을 정리해 새 파일을 만드는 작업)은 읽을 파일 수와 저장 공간을 줄인다.

SSTable A: a:1, c:old, f:2
SSTable B: c:new, d:4
                ↓ compaction
새 SSTable : a:1, c:new, d:4, f:2

컴팩션은 많은 데이터를 다시 읽고 쓴다. 실제 사용자 쓰기보다 저장장치에 더 많은 바이트가 기록되는 쓰기 증폭(write amplification: 논리적 변경보다 내부 병합 때문에 실제 기록량이 늘어나는 현상)이 생긴다.

컴팩션이 느리면 SSTable과 tombstone이 쌓여 읽기가 느려지고 디스크가 찬다. 너무 공격적으로 실행하면 사용자 요청과 I/O를 경쟁한다. LSM 트리 운영에서는 쓰기 속도만 아니라 컴팩션 부채와 디스크 여유를 함께 본다.

레벨 방식과 크기 계층 방식은 병합 시점을 다르게 잡는다

레벨드 컴팩션(leveled compaction: 각 레벨의 키 범위 겹침을 줄이도록 파일을 여러 단계에 배치하고 병합하는 방식)은 읽을 파일 수를 줄이는 데 유리하지만 데이터를 여러 번 다시 쓸 수 있다.

사이즈 티어드 컴팩션(size-tiered compaction: 크기가 비슷한 SSTable 여러 개를 묶어 더 큰 파일로 병합하는 방식)은 쓰기 부담을 줄일 수 있지만 같은 키 범위가 여러 파일에 남아 읽기와 공간 사용이 커질 수 있다.

어느 방식이 낫다는 한 가지 답은 없다. 쓰기량, 읽기 패턴, 값 크기, 삭제 비율, 저장장치 특성에 따라 선택이 달라진다.

이해 확인 질문과 답변

LSM 트리가 쓰기에 유리한 이유는 무엇일까?

작은 변경마다 흩어진 디스크 페이지를 제자리 갱신하지 않고 메모리에 모아 정렬된 새 파일로 순차 기록하기 때문이다. WAL로 내구성을 보완하고 나중에 컴팩션으로 정리한다.

같은 키가 여러 SSTable에 있으면 어느 값을 읽을까?

memtable과 SSTable의 시간·순서 정보를 따라 가장 최신 버전을 고른다. 오래된 값은 새 값이나 tombstone에 가려지고 컴팩션 때 정리될 수 있다.

블룸 필터가 키를 찾았다고 하면 값이 반드시 있을까?

아니다. 블룸 필터는 “없음”은 확실히 거를 수 있지만 “있을 수 있음”에는 거짓 양성이 있다. 후보 SSTable의 실제 인덱스와 데이터를 다시 확인해야 한다.

컴팩션을 멈추면 쓰기만 계속 빠를까?

잠시 그럴 수 있지만 파일과 오래된 버전이 쌓여 읽기와 공간 사용이 악화된다. 디스크가 차거나 쓰기 제한이 걸릴 수 있으므로 컴팩션도 저장 구조의 필수 동작이다.

AI에게 이렇게 요청할 수 있다

put 요청이 WAL과 memtable을 거쳐 SSTable로 flush되는 과정을 보여 줘. 같은 키의 새 값과 tombstone을 여러 SSTable에서 읽는 순서, 블룸 필터의 거짓 양성, 컴팩션으로 읽기 증폭과 쓰기 증폭이 바뀌는 경우를 설명해 줘.

LSM 트리는 쓰기 비용을 없애지 않는다. 작은 무작위 갱신을 메모리와 순차 파일에 모은 뒤, 읽기와 공간 정리 비용을 컴팩션 시점으로 옮긴다.