데이터 저장과 관련된 자료구조, 알고리즘과 분산 처리 방법에 관한 내용을 다루는 책
- DBMS 공통 컴포넌트 정의
- 표준화된 정의는 존재하지 않는다
- 트랜스포트: 클러스터 및 클라이언트 요청을 받는 부분
- 쿼리 프로세서: 파서와 옵티마이저를 통해 쿼리를 해석하고 최적화하여 실행 계획을 생성
- 실행 엔진: 생성된 실행 계획을 로컬쿼리로 스토리지 엔진에 전달하거나 원격 쿼리로 데이터 읽기, 쓰기 및 복제를 수행한다
- 스토리지 엔진
- MVCC나 슬롯 페이지 구조 방식을 이용하여 보통 여러 버전의 레코드를 저장한다
- 트랜잭션 매니저: 트랜잭션을 스케쥴링하고 논리적 일관성을 보장
- 잠금 매니저: 물리적 데이터 무결성을 위해 데이터베이스 객체에 대한 잠금을 제어
- 액세스 메서드: B-트리 등 자료구조를 이용하여 데이터에 대한 접근 및 저장 방식 정의
- 버퍼 매니저: 데이터 페이지를 메모리에 캐시한다
- 복구 매니저: 로그를 유지 관리하고 장애 발생 시 복구
- 데이터베이스의 종류 별 간략 비교
- 인메모리 Vs 디스크
- 주로 디스크 기반 자료 구조는 넓고 낮은 트리인 반면 인메모리는 다양한 자료구조를 사용한다
- 인 메모리는 큰 페이지 캐시를 사용하는 DBMS로 봐도 된다
- 디스크는 직렬화와 데이터 레이아웃을 유지해야하는 오버헤드가 존재한다
- 컬럼형 vs 로우형
- 로우형은 고유 식별 키로 구분할 수 있는 레코드에 형식에 적합하다
- 컬럼형은 특정 필드의 데이터 추세와 평균 등을 계산하는 집계형 작업에 적합하다
- 와이드 칼럼형
- 데이터를 다차원 맵으로 표현하고 여러 컬럼을 패밀리( 같은 자료형 ) 단위로 구분한다
- 패밀리의 데이터를 개별 로우형식으로 저장한다
- 데이터 파일과 인덱스 파일
- 데이터 파일(프라이머리 파일)
- 데이터가 레코드를 저장하는 파일
- 구조
- 힙: 삽입 순서대로 저장되는 구조
- 해시: 키의 해시 값에 해당하는 버킷에 저장하는 구조
- 인덱스(IOT): 인덱스에 실제 데이터 레코드를 저장
- 인덱스 파일
- 레코드를 효율적으로 검색할 수 있는 자료구조
- 기본(primary) 인덱스: 데이터 파일에 대한 인덱스
- 보조 인덱스: 데이터 레코드를 직접 가르키거나 해당 레코드의 기본키를 저장하는 레코드
- 클러스터형 인덱스: 레코드 정렬 순서와 검색 키 정렬 순서가 같은 인덱스
- 버퍼링, 불변성, 순서화
- 데이터베이스 자료 구조가 가진 공통적인 특성 → 안 쓸 수 있지만 가지고는 있는 특성
- 버퍼링: 디스크에 쓰기 전에 일부를 메모리에 저장하는 방식
- 가변성: 파일 일부를 읽고 갱신한 뒤에 똑같은 위치에 다시 쓸지 여부
- 순서화: 디스크 페이지에 레코드를 키 순서로 저장하는 것
- B+ 트리
- 디스크 기반 스토리지 엔진에 유용한 자료구조
- 높은 팬아웃(노드가 가질 수 있는 최대 자식 노드 수)과 낮은 트리 높이를 지니고 있어 디스크 탐색 회수가 적다
- 트리를 나누거나 합쳐 불균형을 제거하는 밸런싱의 빈도가 낮다
- 노드 키를 기준으로 정렬해서 저장하기에 키의 순서가 보장된다
- 리프 노드에만 값을 저장하며 상위 노드는 검색에 필요한 구분 키만 저장한다
- 구분키(인덱스 엔트리)
- 하위 자식 트리의 범위를 지정하는 키.
- 인접한 두 개의 키 사이의 범위를 포함하는 서브 트리를 가르키는 포인터를 가진다
- 노드 분할(승급): 새로운 노드를 할당해 키의 절반을 새로운 노드로 옮기고, 첫번째 키와 포인터를 부모 노드에 포함하는 방식으로 진행
- 노드 병합: 모든 키를 오른쪽 노드에서 왼쪽으로 복사하고, 부모 노드에서 오른쪽 노드를 가르키는 포인터를 제거한다
- B 트리의 변형
- B 트리: 루트부터 모든 레벨의 노드에 값을 저장할 수 있는 트리
- B*-트리: 루트가 아닌 노드를 2/3이상 채워져야 하는 트리
- 키 값과 포인터를 재분배하여 노드 분리보다 비용을 적게 하는 트리
- B-링크 트리: B*-트리에 하이키와 형제 링크 포인터를 추가한 자료 구조
- Copy-On-Write 트리
- 페이지를 복사하고 업데이트 한 뒤 링크 새로 연결하는 트리
- 장점: 래치가 필요 없기 때문에 리더를 동기화 하지 않아도 되며 리더가 라이터를 블록하지 않는다
- 단점: 메모리를 더 많이 쓰고 CPU 자원이 더 필요하다
- Lazy 트리
- 연속된 I/O 요청 횟수를 줄이기 위해 수정 내용을 페이지 단위 버퍼에 저장하는 트리
- 몽고 DB의 wiredTiger 엔진이 유사한 방식의 알고리즘을 사용한다
- 버퍼는 더 나은 동시성을 위해 스킵 리스트 자료구조를 기반으로 한다
- LA-트리 ( 지연 적응형 트리)
- Lazy 트리와 같이 수정 내용을 버퍼에 저장하는 트리
- 각 노드마다 업데이트 버퍼를 유지하지 않고 서브 트리 단위로 그룹화하여 버퍼를 공유
- 변경 사항이 상위 레벨 버퍼에서 하위 버퍼로 전파된다
- FD 트리
- 작은 크기의 B-트리를 버퍼로 사용하고 가득차면 내용을 불변 형태로 기록하는 트리
- 가변 헤드 트리와 여러 개의 정렬된 불변 배열로 구성된다
- 부분적 캐스케이딩을 이용하여 레벨 간 포인터를 유지하고 검색 성능을 높인다
- 정렬된 불변 배열을 이용하여 메모리 증폭 문제를 해결한다
- BW 트리
- 쓰기 증폭: 연속된 페이지 수정으로 인해 원본을 모든 요청마다 업데이트하는 안 좋은 상황
- B-트리 노드를 추가 전용 방식으로 기록되는 작은 그룹으로 나눠 여러 노드에 대한 쓰기 작업을 배치 단위로 처리하는 트리
- 추가 전용 스토리지를 사용해 여러 노드 업데이트를 일괄로 적용하고 연결해 체인을 형성한다
- 한번에 CAS(Compare And Swap)연산을 이용해 잠금(래치)이 필요 없는 트리 생성이 가능하다
- 파일 포맷
- 페이지: 일련의 레코드 또는 슬롯 페이지의 집합
- 디스크는 블록 단위로 읽는 특성 때문에 같은 블록에 대한 작업을 모아 처리한다면 I/O 작업 수를 줄일 수 있다
- 레코드를 저장하기 위해서는 데이터 블록을 할당하고 고정 크기의 기본형과 자료구조를 저장한다. 큰 메모리 청크 또는 가변 길이의 자료 구조는 포인터를 이용한다
- 탐색에 유용한 룩업 테이블을 유지하고 각 레코드의 시작점을 가리키는 오프셋은 헤더와 트레일러 또는 개별 파일에 저장한다
- 페이지 구조
- 고정 길이 구조: 가변 레코드를 효율적으로 처리 할 수 없고, 빈 공간이 아닌 곳에 키 추가 시 여러 원소 재배치가 필요하다
- 슬롯 페이지
- 오버 플로우 페이지
- 오른쪽 추가 기법
- 페이지 정리:
- 트랜잭션 처리와 복구
- 로그 구조 스토리지
- TPC-C: 일반적 어플리케이션의 워크로드를 시뮬레이션하는 온라인 트랜잭션 처리 벤치마크.
- 엔디언: 멀티 바이트 숫자 저장 시의 배열 순서를 정의
- 플래그: 묶음형 불리언과 열거형의 조합