[DDIA] 03장. 저장소와 검색

 

 

들어가기 전에

데이터베이스가 저장과 검색을 내부적으로 처리하는 방법을 애플리케이션 개발자가 주의해야 하는 이유는 무엇일까?
특정 작업부하(workload) 유형에서 성능 개선을 위해 저장소 엔진을 조정하려면
엔진 내부의 작업에 대해 대략적인 개념을 이해할 필요가 있다.

 

 

[개념 사전]

단어	의미
로그(log)	추가 전용(append-only) 데이터 파일 (연속된 추가 전용 레코드, 특정 읽기 전용 프로그램만 읽을 수 있는 바이너리 등)
색인(index)	부가적인 메타데이터를 유지하는 것으로 원하는 데이터의 위치를 찾는 역할
바이트 오프셋(byte offset)	데이터 파일에서 값(value)을 바로 찾을 수 있는 위치 값
세그먼트(segment)	로그 구조화 색인이 데이터베이스를 나누는 단위
컴팩션(compaction)	로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것
툼스톤(tombstone)	특수한 삭제 레코드, 세그먼트 병합 과정에서 삭제된 키의 이전 값을 무시하게 하는 역할
병합정렬(mergesort)	분할 정복 알고리즘의 일종으로, 배열을 재귀적으로 반으로 나눈 뒤 정렬된 상태로 병합하여 정렬하는 알고리즘
멤테이블(memtable)	로그 기반 저장소 엔진에서 디스크에 데이터를 쓰기 전에 메모리에 유지하는 정렬된 데이터 구조
로그 구조화 병합 트리(LMS 트리, Log-Structured Merge-Tree)	로그 구조화 파일 시스템의 초기 작업의 기반이 된 구조 (기본 개념은 백그라운드에서 연쇄적으로 SS테이블을 지속적으로 병합하는 것)
LMS 저장소 엔진	정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진
루씬(Lucene)	엘라스틱서치나 솔라에서 사용하는 전문 검색 색인 엔진(용어 사전(term dictionary)을 저장, 검색 질의로 단어가 들어오면 단어가 언급된 모든 문서 조회)
블룸 필터(Bloom Filter)	집합 내용을 근사한(approximating) 메모리 효율적 데이터 구조, 키가 데이터베이스에 존재하지 않음을 고지하여 불필요한 디스크 읽기 리소스 절약)
크기 계층(size_tiered) 컴팩션	상대적으로 좀 더 새롭고 작은 SS 테이블을 상대적으로 오래됐고 큰 SS 테이블에 병합하는 전략
레벨 컴팩션(leveled compaction)	키 범위를 더 작은 SS 테이블로 나누고 오래된 데이터는 개별 “레벨”로 이동시키는 전략 (컴팩션을 점진적으로 진행, 디스크 공간 덜 사용)
분기 계수(branching factor)	B 트리의 한 페이지에서 하위 페이지를 참조하는 수
고아 페이지(orphan page)	어떤 페이지와도 부모 관계가 없는 페이지
쓰기 전 로그(WAL, write-ahead log) = 재실행 로그(redo log)	트리 페이지에 변경된 내용을 적용하기 전에 모든 B 트리의 변경 사항을 기록하는 추가 전용 파일 (데이터베이스 복구 시 B 트리를 복원하는 데 사용)
래치(latch)	가벼운 잠금(lock)
프랙탈 트리(fractal tree)	B-트리처럼 빠른 읽기 성능을 유지하면서도, LSM-트리처럼 빠른 쓰기 성능을 제공하는 하이브리드 트리 구조
쓰기 증폭(write amplification)	데이터베이스 쓰기 한 번이 데이터베이스 수명 동안 디스크에 여러 번의 쓰기를 야기하는 효과
트랜잭션 시맨틱(semantic)	데이터베이스에서 트랜잭션이 어떻게 동작해야 하는지 정의하는 개념적인 원칙
보조 색인	기본 키(Primary Key)가 아닌 다른 속성(컬럼)을 기준으로 추가하는 인덱스
클러스터드 색인	색인 안에 모든 로우 데이터를 저장하는 형태
비클러스터드 색인	색인 안에 데이터의 참조만 저장하는 형태
커버링 색인	색인 안에 테이블의 컬럼 일부를 저장하는 형태
결합 색인(concatenated index)	하나의 컬럼에 다른 컬럼을 추가하는 방식으로 하나의 키에 여러 필드를 결합하는 형태
편집 거리(edit distance)	문서나 질의의 오타에 대처하기 위해 쓰이는 개념(편집 거리 1은 한 글 자가 추가되거나 삭제되거나 교체됐음을 의믜)
유한 상태 오토마톤(finite state automaton)	특정 입력에 대해 정해진 규칙에 따라 상태를 변경하며 동작하는 모델
레벤슈타인 오토마톤(levenshtein automaton)	특정 편집 거리 내에서 효율적인 단어 검색 제공하는 유한 상태 오토마톤
온라인 트랜잭션 처리(OLTP, online transaction processing)	트랜잭션 처리 시스템으로 대량의 실시간 데이터 입력, 업데이트, 삭제를 처리하는 시스템 (은행 거래, 온라인 쇼핑몰 등에서 사용)
온라인 분석 처리(OLTP, online analytic processing)	대규모 데이터 분석 및 질의를 실시간으로 처리하는 시스템
사실 테이블(fact table)	데이터 웨어하우스에서 사실을 저장하는 테이블. 차원 테이블과 결합하여 분석
차원 테이블(dimension table)	사실 테이블의 수치적 데이터를 분석하기 위한 기준을 제공하는 테이블. (이벤트의 속성인 누가, 언제, 어디서, 무엇을, 어떻게, 왜를 나타냄)
비트맵 부호화(bitmap encoding)	데이터 값을 비트맵으로 표현하는 인코딩 방식. (빠른 검색 유리)
버블(bubble)	CPU 파이프라인에서 발생하는 불필요한 명령어 지연
단일 명령 다중 데이터(SIMD, Single Instruction Multi Data)	하나의 명령어가 여러 데이터를 동시에 처리하는 기술. (벡터화 처리를 통한 성능 향상에 사용)
타이트 루프(Tight Loop)	반복문 내에서 빠르게 실행되는 루프. 반복문 조건이 매우 간단하거나 고정되어 있음.
벡터화 처리(vectorized processing)	여러 데이터 요소를 동시에 처리할 수 있는 기술

 

 

