데이터베이스 storage engine 은 어떻게 동작할까?

같은 데이터를 어떤 DB 는 초당 수십만 write 를 받아내고, 다른 DB 는 같은 부하에서 디스크가 비명을 지른다. 차이는 storage engine — row 를 디스크에 어떻게 박고 어떻게 다시 꺼내오는지 의 설계다. 세상의 storage engine 은 크게 둘로 갈린다. 제자리에 고쳐쓰는 B-tree engine (Postgres / InnoDB / SQLite) 과, 일단 append 하고 나중에 정리하는 LSM-tree engine (RocksDB / Cassandra / LevelDB). 이 가이드는 page · WAL · buffer pool 부터 두 engine 의 read/write/space amplification trade-off 까지, "어떤 워크로드에 뭘 고를까" 를 정리한다.

모든 것은 page 에서 시작한다

DB 는 row 를 한 개씩 디스크에 쓰지 않는다. 고정 크기 블록인 page 단위로 읽고 쓴다. 디스크 I/O 의 최소 단위가 page 이기 때문:

PostgreSQL  : 8KB page (default)
MySQL InnoDB: 16KB page
SQLite      : 4KB page (default)
SQL Server  : 8KB page

heap file = page 의 배열
┌────────┬────────┬────────┬────────┐
│ page 0 │ page 1 │ page 2 │ page 3 │ ...
└────────┴────────┴────────┴────────┘
  ↑ 각 page 안에 여러 row + page header + 빈 공간

한 row 가 100 byte 라도, 그 row 를 읽으려면 그 row 가 든 page 전체(8KB) 를 읽어야 한다. 그래서 "row 1 개 read" 가 사실은 "page 1 개 read" 다. 어떤 row 들을 같은 page 에 모으느냐가 성능을 가른다 (관련: how-database-indexes-work 의 covering index 가 같은 page 지역성을 노린다).

buffer pool — 디스크 I/O 가 지배한다

메모리 read 는 ~100ns, SSD random read 는 ~100µs (1,000 배), HDD seek 는 ~10ms (100,000 배). 그래서 DB 의 1 순위 목표는 디스크를 안 건드리는 것:

SELECT * FROM users WHERE id = 42;

1. id=42 가 든 page 가 buffer pool(메모리)에 있나?
   └ 있음(cache hit)  → 메모리에서 즉시 반환 (~100ns)
   └ 없음(cache miss) → 디스크에서 page read → buffer pool 적재 (~100µs)

buffer pool = 최근 쓴 page 를 메모리에 캐시 (LRU 비슷한 정책)
- PostgreSQL: shared_buffers
- MySQL InnoDB: innodb_buffer_pool_size (보통 RAM 의 50-75%)

OLTP DB 를 튜닝할 때 buffer pool hit rate 가 99% 를 넘는지 보는 이유가 이것. 1% 의 miss 가 1,000 배 느린 디스크 접근을 부른다. OS 의 page cache (관련: how-filesystems-work) 가 그 아래 한 겹 더 있다.

write path 와 durability — WAL

문제: write 를 즉시 디스크의 제자리에 박으면 느리고(random I/O), 쓰는 도중 크래시하면 page 가 반쯤 망가진다(torn page). 해결이 Write-Ahead Log (WAL, redo log):

UPDATE accounts SET balance = balance - 100 WHERE id = 7;

1. 변경 내용을 WAL 에 append (디스크 끝에 순차 write — 빠름)
2. WAL 을 fsync → "이 변경은 영구히 기록됨" 보장
3. 클라이언트에 COMMIT OK 응답  ← 여기서 durable
4. 실제 data page(buffer pool)는 메모리에서만 수정 (dirty page)
5. 나중에 checkpoint 가 dirty page 를 디스크 제자리에 flush

핵심: 디스크 제자리 write 는 천천히 묶어서. durability 는 WAL 의
순차 append + fsync 가 책임진다.

왜 빠른가 — random write (제자리 page 수정) 대신 sequential write (로그 끝에 append). 디스크는 순차 write 가 random 보다 훨씬 빠르다(특히 HDD, SSD 도 마찬가지).

왜 durable 한가 — fsync 가 OS 버퍼를 비워 데이터가 물리적으로 디스크에 닿았음을 보장한다. 크래시 후 재시작하면 WAL 을 처음부터 다시 적용(replay)해서 commit 됐지만 아직 제자리에 안 박힌 변경을 복구한다.

checkpoint 와 fsync

checkpoint — 일정 주기/WAL 크기마다 dirty page 를 데이터 파일 제자리에 flush. 그 시점 이전의 WAL 은 버려도 됨(복구에 불필요).
fsync 비용 — fsync 는 디스크 왕복이라 비싸다. 그래서 여러 트랜잭션을 모아 한 번에 fsync 하는 group commit 으로 throughput 을 올린다.
durability 완화 — Postgres synchronous_commit = off, MySQL innodb_flush_log_at_trx_commit = 2 는 fsync 를 느슨하게 해서 빠르지만, 크래시 시 최근 몇 ms 의 commit 을 잃을 수 있다. trade-off 다.

