데이터베이스에 데이터를 저장하는 방식과 분산 시스템의 일관성을 유지할 때 사용되는 개념과 알고리즘을 설명한다. 나아가 이들을 개선하기 위해 등장한 여러 새로운 알고리즘도 설명한다. 최신 분산 시스템과 논문에서 찾아볼 수 있는 개념들과 관련 문헌을 정리한 이 책을 통해 데이터베이스에 어떤 고질적인 문제가 있는지, 이들을 어떻게 해결할 수 있으며 또 어떤 새로운 연구들이 진행되고 있는지 배우게 될 것이다.

[목 차]

1부. 스토리지 엔진

1장. 소개 및 개요
__DBMS 구조
__인메모리 DBMS 대 디스크 기반 DBMS
__칼럼형 DBMS 대 로우형 DBMS
__데이터 파일과 인덱스 파일
__버퍼링과 불변성, 순서화
__요약

2장. B-트리 개요
__이진 탐색 트리
__디스크 기반 자료 구조
__디스크 기반 자료 구조
__유비쿼터스 B-트리
__요약

3장. 파일 포맷
__파일 포맷의 중요성
__바이너리 인코딩
__파일 포맷 설계 원칙
__페이지 구조
__슬롯 페이지
__셀 구조
__셀 병합으로 슬롯 페이지 구성
__가변 길이 데이터 관리
__버전 관리
__체크섬
__요약

4장. B-트리 구현
__페이지 헤더
__이진 검색
__분할과 병합
__탐색 경로
__리밸런싱
__오른쪽 추가 기법
__압축
__정리와 유지
__요약

5장. 트랜잭션 처리와 복구
__버퍼 관리
__복구
__동시성 제어
__요약

6장. B-트리의 변형
__쓰기 시 복사
__노드 업데이트 추상화
__지연형 B-트리
__FD-트리
__Bw-트리
__캐시 비인지형 B-트리
__요약

7장. 로그 구조 스토리지
__LSM 트리
__읽기, 쓰기, 메모리 공간 증폭
__세부 구현 설명
__비정렬 LSM 스토리지
__LSM 트리 동시성 제어
__로그 스태킹
__LLAMA와 투명한 스태킹
__요약

2부. 분산 시스템

8장. 분산 시스템 개요
__동시 수행
__분산 컴퓨팅의 오류
__클럭과 시간
__분산 시스템 추상화
__장애 모델
__요약

9장. 장애 감지
__하트비트와 핑
__파이 누적 장애 감지
__가십과 장애 감지
__장애 전파를 사용한 문제 해결
__요약

10장. 리더 선출
__불리 알고리즘
__다음 서열로 리더 역할 승계
__후보/일반 노드 최적화
__초대 알고리즘
__링 알고리즘
__요약

11장. 복제와 일관성
__고가용성
__ CAP 이론
__수확률과 산출률
__공유 메모리
__순서화
__일관성 모델
__세션 모델
__결과적 일관성
__조정 가능한 일관성
__증명 복제 노드
__강력한 결과적 일관성과 CRDTs
__요약

12장. 안티-엔트로피와 배포
__읽기 복구
__다이제스트 읽기
__힌트 핸드오프
__머클 트리
__비트맵 버전 벡터
__가십 전파
__요약

13장. 분산 트랜잭션
__원자적 연산처럼 수행하기
__2단계 커밋
__3단계 커밋
__칼빈의 분산 트랜잭션 처리
__스패너의 분산 트랜잭션 처리
__데이터베이스 파티셔닝
__퍼콜레이터의 분산 트랜잭션 처리
__코디네이션 생략
__요약

14장. 합의
__브로드캐스트
__원자적 브로드캐스트
__팍소스
__래프트
__비잔틴 합의
__요약

부록 A. 참고문헌

★ 이 책에서 다루는 내용 ★

