3장. 저장소와 검색

3장의 핵심 내용

• 저장소 엔진 개념
• 로그 구조 계열 저장소 엔진 & 페이지 지향 계열 저장소 엔진

데이터 베이스를 강력하게 만드는 데이터 구조

많은 데이터베이스는 내부적으로 추가 전용 데이터 파일인 로그를 사용
처음부터 끝까지 스캔하는 방식을 비효율적 O(n) -> 특정 키의 값을 효율적으로 찾기 위한 색인 필요

색인? : 데이터 위치 효율적 탐색 목적의 부가 메타 데이터. 질의 성능 개선 목적으로, 쓰기 성능에 부정적 영향.

해시 색인

• 해시 맵으로 구현
  • eg) 비트캐스크 엔진 : 인메모리 해시 맵 사용. 각 키의 값이 자주 갱신되는 상황에 적합. Riak의 기본 저장소 엔진.
• 특정 크기 세그먼트 -> 컴팩션 & 머지 통해 메모리 효율적 관리
  • 컴팩션 : 로그 내 중복 키 버리고 각 키의 최신 갱신 값만 유지
  • 컴팩션 & 세그먼트 병합 과정은 백그라운드에서 수행
• 실제 구현 시 고려사항
  • 파일 형식 : CSV No! 바이너리 형식 사용이 간단하고 더 빠름
  • 레코드 삭제 : 키와 관련된 삭제 시 툼스톤을 추가해야 함. 로그 세그먼트 병합될 때 툼스톤은 병합 과정에서 삭제된 키의 이전 값을 무시.
  • 고장 복구 : DB 재시작 시 인메모리 해시 맵은 손실 발생. 스냅샷을 디스크에 저장해 복구 속도 높일 수 있음.
  • 부분적으로 레코드 쓰기 : 로그에 레코드를 추가하는 과정에 DB가 죽을 수 있음. 비트캐스크 파일은 체크섬 포함. 로그 손상 부분 탐지 후 무시 가능.
  • 동시성 제어 : 세그먼트는 추가 전용 or 불변이기 때문에 다중 스레드로 동시 읽기 가능.

추가 전용 설계(로그) 장점

• 순차적인 쓰기 : 무작위 쓰기보다 빠름
• 동시성, 고장 복구 간단 : 세그먼트 파일의 추가 전용, 불변 특성 덕분.
• 오래된 세그먼트 병합은 시간이 지남에 따라 조각화되는 데이터 파일 문제 피할 수 있음.

해시 테이블 색인 제한 사항

• 메모리 : 키가 너무 많으면 메모리 문제. 해시 충돌 해소 회피 로직 필요.
• 범위 질의에 비효율

SS테이블 & LSM 트리

SS테이블 (Sorted String)

키로 정렬된 형식. 각 키는 각 병합된 세그먼트 파일 내 한 번만 나타남.

해시 색인 로그 세그먼트와 비교했을 때 장점

• 메모리 효율 : 병합정렬 알고리즘.
• 색인 효율 : 모든 키 색인 유지 불필요.
• I/O 대역폭 효율 : 희소 인메모리 색인의 각 항목은 압축된 블록의 시작을 가리킴

SS테이블 생성 & 유지

저장소 엔진 하위와 같이 작동

1. 쓰기 요청. 인메모리 균형 트리 데이터 구조(eg. 레드-블랙 트리)에 추가. 인메모리 트리 = 멤테이블(memtable)

2. 멤테이블 임계치 초과 시 SS테이블 파일로 디스크 기록. SS테이블 디스크 기록하는 동안 쓰기는 새로운 멤테이블 인스턴스에 기록

3. 읽기 요청
   1. 멤테이블에서 키 검색.
   2. 디스크 상의 가장 최신 세그먼트 검색. 두번째 세그먼트, 세번째, …

세그먼트 파일 합치고 덮어 쓰여지거나 삭제된 값을 버리는 병합과 컴팩션 과정 백그라운드 수행.

문제점 : DB 고장 시 디스크에 기록되지 않은 멤테이블 내 가장 최슨 쓰기는 손실. -> 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크 상에 유지.

SS테이블에서 LSM 트리 만들기

LSM 트리(Log-Structured Merge-Tree) : 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진. LSM 기본 개념 : 백그라운드에서 연쇄적으로 SS테이블을 지속적으로 병합하는 것

리악의 LevelDB, 카산드라, HBase 등에서 사용되는 저장소 엔진.

