DDIA 3장 — 저장소와 검색

책: 데이터 중심 애플리케이션 설계 (Designing Data-Intensive Applications), Martin Kleppmann, O'Reilly 챕터: 3장 — Storage and Retrieval

Part 1. 내가 3장에서 가져가려 한 것

다시 펼쳤을 때 빠르게 복기할 수 있도록, 3장에서 진짜 손에 쥐고 가는 핵심을 먼저 정리.

큰 그림 한 줄

하드웨어 한계(디스크 특성) + 워크로드 차이(OLTP/OLAP) 라는 두 제약 위에서, 자료구조와 저장 방식을 조합해 트레이드오프를 조율하고 앱에 맞게 선택한다.

3장의 통찰 3가지

1. 저장 구조는 워크로드를 따른다 — OLTP / OLAP / 시계열 등 패턴별로 최적 엔진이 다름
2. 인덱스는 트레이드오프 — 무료가 아님, 데이터로 결정해야 함
3. 시스템 분리가 정상 — 운영 DB + 검색 + 캐시 + 분석 DB 조합이 현대의 표준

핵심 트레이드오프 두 축

축 1. 쓰기 ↔ 읽기

• 인덱스 多 → 읽기 ↑, 쓰기 ↓
• LSM 트리 → 쓰기 ↑↑, 읽기 보통
• B-트리 → 균형

축 2. OLTP ↔ OLAP

• OLTP (한 행 빠르게) → 행 지향 + B-트리/LSM
• OLAP (수많은 행 집계) → 컬럼 지향 + 압축 + 비트맵

직관으로 박아둔 것들

"디스크는 동영상처럼 읽으면 빠르고, 랜덤 점프하면 느리다"

• 순차 I/O ≫ 랜덤 I/O (HDD 100배, SSD 10배 격차)
• DB 설계의 모든 트릭은 "디스크 접근을 어떻게든 줄이자"

"인덱스가 있으면 100만 번 → 22번"

• ① 인덱스 파일이 작아서 적게 읽음
• ② 정렬돼서 이진 탐색 (O(log n))
• ③ 위치 알면 원본은 점프 한 번

"인덱스 N개 = 쓰기마다 자료구조 N+1개 갱신"

• 인덱스 1개 = 컬럼 1개에 대한 자료구조 1개
• 그래서 무조건 많이 거는 게 좋은 게 아님

"append-only는 끝에만 추가, 수정·삭제는 새 줄로 표현"

• 순차 I/O라 빠름 / 변경 이력 보존 / 동시성·장애에 강함
• 단점은 공간 증가 → 컴팩션 필수
• LSM, WAL, Kafka, Git이 다 같은 가족

"WAL = 데이터 수정 전에 변경 내용을 로그에 먼저 기록"

• Write-Ahead Log: 본 작업보다 앞서서(ahead) 로그를 남긴다
• 어느 시점에 죽어도 재시작 시 WAL을 보고 복구 가능 → 충돌 안전성의 표준 도구
• B-트리(페이지 분할 위험)와 LSM 트리(MemTable 휘발성) 둘 다 WAL 필수

실무 결정에 직접 쓰는 것

워크로드별 엔진 선택

인덱스 추가 기준 체크리스트

추가:

• WHERE / JOIN / ORDER BY에 자주 등장
• 카디널리티 높음
• 테이블이 충분히 큼 (10만 행 이상)
• 읽기 빈도 ≫ 쓰기 빈도

추가하지 말 것:

• 카디널리티 낮음 (boolean, 성별)
• 자주 업데이트되는 컬럼
• 함수 적용된 검색 (별도 함수 인덱스 필요)
• 작은 테이블

결정 절차: 쿼리 로그 → EXPLAIN → 측정 → 가설 → 측정 → 좀비 인덱스 제거

복합 인덱스 핵심 규칙

• 컬럼 순서: 선택도 높은 것을 앞에
• (A, B) 인덱스는 WHERE A, WHERE A AND B엔 쓰이고 WHERE B엔 안 쓰임
• 전화번호부 비유: 성 → 이름

흔한 함정 5가지

1. "일단 다 걸자" → 쓰기 지옥
2. 복합 인덱스 순서 무시 → 안 쓰임
3. 타입 불일치 (WHERE id = '123'이 int일 때) → 인덱스 무시
4. LIKE '%검색어%' → 일반 인덱스 못 씀, 전문 검색 인덱스 필요
5. OR 사용 → 인덱스 활용도 떨어짐

