Kim.C.J.

[데이터 중심 애플리케이션 설계] 03장 디테일

book-cover

[DDIA] 3장 디테일. 저장소와 검색 (Storage and Retrieval)

이 글은 3장 요약 글의 확장판(디테일 편) 이다.
요약에서는 큰 흐름(로그 구조 저장, B-Tree vs LSM, OLTP vs OLAP, 컬럼 지향)을 잡았다면, 여기서는 “저장 엔진이 실제로 부딪히는 디테일”을 파고든다.

  • “append-only”는 왜 빠르고, 왜 결국 컴팩션이 필수인가?
  • 해시 인덱스는 왜 RAM 병목이 되며, 재시작 때 무엇이 문제인가?
  • 컴팩션은 어떻게 동작하고, 왜 밀리면 성능이 무너지는가?
  • SSTable/LSM은 어떤 장치(Bloom filter, sparse index)로 읽기 비용을 줄이는가?
  • B-Tree는 overwrite 기반인데, 왜 WAL 없이는 버틸 수 없는가?
  • 증폭(amplification)은 왜 “비용” 그 자체인가?
  • 컬럼 지향 저장은 왜 분석(OLAP)에서 강한가?

구현 디테일은 DB마다 다르지만(예: MySQL/InnoDB, PostgreSQL, RocksDB/LevelDB), 여기서는 DDIA가 강조하는 공통 원리를 중심으로 정리한다.

0. 저장 엔진을 이해할 때 “디테일”이 중요한 이유

저장 엔진은 단순히 “어떤 인덱스(B-Tree/LSM)를 쓴다”에서 끝나지 않는다.
같은 인덱스라도 다음 선택이 성능과 운영 난이도를 결정한다.

  • I/O 패턴: 순차 쓰기 vs 랜덤 쓰기
  • 레코드 포맷: 길이/체크섬/바이너리 인코딩 여부
  • 복구 설계: WAL, 체크포인트, fsync 타이밍
  • 백그라운드 작업: 컴팩션/머지/GC가 밀릴 때의 폭발 반경
  • 증폭: 논리 I/O 1회가 실제 디스크 I/O 몇 회로 “증식”되는가?

요약하면, “인덱스가 무엇인가”보다 “그 인덱스를 어떤 규칙으로 운영하는가”가 더 실전적이다.

1. append-only 로그: 왜 빠른데, 왜 곧 한계가 오는가?

1.1 append-only가 빠른 이유(직관)

  • 파일 끝에 계속 추가하면 저장 장치 입장에서 예측 가능한 쓰기 흐름이 된다.
  • overwrite(제자리 수정)는 페이지/블록 단위의 랜덤 업데이트가 섞이기 쉬워 비용이 증가한다.

append-only는 “쓰기 비용을 지금이 아니라 나중에” 내는 전략에 가깝다.

1.2 append-only의 부작용: “읽기 모델”이 달라진다

append-only에서 업데이트는 “수정”이 아니라 “새 레코드 추가”다.

  • 같은 key가 여러 번 등장한다(중복 누적).
  • 최신 값을 빠르게 찾으려면 결국 “최신 위치를 가리키는 구조(인덱스)”가 필요하다.
  • 오래된 중복을 치우지 않으면 파일은 계속 비대해진다 → 컴팩션이 필수.

2. 레코드 포맷 디테일: 로그는 “대충 쓰면” 복구가 지옥이 된다

단순히 key=value\n 같은 텍스트는 구현은 쉽지만, 실제 저장 엔진에서는 위험하다.

  • 크래시로 레코드가 반쯤만 기록될 수 있다.
  • 파일 일부 손상 시 어디까지 정상인지 판단이 어렵다.
  • 파싱 비용이 크고(문자열 처리), 랜덤 접근도 비효율적이다.

그래서 흔히 아래 요소를 포함한 포맷을 쓴다.

  • length-prefix: 레코드 길이를 앞에 둬서 다음 레코드로 점프 가능
  • checksum: 레코드 단위 손상 감지
  • binary encoding: key/value를 바이너리로 직렬화

개념 예시는 아래처럼 생각하면 된다.

| record_length | checksum | key_length | key_bytes | value_length | value_bytes |