• LSM 트리 알고리즘은 데이터베이스에 존재하지 않는 키를 찾는 경우 느릴 수 있음 -> 블룸 필터 추가 사용. (집합 내용을 근사한 메모리 효율적 데이터 구조. 키가 데이터베이스에 존재 않음을 알려줌.)
• SS테이블 압축 전략
  • 크기 계층 전략 : 상대적으로 좀 더 새롭고 작은 SS테이블을 상대적으로 오래됐고 큰 SS테이블에 병합
  • 레벨 컴팩션 전략 : 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 레벨로 이동. 컴팩션을 점진적 진행.

B 트리

일반적으로 4KB 크기의 고정 크기 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기 수행.

가장 널리 사용되는 색인 구조.
각 페이지는 주소나 위치 이용해 식별 가능.
B 트리는 새로운 데이터를 디스크 상의 페이지에 덮어쓴다 (cf. 로그 구조화 색인은 파일이 추가되기 때문에 같은 위치의 파일은 변경되지 않음)

신뢰할 수 있는 B 트리를 위해 쓰기 전 로그(write-ahead log, WAL / 재실행 로그(redo log)라고도 함) 데이터 구조를 추가해 B 트리를 구현.

B 트리 장점 : 각 키가 색인의 한 곳에만 정확하게 존재

B 트리 vs LSM 트리 비교

• 읽기 : B 트리 > LSM 트리
  • why? LSM 은 각 컴팩션 단계에 있는 여러 데이터 구조와 SS테이블 확인 과정 필요
• 쓰기 : B 트리 < LSM 트리

LSM 트리 장단점

• 장점
  • 쓰기 처리량
  • 압축률
• 단점
  • 읽기 성능 : 컴팩션 과정의 영향. 컴팩션 연산이 디스크 성능에 영향
  • 높은 쓰기 처리량 : 컴팩션 과정과 공유하는 디스크 대역폭.

기타 색인

• 기본키, 보조 색인
• 힙 파일 : 로우가 저장된 곳
• 클러스터드 인덱스 : 색인 안에 바로 색인된 로우를 저장
  • MySQL 이노DB의 기본 키

트랜잭션 처리와 분석

온라인 트랜잭션 처리(OLTP) & 온라인 분석 처리 (OLAP)

• 온라인 트랜잭션 처리 : 색인을 사용하여 레코드를 찾거나, 사용자 입력을 기반으로 레코드를 삽입, 갱신하는 패턴
• 온라인 분석 처리 : 많은 수의 레코드를 스캔해 일부 칼럼만 읽어 집계 통계를 계산하는 등의 데이터 분석 목적의 처리 방식.
• 데이터 웨어하우스 : 높은 가용성과 낮은 지연을 핵심으로하는 OLTP 데이터 베이스와 달리, OLTP에 영향을 주지 않으면서 질의가 가능한 개별 데이터 베이스. 해당 데이터 베이스로 데이터를 가져오는 과정을 ETL(Extract-Transform-Load)라고 한다. 아파치 하이브, 스파크 SQL, 임팔라 등이 있음.
• 별 모양 스키마 : 데이터 웨어하우스에서 정형화된 데이터 모델링 방식. 특정 시각의 이벤트에 해당하는 레코드를 저장하는 사실 테이블과 이벤트의 속성인 누가, 언제, 어디서, 무엇을, 어떻게, 왜를 나타내는 차원 테이블로 구성된다. 이를 더 정규화하는 경우 눈꽃송이 모양 스키마라고 한다. 다만 작업의 편의성으로 눈꽃송이 모양 스키마보다 별 모양 스키마를 더 선호한다.

칼럼 지향 저장소

대부분의 OLTP 데이터베이스에서 저장소는 로우 지향 방식 데이터 배치.
모든 값을 하나의 로우에 함께 저장하지 않는 대신 각 칼럼별로 모든 값을 함께 저장. -> 질의에 필요한 칼럼만 읽고 분석 가능.
칼럼 지향 저장소 배치는 각 칼럼 파일에 포함된 로우가 모두 같은 순서.

비트맵 부호화방식을 사용하기도 하며, 더 나아가 런-랭스 부호화하는 경우도 있음.

원본 데이터의 비정규화된 복사본인 구체화 뷰(materialized view)를 통해 캐시 적용. 미리 계산했기 때문에 질의 시 매우 빠름. but, 질의 유연성이 떨어짐.