B-tree storage engine — 제자리 갱신

Postgres / MySQL InnoDB / SQLite 가 쓰는 방식. 데이터(또는 clustered index)를 정렬된 B-tree page 로 유지하고, write 는 해당 page 를 제자리에서 수정(update-in-place)한다:

INSERT INTO users (id, ...) VALUES (55, ...);

           [30 | 70]            ← internal page
          /    |    \
    [10|20] [40|50|60] [80|90]  ← leaf page (정렬된 row)
                ↑
   55 는 [40|50|60] leaf 에 들어가야 함 → 그 page read → 55 삽입

문제: page 가 꽉 차면?
[40|50|55|60] 에 더 못 넣음 → PAGE SPLIT
[40|50]  [55|60]  으로 둘로 쪼갬 + 부모 page 에 새 pointer 추가

page split 과 write amplification — row 하나 삽입이 page 분할을 일으키면 여러 page 를 다시 쓴다. 게다가 정렬 순서가 random (예: UUID v4 PK) 이면 split 이 자주 일어나 디스크가 파편화된다 (관련: how-database-indexes-work 의 UUID fragmentation).

강점 — 정렬 상태 유지라 range scan (BETWEEN, ORDER BY) 이 효율적. read 가 보통 1 번의 tree 탐색 + page fetch 로 끝난다 (read amplification 낮음). read-heavy OLTP 의 표준.
약점 — write 가 random I/O + page split. 매우 write-heavy 한 ingest 워크로드에선 부담.

LSM-tree storage engine — append 후 정리

RocksDB / Cassandra / LevelDB / ScyllaDB / HBase 가 쓰는 방식. 제자리 수정을 포기하고, 모든 write 를 메모리에 모았다가 정렬된 파일로 쏟아낸 뒤 백그라운드에서 병합한다:

write:
1. WAL 에 append (durability) + memtable(메모리, 정렬된 구조)에 삽입
2. memtable 이 임계치(예: 64MB) 차면 → 디스크에 SSTable 로 flush
   (SSTable = Sorted String Table, 정렬된 immutable 파일)
3. memtable 은 새로 비우고 계속 받음

디스크에는 SSTable 이 여러 개 쌓인다:
[memtable] (메모리, 최신)
   ↓ flush
[SSTable-4] [SSTable-3] [SSTable-2] [SSTable-1]  (오래된 순)

핵심: write 는 전부 메모리 삽입 + 순차 append. 제자리 수정·random
I/O 가 없다 → write throughput 압도적.

update/delete 도 append:
- UPDATE = 같은 key 의 새 버전을 append (옛 버전은 그냥 남음)
- DELETE = "tombstone" 마커를 append

LSM read path — memtable + SSTable + bloom filter

write 가 싼 대신 read 가 비싸다. 같은 key 가 memtable 에도, 여러 SSTable 에도 흩어져 있을 수 있어 최신 버전을 찾으려면 여러 곳을 봐야 한다:

GET key="user:42"

1. memtable 확인 (최신) → 있으면 반환
2. 없으면 SSTable 을 최신→오래된 순으로 검색
   SSTable-4 → SSTable-3 → SSTable-2 → ...

문제: SSTable 이 10 개면 read 1 번에 디스크 접근 10 번?
→ read amplification

해결: BLOOM FILTER
- 각 SSTable 마다 작은 메모리 bloom filter
- "이 key 가 이 SSTable 에 절대 없다" 를 빠르게 판정 (false positive 만,
  false negative 없음)
- 없다고 나오면 그 SSTable 의 디스크 read 를 통째로 건너뜀
→ 대부분의 불필요한 디스크 접근 제거

그래도 SSTable 이 무한정 쌓이면 read 가 점점 느려지고 디스크도 낭비된다(삭제된 row 의 tombstone, 갱신된 row 의 옛 버전이 계속 남는다). 그래서 compaction 이 필요하다.

compaction — LSM 의 심장

백그라운드 스레드가 여러 SSTable 을 읽어 병합하면서 같은 key 의 옛 버전과 tombstone 을 버리고, 더 적은 수의 큰 SSTable 로 다시 쓴다. 병합 전략이 두 갈래:

SIZE-TIERED (Cassandra default, write 친화)
- 비슷한 크기의 SSTable 이 N 개 모이면 합쳐 더 큰 SSTable 하나로
- write/compaction 부담 낮음
- 단점: 같은 key 가 여러 tier 에 → read & space amplification 높음

