포스트

데이터 중심 애플리케이션 설계03

게시
By seonb2n 12 분읽는 시간

저장소와 검색

데이터베이스의 기본적인 역할

  • 데이터 저장
  • 요청 시, 저장된 데이터 돌려주기

저장 엔진 아키텍처

  • 해시 인덱스 : 키-값 쌍을 파일에 추가하고, 인메모리 해시 맵으로 각 키의 데이터 오프셋을 저장
  • 컴팩션 : 로그에서 중복된 키를 버리고 각 키에 대한 최신 업데이만 유지해서 디스크 공간 회수

SS Table 및 LSM 트리

SSTable

  • SSTable은 로그 구조화 스토리지 세그먼트의 한 형태로, 키-값 쌍이 키에 따라 정렬되어 있는 파일 형식입니다. 이는 단순히 데이터를 기록된 순서대로 저장하는 해시 인덱스 기반의 로그 세그먼트와 구별되는 중요한 특징입니다.
  • 파일이 메모리보다 커도 세그먼트를 병합하는 것이 간단하고 효율적입니다. 이는 머지소트(mergesort) 알고리즘과 유사하게 작동하는데, 여러 입력 파일을 동시에 읽으면서 가장 낮은 키(정렬 순서에 따라)를 출력 파일에 복사하여 새로운 정렬된 세그먼트 파일을 생성합니다.
  • 희소(Sparse) 인메모리 인덱스: 모든 키에 대한 인덱스를 메모리에 유지할 필요 없이, 일부 키에 대한 오프셋만 메모리에 저장하는 희소 인덱스로 충분합니다. 정렬된 특성 덕분에, 메모리 내 인덱스가 가리키는 지점부터 몇 킬로바이트만 스캔하면 원하는 키-값 쌍을 빠르게 찾을 수 있습니다.
  • 정렬된 데이터는 압축률이 매우 높습니다. 키-값 쌍을 그룹화하여 압축된 블록으로 디스크에 기록하면 디스크 공간을 절약하고 I/O 대역폭 사용을 줄일 수 있습니다. 이러한 압축된 컬럼 데이터는 CPU의 L1 캐시에 효율적으로 적재되어 벡터화된 처리(vectorized processing)에 유리합니다.

LSM 트리

  • SSTable을 기반으로 하는 스토리지 엔진의 원리를 의미합니다. 이는 쓰기 작업을 순차적으로 로그에 기록하고, 주기적으로 정렬된 파일(SSTable)로 병합하여 효율적인 쓰기와 검색을 가능하게 합니다.
1
2
3
4
5
6
7
8

LSM-트리의 작동 방식:
1. 쓰기 요청 처리: 쓰기 요청이 들어오면, 먼저 인메모리 균형 트리 데이터 구조(예: 레드-블랙 트리)인 멤테이블(memtable)에 추가됩니다. 이 멤테이블은 키-값 쌍을 항상 정렬된 상태로 유지합니다.
2. 멤테이블 플러시(Flush): 멤테이블이 특정 임계값(일반적으로 몇 메가바이트)보다 커지면, 해당 내용은 SSTable 파일로 디스크에 기록됩니다. 멤테이블이 이미 정렬되어 있으므로 이 과정은 매우 효율적입니다. 새로운 SSTable 파일은 데이터베이스의 가장 최신 세그먼트가 되며, 이 파일이 디스크에 기록되는 동안에도 새로운 쓰기 요청은 새로운 멤테이블 인스턴스에 계속 기록될 수 있습니다.
3. 읽기 요청 처리: 읽기 요청이 오면, 먼저 현재 활성화된 멤테이블에서 키를 찾고, 그 다음에는 가장 최근에 디스크에 기록된 SSTable 세그먼트에서 찾고, 그 다음에는 더 오래된 세그먼트에서 순차적으로 찾아나갑니다.
4. 크래시 복구: 데이터베이스 충돌 시 멤테이블에만 존재하고 디스크에 기록되지 않은 최신 쓰기 요청이 손실되는 것을 방지하기 위해, 모든 쓰기는 별도의 디스크 로그(write-ahead log, WAL)에 즉시 추가됩니다. 이 로그는 정렬되지 않아도 되며, 오직 충돌 후 멤테이블을 복원하는 용도로만 사용됩니다. 멤테이블이 SSTable로 디스크에 기록될 때, 해당 WAL은 폐기될 수 있습니다.
5. 백그라운드 컴팩션: 주기적으로 백그라운드에서 세그먼트 파일 병합 및 컴팩션 프로세스가 실행되어 오래된 데이터(덮어쓰거나 삭제된 값)를 제거하고 디스크 공간을 회수하며 파일 수를 적게 유지합니다.