[특징에 따른 데이터베이스 제품 분류]

❶ 관계형 모델의 인메모리 데이터베이스

• 볼트DB(VoltDB), 멤SQL(MemSQL), 오라클 타임즈텐(Oracle TimesTen)
• 디스크 상 데이터 구조 관리와 관련된 오버헤드를 모두 없애 성능 크게 개선

❷ 지속성 있는 오픈소스 인메모리 키-값 저장소

• 램클라우스(RAMCloud)

❸ 비동기로 디스크에 기록되기 때문에 약한 지속성 제공

• 레디스(Redis), 카우치베이스(Couchbase)

 

03장. 저장소와 검색

[핵심 내용]

이번 장에서는 데이터베이스가 어떻게 저장과 검색을 다루는지 배운다. 고수준에서 저장소 엔진은 OLTP(트랜잭션 처리 최적화)와 OLAP(분석 최적화)라는 범주로 나뉘는데, 엔진 내부에 대한 지식을 통해 어떤 도구가 어떤 상황에서 가장 적합한지 판단하기 위함이 목표이다. 

 

새롭게 알게된 점(New)

[1] 추가 전용 설계가 좋은 설계인 이유

• 추가와 세그먼트 병합이 순차적인 쓰기 작업이기에 무작위 쓰기보다 훨씬 빠르다.
• 세그먼트 파일이 추가 전용이나 불변이면 동시성과 고장 복구가 훨씬 간단하다. (이전 값 부분과 새로운 값 부분을 포함한 파일을 나누어 함께 남겨두기 때문에)
• 오래된 세그먼트 병합이 조각화되는 데이터 파일 문제를 피할 수 있다.

 

