바닥부터 키-값 데이터베이스를 구축했다 — 그 과정에서 배운 것들

현대 스토리지 시스템은 단순히 데이터를 저장하는 것을 넘어,
성능, 안정성, 그리고 장애 복구 가능성을 동시에 고려한 설계를 기반으로 합니다.

Bitcask, Kafka, 그리고 LSM 기반 데이터베이스들은 공통적으로
순차 I/O를 최적화하고, 불변성을 유지하는 구조를 채택하고 있습니다.

이러한 설계 원리를 실제로 이해하기 위해,
간단한 Key-Value 스토리지 엔진인 KestrelCache를 직접 구현했습니다. 

이 글에서는 단순한 기능 소개가 아니라,
스토리지 엔진의 내부 구조와 설계 선택이 가지는 의미를 중심으로 설명합니다.

1. 문제 정의

스토리지 엔진의 핵심 질문은 다음과 같습니다:

데이터를 빠르고 안정적으로 저장하면서, 장애 상황에서도 정확성을 유지할 수 있는가?

전통적인 방식은 데이터를 in-place update로 처리합니다.

하지만 이 방식은 다음과 같은 문제를 발생시킵니다:
• 랜덤 디스크 I/O
• 복잡한 동시성 처리
• 데이터 파편화
• 어려운 장애 복구

KestrelCache는 이러한 문제를 피하기 위해
append-only 기반 로그 구조를 선택했습니다.

2. 시스템 구조

전체 시스템은 두 가지 핵심 구성 요소로 이루어집니다:

메모리 인덱스 (HashMap<Key, Offset>)
                ↓
Append-Only 로그 파일 (디스크)

각 계층의 역할은 명확합니다:
• 디스크 → 데이터의 영속성 보장
• 메모리 → 빠른 조회 성능 제공

이 시스템에서는 로그 파일이 유일한 진실(source of truth)입니다.

3. 쓰기 경로 (Write Path)

쓰기 연산 (Put)은 다음과 같은 순서로 처리됩니다:
1. key와 value를 바이트로 직렬화
2. CRC32 체크섬 생성
3. 로그 파일 끝에 append
4. 메모리 인덱스 업데이트

이 설계의 핵심 특징:
• 모든 쓰기는 순차적
• 기존 데이터를 절대 수정하지 않음
• 구조적으로 crash-safe

순차 디스크 쓰기는 랜덤 쓰기보다 훨씬 높은 성능을 제공합니다.

4. 읽기 경로 (Read Path)

읽기 연산 (Get)은 로그를 순회하지 않습니다.

대신:
1. 메모리 인덱스에서 key 조회
2. 해당 offset 획득
3. 디스크에서 직접 seek
4. 데이터 반환

이로 인해:
• 메모리에서는 O(1)
• 디스크 접근은 단 1회

→ 매우 빠르고 예측 가능한 성능을 제공합니다.

5. 삭제 처리 (Tombstone)

삭제는 실제 데이터 삭제가 아닌,
tombstone 레코드 추가로 처리됩니다.

[기존 데이터]
[tombstone 기록]

tombstone은 다음과 같이 표현됩니다:

ValueSize = -1

이 방식의 장점:
• 파일 재작성 불필요
• 쓰기 성능 유지
• 구조 단순화

하지만 디스크 공간이 계속 증가한다는 단점이 있습니다.

6. 디스크 저장 포맷

각 레코드는 다음과 같은 구조를 가집니다:

[CRC32][KeySize][ValueSize][Key][Value]

구성 요소:
• CRC32 → 데이터 무결성 검증
• KeySize / ValueSize → 경계 구분
• ValueSize = -1 → tombstone

이 구조는:
• 데이터 손상 감지
• 부분 쓰기 검출
• 안전한 복구

를 가능하게 합니다.

7. 메모리 인덱스 설계

인덱스는 단순한 구조입니다:

Dictionary<string, long>

각 key는 최신 데이터의 offset을 가리킵니다.

장점:
• O(1) 조회
• 낮은 복잡도

단점:

👉 전체 인덱스가 메모리에 올라가야 함
→ 데이터 규모가 커질수록 제한 발생

8. 복구 (Recovery)

시스템 시작 시:
1. 로그 파일을 처음부터 끝까지 스캔
2. 각 레코드의 checksum 검증
3. 인덱스 재구성

이 방식은:
• 매우 단순
• 높은 신뢰성

하지만:
• 로그가 커질수록 시작 시간이 증가

9. 로그 및 관측성 (Observability)

스토리지 시스템에서는 로그가 매우 중요합니다.

예시:

[INFO] key=user:1 offset=0 기록됨
[INFO] key=user:1 삭제됨 (tombstone)
[WARN] offset=170에서 checksum 오류 발생

로그는 다음을 가능하게 합니다:
• 디버깅
• 장애 분석
• 시스템 상태 이해

10. 장애 처리

이 구조는 여러 장애 상황을 자연스럽게 처리합니다.

쓰기 도중 크래시
• checksum으로 손상된 레코드 감지
• 이후 레코드 무시

데이터 손상
• CRC32로 검출 가능

전원 장애
• 기존 데이터는 그대로 유지
• append-only 구조로 안정성 확보

11. 성능 특성

장점
• 높은 쓰기 성능 (순차 I/O)
• 단순한 구조
• 안정적인 복구
• 빠른 조회

한계
• 파일 크기 지속 증가
• 메모리 의존 인덱스
• 범위 조회 불가
• 트랜잭션 없음

12. Compaction (필수 요소)

시간이 지나면:
• 오래된 데이터
• tombstone

이 누적됩니다.

Compaction 과정:

로그 스캔 → 최신 데이터만 유지 → 새 파일 생성

이 과정을 통해:
• 디스크 공간 회수
• 읽기 성능 개선

13. 설계 트레이드오프

스토리지 시스템은 결국
👉 트레이드오프의 선택입니다.

14. 핵심 배운 점

이 프로젝트를 통해 얻은 중요한 인사이트:
• 성능은 I/O 패턴에 의해 결정됨
• 순차 접근이 가장 중요함
• 단순한 구조가 더 안정적임
• observability는 필수
• 데이터 무결성은 기본 조건

그리고 가장 중요한 점:

좋은 시스템은 복잡함을 추가하는 것이 아니라,
복잡함을 통제하는 것에서 시작된다.

마무리

KestrelCache는 단순한 프로젝트이지만,
실제 스토리지 엔진의 핵심 원리를 그대로 담고 있습니다.

이러한 기본 구조를 이해하는 것은
백엔드 시스템, 데이터베이스, 분산 시스템을 이해하는 데 매우 중요합니다.