3. Storage and Retrieval

• 3장의 핵심: OLTP에서는 적은 레코드를 빠르게 찾고 갱신하는 색인 구조가 중요하고, OLAP에서는 많은 레코드를 싸고 빠르게 스캔·집계하는 저장 형식이 중요함
• 그래서 여러 유형과 방법을 소개하는데, 결론은 저장소 엔진을 세부적으로 이해할수록 어떤 DB가 어떤 작업부하에 맞는지 더 잘 판단할 수 있다는 것

저장소 엔진은 크게 두 계열

• 로그 구조화(log-structured) 계열: Bitcask, SSTable, LSM 트리
• 페이지 지향(page-oriented) 계열: B 트리

3.1 The Simplest Database

• 가장 단순한 DB는 append-only 파일

• 책은 셸 함수 두 개로 만든 가장 단순한 key-value 저장소에서 출발함

• 쓰기 함수는 키,값 한 줄을 파일 끝에 계속 덧붙이기만 함

• 읽기 함수는 파일 전체를 훑어서 같은 키 중 가장 마지막 줄의 값을 돌려줌

1. 쓰기가 단순하고 빠름. 많은 DB도 내부적으로 append-only 로그를 씀
2. 키를 찾을 때마다 파일 전체를 훑어야 함. 검색 비용 O(n)

• 그래서 빠른 조회를 위해 별도의 데이터 구조, 즉 색인(index)이 필요해짐

3.2 Indexes and Trade-offs

• 색인은 기본 데이터에서 파생된 부가 메타데이터 구조. 하나의 데이터를 여러 방식으로 검색하려면 여러 종류의 색인이 필요할 수 있음
• 색인의 특징
  1. 데이터 자체를 바꾸지는 않음
  2. 주로 질의 성능에 영향을 줌
  3. 읽기는 빨라질 수 있음(빨라질 수도, 아닐 수도). 하지만 쓸 때마다 색인도 갱신해야 하므로 쓰기는 느려짐
• 그래서 어떤 색인을 고를지는 개발자의 몫

3.3 Hash Indexes

• 키-값 저장소는 해시 맵과 매우 비슷함. 키마다 데이터 파일의 바이트 오프셋을 가리키는 인메모리 해시 맵을 유지함
• 쓰기
  • 로그 파일 끝에 키-값 쌍을 덧붙임
  • 해시 맵에 그 키의 최신 오프셋을 반영
• 읽기
  • 해시 맵에서 오프셋을 확인
  • 디스크의 그 위치로 바로 가서 값을 읽음

장점

• 구조가 단순함
• 모든 키가 메모리에 들어간다는 가정 하에서 매우 빠름
• 값은 디스크에 있어도 되고, OS 캐시에 있으면 더 빠름
• 같은 키가 자주 갱신되는 작업부하에 잘 맞음
  • e.g. 동영상 URL → 재생 횟수

로그 세그먼트와 컴팩션

• append만 계속하면 디스크 공간이 끝없이 늘어남
• 해결
  • 로그를 segment 단위로 나눔
  • 오래된 세그먼트에 compaction(중복 키를 지우고 각 키의 최신 값만 남김)을 수행
  • 병합과 컴팩션은 보통 백그라운드 스레드에서 함

flowchart LR
  s1["Segment 1<br/>a=1, b=2, a=3"] --> merge["Merge & Compaction"]
  s2["Segment 2<br/>b=5, c=7"] --> merge
  merge --> out["Merged Segment<br/>a=3, b=5, c=7"]

실제 구현 시 고려할 점

• CSV보다 바이너리 형식이 적합
• 삭제는 툼스톤(tombstone) 레코드로 표현
• 크래시 후 인메모리 해시 맵은 사라지므로 복구가 필요
• 부분 쓰기 손상을 감지하는 체크섬 등이 필요
• 순차 쓰기라 쓰기 스레드 하나만 둬도 구현이 단순

한계

• 모든 키를 메모리에 올려야 함
• 범위 질의(range query)에 비효율적
  • e.g. kitty00000 ~ kitty99999 사이 키를 순차 스캔하기 어려움

3.4 SSTables and LSM-Trees

• 해시 색인의 한계를 넘기 위해 나온 구조가 SSTable(Sorted String Table)
• 키-값 쌍을 로그에 쓰되, 키 순서대로 정렬해서 저장

