Log-Structured 저장소 엔진#

핵심 아이디어: 데이터를 append-only 로그 파일에 순차적으로 쓰고 백그라운드에서 정리(compaction)

특징:

• 쓰기가 매우 빠름 (순차적 쓰기)
• 데이터가 여러 곳에 중복 저장될 수 있음
• 백그라운드 compaction으로 공간 회수
• ex): Cassandra, HBase

동작 방식:

1
시간 순서대로 쓰기:
2
[key1=A] → [key2=B] → [key1=C] → [key3=D] → [key2=E]
3

4
읽을 때: 뒤에서부터 찾음 (key1의 최신값은 C)

Page-Oriented 저장소 엔진#

핵심 아이디어: 디스크를 고정 크기 페이지로 나누고, 각 페이지를 in place로 수정(overwrite)하는것

특징:

• 읽기가 예측 가능하고 안정적
• B-Tree가 대표적인 구현
• 각 키는 정확히 한 곳에만 존재
• ex): MySQL (InnoDB), PostgreSQL, SQLite

동작 방식:

1
페이지 구조:
2
[Page 1: key1=A, key2=B]
3
[Page 2: key3=D, key4=F]
4

5
key1 업데이트 시 → Page 1에서 직접 수정
6
[Page 1: key1=C, key2=B]  ← 제자리 수정

Concept

• Storage Engine : 데이터를 디스크에 저장하고 검색하는 데이터베이스의 핵심 컴포넌트. 쿼리 언어와 독립적으로 동작
• Log-Structured Storage: 데이터를 append-only 로그에 순차적으로 쓰고, 나중에 compaction으로 정리하는 방식. 쓰기 성능이 우수
• Page-Oriented Storage : 디스크를 고정 크기 페이지로 나누고 제자리에서(in place) 수정하는 방식. 읽기 성능이 예측 가능
• 순차적 쓰기(Sequential Write): 디스크의 연속된 위치에 데이터를 쓰는 방식. 랜덤 쓰기보다 훨씬 빠름
• 랜덤 쓰기(Random Write): 디스크의 임의의 위치에 데이터를 쓰거나 읽는 방식. HDD에서는 헤드가 물리적으로 이동해야 하므로 매우 느림(수 ms). SSD에서도 순차 액세스보다 느리며, 쓰기 증폭을 유발. B-Tree는 랜덤 I/O를 피할 수 없지만 페이지 캐싱으로 완화
• 바이트 오프셋(Byte Offset): 파일 내에서 특정 데이터의 위치를 나타내는 숫자. 빠른 랜덤 액세스에 사용
• 쓰기 증폭(Write Amplification) : 실제 쓰려는 데이터보다 더 많은 데이터를 디스크에 쓰게 되는 현상. B-Tree에서 한 바이트 변경에도 전체 페이지를 쓰는 경우
• WAF (Write Amplification Factor): 실제 쓴 데이터 대비 물리적으로 쓴 데이터의 비율. SSD 수명과 직결
• Copy-on-Write: 데이터 수정 시 원본을 보존하고 새 복사본을 만드는 기법. 스냅샷과 MVCC에 활용
• MVCC(Multi-Version Concurrency Control): 동시성 제어를 위해 데이터의 여러 버전을 유지하는 것. 핵심 아이디어는 읽기 작업은 특정 시점의 스냅샷을 보고 쓰기는 새 버전을 생성하는 것. 각 행의 버전번호와 타임스탬프를 부여해 트랜잭션이 자신의 타임스탬프보다 이전 버전만 읽게끔 한다.
• 단편화: Fragmentation. 기억장치에서 자원이 여러 조각으로 나눠서서 낭비되는것. 기본적으로 필요한 크기의 연속된 공간을 할당할 수 없어 메모리 효율성이 저하되는것

두 접근 방식의 기본 trade-off#

Key_Takeaways

• Log-Structured는 쓰기에 최적화되어 있고, Page-Oriented는 읽기에 최적화
• Log-Structured는 append-only라 동시성 제어가 쉬움
• Log-Structured는 같은 데이터가 여러 곳에 저장되며 읽기 시 최신 파일을 찾기 위해 여러 파일을 확인할 필요가 있다.
• Log-Structured는 읽기 증폭 Page-Oriented는 쓰기 증폭
• Page Oriented는 페이지 단위 잠금을 지원해 트랜잭션 지원 용이
• Page Oriented는 random io 기반이라 Sequential io보다 느림
• Log-Structured의 대표는 LSM Tree, Page-Oriented의 대표는 B-Tree

Segmentation#

: 로그파일이 무한정 커지는 문제를 해결하기 위헤 일정 크기로 로그파일을 분할한것

Compaction#

: Compaction은 같은 키의 오래된 값이 누적되었을때 오래된 값을 정리하고 merge하는 방식으로 최신 값만 segment에 남기는 기법

Compaction 전략

1. 백그라운드 프로세스로 실행 (쓰기 차단 없음)
2. 여러 세그먼트를 하나로 병합
3. 중복 키 제거, 최신 값만 유지
4. 병합 완료 후 원본 세그먼트 삭제

Concept

• In-Memory HashMap 인덱스: 키를 바이트 오프셋에 매핑하는 메모리 해시 테이블. O(1) 조회 시간으로 빠른 읽기 제공. 단점은 모든 키가 메모리에 들어가야 하는것.
• 바이트 오프셋(Byte Offset): 파일 시작점부터의 거리(바이트 단위). seek() 시스템 콜로 해당 위치로 즉시 이동
• Log Segment: 로그 파일을 관리 가능한 크기(예: 1MB, 1GB)로 나눈 단위. 일정 크기 도달 시 닫고 새 세그먼트 생성. 각 세그먼트는 독립적인 인덱스 보유
• Compaction (압축): 여러 세그먼트를 병합하면서 중복된 키의 오래된 값을 제거하고 최신 값만 유지하는 과정. 백그라운드에서 수행되어 공간 회수 및 읽기 성능 향상 -fsync vs fdatasync: 디스크 쓰기 동기화 시스템 콜. 내구성(Durability) 보장 수준과 성능 trade-off
• Segment Merging: 여러 세그먼트를 하나로 합치는 과정. Compaction과 함께 수행되며, 세그먼트 수를 줄여 읽기 시 검색 범위 축소
• Sequential I/O: 디스크의 연속된 위치에 순서대로 읽거나 쓰는 방식. HDD에서 헤드 이동 최소화, SSD에서 캐시 효율 극대화
• Random I/O: 디스크의 임의 위치를 불규칙하게 접근. HDD에서는 매번 헤드 이동(5-10ms)으로 극도로 느림. B-Tree 등 페이지 기반 구조에서 불가피
• mmap (Memory-Mapped File): 파일을 메모리처럼 접근하는 기법. 인덱스를 디스크에 저장하고 mmap으로 로드하면 재시작 시 복구 빠름
• Tombstone (삭제 마커): 키 삭제 시 로그에 삭제 표시를 append. Compaction 시 제거