LSM Tree는 왜 쓰기를 먼저 받아들이고 나중에 정리할까

in DEVELOP on Database, Storage-engine, Lsm-tree, Cassandra, Rocksdb

LSM Tree의 WAL, MemTable, SSTable, Bloom Filter, Compaction 전략과 read/write/space amplification을 정리합니다.

저장 엔진은 결국 시간을 다루는 방식이다.

B-Tree 계열은 데이터가 있어야 할 자리를 찾아가 그 자리의 page를 고친다. 읽기와 범위 조회에는 단정한 구조다. 대신 쓰기가 많아질수록 여러 위치의 page가 더러워지고, flush나 page split이 랜덤 I/O처럼 나타날 수 있다.

LSM Tree는 다른 약속을 한다.

지금은 일단 빠르게 받아 적고, 정리는 나중에 묶어서 하자.

쓰기 요청은 먼저 append-friendly한 디스크 로그와 메모리 구조에 들어간다. 메모리가 차면 정렬된 불변 파일로 내려보낸다. 파일이 많아지면 배경에서 merge한다. 이 덕분에 쓰기 경로는 단순하고 빠르지만, 읽기와 compaction에는 반드시 비용이 생긴다.

B-Tree와 LSM은 쓰기를 미루는 방식이 다르다

B-Tree는 데이터가 들어갈 위치를 찾아 leaf page를 수정한다. 그 page가 캐시에 있으면 빠르게 끝날 수 있지만, 결국 더러운 page는 디스크에 내려가야 한다. page split이 생기면 주변 구조도 바뀐다.

물론 실제 데이터베이스는 B-Tree 위에도 WAL, MVCC, page cache, checkpoint 같은 장치를 겹쳐 쓴다. 여기서는 저장 엔진이 변경분을 최종 정렬 구조에 반영하는 기본 방향을 비교하는 것이다.

LSM은 page를 제자리에서 고치지 않는다. 새 변경분을 먼저 로그와 메모리에 넣고, 나중에 정렬된 파일로 내려보낸다.

B-Tree
  key 위치를 찾아 page를 수정

LSM Tree
  변경분을 먼저 append
  메모리에서 정렬
  디스크에는 immutable sorted run으로 flush
  나중에 compaction으로 정리

그래서 LSM은 write-heavy workload에 강하다. Cassandra, RocksDB, LevelDB, HBase, ScyllaDB, TiKV 같은 시스템들이 이 계열의 아이디어를 사용한다.

다만 이 말이 “LSM은 항상 B-Tree보다 좋다”는 뜻은 아니다. B-Tree는 point read, range scan, update-in-place가 잘 맞는 워크로드에서 여전히 강하다. LSM은 쓰기 경로를 편하게 만든 대신, 읽기와 compaction을 더 복잡하게 만든다.

기본 부품: WAL, MemTable, SSTable

LSM 기반 저장 엔진의 기본 부품은 보통 세 가지다.

  • WAL 또는 commit log: 장애 복구를 위한 디스크의 append-only 로그다.
  • MemTable: 메모리에 있는 정렬된 구조다. Skip list, tree 계열 구조가 자주 쓰인다.
  • SSTable: 디스크에 내려간 immutable sorted file이다.

정확히 말하면 WAL은 MemTable처럼 메모리에 머무는 자료구조가 아니다. 쓰기 호출이 OS page cache나 파일 시스템 버퍼를 거칠 수는 있지만, 장애 복구 관점에서 WAL의 역할은 디스크, HDFS, 별도 로그 디렉터리 같은 persistent storage에 먼저 기록을 남기는 것이다. 메모리에 있는 것은 MemTable이고, WAL은 그 MemTable을 잃어버렸을 때 다시 재구성하기 위한 기록이다.

쓰기 흐름은 단순하다.

PUT user:1 = "kim"

1. WAL에 append한다.
2. MemTable에 반영한다.
3. MemTable이 커지면 immutable MemTable로 바꾼다.
4. 정렬된 순서 그대로 SSTable로 flush한다.

Durability의 정확한 시점은 구현과 설정에 따라 다르다. 어떤 시스템은 매 요청마다 fsync에 가깝게 동기화하고, 어떤 시스템은 주기적으로 sync한다. 중요한 구조적 사실은 같다. 쓰기 경로는 먼저 WAL append와 메모리 반영으로 끝내고, 디스크의 정렬된 본체인 SSTable은 나중에 만들어진다.

Cassandra 공식 문서도 이 흐름을 commit log 기록, memtable write, memtable flush, SSTable 저장 순서로 설명한다. MemTable은 정렬된 상태로 쓰기를 보관하고, 한계에 도달하면 디스크의 immutable SSTable로 flush된다. RocksDB도 WAL을 MemTable operation을 persistent medium의 log file로 직렬화하는 구조로 설명하고, HBase 역시 WAL이 HDFS의 /hbase/WALs/ 아래에 위치한다고 설명한다.