이 책은 관계형 DBMS나 NoSQL 시스템에 관한 책이 아니다. 대신 다양한 종류의 데이터베이스 시스템에서 사용되는 알고리즘과 개념을 스토리지 엔진과 분산 저장을 담당하는 컴포넌트에 초점을 두고 설명한다.
쿼리 계획과 쿼리 최적화, 스케줄링, 관계형 모델 등의 주제는 여러 훌륭한 이론서에서 쉽게 접할 수 있다. 이들은 대부분 사용자의 관점에서 각 주제를 설명하지만 이 책은 데이터베이스의 내부 구조를 집중적으로 설명한다.
이 책에서 언급된 데이터베이스 시스템 간의 공통적 언어는 없기 때문에 쿼리 언어는 다루지 않는다. 이 책을 집필하고자 15권의 책과 300편 이상의 논문, 수많은 블로그 글, 소스 코드, 여러 오픈소스 데이터베이스의 기술 문서를 참고했다. “데이터베이스 업계와 연구자들이 이 주제에 대해 논의하는가?”라는 질문의 답을 기반으로 주제를 책에 포함할지 여부를 결정했다. 답이 “그렇다”라면 주저 없이 긴 목록에 추가했다.

■ 스토리지 엔진: 스토리지 종류와 분류법을 알아보고 B-트리 기반과 불변 로그 구조 기반의 스토리지 엔진을 설명한다.
■ 스토리지 구성 요소: 페이지 캐시와 버퍼 풀과 같은 보조 자료 구조를 사용해 데이터베이스 파일을 효율적으로 저장하는 스토리지 구축 방법을 설명한다.
■ 분산 시스템: 노드 및 프로세스가 서로 어떻게 연결되고 복잡한 통신 패턴을 형성할 수 있는지 단계별로 설명한다.
■ 데이터베이스 클러스터: 최신 데이터베이스에서 사용되는 일관성 모델과 분산 스토리지 시스템이 일관성을 보장하는 방법을 설명한다.

★ 이 책의 대상 독자 ★

여러 중요한 데이터베이스 시스템 관련 개념을 쉽게 설명한다. 각 개념을 더 깊이 알고 싶은 독자에게 지침서가 될 것이다. 이미 모두 익숙한 개념이라면 참고서로 도움될 것이다.
이 책의 대상 독자는 데이터베이스 개발자만이 아니다. 데이터베이스 시스템을 사용해 소프트웨어를 개발하는 소프트웨어 개발자와 신뢰성 엔지니어, 아키텍트, 엔지니어링 매니저에게도 도움이 될 것이다.
회사에서 데이터베이스, 메시징 큐, 컨테이너 플랫폼, 태스크 스케줄러 등의 인프라를 사용 중이라면 해당 프로젝트의 변경 로그를 읽고, 메일링 리스트에 가입하고, 커뮤니티와 교류해 프로젝트에 관한 최신 정보를 항상 알고 있어야 한다. 시스템에 관련된 용어와 내부 구조를 이해하면 더 많은 정보를 알아낼 수 있으며 좀 더 효율적으로 툴을 사용해 문제와 병목현상을 방지, 식별 및 해결할 수 있다. 데이터베이스 시스템의 동작 방식에 대한 전반적인 이해는 문제를 해결하는 데 많은 도움이 될 것이다. 이런 지식을 바탕으로 가설을 형성하고 검증한 뒤에 원인을 찾아 다른 프로젝트 관리자에게 알리는 것은 중요하다.
또한 취미로 컴파일러를 만들고 직접 운영체제와 텍스트 에디터, 컴퓨터 게임을 개발하거나 새로운 프로그래밍 언어를 학습하는 등 새로운 정보를 습득하길 좋아하는 호기심 많은 사람들에게 도움이 될 것이다.
아울러 독자는 백엔드 시스템 개발 시 또는 사용자로 데이터베이스 시스템을 이용해본 경험이 있을 거라고 가정한다. 자료 구조에 관한 사전 지식이 있다면 내용을 더 빨리 이해할 수 있을 것이다.

★ 이 책의 구성 ★

