LSM 트리란? 로그 구조 병합 트리 완벽 해설

LSM 트리란?

로그 구조 병합 트리(LSM)는 들어오는 쓰기를 메모리에 버퍼링한 뒤, 정렬된 불변 배치 형태로 디스크에 병합하는 데이터 구조입니다. 데이터를 제자리에서 수정하는 일은 절대 없습니다. 대신 변경 사항을 축적하고 정리 작업을 미룹니다. 읽기 측의 단순성을 포기하는 대신 쓰기 처리량을 확보하는 방식입니다.

LSM 트리는 Patrick O’Neil, Edward Cheng, Dieter Gawlick, Elizabeth O’Neil이 1996년에 발표한 로그 구조 병합 트리(LSM 트리)라는 논문에서 체계화되었습니다. 약 10년 동안 비교적 잘 알려지지 않은 학술 구조로 남아 있다가 Google의 Bigtable이 이 개념을 기반으로 스토리지 계층을 구축하면서 주목받았습니다. Bigtable의 설계는 LevelDB로, LevelDB는 RocksDB로 이어졌으며, 대량 수집을 위해 만들어진 대부분의 시스템 아래에는 어떤 형태로든 LSM 트리가 자리 잡고 있습니다.

이름만 보면 하나의 트리처럼 보이지만, 이는 상당히 오해를 부르는 표현입니다.

LSM 트리는 다음 세 구성 요소가 유기적으로 맞물려 작동하는 구조로 이해하는 편이 정확합니다.

• memtable: 가장 최근의 쓰기를 보관하는 인메모리 버퍼
• write-ahead log(WAL): 쓰기를 영속화하는 디스크의 추가 전용 파일
• 계속 늘어나는 sorted string table 파일(SST): 더 오래된 모든 데이터를 보관하는 정렬된 불변 파일

LSM의 흥미로운 동작 대부분은 데이터가 이 세 구성 요소 사이를 이동하는 방식에서 비롯됩니다. 이 모든 이동은 보통 put이라고 부르는, 겉보기에는 단순한 단일 함수 호출에서 시작됩니다.

put이란?

Put은 내부적으로 레코드 하나만 포함하는 WriteBatch를 구성한 뒤, 변경을 처리하는 **Write()**에 전달하는 편의 래퍼입니다.

자연스럽게 **Put(key, value)**에서 시작할 수 있지만, 엄밀히 말해 RocksDB에는 그런 단독 연산이 없습니다. 모든 쓰기는 배치이며, 하나의 put은 단지 항목이 하나인 배치입니다. 이는 네이티브 연산이므로 RocksDB에서는 원자적인 다중 키 쓰기를 별도 비용 없이 사용할 수 있습니다.

WriteBatch는 고정된 형태의 압축된 바이트 문자열입니다. 8바이트 시퀀스 번호와 4바이트 레코드 수를 담은 12바이트 헤더 뒤에 레코드가 이어집니다. 각 레코드는 1바이트 타입 태그, 길이 접두사가 붙은 키, 그리고 쓰기의 경우 길이 접두사가 붙은 값으로 구성됩니다.

이 시리즈의 첫 글에서 설명한 ‘키와 값은 임의의 바이트 배열’이라는 말이 여기서 문자 그대로 적용됩니다. 배치 인코딩은 바이트의 의미를 알지도, 신경 쓰지도 않습니다. 길이 접두사만이 유일하게 강제되는 구조입니다.

모든 배치에는 시퀀스 번호라는 단조 증가 카운터가 부여됩니다. 이 번호는 데이터베이스가 지금까지 수락한 모든 쓰기의 전체 순서를 정합니다. 스냅샷, 일관된 읽기, 충돌 복구가 가능한 것은 시퀀스 번호 덕분입니다. WAL의 모든 레코드는 자신의 순서를 알고 있으므로 재생할 수 있습니다.

Put, Delete, Merge

중요한 점은 Put이 kTypeValue이고 Delete가 kTypeDeletion이라는 것입니다. 즉, delete는 제거가 아닙니다. 삭제 사실을 기록하는 쓰기, 즉 tombstone이며 실제 공간 회수는 compaction까지 미뤄집니다.