SSTable은 그냥 데이터 파일 하나가 아니다

SSTable은 “정렬된 key-value 파일”이라고 말하면 이해는 쉽지만, 실제 저장 엔진에서는 주변 메타데이터가 같이 붙는다.

대표적으로 다음이 있다.

  • 데이터 블록: 실제 row나 key-value payload.
  • 인덱스: key에서 파일 위치를 찾기 위한 구조.
  • 요약 정보: 큰 인덱스를 더 빠르게 좁히기 위한 sampling.
  • Bloom filter: 이 파일에 key가 없다는 사실을 빠르게 거르기 위한 확률적 구조.
  • 통계와 메타데이터: timestamp, tombstone, 압축, TTL, compaction 정보 등.

정렬되어 있다는 점은 중요하다. 정렬된 파일끼리는 merge sort처럼 순서대로 훑으면서 합칠 수 있다. LSM의 compaction은 이 성질 위에 서 있다.

읽기는 여러 층을 조심스럽게 확인한다

쓰기와 달리 읽기는 조금 더 바쁘다. 찾는 key가 아직 MemTable에 있을 수도 있고, 최근 flush된 SSTable에 있을 수도 있고, 오래된 level에 있을 수도 있다.

Bloom filter의 역할은 “있다”를 보장하는 것이 아니다. “없다”를 빠르게 말해주는 것이다.

Bloom filter says NO
  -> 이 SSTable에는 key가 없다. 디스크 read 생략.

Bloom filter says MAYBE
  -> 있을 수도 있다. index와 data block을 확인.

여러 SSTable에서 같은 key의 서로 다른 version이 나올 수 있다. 이때 저장 엔진은 timestamp, sequence number, tombstone 같은 규칙으로 최신 값을 고른다.

Range scan은 조금 다르다. Bloom filter는 특정 key 부재 확인에는 좋지만, 넓은 범위 조회에서는 도움의 폭이 작다. 대신 SSTable이 정렬되어 있다는 점이 중요해진다. 여러 sorted run을 merge하면서 범위를 읽는다.

Delete는 지우는 것이 아니라 tombstone을 쓰는 것이다

SSTable은 immutable이다. 이미 디스크에 내려간 파일 안의 key를 그 자리에서 지우지 않는다.

삭제 요청이 오면 새로운 변경분을 append한다.

DELETE user:1

MemTable
  user:1 = TOMBSTONE

나중에 flush
  SSTable N: user:1 = TOMBSTONE

읽기 시점에는 tombstone이 이전 값을 가린다. 물리적인 삭제는 compaction에서 일어난다. 단, tombstone을 아무 때나 버리면 안 된다. 다른 SSTable이나 다른 복제본에 오래된 값이 남아 있을 수 있기 때문이다.

Cassandra 같은 분산 저장소에서는 tombstone을 언제 안전하게 제거할 수 있는지가 특히 중요하다. tombstone과 그 tombstone이 지우는 과거 데이터가 서로 다른 SSTable에 있을 수 있고, 복제본 복구나 repair 타이밍도 고려해야 한다.

Compaction은 LSM의 심장이다

MemTable을 flush할 때마다 SSTable은 계속 늘어난다. 그대로 두면 읽기마다 너무 많은 파일을 봐야 한다. 그래서 LSM은 background compaction으로 파일들을 합친다.

Before
SSTable A: a=1, b=2, d=7
SSTable B: b=3, c=4
SSTable C: d=TOMBSTONE

After compaction
SSTable D: a=1, b=3, c=4

위 예시는 d의 tombstone이 더 이상 필요 없다고 판단된 경우다. tombstone은 compaction 대상에 들어왔다고 무조건 사라지지 않는다. 오래된 값이나 복제본 복구 가능성을 아직 가려야 한다면, 새 SSTable에 다시 기록될 수 있다.

Compaction이 하는 일은 단순한 압축이 아니다.

  • 여러 sorted run을 merge한다.
  • 같은 key의 오래된 version을 버린다.
  • tombstone이 안전하면 제거한다.
  • level이나 size tier 규칙에 맞게 새 SSTable을 만든다.

대신 비용이 크다. 기존 SSTable을 읽고 새 SSTable을 쓴다. compaction 중에는 입력 파일과 출력 파일이 잠시 함께 존재할 수도 있다. 그래서 compaction은 write amplification과 space amplification을 만든다. 배경 작업이지만 디스크 대역폭을 먹기 때문에 p99 latency를 흔들 수도 있다.

Compaction 전략은 무엇을 희생할지 정하는 일이다

LSM에서 compaction 전략은 단순한 청소 정책이 아니다. 읽기, 쓰기, 공간 사용량의 균형을 정하는 설계다.

RocksDB의 기본 compaction은 leveled compaction이다. L0에는 새 파일이 겹친 range로 들어올 수 있지만, 하위 level로 내려갈수록 key range를 정리해 read 후보를 줄인다.