B 트리

설계 철학 및 작동 방식

  • B-트리는 키-값 쌍을 키 순서로 정렬하여 저장하며, 이를 통해 효율적인 키-값 조회 및 범위 쿼리를 가능하게 합니다.
  • 로그 구조화된 저장 엔진(예: SSTable)과는 달리, B-트리는 디스크를 고정 크기 페이지(page)의 집합으로 취급하며, 페이지를 덮어쓰는(update-in-place) 방식으로 데이터를 관리합니다.
  • 데이터를 삽입할 때 페이지가 가득 차면 페이지가 분할되고, 이로 인해 부모 페이지의 참조도 업데이트하기 위해 여러 페이지를 덮어써야 할 수 있습니다.

신뢰성 및 충돌 복구(Crash Recovery):

  • B-트리 구현은 데이터베이스 충돌에 대비하여 쓰기 전 로그(Write-Ahead Log, WAL) 또는 리두 로그(redo log)라고 불리는 추가 데이터 구조를 디스크에 포함하는 것이 일반적입니다.
  • 모든 B-트리 수정은 페이지에 적용되기 전에 먼저 WAL에 기록되어야 합니다.
  • 데이터베이스가 충돌 후 다시 시작될 때, 이 로그는 B-트리를 일관된 상태로 복원하는 데 사용됩니다.

동시성 제어(Concurrency Control):

  • 인 플레이스(in-place) 업데이트 방식 때문에 여러 스레드가 동시에 B-트리에 접근할 경우 신중한 동시성 제어가 필요합니다.
  • 이는 일반적으로 래치(latches)라는 경량 잠금으로 트리의 데이터 구조를 보호함으로써 이루어집니다.
  • 로그 구조화 방식은 백그라운드에서 모든 병합을 수행하고 주기적으로 이전 세그먼트를 새로운 세그먼트로 원자적으로 교체하기 때문에 이 점에서 더 간단합니다.

최적화 및 변형 (B+ 트리):

  • B-트리 페이지 공간을 절약하기 위해 전체 키를 저장하는 대신 키를 축약할 수 있습니다. 특히 트리 내부의 페이지에서는 키가 키 범위 사이의 경계 역할을 할 정보만 제공하면 됩니다.
  • 이러한 최적화를 통해 페이지에 더 많은 키를 압축할 수 있어 트리의 분기 계수(branching factor)를 높이고, 결과적으로 트리의 깊이를 줄일 수 있습니다.
  • 이러한 변형은 때때로 B+ 트리라고도 불리지만, 이 최적화가 너무 일반적이어서 다른 B-트리 변형과 구별되지 않는 경우가 많습니다.

SSTable 및 LSM-트리와의 비교:

  • B-트리 인덱스는 모든 데이터를 최소 두 번 써야 합니다: 한 번은 쓰기 전 로그에, 다른 한 번은 트리 페이지 자체에 (그리고 페이지가 분할될 때 다시 쓰여질 수도 있습니다).
  • 몇 바이트만 변경되더라도 페이지 전체를 한 번에 써야 하는 오버헤드도 있습니다.
  • 반면, 로그 구조화 저장 엔진은 랜덤 쓰기를 순차 쓰기로 전환하여 하드 드라이브 및 SSD의 성능 특성 덕분에 더 높은 쓰기 처리량(throughput)을 지원할 수 있습니다.
  • 로그 구조화 방식은 백그라운드에서 병합을 수행하며 들어오는 쿼리에 방해 없이 이전 세그먼트를 새 세그먼트로 원자적으로 교체합니다.

OLTP

  • 적은 수의 레코드를 키로 조회하며, 사용자 입력에 따른 무작위 접근 및 낮은 지연 시간의 쓰기가 주된 패턴

OLAP

  • 대량의 레코드를 집계하며, ETL 또는 이벤트 스트림을 통한 쓰기가 주된 패턴
  • 스타 스키마는 팩트 테이블과 차원 테이블로 구성되어 있음. 분석에 자주 사용되는 데이터 모델링
독서
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.