Put과 Delete는 Merge 연산이 기록하는 kTypeMerge와 WriteBatch 형식을 공유합니다. 쓰기에 최적화된 저장소에서 읽기-수정-쓰기는 치명적이므로 Merge가 필요합니다. Put으로 카운터를 증가시키려면 현재 값을 읽고 1을 더한 뒤 결과를 다시 써야 합니다. 숫자 하나를 바꾸기 위해 데이터베이스를 두 번 탐색해야 하며, 읽기에는 전체 읽기 경로의 비용이 발생합니다.

Merge는 읽기를 완전히 건너뜁니다.

대신 피연산자, 즉 ‘1 더하기’와 같은 변경 설명을 추가하고 반환합니다. 쓰기 시점에는 아무것도 계산하지 않습니다. 이후 키를 다시 읽거나 compaction이 해당 체인을 만날 때, 데이터베이스가 애플리케이션에서 제공한 merge operator를 사용해 피연산자를 최종 값으로 합칩니다.

Delete는 공간 회수를 미루고, Merge는 계산을 미룹니다.

LSM 트리의 모든 특성은 이 세 가지 타입 태그에 드러납니다. 기존 상태에 논리적으로 의존하는 변경까지 포함해 모든 변경이 맹목적인 append가 됩니다. LSM 트리에서는 모든 것이 append입니다.

LSM 트리 쓰기 경로 해설

LSM 트리를 가장 명확하게 이해하는 방법은 단일 **Put(key, value)**가 함수 호출에서 디스크까지 이동하는 과정을 따라가는 것입니다.

1단계: Write-Ahead Log

쓰기는 먼저 WAL에 추가됩니다. 이 append는 memtable을 건드리기 전에 수행되며, 이 순서가 영속성 계약을 형성합니다. WAL append가 완료되면 쓰기는 아직 읽기 좋은 형태로 정리되지 않았더라도 충돌 후에도 보존되는 형태로 디스크에 존재합니다.

로그에 append하는 것은 가장 저렴한 디스크 연산입니다. 이것이 바로 핵심입니다. 순차 쓰기의 비용만으로 영속성을 확보합니다.

RocksDB는 비용을 더 분산하기 위해 동시 쓰기를 그룹 커밋으로 묶습니다. sync 옵션은 호출이 반환되기 전에 append를 OS 페이지 캐시에서 안정적인 스토리지로 flush할지 제어합니다.

2단계: Memtable

영속성이 확보되면 쓰기가 memtable에 삽입됩니다. 기본적으로 RocksDB의 memtable은 skiplist입니다. memtable은 동시 쓰기를 수용하는 동시에 읽기와 이후 flush를 위해 콘텐츠를 정렬된 키 순서로 반환해야 하므로 skiplist를 사용합니다.

skiplist는 모든 항목을 항상 정렬된 상태로 유지하면서 lock-free 동시 삽입을 지원합니다. 서류를 쌓아 두는 대신 들어오는 즉시 정리하는 것과 같은 데이터 구조입니다.

3단계: Memtable이 가득 참

memtable은 설정된 임곗값인 write_buffer_size에 도달할 때까지 커지며, 기본값은 64MB입니다. 임곗값에 도달하면 불변 상태로 표시되고 비어 있는 새 memtable로 교체됩니다. 들어오는 쓰기는 중단 없이 계속됩니다. 가득 찬 고정 상태의 memtable은 백그라운드에서 flush될 차례를 기다립니다.

쓰기는 flush 자체 때문에 차단되지 않습니다.

4단계: Flush

백그라운드 스레드는 불변 memtable을 트리의 레벨 0(L0)에 SST 파일로 기록합니다. skiplist는 이미 정렬되어 있으므로 flush는 항목을 순서대로 순회하며 기록하는 단일 순차 패스로 이루어집니다.

이제 memtable의 역할은 끝났으며, 해당 WAL 항목은 이후 폐기할 수 있습니다. 데이터는 이제 영구적이고 읽을 수 있는 형태로 디스크에 보존됩니다.

SST 파일 안에는 무엇이 있나요?

데이터는 남은 수명 동안 SST 파일에 머뭅니다. SST 파일은 세 가지 블록과 footer로 구성됩니다.

• 데이터 블록: 정렬된 항목 자체로, 각각 수 KB이며 개별적으로 압축됨
• 인덱스 블록: 키 범위를 블록 오프셋에 매핑해 조회 시 올바른 블록으로 바로 이동할 수 있게 함
• 선택적 bloom filter 블록: 다른 데이터를 읽지 않고도 ‘이 키는 이 파일에 확실히 없다’고 답할 수 있는 압축된 확률적 요약
• footer: 위의 모든 요소가 있는 위치를 나타냄