이 포맷이면,

  • 순차 스캔이 빠르고,
  • 손상된 레코드를 감지해 “그 구간만 건너뛰는” 복구 전략도 가능해진다.

3. 해시 인덱스(로그 구조 + key→offset): “RAM이 곧 한계”가 된다

3.1 구조

  • 데이터는 append-only 로그에 저장
  • 인덱스는 해시맵: key -> 최신 레코드 오프셋

쓰기:

  1. 로그 append
  2. 해시맵에서 key의 오프셋 갱신

읽기:

  1. 해시맵으로 오프셋 조회
  2. 해당 위치에서 레코드 읽기

3.2 현실적인 병목 1: 인덱스가 메모리를 먹는다

해시 인덱스의 강점(빠른 조회)은 곧 약점이 된다.

  • key 수가 늘수록 해시맵이 RAM을 크게 점유한다.
  • 결국 “값은 디스크에 있는데 인덱스가 메모리 병목”이 될 수 있다.

3.3 현실적인 병목 2: 재시작 시 인덱스 복구

인메모리 해시맵은 재시작하면 사라진다. 복구 방식은 보통 두 가지다.

(1) 로그 전체 스캔

  • 파일을 앞에서부터 읽으며 각 key의 “마지막 등장 위치”로 해시맵을 재구성
  • 데이터가 크면 재시작이 느려진다.

(2) 스냅샷/체크포인트 + 이후 로그 재생

  • 주기적으로 해시맵(또는 메타데이터)을 디스크에 저장
  • 재시작 시 스냅샷 로드 후, 스냅샷 이후의 로그만 반영
  • 복구 시간을 크게 줄일 수 있다.

3.4 근본 한계: 범위 질의(range query)

해시 인덱스는 정렬 정보가 없어서 다음이 약하다.

  • BETWEEN, ORDER BY, prefix 검색
  • “키 순서대로 스캔”이 필요한 질의

이 지점에서 B-Tree나 LSM 같은 “정렬 기반” 인덱스 구조가 등장한다.

4. 컴팩션(Compaction): 진짜는 “병합(merge) + 최신값만 남기기”다

컴팩션은 로그 구조 저장에서 GC(가비지 컬렉션)에 해당한다.

  • 중복 key(업데이트 누적)
  • 삭제 표식(tombstone)
  • 오래된 값

이들을 정리해 “저장 크기”와 “읽기 비용”을 통제한다.

4.1 세그먼트 + 머지의 직관적인 예

세그먼트(segment)로 로그를 나눈다고 하자.
시간이 흐르면 동일 key가 여러 번 기록된다.

seg1(오래됨): (a=1) (b=1) (c=1)
seg2        : (a=2) (d=1)
seg3(최신)  : (b=2) (c=2)

컴팩션은 여러 세그먼트를 읽어 “최신 값만 남기는” 새 파일을 만든다.

merge 결과: (a=2) (b=2) (c=2) (d=1)

핵심은 이거다.

  • 같은 key가 여러 번 나오면 가장 최신 레코드만 남긴다
  • 나머지는 버린다 → 디스크 회수 + 읽기 단순화

4.2 컴팩션이 “밀릴 때” 무슨 일이 생기나?

컴팩션이 제때 수행되지 않으면 문제가 연쇄적으로 온다.

  • 디스크: 중복/삭제 누적으로 사용량 증가 → 디스크 full 위험
  • 읽기: 더 많은 파일/세그먼트를 확인 → 지연 증가(p99 악화)
  • 쓰기: 백그라운드 작업이 밀려 쓰기까지 영향(스톨, throttling) 가능

로그 구조 저장에서 컴팩션은 “옵션”이 아니라 “생존 조건”에 가깝다.

5. B-Tree 계열(실전은 B+Tree): 페이지 엔진 + overwrite + WAL

B-Tree는 “전통적이고 범용적인” 인덱스지만, 디테일은 사실상 “페이지 기반 저장 엔진”의 이야기다.

5.1 페이지(page) 단위가 모든 것을 결정한다

  • 디스크는 보통 페이지/블록 단위로 I/O가 일어난다.
  • B-Tree는 노드를 페이지 크기에 맞춰 구성한다.
  • 한 페이지에 많은 키를 넣어 트리 높이를 낮춘다 → 디스크 I/O 횟수 감소