Cassandra의 Size-Tiered Compaction Strategy는 비슷한 크기의 SSTable 묶음을 병합하는 쪽에 가깝다. 쓰기 처리량에는 유리하지만, 같은 key가 여러 SSTable에 흩어질 수 있어 읽기 후보가 많아질 수 있다.

RocksDB의 Universal Compaction은 tiered family에 속한다. 쓰기 증폭을 낮추려는 선택이지만, 읽기 증폭과 공간 증폭, compaction traffic의 변동성을 더 크게 가져갈 수 있다.

세 가지 amplification을 같이 봐야 한다

LSM을 볼 때는 세 가지 amplification을 함께 봐야 한다.

쓰기 처리량만 보면 tiered 계열이 좋아 보일 수 있다. 하지만 read-heavy 서비스에서는 많은 sorted run이 p99 read latency를 밀어 올릴 수 있다.

읽기를 안정적으로 만들려면 leveled 계열이 좋아 보일 수 있다. 하지만 더 많은 compaction write가 생기고, SSD endurance나 background I/O가 문제가 될 수 있다.

공간을 아끼려면 오래된 version과 tombstone을 자주 정리해야 한다. 하지만 그 역시 compaction I/O를 늘린다.

결국 LSM 튜닝은 “무엇을 가장 싸게 만들 것인가”를 정하는 일이다.

B-Tree와 나란히 보면

항목 B-Tree 계열 LSM Tree 계열
쓰기 방식 대상 page를 찾아 수정한다. WAL과 MemTable에 먼저 append/update하고, 나중에 flush한다.
디스크 파일 페이지가 계속 갱신된다. SSTable은 immutable하고 새 파일이 계속 생긴다.
읽기 트리 탐색으로 위치를 좁힌다. MemTable과 여러 SSTable 후보를 확인하고 merge한다.
범위 조회 leaf 순회가 자연스럽다. 정렬된 run들을 merge해야 하며 compaction 상태에 영향을 받는다.
삭제 page에서 직접 제거하거나 표시한다. tombstone을 기록하고 compaction에서 안전하게 제거한다.
대표 비용 랜덤 page 갱신, split, dirty page flush. read amplification, write amplification, compaction I/O.

SSD 시대에도 append-first가 의미 있는 이유

HDD에서는 sequential I/O와 random I/O의 차이가 극단적이었다. SSD에서는 그 차이가 줄었지만 LSM의 의미가 사라지지는 않는다.

SSD도 내부적으로 erase block, write amplification, garbage collection, FTL mapping을 가진다. 작은 랜덤 쓰기를 많이 만드는 것보다 큰 순차 쓰기와 배경 merge로 묶는 편이 여전히 유리한 경우가 많다.

다만 SSD에서는 또 다른 균형이 생긴다. Compaction이 너무 많이 돌면 저장 엔진의 write amplification과 SSD 내부 write amplification이 겹친다. 그래서 현대 LSM 엔진은 compaction rate limiting, compression, partitioned index, block cache, tiered storage 같은 최적화를 함께 쓴다.

운영에서 실제로 아픈 곳

LSM 시스템의 장애와 지연은 보통 compaction 주변에서 보인다.

  • 쓰기는 빠른데 read p99가 튄다: SSTable 수가 많거나 Bloom filter/index/cache 효율이 떨어졌을 수 있다.
  • 주기적으로 latency가 솟는다: compaction이 디스크 bandwidth를 가져가고 있을 수 있다.
  • 디스크 사용량이 갑자기 늘어난다: compaction 중 입력 SSTable과 출력 SSTable이 동시에 존재할 수 있다.
  • delete를 많이 했는데 공간이 바로 줄지 않는다: tombstone은 compaction에서 안전할 때 제거된다.
  • 쓰기 처리량이 갑자기 막힌다: MemTable flush나 compaction이 밀려 backpressure가 걸렸을 수 있다.

그래서 LSM 기반 DB를 운영할 때는 단순 QPS보다 pending compaction, SSTable count, Bloom filter hit/miss, block cache hit ratio, flush latency, disk bandwidth, write stall을 같이 봐야 한다.

한 문장으로 정리하면

LSM Tree는 랜덤 업데이트를 sequential append와 background merge로 바꿔 쓰기 경로를 단순하게 만드는 저장 엔진 구조다.

대신 데이터는 여러 층에 잠시 흩어지고, compaction이 그 흩어진 시간을 다시 접는다. WAL은 방금 쓴 값을 잃지 않게 하고, MemTable은 새 값을 조용히 정렬하고, SSTable은 식은 커피처럼 단단해진 기록으로 남는다. 그리고 compaction은 그 기록들을 다시 한 줄로 읽기 좋게 정리한다.

LSM을 이해한다는 것은 단순히 “쓰기 빠른 자료구조”를 외우는 것이 아니다. 지금 빠르게 받아들인 쓰기를 언제, 어디서, 어떤 비용으로 정리할지 이해하는 일이다.

참고한 자료

© 2024. All rights reserved.