이 레이아웃의 모든 요소는 이후 읽기에서 접근하는 바이트 수를 최소화하기 위해 존재합니다. 특히 인덱스와 bloom filter가 중요합니다.

쓰기 경로 단계별 살펴보기

앞에서 설명한 모든 동작은 직접 관찰할 수 있습니다. 이 섹션에서는 RocksDB에 포함된 검사 도구인 ldb와 sst_dump를 사용해 하나의 Put이 데이터베이스를 통과하는 과정을 빠르게 추적합니다. 예제는 Rust와 rocksdb crate를 사용하지만, 어떤 바인딩을 사용해도 됩니다.

사전 준비

직접 따라 하려면 RocksDB 명령줄 도구와 Rust 툴체인을 설치하세요.

macOS에서는 brew install rocksdb로 ldb와 sst_dump를 모두 설치할 수 있습니다. Debian/Ubuntu에서는 rocksdb-tools 패키지를 사용합니다.

설치가 끝나면 새 프로젝트를 만드세요.

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

rocksdb crate는 첫 빌드 시 RocksDB C++ 라이브러리를 소스에서 컴파일하므로 첫 cargo run에는 몇 분이 걸릴 수 있습니다.

1단계: 쓰고 종료하기

src/main.rs의 내용을 다음 코드로 교체하세요.

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// Deliberately no flush. Let the process exit.
}

cargo run으로 한 번 실행한 뒤 생성된 데이터베이스 디렉터리를 나열하세요.

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

CURRENT와 MANIFEST 파일은 데이터베이스의 파일 목록을 추적하고, OPTIONS는 데이터베이스를 열 때 사용한 설정을 기록합니다. 번호가 없는 LOG는 디버깅을 위한 사람이 읽을 수 있는 텍스트 로그입니다. write-ahead log 자체인 000004.log와 혼동하지 마세요.

정확한 파일 번호는 실행할 때마다 달라지지만 구조는 동일합니다.

디렉터리에 .sst 파일이 하나도 없다는 점에 주목하세요. 프로세스가 종료된 후에도 유지되므로 쓰기는 영속적이지만, 아직 WAL 레코드로만 존재합니다. 영속성과 정리가 분리되어 작동하는 모습입니다.

2단계: WAL 덤프하기

ldb가 디렉터리에 있는 .log 파일을 가리키도록 하세요.

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

배치는 하나입니다. 시퀀스 번호는 1이고 1개의 레코드(29바이트)를 포함합니다. 이 레코드는 키 slot:0001이 16진수로 인코딩된 PUT입니다.

크기는 앞에서 살펴본 인코딩과 일치합니다. 12바이트 헤더와 17바이트 레코드로 구성되며, 레코드에는 타입 태그 하나, 길이 접두사 두 개, 9바이트 키, 5바이트 값이 포함됩니다.

3단계: Flush하고 SST 덤프하기

먼저 데이터베이스 디렉터리, 즉 rm -rf /tmp/lsm-trace를 삭제해 이번 실행을 깨끗한 상태에서 시작하세요.

put 다음에 main.rs에 한 줄을 추가하세요.

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

**db.flush().unwrap();**을 호출하면 memtable이 가득 찰 때까지 기다리지 않고 SST 파일로 기록됩니다.

파일을 다시 실행한 뒤 디렉터리를 나열하세요.

이제 출력에 새 .sst 파일이 나타납니다. 실제 파일 이름을 대입해 sst_dump의 유용한 두 모드로 검사할 수 있습니다.

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

sst_dump는 스캔 출력 전에 파일 형식에 관한 몇 줄의 서문을 출력합니다. 여기와 아래의 출력에서는 해당 부분을 생략했습니다.

이것이 새로운 영구 저장소에 자리 잡은 키-값 쌍입니다. 시퀀스 번호도 그대로 유지됩니다.

다음 명령어로 속성을 확인할 수 있습니다.

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

속성 출력에는 앞에서 살펴본 SST 구조가 항목별로 표시됩니다. 데이터 블록 수와 크기, 인덱스 블록 크기, 필터 존재 여부, 압축 알고리즘, 항목 수를 확인할 수 있습니다.

키가 하나뿐이지만, 한 가지 유용한 예외를 제외하면 모든 구조 요소가 항목별로 표시됩니다. RocksDB에서 bloom filter는 선택 사항이고 filter_policy로 설정하며 기본 옵션에는 지정되어 있지 않습니다. 따라서 필터 블록 크기는 0이고 필터 정책은 N/A입니다.

