LSM 트리 (Log-Structured Merge-Tree)

쓰기를 메모리에 모았다가 디스크에 통째로 쏟아붓는 저장 엔진 · RocksDB · LevelDB · Cassandra · HBase의 심장

문제. 디스크(특히 HDD, 그리고 SSD도)는 여기저기 흩어진 위치에 조금씩 쓰는 것(random write)을 아주 싫어한다. 반대로 한 곳에 쭉 이어서 쓰는 것(sequential write)은 수십~수백 배 빠르다.

아이디어. 그럼 매번 디스크의 제자리에 값을 고쳐 쓰지 말고, 변경을 메모리에 모아뒀다가 가득 차면 정렬된 파일 하나로 순차 기록하자. 이미 쓴 파일은 절대 고치지 않고(불변, immutable), 나중에 여러 파일을 병합(merge)하며 정리한다.

이 구조가 바로 LSM 트리다. 이름의 "Log"는 순차 기록, "Merge"는 병합 정리를 뜻한다.

구성 요소

1. MemTable (메모리)

최근 쓰기가 담기는 정렬된 자료구조(보통 스킵 리스트나 균형 트리). 키 순서가 항상 유지된다. 같은 키를 또 쓰면 덮어쓰지 않고 최신 값으로 갱신만 한다.

2. WAL (쓰기 전 로그)

MemTable은 메모리라 껐다 켜면 날아간다. 그래서 쓰기는 먼저 디스크의 WAL 파일에 순차 append한 뒤 MemTable에 넣는다. 죽었다 살아나면 WAL을 재생(replay)해 MemTable을 복구한다.

3. SSTable (Sorted String Table, 디스크)

MemTable이 가득 차면 Flush: 내용을 키로 정렬된 불변 파일로 디스크에 순차 기록한다. 한 번 만들어진 SSTable은 절대 수정되지 않는다(읽기만).

4. Compaction (컴팩션 / 병합)

SSTable이 쌓이면 읽기가 느려진다. 그래서 백그라운드에서 여러 SSTable을 병합 정렬하며 하나로 합친다. 이때 같은 키의 옛 값은 버리고, 삭제 표시(tombstone, 묘비)에 걸린 키는 완전히 제거한다.

삭제도 "쓰기"다. LSM 트리는 파일을 못 고치므로, 지우려면 key → tombstone이라는 특수 값을 새로 쓴다. 실제 데이터는 컴팩션 때 사라진다.

직접 해 보기

MemTable은 4개가 차면 자동으로 Flush → Level 0에 SSTable이 쌓인다. Level 0에 SSTable이 3개 모이면 자동 컴팩션 → Level 1 하나로 병합된다. "읽기"는 MemTable → L0(최신순) → L1 순서로 훑으며, 처음 만난 값이 정답이다.

왜 이렇게까지 하나 — 읽기/쓰기 증폭

쓰기 증폭 (Write Amplification). 사용자는 키를 한 번 썼는데, 그 데이터는 WAL 기록 → Flush → 여러 번의 컴팩션을 거치며 디스크에 여러 번 다시 쓰인다. 대신 매번이 순차 쓰기라서 총량이 많아도 빠르다.

읽기 증폭 (Read Amplification). 어떤 키가 어느 SSTable에 있는지 모르니 최악의 경우 여러 파일을 다 열어봐야 한다. 이를 줄이는 장치:

Bloom 필터: SSTable마다 "이 키 없음"을 빠르게 판단해 디스크 접근을 건너뛴다.
Sparse Index: SSTable 안 키의 위치를 듬성듬성 기록해 이진 탐색으로 근처를 찾는다.
레벨 구조: 레벨이 깊어질수록 파일이 크고 키 범위가 안 겹치게 유지해 후보를 좁힌다.

공간 증폭 (Space Amplification). 옛 값과 tombstone이 컴팩션 전까지 디스크를 차지한다.

B-트리 인덱스와 비교

항목	B-트리 (제자리 갱신)	LSM 트리 (로그 구조)
쓰기	페이지를 찾아가 random write	메모리 append + 순차 flush → 빠름
읽기	트리 한 경로 → 예측 가능하게 빠름	여러 SSTable 확인 가능 → 느릴 수 있음
디스크 활용	페이지 단편화·여유 공간 필요	압축 잘 됨, 순차 파일
삭제	즉시 반영	tombstone → 컴팩션 때 실제 제거
대표	MyS(InnoDB), PostgreSQL, 대부분 RDB	RocksDB, LevelDB, Cassandra, HBase, ScyllaDB

한 줄 요약: 쓰기가 많고 SSD에 최적화하고 싶다면 LSM, 읽기 지연이 안정적이어야 하면 B-트리. 실제 시스템은 둘을 섞어 쓰기도 한다.

읽기 경로 의사코드

# get(key): 최신 데이터가 있는 곳부터 확인, 처음 만난 값이 정답
def get(key):
    if key in memtable:
        return resolve(memtable[key])          # tombstone이면 "없음"

    for sst in level0_sstables[::-1]:          # 최신 파일부터
        if sst.bloom.might_contain(key):        # Bloom 필터로 빠른 배제
            v = sst.lookup(key)                 # sparse index + 이진 탐색
            if v is not None: return resolve(v)

    for lvl in (1, 2, 3, ...):               # 레벨은 키 범위가 안 겹침 → 파일 1개만
        sst = level[lvl].find_range(key)
        if sst and sst.bloom.might_contain(key):
            v = sst.lookup(key)
            if v is not None: return resolve(v)

    return "없음"

기억할 것 세 가지 — ① 쓰기는 메모리에 모았다 순차로 flush, ② 파일은 불변, 정리는 컴팩션이 병합으로, ③ 삭제는 tombstone.