5.2 range query가 강한 이유(리프 연결)

많은 구현이 B+Tree 형태다.

  • 내부 노드: 키 범위 안내(포인터)
  • 리프 노드: 실제 레코드(또는 레코드 포인터) 저장
  • 리프 노드끼리 연결되어 있어 범위 스캔이 자연스럽다

즉,

  • 시작 지점만 찾으면
  • 그 다음은 리프를 순서대로 쭉 읽는다

그래서 BETWEEN, ORDER BY에 강하다.

5.3 overwrite의 숙명: WAL 없이는 복구가 깨진다

B-Tree는 페이지를 제자리 수정한다.
하지만 크래시가 나면 “페이지가 반만 갱신된 상태”가 남을 수 있다.

그래서 일반적으로:

  1. 변경 사항을 WAL에 먼저 기록
  2. 실제 페이지에 반영
  3. 체크포인트로 WAL 정리(재생 범위 축소)

결론: overwrite 기반 저장은 WAL/체크포인트 설계와 한 몸이다.

5.4 성능 흔들림 포인트: 페이지 split/merge

삽입이 계속되면 어떤 리프 페이지가 꽉 차고 split이 발생한다.

  • 새 페이지 할당
  • 부모 노드 갱신
  • 경우에 따라 연쇄적 구조 변화

이 과정은 지연 스파이크의 원인이 될 수 있다(특히 동시성/락과 만나면 더 민감).

6. LSM-Tree 디테일: Memtable, SSTable, 그리고 “읽기 비용을 줄이는 장치들”

LSM은 철학이 명확하다.

  • 쓰기는 append 중심으로 “싸게”
  • 대신 읽기/정리를 위해 백그라운드 병합(compaction)을 수행

6.1 기본 흐름(운영 관점에서 가장 중요)

  • (쓰기) WAL 기록 → Memtable 반영(정렬 구조)
  • (flush) Memtable이 일정 크기면 SSTable로 디스크 flush(정렬된 불변 파일 생성)
  • (정리) 여러 SSTable을 compaction으로 병합/정리

6.2 SSTable이 정렬되어서 생기는 혜택

정렬된 불변 파일이면:

  • 머지가 싸다: 순차 읽기 + 병합 정렬
  • 인덱스를 조밀하게 만들 필요가 없다: sparse index 가능
  • 블록 압축이 잘 먹는다: 비슷한 값들이 모이기 쉬움

6.3 읽기 비용 완화 장치 1: Bloom Filter

LSM은 읽을 때 여러 SSTable을 확인할 수 있다.
Bloom filter는 “이 파일에 해당 key가 없음”을 빠르게 걸러준다.

  • 없다고 판단되면 → 그 SSTable은 아예 읽지 않는다
  • false positive(있다고 잘못 판단)는 가능하지만, false negative(없는데 있다고 판단)는 없도록 설계한다

6.4 읽기 비용 완화 장치 2: Sparse Index + 블록(block)

SSTable 내부는 흔히 “블록(block)” 단위다.

  • 블록 단위로 압축/체크섬을 붙일 수 있고
  • sparse index로 “대략 어느 블록”인지 찾고
  • 해당 블록만 읽어 확인한다

정렬되어 있으니, 블록 안에서는 이진 탐색(혹은 작은 스캔)으로 key를 찾는 형태가 가능하다.

7. 컴팩션 정책: Size-tiered vs Leveled (LSM의 성격을 결정하는 스위치)

LSM에서 성능/운영 난이도를 좌우하는 게 컴팩션 정책이다.

7.1 Size-tiered compaction (STCS)

  • 비슷한 크기의 SSTable 여러 개를 한 번에 합쳐 더 큰 파일로 만든다.
  • 장점: 쓰기 처리량이 잘 나오기 쉬움(단순하고 강한 순차 I/O)
  • 단점: 파일 간 키 범위가 겹치기 쉬워 읽기 시 여러 파일을 보게 됨 → 읽기 증폭↑