[2] SS 테이블과 멤 테이블

• 데이터 읽기
  • 요청을 효율적으로 처리하기 위해 레코드들을 블록 단위로 그룹화하고 디스크에 쓰기 전에 압축한다.
  • SS 테이블 내의 인덱스는 모든 키를 직접 가리키지 않고, 블록의 시작 위치를 가리킨다.
  • 요청 시 먼저 멤테이블에서 키를 찾고, 디스크 상의 가장 최신 세그먼트부터 그다음 오래된 세그먼트 순으로 찾는다.
  • 블룸 필터(Bloom Filter)를 사용해 키가 데이터베이스에 존재하지 않을 때를 알려 불필요한 디스크 읽기를 절약할 수 있다.
• 데이터 쓰기
  • 요청 시 멤테이블(memtable)(인메모리 균형 트리 데이터 구조)에 레코드를 추가하고, 임곗값보다 커지면 SS 테이블 파일로 디스크에 기록한다.
• 병합 전략
  • 크기 계층(size-tiered) : 상대적으로 좀 더 새롭고 작은 SS 테이블을 상대적으로 오래됐고 큰 SS 테이블에 병합하는 전략
  • 레벨 컴팩션(leveled compaction) : 키 범위를 더 작은 SS 테이블로 나누고 오래된 데이터는 개별 레벨로 이동하는 전략 (컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용함)
• 데이터베이스가 고장났을 때, 멤테이블에 있는 최신 레코드가 손실되는 문제를 해결하기 위해 디스크 상에 로그를 유지해야 한다. (SS 테이블 저장 뒤 제거)

 

[3] LMS 트리

낮은 비용으로 색인을 제공하며 고성능의 데이터 타입과 삭제를 지원하는 디스크 기반의 자료구조
a disk-bsed data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period
- Patrik O’Neil

• 백그라운드에서 연쇄적으로 SS 테이블을 지속적으로 병합한다.
• 데이터가 정렬된 순서로 저장돼 있다면 질의를 효율적으로 실행할 수 있다.
• 쓰기 증폭(write amplification)이 낮고 순차적으로 컴팩션된 SS 테이블 파일을 쓰기 때문에 높은 쓰기 처리량을 보장할 수 있다.

 

[4] B 트리

• B 트리의 기본적인 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어쓴다.

 

[5] 온라인 트랜잭션 처리(OLTP) 시스템과 온라인 분석 처리(OLAP) 시스템

특성	OLTP	OLAP
주요 읽기 패턴	질의당 적은 수의 레코드, 키 기준으로 가져옴	많은 레코드에 대한 집계
주요 쓰기 패턴	임의 접근, 사용자 입력을 낮은 지연 시간으로 기록	대규모 불러오기(bulk import, ETL) 또는 이벤트 스트림
주요 사용처	웹 애플리케이션을 통한 최종 사용자/소비자	의사결정 지원을 위한 내부 분석가
데이터 표현	데이터의 최신 상태(현재 시점)	시간이 지나며 일어난 이벤트 이력
데이터셋 크기	기가바이트에서 테라바이트	테라바이트에서 페타바이트

 

 

[6] 데이터 웨어하우징

데이터 웨어하우스(Data Warehouse)
분석가들이 OLTP 작업에 영향을 주지 않고 마음껏 질의할 수 있는 개별 데이터베이스

• ETL(Extract-Transform-Load)
  • Extract : OLTP 데이터베이스에서 주기적인 데이터 덤프나 지속적인 갱신 스트림으로 데이터 추출
  • Transform : 분석 친화적인 스키마로 변환 후 정리
  • Load : 데이터 웨어하우스에 적재