데이터베이스 시스템 간의 가장 중요한 차이점은 데이터 저장 방법과 분산 처리 방법에 있다(다른 중요한 서브시스템이 있을 수 있지만 이 책에서는 다루지 않는다). 이 책은 스토리지(1부)와 분산(2부)을 담당하는 서브시스템 및 구성 요소에 관한 설명으로 이뤄져 있다.
1부에서는 노드 로컬 프로세스를 논의하고, 데이터베이스 시스템의 핵심 구성 요소이며 가장 중요한 스토리지 엔진을 설명한다. DBMS의 구조에 대한 설명으로 시작해 기본 저장 매체 및 레이아웃을 기반으로 데이터베이스 시스템을 분류하는 몇 가지 방법을 소개한다.
이어 스토리지 구조를 설명한다. 디스크 기반 자료 구조와 인메모리 자료 구조의 차이점을 알아보고 B-트리 알고리즘과 직렬화, 페이지 레이아웃, 디스크에서의 표현 방식 등의 B-트리를 효율적으로 디스크에 저장하는 데 필요한 개념을 설명한다. 나아가 B-트리에서 파생된 여러 다양한 변형 B-트리도 소개한다.
마지막으로 몇 가지 로그 구조 스토리지 변형을 설명하고 왜 파일 및 스토리지 시스템 구현에서 자주 사용되는지 알아본다.
2부에서는 여러 독립적인 노드를 데이터베이스 클러스터로 구성하는 방법을 설명한다. 장애 허용 분산 시스템을 구축하는 데 필요한 이론적 개념을 설명하고 분산 시스템이 단일 노드 애플리케이션과 어떻게 다르고 분산 환경에서 어떤 문제와 제약, 복잡성이 발생할 수 있는지 알아본다.
이어 분산 알고리즘을 설명한다. 장애 감지 시 이를 보고하고 장애가 발생한 노드는 시스템에서 제외시켜 성능과 안정성을 높일 수 있는 장애 감지 알고리즘을 설명한다. 뒷장에서 설명하는 대부분의 알고리즘은 리더 프로세스가 필요하기 때문에 리더 선출 알고리즘과 사용 사례에 대해서도 논의한다.
분산 시스템에서 가장 어려운 부분은 데이터의 일관성을 유지하는 것이기 때문에 데이터 이중화, 일관성 모델, 복제본 간의 불일치, 결과적 일관성 등의 개념도 설명한다. 결과적 일관성을 보장하는 시스템에서 데이터의 일관성을 유지하기 위해 사용하는 안티-엔트로피 알고리즘과 데이터 전파를 위해 사용하는 가십 프로토콜도 알아본다. 마지막으로 데이터베이스 트랜잭션의 맥락에서 논리적 일관성을 논의하고, 합의 알고리즘에 관한 설명으로 마무리한다.

★ 옮긴이의 말 ★