SSTable의 장점

1. 세그먼트 병합이 쉬움
   • 정렬된 파일끼리 병합정렬처럼 합칠 수 있음
   • 같은 키가 여러 세그먼트에 있으면 최신 값을 남김
2. 모든 키를 메모리에 둘 필요가 없음
   • 일부 키만 가리키는 희소 색인(sparse index)만 있어도 됨
   • 키가 어디쯤 있을지 범위를 좁힌 뒤 그 구간만 스캔
3. 블록 압축이 가능
   • 인접한 키-값들을 블록으로 묶어 압축하면 디스크 공간과 I/O 대역폭을 아낄 수 있음

쓰기 문제와 멤테이블(memtable)

• 문제는 실제 쓰기가 임의 순서로 들어온다는 점
• 해결: 메모리 안에서 정렬 구조를 유지함
  • 보통 균형 트리를 사용한다?
  • 이 인메모리 정렬 구조가 멤테이블(memtable)

LSM 트리의 동작

• 쓰기가 들어오면 멤테이블에 기록
• 멤테이블이 커지면 디스크에 SSTable로 flush
• 읽을 때는
  1. 멤테이블 확인
  2. 가장 최신 SSTable 확인
  3. 더 오래된 SSTable 순서대로 확인
• 백그라운드에서 세그먼트 병합과 컴팩션 수행

flowchart TD
  write["Write"] --> mem["Memtable<br/>(in-memory, sorted)"]
  write --> log["Append-only Log<br/>(crash recovery)"]
  mem -- "flush" --> sst1["SSTable (newest)"]
  sst1 --> compact["Background Compaction"]
  sst2["SSTable (older)"] --> compact
  compact --> merged["Merged SSTable"]

크래시 복구

• 아직 flush되지 않은 멤테이블 데이터는 크래시 때 사라질 수 있음
• 그래서 별도의 append-only 로그를 두고, 재시작 후 멤테이블을 복구

관련 기술

• LevelDB, RocksDB
• Cassandra, HBase
• Lucene도 비슷한 원리를 활용

성능 최적화

• 존재하지 않는 키를 찾으면 느릴 수 있어서 Bloom Filter를 씀
• 컴팩션 전략: size-tiered compaction, leveled compaction 등

LSM 트리의 특징

• 데이터셋이 메모리보다 훨씬 커도 잘 동작
• 키가 정렬돼 있어서 범위 질의 가능
• 디스크 쓰기가 순차적이라 쓰기 처리량이 높음

3.5 B-Trees

• B 트리(B-tree)는 가장 널리 쓰이는 색인 구조
  • 키가 정렬되어 있어서 검색과 범위 질의에 유리
  • LSM과 달리 고정 크기 페이지(page) 중심으로 동작

구조

• 페이지들이 트리 구조를 이룸
• 루트에서 시작해 키 범위에 맞는 하위 페이지를 따라 내려가고, 마지막 리프 페이지에서 값을 찾음

flowchart TD
  root["Root Page"] --> inner1["Page: keys 0–99"]
  root --> inner2["Page: keys 100–199"]
  inner2 --> leaf1["Leaf: 100–149"]
  inner2 --> leaf2["Leaf: 150–199"]

삽입과 분할

• 넣을 페이지에 여유가 있으면 그대로 삽입
• 공간이 부족하면 페이지를 분할(split)하고 상위 페이지도 갱신
• 트리는 균형을 유지하므로 깊이는 O(log n)

특징

• 데이터를 제자리 갱신(in-place update)함. 기존 페이지를 덮어씀
• 이게 append-only 기반 LSM과 가장 큰 차이

신뢰성 문제와 WAL

• 여러 페이지를 갱신하는 중간에 크래시가 나면 색인이 깨질 수 있음
• 이를 막으려고 WAL(write-ahead log)을 둠. 변경 내용을 먼저 로그에 쓰고 나서 실제 페이지에 반영

동시성 제어

• 여러 스레드가 동시에 접근하면 일관성이 깨질 수 있으므로 보통 latch 같은 잠금으로 보호

최적화

• copy-on-write 방식
• 키 축약 저장
• 리프 페이지의 연속 배치
• 형제 페이지 포인터
• 프랙탈 트리 등의 변형
• 사실 이 부분은 뭐라는지 잘 모르겠어서 나중에 다시 볼 예정