자주 헷갈리는 것 — 분리 정리

순차 I/O vs 인덱스

• 다른 레이어. 순차 I/O는 디스크 물리 사실, 인덱스는 별개 자료구조
• 핵심 긴장: "인덱스로 점프 = 랜덤 I/O" → 3장 전체를 관통하는 트레이드오프

해시 인덱스 vs 인메모리 DB

• 해시 인덱스 = 인덱스의 자료구조
• 인메모리 DB = 데이터 저장 위치
• 독립적인 차원 (4가지 조합 모두 가능)
• Bitcask = 디스크 데이터 + 메모리 인덱스 / Redis = 메모리 데이터 + 메모리 인덱스

인메모리 DB가 빠른 진짜 이유

• "디스크 안 써서"가 아니라 → 자주 쓰는 페이지는 어차피 OS 페이지 캐시에 있음
• 진짜 이유: 디스크용 인코딩 오버헤드 제거 + 풍부한 자료구조 (Sorted Set 등) 사용 가능

한 장으로 보는 3장

[저장 엔진]
   ├─ OLTP (한 행 빠르게)
   │    ├─ B-트리 ── MySQL, PostgreSQL
   │    └─ LSM 트리 ── Cassandra, RocksDB
   └─ OLAP (수많은 행 집계)
        └─ 컬럼 지향 ── Redshift, BigQuery, ClickHouse

핵심: 모든 인덱스/저장 = "쓰기 비용 ↔ 읽기 속도" 다이얼

Part 2. 상세 학습 정리

사전 지식 — 3장 읽기 전 알아둘 것

메모리 계층

→ RAM에게 1초가 HDD에게는 한 달.

SSD vs HDD

→ SSD 시대에도 순차 I/O 우위는 여전. LSM 트리 같은 설계가 유효한 이유.

순차 I/O vs 랜덤 I/O

• 순차: 디스크 연속 위치 → 빠름
• 랜덤: 흩어진 위치 점프 → 느림

랜덤 I/O 발생 예시:

• B-트리 인덱스 조회 (트리 따라 페이지 점프)
• 인덱스 → 원본 테이블 점프
• 여러 인덱스 동시 사용
• JOIN 연산
• B-트리 INSERT/UPDATE (페이지 분할 시 더 심함)
• OS 페이지 폴트 (swap)
• 여러 사용자 동시 접근 (실무에서 큰 비중)
• 단편화된 파일

페이지 / 블록

• 디스크는 1바이트 못 읽음 → 4KB ~ 16KB 덩어리 단위
• B-트리 노드가 페이지 크기로 만들어지는 이유

핵심 자료구조

B-트리가 이진 트리 아닌 이유: 분기 수 수백 → 100만 데이터 깊이 3~4 → 디스크 접근 횟수 최소화하려는 진화.

시간 복잡도 직관

• O(1) — 해시 조회 (1번)
• O(log n) — 트리/이진 탐색 (100만 → ~20번)
• O(n) — 풀 스캔 (100만 → 100만 번)
• "인덱스 있으면 20번, 없으면 100만 번. 그게 인덱스의 정체."

데이터 지역성

"자주 같이 쓰는 데이터를 물리적으로 가까운 곳에"
→ 디스크가 페이지 단위로 읽으니 한 번에 필요한 정보를 다 가져오기 위함
→ 2장 문서 모델의 강점이자 B-트리 페이지 설계의 근거

인덱스의 본질

CREATE INDEX가 만드는 것

별도 파일 생성. 구조: 검색 키 → 원본 데이터의 디스크 위치. 원본 테이블에 손대지 않고 옆에 새 파일 추가.

원본 테이블:                    인덱스:
위치 0:   user_id=42, ...       user_id=17 → [위치 64, 256]
위치 64:  user_id=17, ...       user_id=42 → [위치 0, 128]
위치 128: user_id=42, ...       user_id=89 → [위치 192]

왜 빨라지나 (3가지 동시)

1. 인덱스 파일이 작아 적게 읽음 (원본의 10~30%)
2. 정렬돼서 이진 탐색 가능 → O(log n)
3. 위치 알면 원본은 점프 한 번

핵심 트레이드오프

"인덱스는 쓰기 속도를 희생시켜 읽기 속도를 얻는 트레이드오프다."