• 분석용 스키마
  • 별 모양 스키마(star shema)(차원 모델링(dimensional modeling)
  • 데이터 웨어하우스가 사용하는 정형화된 방식으로, 테이블 관계가 시각화될 때 사실 테이블이 가운데에 있고 차원 테이블로 둘러싸고 있는 모양으로 보인다.
  • 눈꽃송이 모양 스키마(Snowflake schema)
  • 차원 테이블의 계층적 형태를 포함하는 스키마이다.
• 데이터 큐브(Data Cube, = OLAP 큐브)
  • 집계 데이터 캐시를 만들기 위해 구체화 뷰(materialized view)를 사용한다.
  • 특정 질의를 효과적으로 미리 계산했기 때문에 해당 질의 수행 속도를 높일 수 있다.
  • 원시 데이터에 질의하는 것과 동일한 유연성이 없다.

 

[7] 컬럼 지향 저장소

• 모든 값을 하나의 로우에 함께 저장하지 않고, 각 컬럼 별로 모든 값을 함께 저장한다.
• 저장소 배치는 각 컬럼에 포함된 로우가 모두 같은 순서이므로, 전체 값을 다시 모으려면 각 컬럼 파일의 n번째 항목을 가져오면 된다.
• 컬럼 데이터를 암축해 디스크 처리량을 줄일 수 있다.

 

어려웠거나 이해하지 못한 부분(Difficulty)

• 페이지에 전체 키를 저장하는 게 아니라 키를 축약해 쓰면 공간을 절약할 수 있다. (페이지 하나에 키를 더 많이 채우면 트리는 더 높은 분기 계수를 얻는다. 그러면 트리 깊이 수준을 낮출 수 있다.)

 

추가 내용(Amendment)

[1] Key Compression (키를 어떻게 축약하는가?)

• 키 값을 압축하거나 단순화해서 저장 공간을 절약하는 방식
• Prefix 축약 (e.g. CUBRID 인덱스 prefix compression 소개와 활용)
• 비트맵 인코딩 등

 

[2] 아파치 HBase

하둡 플랫폼을 위한 공개 비관계형 분산 데이터베이스.
압축, 인메모리 처리, 초기 빅테이블에 제시되어 있는 Bloom Filter 기능을 제공한다. HBase에 있는 테이블들은 하둡에서 동작하는 맵리듀스 작업을 위한 입출력을 제공하며, 자바 API 등을 통해 접근할 수 있다.
출처: 위키백과

 

HBase 데이터 저장 구조 (출처: https://newstellar.tistory.com/5)

종류	쓰기	읽기
특징	- 데이터를 쓰기 전 Region Server와 통신하여 WAL 파일에 해당 데이터를 추가한다. - 추가된 데이터는 MemStore에 복사된다. - MemStore의 임계점에 이르면, 데이터들을 HFile에 dump 혹은 commit한다. | - 읽기 요청을 하면 Scanner가 Block cache에서 Row cell을 찾는다.	- Scanner의 탐색 실패 시, MemStore로 이동하여 dump 이전의 데이터가 남아있는지 검색한다. - MemStore에서도 발견하지 못했다면 Bloom Filter와 Block Cache를 이용하여 HFile로부터 데이터를 가져온다.

• Region Server
  • 분산 데이터베이스 시스템에서 사용되는 서버(데이터의 지역성을 관리하고 처리하는 역할)
  • 구성 요소
    • MemStore
    • HFile : 데이터를 디스크에 저장하는 파일 포맷
    • Block Cache : 디스크에서 읽어야 할 데이터를 블록 단위로 메모리에 캐시
    • WAL(Write-Ahead Log)
• Block Cache : 디스크에서 읽어야 할 데이터를 블록 단위로 메모리에 캐시

 

[3] 추가로 볼 자료

바닥까지 파보는! HBase random read 성능 개선기 (자료, 영상)

• Compaction, BF로 인한 Read Amplification 감소 등에 관한 내용과 더불어 데이터 블록 크기에 따른 캐시 활용도 문제를 언급하고 성능 최적화 방법을 소개하는 세션
• 개념
  • Read Amplification : 데이터베이스나 저장 시스템에서 불필요한 읽기 작업이 발생하는 현상
  • Cache Pollution Problem : 큰 데이터 블록에서 캐시 활용도가 떨어지는 현상

 

참고

• SS Table과 SML Tree 비교