3.6 Comparing B-Trees and LSM-Trees

• 일반적으로 LSM 트리는 쓰기에 강하고, B 트리는 읽기에 강함

LSM 트리의 장점

• 순차 쓰기 기반이라 쓰기 처리량이 높음
• 압축률이 더 좋고 저장 공간 오버헤드가 낮음
• 파편화가 적음
• 특히 자기 디스크에서는 임의 쓰기보다 순차 쓰기가 훨씬 빠르다는 점이 중요

LSM 트리의 단점

• 컴팩션이 읽기와 쓰기에 영향을 줄 수 있음
• 상위 백분위 응답 시간이 길어질 수 있음
• 컴팩션이 유입 쓰기 속도를 못 따라가면 세그먼트가 쌓이고 읽기도 느려짐. 그래서 명시적인 모니터링이 필요

B 트리의 장점

• 각 키가 색인 안의 한 곳에만 정확히 존재
• 강한 트랜잭션 시맨틱과 잘 맞음
• 오랫동안 검증되어 구현 성숙도가 높음?
  • 이게 장점인지? 구현을 잘 하면 되는 거 아닌지?

3.7 Other Indexing Structures

보조 색인(secondary index)

• 기본키 외 다른 칼럼에도 색인을 둘 수 있음
• 조인 성능에 매우 중요
• 기본키와 달리 고유하지 않을 수 있다는 점이 차이

색인 안에 값 저장하기

• 색인의 값은 실제 로우 자체일 수도, 다른 곳에 저장된 로우를 가리키는 참조일 수도 있음
• 실제 로우를 저장한 곳을 힙 파일이라 함
• 변형
  • 클러스터드 색인: 색인 안에 실제 로우 저장
  • 비클러스터드 색인: 로우 위치만 저장
  • 커버링 색인: 일부 칼럼을 색인 안에 함께 저장

다중 칼럼 색인

• 여러 칼럼을 동시에 질의하려면 단일 키 색인만으로는 부족

• 결합 색인(concatenated index), 다차원 색인(multidimensional index)

• e.g. 위도·경도 두 범위를 동시에 거는 지도 검색

• 예: 지도에서 위도와 경도가 각각 어떤 범위 안에 있는 가게를 모두 찾는 질의

• 이런 2차원 범위 질의는 일반 B 트리나 LSM 트리로는 비효율적일 수 있음

• 그래서 공간 채움 곡선, R 트리 같은 전문 공간 색인을 씀

전문 검색과 퍼지 색인

• 정확한 키 일치가 아니라 오타, 유사어, 형태소 변형 등을 다루려면 별도 기술이 필요
• Lucene은 편집 거리 기반 검색, 오토마톤 등을 쓴다? → 이게 뭔지는 아직 모르겠음

3.8 In-Memory Databases

• 지금까지 본 구조는 대부분 디스크의 한계를 보완하려는 시도. 메모리가 점점 싸지면서 전체 데이터를 메모리에 두는 인메모리 DB도 현실적인 선택지가 됨

특징

• 일부는 캐시 용도로만 씀. e.g. Memcached
• 일부는 지속성을 목표로 함: 디스크 로그, 주기적 스냅샷, 복제, 특수 하드웨어 등

중요한 점

• 인메모리 DB가 빠른 이유는 단순히 디스크를 안 읽어서가 아님
  • 디스크 기반 엔진도 OS 캐시 덕분에 메모리에서 읽을 수 있음
  • 오히려 디스크용 포맷으로 부호화하는 오버헤드가 줄어서 빠를 수 있음

추가 장점

• Redis처럼 우선순위 큐, set 같은 다양한 자료구조를 제공할 수 있음
• 안티 캐싱처럼 메모리가 부족할 때 일부 데이터를 디스크로 내보내는 방식도 연구됨

3.9 Transaction Processing or Analytics?

3.10 Data Warehousing

• 기업은 보통 OLTP 시스템을 여러 개 운영함. 운영 DB에 무거운 분석 질의를 직접 날리면 서비스 성능이 떨어질 수 있음
• 그래서 분석 전용 DB인 데이터 웨어하우스(data warehouse)를 따로 둠. 웨어하우스는 여러 OLTP 시스템의 읽기 전용 복사본

ETL

• OLTP 시스템에서 데이터를 Extract → Transform → Load 해서 웨어하우스로 옮김