• 데이터 쓸 때마다 인덱스도 갱신 필요
• 인덱스가 많을수록 쓰기 시 갱신할 자료구조 증가
• → 인덱스는 공짜가 아니다. 쿼리 패턴 보고 골라서 걸어야

인덱스의 작동 단위

• 인덱스 1개 = 컬럼 1개에 대한 자료구조 1개
• 다른 컬럼 검색 시 별도 인덱스 필요
• 인덱스 5개 = 자료구조 5개 동시 관리 = 쓰기 시 6번 갱신

WAL (Write-Ahead Log)

정의

"실제 데이터 파일을 수정하기 전에, 변경 내용을 먼저 로그 파일에 기록한다".

• Write-Ahead = 본 작업보다 앞서서
• Log = 변경 이력 파일

동작 방식

쓰기 한 번에 두 단계가 들어간다:

1단계: WAL 파일 끝에 "이런 변경을 할 거야" 기록 (append-only, 순차 I/O)
       ↓ fsync로 디스크에 확실히 저장
2단계: 실제 데이터 파일을 수정 (B-트리 페이지 갱신 또는 MemTable 갱신)

어느 시점에 죽어도 안전한 이유

핵심 포인트

• 소프트웨어 레벨 개념: DB 프로그램이 만드는 일반 파일. 하드웨어가 제공하는 기능이 아님.
• 하드웨어 접점은 fsync() 한 군데: "OS 페이지 캐시가 아니라 진짜 디스크에 썼는지" 보장하는 시스템 콜.
• DB마다 이름과 구현이 다름: PostgreSQL은 WAL, MySQL InnoDB는 redo log, Cassandra는 commit log, SQLite는 WAL/Rollback Journal 모드 선택.

3장 맥락에서

• B-트리: 페이지 분할 도중 다운되면 트리가 깨질 위험 → WAL 필수
• LSM 트리: MemTable이 메모리에 있어 휘발 위험 → WAL 필수
• 같은 도구로 다른 위험을 막는다. 충돌 안전성의 사실상 표준.

(WAL의 본격적인 트랜잭션 맥락은 7장에서 다시 등장.)

3.1 데이터베이스를 강화하는 데이터 구조

3.1.1 가장 단순한 DB

셸 스크립트 두 줄짜리 DB:

db_set () { echo "$1,$2" >> database; }
db_get () { grep "^$1," database | sed -e "s/^$1,//" | tail -n 1; }

• 쓰기: 파일 끝에 한 줄 추가 → 순차 I/O → 매우 빠름
• 읽기: 파일 전체 grep → O(n) → 끔찍

→ append-only 로그의 원형. Cassandra, Bitcask, Kafka, WAL 등이 이 아이디어.

3.1.2 해시 인덱스 (Bitcask)

구조

디스크 (append-only):           메모리 (해시 맵):
위치 0:   123, {...}             123 → 80 (가장 최신)
위치 32:  42,  {...}             42  → 170
위치 80:  123, {...}             88  → 130
위치 130: 88,  {...}
위치 170: 42,  {...}

• 쓰기: 디스크 append + 메모리 해시 갱신 → 매우 빠름
• 읽기: 해시 맵 조회 → 디스크 한 번 읽기 → 매우 빠름

세그먼트 + 컴팩션

• 일정 크기마다 새 세그먼트 파일 분리
• 백그라운드에서 닫힌 세그먼트의 최신 값만 남기고 정리

결정적 한계

1. 키가 메모리에 다 들어가야 함 — 대규모 데이터셋 불가
2. 범위 쿼리 불가 — 해시는 순서 없음

3.1.3 SSTable과 LSM 트리

SSTable의 마법

세그먼트 파일을 키 순서로 정렬해서 저장.

1. 인덱스가 메모리에 다 안 들어가도 됨 — sparse 인덱스로 충분
2. 범위 쿼리 가능 — 정렬돼있어 시작점 찾고 옆으로 쭉
3. 컴팩션이 효율적 — k-way merge로 순차 I/O로 합쳐짐

LSM 트리 메커니즘

쓰기 흐름:
1. WAL에 append (디스크, 순차) ← 충돌 안전성
2. MemTable에 추가 (메모리, 정렬 유지)
                    ↓
3. MemTable이 가득 차면 → SSTable로 플러시 (디스크, 순차)
                    ↓
4. SSTable들이 쌓이면 → 컴팩션 (백그라운드, 순차)