프로덕션 환경에서 거의 항상 bloom filter를 활성화하는 이유는 다음 글에서 다룹니다.

4단계: 다시 열고 로그 확인하기

put과 flush 줄을 주석 처리해 DB::open 줄만 남긴 뒤 다시 실행하세요. 이제 디렉터리를 나열하면 기존 000004.log가 사라지고 번호가 더 높은 새 로그가 생성된 것을 볼 수 있습니다. 이 로그는 거의 비어 있습니다. 기존 내용은 3단계에서 SST로 flush되었으므로 레코드는 더 이상 필요하지 않게 되었고, RocksDB는 다시 열 때 파일을 폐기했습니다.

이것이 WAL과 memtable의 전체 수명 주기가 연결되는 방식입니다.

한 단계 더 깊이 살펴보려면 Linux에서 1단계의 바이너리를 strace -e trace=write,fdatasync로 실행해 syscall 경계의 영속성 계약을 확인할 수 있습니다. 순차 write 호출은 .log 파일에 append하며, fdatasync는 WriteOptions.sync가 설정된 경우에만 나타납니다.

5단계: 키를 삭제하고 남은 데이터 확인하기

delete가 쓰기라는 앞의 설명도 직접 확인할 수 있습니다.

키를 삭제하고 다시 강제로 flush하도록 main.rs를 수정하세요.

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

실행한 뒤 디렉터리를 나열하세요.

이제 .sst 파일이 두 개 있습니다. 이전 파일은 불변이므로 수정되지 않았으며 여전히 키와 값을 포함합니다. 스캔으로 이를 확인할 수 있습니다.

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

이제 새 파일을 스캔하세요.

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

키는 같지만 시퀀스 번호가 더 높고, type:1이 아니라 type:0이며 값이 없습니다. 이것이 tombstone입니다. WriteBatch 섹션의 kTypeDeletion 레코드가 자체 SST로 flush된 것입니다. 이제 데이터베이스에는 값과 삭제 기록이 서로 다른 파일에 나란히 존재합니다.

키를 읽으면 tombstone이 우선되어 이 모순이 해소됩니다.

프로그램에 조회를 추가해 확인할 수 있습니다.

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

읽기 경로는 최신 데이터를 먼저 확인하고 시퀀스 번호 2가 시퀀스 번호 1보다 우선하므로 not found가 출력됩니다. 데이터베이스 관점에서는 값이 사라졌지만, 실제로는 여전히 이전 SST 파일의 디스크에 남아 있습니다.

아직 아무 공간도 회수되지 않았습니다. 삭제 사실만 기록되었을 뿐이며, compaction이 두 파일을 병합하고 tombstone과 가려진 값을 모두 제거할 때까지 tombstone이 값을 계속 가립니다.

6단계: 키를 삭제하고 남은 데이터 확인하기

Merge 레코드 타입도 관찰할 수 있습니다. RocksDB는 피연산자의 의미를 자체적으로 알 수 없으므로 merge operator를 설정해야 합니다.

데이터베이스 디렉터리를 다시 삭제하고 main.rs를 다음 코드로 교체하세요.

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

WAL을 덤프하면 세 개의 개별 MERGE 레코드가 표시됩니다. 즉, 한 번의 읽기 대신 세 번 append한 것입니다.

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

merge operator는 읽기 시점에 원시 바이트 결과와 함께 체인을 합쳤습니다. 51은 문자 3의 ASCII 코드이므로 프로그램은 **Some([51])**을 출력합니다. 다시 말해, 키와 값은 임의의 바이트 배열이기 때문입니다.

조회 전에 **db.flush().unwrap();**을 추가하고 디렉터리를 삭제한 뒤 프로그램을 다시 실행할 수도 있습니다. SST를 스캔하면 단일 레코드가 표시됩니다.

'counter' seq:3, type:2 => 3

flush가 operator를 적용하고 이들을 단일 피연산자로 합쳤습니다.

레벨 0은 왜 특별한가요?

새 SST 파일은 레벨 0에 저장됩니다. 각 파일은 memtable의 직접적인 스냅샷이며 해당 memtable이 수용한 키 범위를 그대로 포함합니다. 따라서 L0 파일은 서로 겹칠 수 있고 실제로 자주 겹칩니다. 더 깊은 레벨의 파일은 서로 겹치지 않는다는 점에서 다릅니다. 각 파일이 고유한 키 범위를 소유하므로 특정 키를 포함할 수 있는 파일은 레벨당 최대 하나입니다.