flowchart LR
  oltp1["OLTP DB A"] --> etl["Extract → Transform → Load"]
  oltp2["OLTP DB B"] --> etl
  oltp3["OLTP DB C"] --> etl
  etl --> dw["Data Warehouse"]
  dw --> analyst["Analytics Queries"]

3.11 Stars and Snowflakes: Schemas for Analytics

• 분석에서는 보통 별 모양 스키마(star schema)를 많이 씀
• 중심에 사실 테이블(fact table): 각 로우가 이벤트 하나
• 주변에 차원 테이블(dimension table): 제품, 날짜, 매장, 고객, 프로모션 등. 누가, 언제, 어디서, 무엇을, 왜에 해당하는 속성을 설명함

특징

• 사실 테이블은 매우 큼
• 차원 테이블은 메타데이터를 풍부하게 담음
• 날짜도 차원 테이블로 둬서 공휴일 여부 같은 속성을 함께 저장할 수 있음

눈꽃송이 스키마

• 차원 테이블을 더 정규화해 세분화한 구조
• 하지만 분석가는 보통 별 모양 스키마를 더 다루기 쉽게 여긴다? → 누구 맘대로?

3.12 Column-Oriented Storage

• 분석 질의는 보통 모든 칼럼을 읽지 않음. 칼럼이 100개인 사실 테이블에서 실제 질의는 4~5개만 쓸 수 있음
• 로우 지향 저장은 로우 전체를 읽고 필요 없는 칼럼을 버려야 해서 비효율적

칼럼 저장의 아이디어

• 로우 단위가 아니라 칼럼별로 값을 모아 저장
• 질의에 필요한 칼럼만 읽으면 되므로 디스크에서 읽는 양이 크게 줄고, 분석 질의에 매우 적합함

flowchart LR
  subgraph row["Row-oriented"]
    r1["row1: date, product, store, qty"]
    r2["row2: date, product, store, qty"]
  end
  subgraph col["Column-oriented"]
    c1["date: d1, d2, ..."]
    c2["product: p1, p2, ..."]
    c3["qty: q1, q2, ..."]
  end

3.13 Column Compression and Bitmap Encoding

• 칼럼 저장소는 압축과 궁합이 좋음. 같은 칼럼 안에서 값이 반복되는 경우가 많기 때문

비트맵 인코딩

• 고유값마다 비트맵 하나를 둠. 로우가 그 값을 가지면 1, 아니면 0

추가 압축

• 대부분이 0이면 런 렝스 인코딩(RLE)으로 압축
• 그래서 필터 조건 계산이 빨라지고, OR·AND 같은 비트 연산으로 조건을 결합할 수 있음

3.14 Sort Order and Vectorized Processing in Column Storage

• 칼럼 저장은 디스크 I/O뿐 아니라 CPU 처리에도 유리
• 필요한 칼럼만 L1 캐시에 맞는 크기로 가져와 처리할 수 있고, 압축된 블록 위에서 바로 연산하는 벡터화 처리도 가능

정렬 순서의 중요성

• 칼럼을 각각 따로 정렬하는 게 아니라, 로우 순서를 유지한 채 전체를 어떤 기준으로 정렬
• 자주 쓰는 질의 기준으로 정렬하면 범위 스캔이 쉬워지고 압축률도 높아짐

3.15 Writing to Column-Oriented Storage

• 칼럼 저장소는 읽기에는 강하지만 쓰기에는 불리
• 압축된 칼럼 파일 중간에 값을 끼워 넣거나 제자리 갱신하기 어려움

해결 방식

• 먼저 인메모리 저장소에 쓰기를 모으고
• 이후 배치로 디스크의 칼럼 파일과 병합
• LSM 트리식으로…

3.16 Aggregation: Data Cubes and Materialized Views

• 자주 쓰는 집계 결과를 미리 계산해 저장한 것이 구체화 뷰(materialized view)
• 일반 뷰는 질의 정의만 저장하지만, 구체화 뷰는 실제 결과를 디스크에 저장

데이터 큐브

• 구체화 집계의 특수한 경우. 날짜, 제품, 매장 등 여러 차원 기준으로 집계값을 저장
• 특정 분석 결과를 매우 빠르게 조회할 수 있지만, 원시 데이터 질의만큼 유연하지는 않음