BigQuery 시리즈를 마치고 다시 데이터 엔지니어링 시리즈로 돌아왔습니다. Row vs Column 편에서 InnoDB가 페이지를 B+ Tree로 관리한다고 한 문단으로 지나갔는데, 이번 글은 그 한 문단을 풉니다. B-tree가 어떻게 쓰고 왜 쓰기가 비싼지, 그것을 뒤집은 LSM 트리는 무엇을 내주고 무엇을 얻었는지를 봅니다.
1. 문제는 랜덤 쓰기다
1-1. B+ tree는 제자리에서 고친다
MySQL InnoDB와 PostgreSQL은 둘 다 B+ tree를 씁니다. Row vs Column 편에서 InnoDB가 16KB 페이지 안에 행을 담고 페이지들을 B+ tree로 엮는다고 했는데, InnoDB는 테이블 자체가 클러스터드 B+ tree이고 PostgreSQL은 테이블은 heap이되 인덱스가 B+ tree입니다. PostgreSQL도 페이지(8KB) 단위로 읽고 쓰는 점은 같습니다.
핵심은 페이지가 I/O의 단위라는 점입니다. InnoDB 용어집 정의 그대로, 페이지는 InnoDB가 다루는 기본 I/O 단위입니다. 행 하나를 고치면 그 행이 든 페이지 한 장을 통째로 읽어 메모리에서 바꾸고, 다시 한 장을 통째로 씁니다. 여기에 안전장치가 하나 더 붙습니다. PostgreSQL은 체크포인트 이후 페이지를 처음 건드릴 때 페이지 전체를 WAL에 한 번 더 기록하고(full_page_writes), InnoDB는 데이터 파일에 쓰기 전에 doublewrite buffer에 먼저 씁니다.
즉 수십 바이트짜리 행 하나를 UPDATE해도 디스크에는 페이지 한 장에 로그 이미지까지, 수십 KB가 나갑니다. 이것을 write amplification이라고 부릅니다. 쓴 데이터 대비 실제로 디스크에 나간 바이트의 비율입니다.
1-2. 페이지는 반쯤 비어 있다
B+ tree는 정렬을 유지해야 하니 새 키가 들어갈 자리가 정해져 있습니다. 그 페이지가 꽉 차 있으면 둘로 쪼갭니다(split). InnoDB 문서에 따르면 순차 삽입이면 페이지의 1/16을 비워 두고, 랜덤 순서로 삽입되면 페이지가 1/2에서 15/16 사이로 찹니다.
랜덤 쓰기가 B-tree에 불리한 이유가 여기 세 겹으로 있습니다. 매 쓰기가 페이지 단위 I/O이고, 그 쓰기가 트리 여기저기 흩어져 순차 I/O가 안 되며, 쪼개진 페이지들이 공간을 남깁니다.
2. LSM은 고치지 않고 덧붙인다
2-1. 1996년 논문이 푼 문제
LSM 트리는 O'Neil 외 3인이 1996년 Acta Informatica에 발표한 구조입니다. 논문 초록이 문제를 짚습니다. B-tree 같은 디스크 기반 인덱스는 트랜잭션의 I/O 비용을 사실상 두 배로 만든다는 것, 그리고 LSM은 인덱스 변경을 미뤄서 모아 두었다가 메모리 컴포넌트에서 디스크 컴포넌트로 머지 소트 방식으로 흘려보낸다는 것입니다.
논문은 한계도 명시합니다. 즉시 응답이 필요한 조회는 경우에 따라 I/O 효율을 잃는다고 적었고, 조회보다 삽입이 많은 워크로드에 가장 유용하다고 했습니다. 30년 뒤 '쓰기에 강하고 읽기에 약하다'는 통념이 여기서 나왔습니다.
논문 원문의 구성은 메모리의 C0와 디스크의 C1, 그리고 둘 사이의 rolling merge입니다. 지금 널리 쓰는 memtable, SSTable 같은 용어는 Bigtable 논문(2006)에서 왔고 LevelDB와 RocksDB가 대중화한 이름입니다.
2-2. memtable에서 SSTable까지
RocksDB 기준으로 쓰기 경로는 memtable → SSTable → compaction 순입니다.
쓰기 요청
→ WAL에 append (내구성)
→ memtable에 삽입 (메모리, 정렬 유지)
memtable이 차면
→ immutable memtable로 전환, 새 memtable 생성
→ 백그라운드 스레드가 immutable memtable을 디스크로 flush
→ Level-0 (L0)의 SSTable 파일 하나가 됨
L0 파일이 쌓이면
→ compaction: L0 파일들을 L1과 병합
→ L1이 차면 L2로, ... Lmax까지쓰기 관점에서 보면 디스크에 나가는 것은 전부 순차 append입니다. WAL도 append, flush도 새 파일 생성, compaction도 새 파일 생성입니다. 기존 파일을 제자리에서 고치는 일이 없습니다. HBase 문서는 데이터를 제자리에서 수정하지 않는다고 한 줄로 적습니다.
SSTable은 Sorted String Table의 약자로, 키 순으로 정렬된 불변 파일입니다. 한 번 쓰면 안 바뀌고, 지워질 때는 compaction이 새 파일을 만든 뒤 통째로 삭제됩니다.
2-3. 삭제도 덧붙인다
제자리 수정이 없으니 삭제도 덧붙이는 식입니다. 키를 지우면 그 키에 tombstone(삭제 표식)을 새로 씁니다. 읽을 때 tombstone을 만나면 아래 레벨에 남아 있는 옛 값을 무시합니다.
실제 삭제는 compaction 때 일어납니다. LevelDB 구현 문서 기준으로, compaction은 덮어쓰인 값을 버리고, 상위 레벨에 그 키 범위를 덮는 파일이 없을 때 tombstone도 버립니다. Cassandra는 여기에 유예 기간을 둡니다. gc_grace_seconds 기본값 864,000초(10일)가 지나야 compaction이 tombstone을 치웁니다. 노드 간 복제가 덜 끝난 상태에서 tombstone을 지우면 죽은 데이터가 되살아나기 때문입니다. 유예 기간보다 오래 다운됐던 노드가 복귀하면서 옛 값을 최신으로 다시 퍼뜨리는 현상이라, zombie data 또는 data resurrection이라고 부릅니다.
3. 대가는 세 가지 증폭이다
LSM이 쓰기를 순차 append로 바꾼 대가는 세 가지 증폭으로 돌아옵니다. RocksDB Tuning Guide의 정의를 따릅니다.
3-1. Write amplification
compaction이 같은 데이터를 레벨마다 다시 씁니다. Tuning Guide의 leveled compaction 예시가 이렇습니다.
memtable → L0 flush : 1배
L0 → L1 : 2배 (L1 크기가 L0와 같아서)
L1 → L2 : 10배
L2 → L3 : 10배
L3 → L4 : 10배
─────────────────────────────
합계 : 약 33배이 수치는 Tuning Guide의 예시 설정(L1 512MB, 레벨 비율 10, DB 500GB로 4레벨) 기준입니다. 레벨 수와 max_bytes_for_level_base, dynamic level size 여부에 따라 달라집니다. 10배가 나오는 이유는 레벨 간 크기 비율입니다. max_bytes_for_level_multiplier 기본값이 10이라, L1의 파일 하나를 L2로 내리면 L2에서 겹치는 파일이 대략 10개라서 그만큼 다시 씁니다.
B-tree의 페이지 단위 증폭과 종류가 다릅니다. B-tree는 쓰기 한 번마다 즉시 페이지 한 장이 나가고, LSM은 쓰기 자체는 작지만 나중에 compaction이 여러 번 다시 씁니다. 총량으로는 LSM이 더 쓸 수도 있는데, 전부 순차 I/O라 디스크 입장에서는 훨씬 쌉니다.
3-2. Read amplification
키 하나를 찾으려면 memtable을 보고, L0의 파일들을 보고(L0는 파일끼리 키 범위가 겹칩니다), L1, L2를 차례로 봅니다. 읽기 한 번에 여러 파일을 뒤지는 것이 read amplification입니다.
이것이 LSM에서 Bloom filter가 선택이 아니라 필수인 이유입니다. SSTable마다 Bloom filter를 두면 그 파일에 키가 없다는 것을 디스크를 안 읽고 알 수 있습니다. RocksDB에서 Bloom filter를 켜면 기본이 키당 10비트로, 오탐률 약 1%입니다. Bloom filter 자체는 뒤에 따로 한 편으로 다룹니다.
3-3. Space amplification
Space amplification은 compaction이 끝나기 전까지 같은 키의 옛 버전이 여러 레벨에 남아 있는 것입니다. leveled compaction은 이것을 잘 억제해서 레벨 비율 10 기준 최악 약 1.11배(Facebook의 CIDR 2017 논문 계산)이고, universal compaction은 compaction 도중 디스크 사용량이 일시적으로 두 배가 됩니다.
3-4. Leveled와 universal
RocksDB의 주력 compaction 전략은 leveled와 universal 둘이고(TTL 캐시용 FIFO는 별도), 셋 중 무엇을 아낄지가 갈립니다.
Universal 문서에는 write amplification을 낮추는 대신 read와 space amplification을 내준다고 적혀 있습니다. 쓰기가 압도적인 로그성 워크로드면 universal, 읽기가 섞이면 leveled가 출발점입니다.
4. 읽기 경로와 범위 스캔
읽기는 위에서 아래로 내려갑니다. memtable에 있으면 거기서 끝이고, 없으면 block cache, 그다음 각 SSTable의 Bloom filter, 그다음에야 디스크입니다. 논문의 표현으로는 C0를 먼저 보고 C1을 보는 것이고, LevelDB 구현 문서로는 memtable은 모든 읽기에서 참조된다는 것입니다.
점 조회는 이 구조로 감당이 됩니다. Bloom filter가 대부분의 파일을 건너뛰게 해 주기 때문입니다. 문제는 범위 스캔입니다. RocksDB Overview에도 대부분의 LSM 엔진은 효율적인 범위 스캔을 지원하기 어렵다고 적혀 있습니다. WHERE id BETWEEN 100 AND 200은 Bloom filter가 도움이 안 됩니다. Bloom filter는 특정 키 하나의 유무만 답하는 구조라 범위 조건에는 쓸 수 없고, 범위 스캔은 memtable부터 마지막 레벨까지 모든 SSTable을 병합 이터레이터로 합쳐 읽어야 합니다. RocksDB는 키 접두사 단위의 prefix bloom filter로 접두사 범위 스캔은 보완하지만, 임의 범위에는 해당하지 않습니다.
B+ tree는 반대입니다. 리프 노드끼리 옆으로 연결돼 있어서(PostgreSQL nbtree의 right-sibling link) 시작점만 찾으면 그대로 옆으로 읽어 나갑니다. 'B-tree는 읽기에 강하다'는 말은 범위 스캔에 강하다는 뜻입니다.
5. 통념이 깨지는 곳
5-1. 쓰기가 항상 빠르지는 않다
flush나 compaction이 쓰기 속도를 못 따라가면 RocksDB는 쓰기를 늦추거나 멈춥니다. Write stall입니다. 기본값으로 L0 파일이 20개면 쓰기가 느려지고 36개면 멈춥니다. compaction 대기 바이트가 64GB를 넘으면 느려지고 256GB면 멈춥니다. memtable도 max_write_buffer_number 기본 2개까지만 쌓입니다.
쓰기가 빠른 것은 백그라운드가 따라올 때까지입니다. 버스트가 compaction 처리량을 넘는 순간 LSM은 B-tree보다 느려질 수 있고, 그 시점을 미리 알기 어렵습니다.
5-2. 읽기가 항상 빠르지도 않다
범위 스캔은 앞에서 봤듯 B-tree 우위입니다. 점 조회는 다릅니다. B-tree도 루트에서 리프까지 내려가야 하고, 상위 노드가 메모리에 있다는 전제(논문도 C1의 상위 디렉토리 노드는 메모리 상주를 기대한다고 씁니다)가 깨지면 그 자체로 디스크 I/O입니다. LSM은 Bloom filter가 있으면 점 조회에서 밀리지 않습니다.
5-3. SSD에서도 차이는 남는다
랜덤 I/O 페널티가 SSD에서 줄어드니 B-tree의 약점이 사라진다는 주장입니다. Facebook의 CIDR 2017 논문이 이 질문을 다룹니다. SSD에서는 오히려 공간이 문제입니다. B-tree 페이지는 1/2에서 2/3만 차서 space amplification이 1.5배를 넘습니다. Facebook 프로덕션 관찰로는 RocksDB가 InnoDB 대비 저장 공간 약 절반, 쓰기량 10~15%였고, LinkBench 벤치마크에서도 저장 공간 절반 미만, 트랜잭션당 쓰기량 20% 미만이었습니다. SSD는 쓰기 횟수가 수명이라 쓰기량 차이가 곧 비용 차이입니다.
다만 공간과 쓰기량 비교입니다. 지연 시간 비교는 아니고, 그쪽은 워크로드에 따라 갈립니다.
6. 이미 쓰고 있는 LSM
어느 쪽인지 헷갈리는 시스템들을 정리하면 이렇습니다.
전부 공식 문서에 명시된 것들입니다. Cassandra는 LSM 트리 기반이라고, HBase는 LSM이 HBase의 설계 기반 패턴이라고, CockroachDB는 Pebble이 LSM을 쓴다고 적습니다.
이 시리즈와 BigQuery 시리즈에서 본 것 중에도 닮은꼴이 있습니다. Iceberg는 데이터 파일이 불변이고 삭제를 별도 delete file로 기록해 읽을 때 적용합니다. BigQuery CDC는 스트리밍 버퍼(쓰기 최적화 저장소)에 받아 두고 background apply로 base에 병합하며, 그 전에 조회가 오면 runtime merge를 합니다. 쓰기는 덧붙이고 읽기는 병합한다는 뼈대가 같습니다.
Iceberg 스펙에는 레벨도 자동 compaction도 없고(rewriteDataFiles는 외부에서 돌리는 유지보수 작업입니다), Google은 CDC 문서에서 LSM이나 memtable이라는 말을 쓰지 않습니다. 구조가 닮았다는 것이지 LSM을 구현했다는 뜻은 아닙니다.
마무리
B-tree와 LSM의 차이는 결국 쓰기를 제자리에서 할 것인가 덧붙일 것인가로 수렴합니다. 제자리 수정은 읽기 경로가 하나라 단순하고 범위 스캔이 빠른 대신 쓰기마다 페이지 한 장이 나가고, 덧붙이기는 쓰기가 순차 I/O가 되는 대신 읽기가 여러 파일을 뒤지고 compaction이 뒤에서 계속 돕니다. 어느 쪽이 맞는지는 쓰기와 읽기의 비율, 점 조회와 범위 스캔의 비율이 정합니다.
다음 글에서는 두 테이블을 붙이는 방법을 알아보겠습니다. Hash join, Sort-merge join, Nested loop join이 노드 안에서 실제로 어떻게 매칭하는지, 메모리가 모자랄 때 무슨 일이 나는지까지 뜯어보겠습니다.