7.2 Leveled compaction (LCS)

  • 레벨을 나누고, 각 레벨에서 키 범위가 가능하면 겹치지 않게 유지하려고 한다.
  • 장점: 읽기 시 확인해야 하는 파일 수가 줄어 지연이 안정적 → 읽기 증폭↓
  • 단점: 데이터가 레벨 이동 과정에서 더 자주 재작성될 수 있음 → 쓰기 증폭↑

STCS는 “쓰기 친화”, LCS는 “읽기 안정” 쪽으로 기울기 쉽다.

8. Tombstone(삭제 표식): 삭제는 왜 바로 사라지지 않나?

LSM에서 삭제는 “지우기”가 아니라 “삭제 레코드 추가”다.

  • 삭제 요청 → (key = TOMBSTONE) 레코드를 append
  • 이후 컴팩션 과정에서:
    • tombstone이 오래된 값을 “가리며”
    • 일정 조건이 충족되면 실제로 제거된다

이 방식은 append-only 철학을 유지하면서도, “삭제 사실”을 시스템 전반(복제/동기화 등)으로 전달하는 데 유리한 측면이 있다.

9. 증폭(Amplification): 결국 비용(돈/지연/수명)이다

9.1 Read amplification

  • LSM: 최신 값을 찾기 위해 여러 SSTable/레벨을 확인할 수 있음
    → Bloom filter, leveled compaction 등으로 완화
  • B-Tree: 탐색 경로는 명확하지만, 캐시 미스가 나면 랜덤 I/O 비용이 커질 수 있음

9.2 Write amplification

  • LSM: 컴팩션 때문에 같은 데이터가 여러 번 “다시 쓰일” 수 있음
  • B-Tree: 페이지 split/정리/체크포인트 등으로 논리 쓰기 대비 실제 쓰기량이 늘 수 있음

증폭이 중요한 이유는 명확하다.

  • SSD 수명(쓰기량)과 직결
  • 디스크 I/O(=클라우드 비용/성능)와 직결
  • p99 지연, 장애(디스크 full), 운영 난이도와 직결

10. OLAP/컬럼 지향 저장 디테일: “압축이 잘 되는 이유”를 한 번 더

컬럼 저장은 값이 “비슷한 것끼리” 모이기 쉬워 압축이 잘 된다.
(행 저장은 여러 타입이 섞여 압축 효율이 떨어지기 쉬움)

대표적인 기법들:

  • Dictionary encoding: 문자열/범주형을 작은 정수 ID로 치환
  • RLE(Run-Length Encoding): 같은 값 반복을 (값, 반복횟수)로 저장
  • Bit-packing: 값 범위가 작으면 필요한 비트 수만큼만 저장

OLAP에서 자주 하는 일이 “몇 개 컬럼만 뽑아 대량 스캔/집계”이므로, 컬럼 저장은 I/O 자체를 줄이고(필요 컬럼만 읽기), 압축으로 읽어야 할 바이트 수까지 줄이는 구조다.

11. 실전 체크리스트(운영 관점)

  • 내 서비스의 병목은 CPU인가 I/O인가? (대부분은 결국 I/O가 발목을 잡는다)
  • point lookup vs range scan 비중은? (해시 vs 정렬 인덱스 선택의 핵심)
  • p99 지연이 중요한가, throughput이 중요한가?
  • 컴팩션이 밀렸을 때의 “폭발 반경”을 감당할 수 있는가?
  • 스토리지 비용(용량/IOPS)과 SSD 쓰기량(증폭)을 모니터링하고 있는가?
  • 분석 쿼리가 OLTP에 영향을 주는가? (OLAP 분리/컬럼 포맷 도입 시점)

12. 한 문단 결론

저장 엔진은 “인덱스 구조(B-Tree/LSM)”만 외워서는 이해가 끝나지 않는다.
진짜 성격은 레코드 포맷, WAL/복구, 컴팩션 정책, 증폭 관리, 그리고 I/O 패턴에서 결정된다.
DDIA 3장의 핵심은 결국 “DB는 쿼리를 처리하는 소프트웨어이면서 동시에, 디스크 위에서 살아남는 시스템”이라는 감각을 갖는 것이다.

Leave a comment

You may also enjoy