• MemTable: 메모리 정렬 자료구조 (red-black tree, skip list)
• WAL: MemTable 휘발성 보호 — 서버 죽어도 복구
• Bloom Filter: 키가 SSTable에 "확실히 없다"를 빠르게 판단
• 사용처: LevelDB, RocksDB, Cassandra, HBase

3.1.4 B-트리

핵심 발상

데이터를 고정 크기 페이지(4~16KB)로 나누고, 페이지를 트리로 연결.

                [루트]
                [50 | 100]
               /     |     \
          [10|30] [60|80] [120|150|200]

• 한 페이지에 수백 개 키 → 분기 수 큼 → 깊이 얕음 (100만 데이터 깊이 3~4)
• 노드 = 디스크 페이지

쓰기 메커니즘

1. 루트부터 내려가서 키 들어갈 리프 페이지 찾기
2. 페이지 메모리로 읽기
3. 값 갱신
4. 페이지 디스크에 다시 쓰기 (in-place 덮어쓰기)

→ LSM의 append-only가 아니라 있던 자리 수정.

페이지 분할

가득 찬 페이지에 새 키 → 두 페이지로 분할 + 부모에 새 키 추가. 최악의 경우 루트까지 전파.

충돌 안전성 — WAL 필수

페이지 분할 중 서버 다운 → 트리 깨질 위험 → WAL 먼저 쓰고 페이지 수정.

동시성

페이지 계속 수정 → 잠금(latch) 필요 → LSM(SSTable 불변)보다 복잡.

사용처

MySQL InnoDB, PostgreSQL, Oracle, SQL Server, SQLite, MongoDB(WiredTiger). 40년간 표준.

B-트리 vs LSM 비교

3.1.5 기타 인덱싱 구조

기본 키 vs 보조 인덱스

• 기본 키: PK 자동 생성, unique
• 보조 인덱스: 다른 컬럼, 한 키에 여러 위치 가능

인덱스에 값 저장하는 방식

• 힙 파일 + 위치만: 인덱스 → 힙 이중 점프
• 클러스터드: 인덱스 안에 데이터 통째로 (InnoDB의 PK)
• 커버링: 자주 쓰는 컬럼만 INCLUDE → 인덱스만 보고 끝

다중 컬럼 인덱스

• 연결 인덱스: 컬럼 순서가 핵심 (전화번호부 비유)
• 공간 인덱스 (R-트리): 위도/경도 등 다차원

전문 검색 인덱스

• 역인덱스: "단어 → 문서 목록"
• 형태소 분석, 퍼지 검색, BM25 점수
• Elasticsearch, Solr

인메모리 DB

• Redis, Memcached, VoltDB, SAP HANA
• 빠른 진짜 이유: 디스크용 인코딩 오버헤드 제거 + 풍부한 자료구조 가능
• 영속성: WAL/스냅샷/복제로 처리

3.2 OLTP vs OLAP

두 워크로드의 본질적 차이

쿼리 패턴 차이

OLTP: 조건 명확, 결과 적음, 인덱스로 점프

SELECT * FROM orders WHERE user_id = 42 LIMIT 10;

OLAP: 수억 행 스캔, 집계, 소수 컬럼만 사용

SELECT category, SUM(amount) FROM orders
WHERE created_at >= '...' GROUP BY category;

분리 아키텍처

[사용자] → [OLTP DB] ──ETL──→ [데이터 웨어하우스] ← [분석가]

• ETL: Extract → Transform → Load
• 분석 쿼리가 운영 시스템에 영향 안 줌

데이터 웨어하우스

• 클라우드: Redshift, BigQuery, Snowflake
• 오픈소스: ClickHouse, Presto/Trino, Hive
• 엔터프라이즈: Teradata, Vertica

분석용 스키마

• 별 스키마: 가운데 팩트 + 둘러싼 디멘전. 실무 표준.
• 눈송이 스키마: 디멘전 더 정규화. 조인 늘어 덜 쓰임.

3.3 컬럼 지향 저장소

핵심 발상

저장 단위를 행 → 컬럼으로 뒤집기. 같은 컬럼 값들이 디스크상 연속.

행 지향:                   컬럼 지향:
[1, 42, electronics, 100]  order_id: [1, 2, 3, ...]
[2, 17, books, 30]         user_id:  [42, 17, 42, ...]
[3, 42, electronics, 200]  category: [electronics, books, ...]
                           amount:   [100, 30, 200, ...]