LEVELED (RocksDB/LevelDB default, read 친화)
- L0, L1, L2 ... 레벨 구조. 각 레벨은 이전의 ~10 배 크기
- 한 레벨 안에서는 SSTable 끼리 key range 가 겹치지 않음
  → 한 key 는 레벨당 최대 1 개 SSTable 에만 존재
- read amplification 낮음 (레벨 수만큼만 봄)
- 단점: 병합을 자주/넓게 해야 해서 write amplification 높음

compaction 은 공짜가 아니다 — 디스크 I/O 와 CPU 를 먹고, 잘못 튜닝하면 foreground write 와 자원을 다툰다(write stall). LSM 운영의 절반이 compaction 튜닝이다.

세 가지 amplification

storage engine 을 평가하는 세 축. 셋을 동시에 최소화할 수 없고, 하나를 줄이면 다른 하나가 늘어난다:

write amplification — 논리적 1 byte write 가 실제 디스크에 몇 byte 를 쓰게 하는가. B-tree: page split + 제자리 page 재기록. LSM: compaction 이 같은 데이터를 레벨마다 다시 씀(특히 leveled).
read amplification — 논리적 read 1 번이 디스크 page 를 몇 번 읽는가. B-tree: 보통 낮음(tree depth ≈ 3). LSM: 여러 SSTable + bloom filter 확인으로 더 높음.
space amplification — 실제 데이터 대비 디스크 가 몇 배 차지하는가. B-tree: 제자리 갱신이라 낮은 편(단, fragmentation/fill factor). LSM: 옛 버전·tombstone 이 compaction 전까지 남아 더 높을 수 있음(size-tiered 가 특히).

대략적 경향 (절대적이지 않음):

                write amp   read amp   space amp
B-tree            중간        낮음        낮음
LSM (leveled)     높음        중간        중간
LSM (size-tiered) 낮음        높음        높음

어떤 engine 을 고를까

write-heavy ingest → LSM — 시계열, 로그, IoT, 메시지/이벤트 적재, 대량 INSERT. 순차 append 라 write throughput 이 압도적. Cassandra / RocksDB / ScyllaDB.
read-heavy + range query OLTP → B-tree — 일반 웹/앱 백엔드, 트랜잭션, ORDER BY / BETWEEN 많은 조회, 낮은 read latency 가 중요할 때. PostgreSQL / MySQL InnoDB.
둘 다 필요 — MySQL 은 MyRocks(InnoDB 자리에 RocksDB)로, Postgres 는 워크로드 분리로 대응하기도 한다. RocksDB 는 임베디드 storage engine 으로 여러 DB 의 하부 엔진이다.

대조: column-oriented storage (OLAP)

지금까지는 row 단위로 저장하는 row-oriented (OLTP) engine 이었다. 분석(OLAP)은 반대로 column-oriented 로 저장한다:

row store (한 row 의 모든 column 을 붙여서):
[id=1,name=Kim,age=30][id=2,name=Lee,age=25] ...
→ "이 user 의 모든 필드" 가 한 page 에. OLTP 에 유리.

column store (같은 column 의 값을 붙여서):
id:   [1, 2, 3, ...]
name: [Kim, Lee, Park, ...]
age:  [30, 25, 41, ...]
→ "모든 user 의 age 평균" 같은 집계는 age 컬럼만 통째로 read.
   필요 없는 컬럼은 디스크조차 안 건드림 + 같은 타입이라 압축률 ↑

예: ClickHouse, DuckDB, Parquet, Redshift, BigQuery, Snowflake

SELECT 가 몇 컬럼만 보고 row 수백만을 집계하는 분석 쿼리에선 column store 가 row store 를 압도한다. 반대로 "한 row 의 전체 필드를 읽고 쓰는" OLTP 에선 row store 가 유리하다. 워크로드가 용도를 가른다.

실전 정리

디스크 I/O 단위는 row 가 아니라 page(보통 4-16KB). buffer pool hit rate 가 OLTP 성능을 지배한다.
WAL 이 durability + 빠른 write 를 동시에 준다 — 순차 append + fsync 후 commit, 제자리 flush 는 checkpoint 가 천천히.
B-tree = 제자리 갱신, 낮은 read/space amp, range scan 강함 → read-heavy OLTP (Postgres / InnoDB).
LSM-tree = memtable → SSTable → compaction, 낮은 write amp, 높은 write throughput → write-heavy ingest (RocksDB / Cassandra).
LSM read 는 bloom filter 로 불필요한 SSTable 접근을 거른다. compaction 은 leveled(read 친화) vs size-tiered(write 친화).
write / read / space amplification 은 셋 다 최소화 불가 — engine 선택은 이 trade-off 를 워크로드에 맞추는 것.
분석(OLAP)은 column store — 필요한 컬럼만 읽고 압축률이 높다. row store(OLTP)와 용도가 다르다.