그 결과 모든 L0 파일은 키가 숨어 있을 수 있는 별도의 위치가 됩니다. 따라서 L0 파일 수는 읽기 성능에 직접적인 부담을 줍니다. RocksDB가 L0 파일 수를 면밀히 감시하고, 수가 너무 많아지면 쓰기를 제한하거나 아예 중단하는 이유입니다.

L0를 작게 유지하는 것은 compaction의 주요 작업 중 하나입니다.

쓰기에서 LSM 트리가 B-tree보다 뛰어난 이유는 무엇인가요?

B-tree는 읽을 때 모든 데이터를 정확한 위치에서 찾을 수 있도록 쓰기 시점에 정리 비용을 지불합니다. 반면 LSM 트리는 정리를 백그라운드 compaction으로 미루고 나중에 대량으로 처리합니다.

B-tree는 대부분의 전통적인 데이터베이스를 뒷받침하는 구조입니다. 데이터를 제자리에서 업데이트하므로 쓰기마다 키를 소유한 페이지를 찾아 읽고, 수정한 뒤 다시 기록합니다. 관련 페이지는 디스크 전체에 흩어져 있으므로 논리적으로 무작위인 쓰기 스트림이 물리적으로 무작위인 I/O 스트림으로 바뀝니다.

LSM 트리는 쓰기 시점에 이 비용을 지불하지 않습니다. WAL에 append하고, memtable에 버퍼링하며, flush로 배치 처리합니다. 모든 디스크 쓰기는 순차적이며 정리에 따른 부채는 compaction으로 미뤄집니다. 작업 자체가 사라지는 것은 아닙니다. 디스크가 매우 효율적으로 처리할 수 있는 형태로 통합해 나중에 대량으로 비용을 지불합니다.

SSD는 데이터를 제자리에서 덮어쓸 수 없으므로 이 차이는 특히 중요합니다.

플래시 스토리지는 수백 KB에서 수 MB에 이르는 큰 블록 단위로 지우고 더 작은 페이지 단위로 씁니다. 따라서 작은 무작위 덮어쓰기가 발생할 때마다 드라이브의 플래시 변환 계층(FTL)은 내부적으로 유효한 데이터를 이동하고 블록을 지워야 합니다.

B-tree의 무작위 페이지 쓰기는 FTL에 이 작업을 끊임없이 강제합니다. 장치에서 발생하는 쓰기 증폭이 데이터 구조 자체에서 발생하는 비용 위에 더해지며, 처리량과 드라이브 수명 모두에 영향을 줍니다. LSM 트리의 대규모 순차 쓰기는 플래시 하드웨어에 제공할 수 있는 거의 최적의 작업 형태입니다.

이를 대출로 생각하면 이해하기 쉽습니다. 미뤄 둔 정리 비용은 compaction I/O로 돌아오고, 읽기는 B-tree보다 더 많은 위치를 확인해야 합니다. 즉, LSM 트리는 지금 쓰기 처리량을 확보하고 나중에 읽기 증폭과 공간 증폭의 형태로 상환합니다.

읽기, 쓰기, 공간 증폭 측면에서 LSM 트리와 B-tree를 더 자세히 비교하려면 B-Tree와 LSM-Tree 비교를 참고하세요.

RocksDB가 충돌한 후에는 어떻게 되나요?

memtable은 휘발성 메모리이므로 충돌이 발생하면 지워집니다. 바로 이 때문에 WAL이 존재합니다.

재시작 시 RocksDB는 확인되었지만 아직 SST로 flush되지 않은 모든 쓰기를 재생합니다. 이들을 새 memtable에 삽입해 충돌 전 상태를 재구성합니다. 복구 비용은 flush되지 않은 데이터 양에 비례하므로 WAL과 memtable의 수명 주기가 연결되어 있습니다. memtable의 내용이 SST로 안전하게 flush되면 해당 로그 항목은 더 이상 필요하지 않으며 WAL을 잘라낼 수 있습니다.

로그 append가 저장되는 순간 쓰기는 영속성을 얻습니다. 이후 flush로 정리되면 저렴하게 읽을 수 있게 됩니다. B-tree는 이 두 과정을 결합하지만 LSM 트리는 분리합니다. LSM 구조의 특성 대부분은 이 분리에서 비롯됩니다.