이 책을 번역하는 데 생각 이상으로 오랜 시간이 걸렸다. 학교에서 공부하기도 했고 업무에서도 종종 논의한 개념이기 때문에 꽤 알고 있다고 생각했지만 오산이었다. 여러 번 읽고 다른 자료들도 참고해야 어느 정도 이해할 수 있었다. 데이터베이스 분야는 번역 용어가 아직 정립되지 않았다는 것도 몸소 느꼈다. 일반적으로 원서와 영어 논문을 참고하다 보니 영어가 더 익숙한 용어들을 굳이 번역해야 하나 싶기도 했다. 예를 들어 ‘READ UNCOMMITTED’ 격리 수준을 ‘커밋 전에 읽기’라고 부르는 경우는 흔하지 않다. 하지만 어색하더라도 의미가 더 잘 와 닿는다면 좋은 시도라고 생각한다.
이 책은 데이터베이스를 지탱하는 알고리즘을 설명하고 최신 논문과 시스템에서만 접할 수 있는 관련 개념들을 정리한 책이다. 데이터베이스를 공부하는 학생과 현업 개발자 그리고 특히 여러 최신 데이터베이스의 원리와 기술을 숙지해야 하는 데이터베이스 연구자들을 위한 책이다. 관계형 데이터베이스 시스템을 사용해봤고, 분산 시스템을 사용해 새로운 시스템을 구축하려는 개발자라면 많은 도움이 될 것이다. 이미 검증된 라이브러리가 많아서 직접 알고리즘을 작성하거나 데이터베이스 엔진을 개발하는 일은 흔하지 않다. 하지만 이론과 알고리즘을 이해하는 정도는 컴퓨터 과학자와 일반 개발자를 나누는 기준이 되며, 최선의 해결책을 찾는 데 결정적인 역할을 한다. 이 책은 데이터베이스 개발자라면 반드시 알아야 하는 분산 시스템의 기본 이론 및 알고리즘을 설명하는 책이다.
데이터베이스별로 어떤 기능이 있는지, 얼마나 빠른지 또 어떤 유형의 애플리케이션에서 사용되는지 등의 실용적인 측면은 다루지 않는다. SQL과 같은 쿼리 언어와 쿼리 플랜도 설명하지 않는다. MySQL과 오라클 중에 어떤 것을 선택해야 할지 고민 중이거나, 1억 건이 넘는 로우를 어떤 데이터베이스에 저장해야 할지 고민 중이라면 이 책은 도움이 되지 않을 것이다. 대신 데이터베이스 이론과 알고리즘을 스토리지 관점에서 설명하고, 분산 시스템의 기본 개념과 알고리즘을 설명한다. 다른 이론서와의 차이점은 기존 알고리즘을 개선한 여러 변형 알고리즘도 설명한다는 점이다. 최신 분산 시스템에서 사용되는 알고리즘이 궁금하다면 많은 도움이 될 것이다.
1부(1~7장)는 데이터베이스에 데이터를 저장하는 방식에 대해 설명한다. 데이터베이스에서 가장 중요한 B-트리 알고리즘을 설명하고 캐시 정책, 복구, 동시성 제어 등의 중요한 주제도 다룬다. 6장과 7장이 1부의 핵심이다. Lazy B-트리와 Bw-트리, LSM 트리, Wisckey 등의 변형된 B-트리를 설명한다.
2부(8~14장)는 분산 데이터베이스 시스템의 일관성을 유지하기 위해 사용되는 알고리즘에 대해 설명한다. 장애 감지, 리더 선출, 안티 엔트로피, 분산 트랜잭션, 합의 알고리즘 등을 다룬다. 분산 시스템은 여러 노드로 구성되기 때문에 이들 사이에는 서로의 문제를 감지하고, 작업을 나눠서 실행하고, 상태에 대한 합의를 하는 알고리즘이 필요하다.
각 주제를 더 알고 싶다면 각 장 끝에 정리된 문헌과 논문을 꼭 참고하길 바란다. 인터넷에서 관련 자료와 예제를 찾아보는 것도 많은 도움이 될 것이다.



추천사

마이클 클리신(Michael Klishin)(오래된 RabbitMQ 커미터)
작업에 적합한 도구를 찾으려면 도구의 내부 구조와 알고리즘을 이해해야 한다. 이 책은 여러 데이터베이스 관련 주제에 대해 데이터베이스 전문가가 직접 쓴 입문서다.


네이트 맥콜(Nate McCall)(아파치 카산드라 커미터, PMC 의장)
데이터베이스 기술을 다루는 모든 사람에게 꼭 필요한 책이다. 특히 어떤 데이터베이스 시스템을 사용할지 결정해야 하는 상황이라면 큰 도움이 될 것이다.

알렉스 페트로프(Alex Petrov)
데이터 인프라 엔지니어이자 아파치 카산드라 커미터, PMC 멤버다. 주요 연구 분야는 데이터베이스와 스토리지 시스템이며 스토리지와 분산 시스템, 알고리즘에 관심이 많다.