분석에 유리한 4가지 이유

1. 불필요 컬럼 안 읽음 — 50개 중 3개만 쓸 때 I/O ~15배 ↓
2. 압축 효과적 — RLE, 사전 인코딩
3. 비트맵 인덱스 — CPU 비트 연산으로 필터
4. CPU 캐시 / SIMD 친화 — 연속 메모리 + 동일 타입

압축 기법

• RLE (런렝스 인코딩): [Q4, Q4, Q3] → [(Q4,2), (Q3,1)]
• 사전 인코딩: 문자열 → 정수
• 비트맵: 정수 컬럼 → 비트 연산으로 필터

컬럼 정렬 (Sort Key)

• 한 컬럼 기준 정렬 → 모든 컬럼이 같이 정렬
• RLE 효율 ↑
• 분석 DB 기본: 시간 컬럼 기준

약점: 단일 행 쓰기

컬럼 파일 N개에 각각 추가 → 랜덤 I/O N번 → OLTP 부적합.

해법: LSM 차용

1. 메모리 행 지향 버퍼
2. 일정량 쌓이면 컬럼으로 변환해 일괄 쓰기
3. 백그라운드 컴팩션

→ Vertica, Druid 등. 3.1의 LSM 패턴이 또 등장.

구체화 뷰 / 데이터 큐브

자주 쓰는 집계 미리 계산. 큐브 = 여러 차원 사전 집계.

• 장점: 즉시 응답
• 단점: 미정의 차원 무력
• 실무: 자주 쓰는 것만 큐브

사용처

• 클라우드 DW: Redshift, BigQuery, Snowflake
• 오픈소스: ClickHouse, Druid, Pinot
• 파일 포맷: Parquet, ORC

학습 중 던졌던 질문 모음

Q. 순차 I/O는 추가 정보가 필요한가? 그게 인덱스인가?

• 순차 I/O는 디스크 물리 사실, 추가 정보 없음
• 인덱스는 별개의 자료구조 (다른 레이어)
• 핵심 긴장: "인덱스로 점프 = 랜덤 I/O"

Q. 데이터 지역성이 뭐였지?

• "자주 같이 쓰는 데이터를 물리적으로 가까운 곳에"
• 디스크 페이지 단위 읽기를 효율적으로 활용

Q. 인덱스는 어떻게 정하는가?

• WHERE/JOIN/ORDER BY 자주 쓰이는 컬럼
• 카디널리티 높음
• 쿼리 로그 → EXPLAIN → 측정 → 가설 → 측정

Q. 인덱스가 있으면 왜 빠른가?

• ① 작아서 적게 읽음 ② 정렬돼서 이진 탐색 ③ 위치 알면 점프 한 번

Q. append-only란?

• "끝에만 추가, 수정·삭제는 새 줄로"
• 순차 I/O / 변경 이력 보존 / 동시성 강함
• LSM, WAL, Kafka, Git이 같은 가족

Q. 해시 인덱스는 모든 속성을 다 해시로 등록하나?

• 인덱스 1개 = 키 1개 담당
• 여러 컬럼 검색 = 별도 인덱스 N개

Q. 해시 인덱스가 인메모리 DB에서 쓰는 인덱싱인가?

• 별개 차원
• 해시 인덱스 = 자료구조 / 인메모리 DB = 데이터 위치
• Bitcask = 디스크 데이터 + 메모리 인덱스

Q. SSD와 HDD 차이?

• HDD: 자기 디스크 + 헤드 (물리, 느림)
• SSD: 반도체 (전기, 빠름)
• SSD 시대에도 순차/랜덤 격차는 존재 (10배)

Q. 랜덤 I/O 발생 예시?

• B-트리 인덱스 조회, JOIN, 인덱스→원본 점프
• B-트리 INSERT/UPDATE (페이지 분할)
• 여러 동시 사용자 (실무 큰 비중)
• OS 페이지 폴트, 단편화된 파일

다음 장 미리보기

4장. 부호화와 발전 (Encoding and Evolution)

3장이 "디스크에 어떻게 저장할까"였다면, 4장은 "네트워크/디스크로 어떻게 주고받을까".

등장 인물:

• JSON, XML, CSV
• Protocol Buffers, Thrift, Avro
• 전후방 호환성 (forward/backward compatibility)
• REST, RPC, 메시지 큐, 액터 모델