Solana는 쓰기 경로에 어떤 부담을 주나요?

이 시리즈의 첫 번째 글에서는 Agave가 Solana 원장을 RocksDB에 저장하는 방식을 설명했습니다. 쓰기 경로 관점에서 이 워크로드는 쓰기 경로를 위해 특별히 설계된 스트레스 테스트에 가깝습니다. 원장 데이터의 원시 단위인 샤드는 네트워크를 통해 회선 속도로 계속 도착하며, 검증인의 스토리지 계층이 작업을 완료하려면 모든 샤드가 WAL append와 memtable 삽입 경로를 통과해야 합니다.

여기에 사용되는 메커니즘은 이 글에서 추적한 것과 정확히 같지만 프로덕션 규모로 작동합니다. 샤드가 도착하면 Agave의 Blockstore 삽입 경로는 들어온 샤드의 전체 배치를 검증하고, 누락된 샤드에 Reed-Solomon 복구를 시도한 뒤, 모든 데이터(샤드 페이로드, 슬롯 메타데이터, 소거 메타데이터, 인덱스 업데이트)를 하나의 RocksDB WriteBatch에 준비하고 단일 원자적 쓰기로 커밋합니다.

insert_data_shred를 단순화하면 다음과 같습니다.

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

이 주석은 Agave 엔지니어들이 이 글의 핵심을 아홉 단어로 표현한 것입니다. 배치는 원자성의 단위이며, 삽입 도중 검증인이 충돌해도 원장이 절반만 업데이트된 상태로 절대 남아서는 안 됩니다.

앞의 예제에서 추적한 항목 하나짜리 배치는 검증인 내부에서는 수천 개의 항목으로 구성된 배치가 됩니다. 여러 column family에 걸친 샤드와 메타데이터, 하나의 시퀀스 번호 범위, 하나의 WAL append, 하나의 그룹 커밋으로 구성됩니다.

다행히 샤드는 슬롯 번호로 시작하며, 단순화된 코드 스니펫의 (slot, index) 튜플이 ShredData 키입니다. 슬롯은 거의 단조롭게 증가합니다. 따라서 각 memtable은 키 공간에서 좁고 대부분 연속된 범위를 수용하며, flush로 생성된 L0 파일은 거의 겹치지 않습니다.

이 쓰기 경로의 영향은 Helius에서도 직접 체감합니다.

Helius에서 운영하는 아카이브 시스템은 Solana의 전체 트랜잭션 기록을 RocksDB에 수집합니다. 수백 TB 규모로 append가 많고 계속 성장하는 워크로드입니다. 이 아키텍처로 마이그레이션한 과정은 ClickHouse에서 RocksDB로 마이그레이션한 글에 정리되어 있습니다.

결론

LSM 트리는 하드웨어와 맺은 거래입니다. 데이터 정리 작업을 미루는 대신 모든 쓰기를 순차적으로 만듭니다. 따라서 읽기 경로는 B-tree보다 더 많은 위치에서 데이터를 찾아야 합니다. memtable은 데이터를 수용하고, WAL은 영속성을 보장하며, SST는 계속 쌓입니다. 무작위 덮어쓰기에 이중으로 불리한 플래시 스토리지에서는 매우 훌륭한 거래입니다.

하지만 쓰기는 쉬운 절반에 불과합니다. 이 설계의 비용은 읽기에서 발생합니다. 키의 현재 값이 memtable, L0 파일 또는 그 아래의 어느 레벨에든 존재할 수 있기 때문입니다. 이 비용을 제한하는 메커니즘에서 LSM 엔지니어링이 본격적으로 흥미로워집니다.

시리즈의 다음 글에서는 읽기 경로를 따라가며 memtable, bloom filter, 블록 캐시, 증폭 트라이앵글이 실제로 작동하는 방식을 다룹니다.

하나의 키-값 쌍이 서로 다른 네 가지 데이터 구조를 통과하는 과정을 추적하는 일이 즐겁게 느껴진다면 Helius와 함께 만들어 보세요. 이 시리즈에서 설명한 시스템은 Helius가 인터넷 자본 시장 규모로 배포하고 운영하며 최적화하는 시스템입니다. 현재 엔지니어링 팀 전반에서 인재를 채용하고 있습니다. helius.dev/careers에서 모든 채용 공고를 확인하세요.