Search
📖

[데이터 중심 애플리케이션 설계] 3. 저장소와 검색 (2)

Created
2023/02/13 13:30
Tags
Review
Book
Architcture
Study
Last edited time
2023/05/02 11:00
Status
Done

내용 정리

1. B 트리

1.1. 정의

보편적인 색인 구조
전통적으로 4KB 크기(때로는 더 큰)의 고정 크기 블록 또는 페이지로 나눔 한번에 하나의 페이지에 읽기 또는 쓰기를 진행
디스크가 고정 크기 블록으로 배열되기 때문에, 근본적으로 하드웨어와 더 밀접한 관련이 있음
각 페이지는 주소나 위치를 이용해 식별 가능
이 방식으로 하나의 페이지가 다른 페이지 참조 가능
포인트와 비슷한 개념이나 메모리가 아닌 디스크에 존재

1.2. 특징

정렬된 키-값 쌍으로 유지 → 키-값 검색 및 범위 질의에 효율적
관계형 데이터 베이스의 표준 색인 구현 (비관계형 데이터베이스에서도 많이 활용)
탐색 방식 (색인)
한 페이지는 B 트리의 루트(root)로 지정
색인에서 키를 찾으려면 루트에서 시작
페이지는 여러 키와 하위 페이지의 참조를 포함
각 하위페이지에 저장된 키가 계속 이어지는 범위를 담당
참조 사이의 키는 해당 범위의 경계가 어디인지 나타냄
최종적으로 개별 키(리프 페이지; leaf page) 를 포함하는 페이지에 도달
이 페이지는 각 키의 값을 포함 하거나 값을 찾을 수있는 페이지의 참조를 포함
분기 계수
B 트리의 한 페이지에서 하위 페이지를 참조하는 수
값 갱신 및 추가
갱신
키를 포함하고 있는 리프 페이지 검색 후 페이지의 값을 바꾼 다음, 페이지를 디스크에 기록
페이지에 대한 모든 참조는 계속 유효함
추가
새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가
새로운 키를 수용한 페이지에 여유 공간이 없는 경우
페이지를 반으로 나눔
상위 페이지가 새로운 키 범위의 하위 부분을 알 수 있게 갱신
위 알고리즘은 트리가 계속 균형을 유지하는 것을 보장함

1.3. 시간복잡도

N개의 키를 가진 B 트리의 깊이는 항상 O(logN)이다.
대부분의 데이터베이스는 B 트리의 깊이가 3~4단계에서 충분히 검색 가능
분기 계수 500의 4KB 페이지의 4단계 트리는 256TB의 3승까지 저장 가능

1.4. 신뢰할 수 있는 B트리 만들기

쓰기 동작
새로운 데이터를 디스크 상의 페이지에 덮어씀
덮어쓰더라도 페이지를 가리키는 모든 참조는 온전히 남음
cf)
로그 구조화 색인은 파일에 추가함. 같은 위치의 파일은 변경하지 않음
쓰기 전 로그 (Write-ahead log, WAL; 재실행 로그)
여러 페이지를 덮어 써야 하는 경우, 일부만 기록되고 DB가 고장난다면 고아 페이지가 발생할 수 있음
데이터베이스 고장상황에서 스스로 복구할 수있게 만들기위해 디스크 상에 WAL이라고 하는 데이터 구조를 추가해 B 트리를 구현
트리 페이지에 변경된 내용을 적용하기전에 모든 B 트리의 변경사항을 기록하는 추가 전용 파일
데이터 베이스 고장 이후 복구될 때 일관성 있는 상태로 B 트리를 다시 복원하는데 사용
동시성 제어
다중 스레드가 동시에 B 트리에 접근하는 경우
래치(latch): 가벼운 잠금으로 트리의 데이터 구조를 보호

1.5. B 트리 최적화

쓰기시 복사 방식 (Copy-on-write schema)
페이지 덮어 쓰기와 고장 복구를 위한 WAL 유지 대신 일부 데이터베이스에서 사용
변경된 페이지는 다른 위치에 기록
트리에 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가리키게 함
동시성 제어에도 유용
페이지에 키를 축약하여 공간 절약
리프 페이지를 디스크 상에 연속된 순서로 나타나게끔 트리 배치
트리에 포인터 추가
리프 페이지 양쪽에 형제 페이지에 대한 참조를 가지면 순서대로 키 스캔 가능
B+트리
프랙탈 트리

1.6. B트리 vs LSM 트리

LSM 트리 장점
B 트리 색인은 모든 데이터 조각을 최소한 두번 기록 해야 함
쓰기전 로그 & 트리 페이지
로그 구조화 색인
SS 테이블의 반복된 컴팩션과 병합으로 인해 여러번 데이터를 써야함
쓰기 증폭 (write amplification)
데이터베이스 쓰기 한번이 데이터베이스 수명 동안 디스크에 여러번 쓰기를 야기하는 효과
쓰기증폭이란, 1번의 데이터 베이스 쓰기가 1번이 아닌 여러번 쓰기를 유발하는 현상을 일컫음
SSD는 수명이 다할때까지 블록 덮어쓰기 횟수가 제한되므로 쓰기 증폭이 SSD에 유용함
쓰기가 많은 애플리케이션의 성능 병목 - 디스크 쓰기 속도
쓰기 증폭 = 성능 비용
LSM 트리는 B 트리보다 쓰기 처리량을 높게 유지할 수 있음
순차적으로 컴팩션된 SS테이블 파일을 쓰기 때문
압축률이 좋음
저장소 오버헤드가 낮음
페이지 지향적이지 않고, 주기적으로 파편화를 없애기위해 SS 테이블을 다시 기록함
SSD
SSD 펌웨어는 저장소 순차적 쓰기 패턴을 위해 내부적으로 로그 구조화 알고리즘을 사용
낮은 쓰기 증폭과 파편화 감소는 SSD에 유리
LSM 트리 단점
컴팩션 과정이 때로는 진행중인 읽기/쓰기에 영향을 줄 수 있음
컴팩션을 점진적으로 백그라운드에서 수행
그러나 디스크가 가진 자원은 한계가 있음
비싼 컴팩션 연산이 끝날때 까지 요청이 대기해야하는 상황이 발생할 수 있음
높은 쓰기 처리량
디스크 쓰기 대역폭은 유한함, 일부 로직이 대역폭을 공유해야함
초기 쓰기(logging)
멤테이블을 디스크로 방출(flush)
컴팩션 스레드
데이터베이스가 커질수록 컴팩션을 위한 디스크 대역폭이 필요함
컴팩션 주의 깊게 설정 필요
컴팩션이 유입 쓰기 속도를 따라갈 수 없는 경우 발생
디스크상에 병합되지 않은 세그먼트 수는 디스크 공간이 부족할 때까지 증가
더 많은 세그먼트 파일을 확인해야하므로 읽기 또한 느려짐
상황 감지를 위한 명시적 모니터링 필요
B 트리 장점
각 키가 색인의 한곳에만 정확히 존재
cf) 로그 구조화 저장소엔진은 다른 세그먼트에 같은 키 다중 복사본 존재 가능
강력한 트랜잭션 시맨틱을 제공하는 데이터베이스에 유리

2. 기타 색인 구조

지금까지 살펴본 색인은 키-값 색인
관계형 모델의 기본키 색인 (primary key)
관계형 테이블에서 하나의 로우, 문서 데이터베이스에서는 하나의 문서를, 그래프 모델에서는 하나의 정점을 고유하게 식별 가능
보조 색인 (secondary index)
키-값 색인에서 쉽게 생성가능
기본키 색인과 다르게 키가 고유하지 않음
같은 키를 가진 많은 로우(문서, 정점)이 존재 가능
해결 방법
색인의 각 값에 일치하는 로우 식별자 목록 생성하는 방법
로우 식별자를 추가하여 각 키를 고유하게 만드는 방법

2.1. 색인 안에 값 저장하기

색인
키: 질의가 검색하는 대상
1.
실제 로우(문서, 정점) - 클러스터드 색인
2.
다른곳에 저장된 로우를 가리키는 참조 - 비클러스터드 색인
로우가 저장된 곳을 힙파일이라고 함
힙파일
특정 순서 없이 데이터 저장
힙 파일 접근 방식이 일반적인 방식
여러 보조 색인이 존재할 경우 데이터 중복 피할 수 있음
키를 변경하지 않고 값을 갱신할 때 효율적
기존의 값 공간을 그대로 사용할 수 있는 경우 → 레코드를 제자리에 덮어씀
기존의 값 공간을 그대로 사용할 수 없는 경우
충분한 공간이 있는 새로운 곳으로 위치 이동 필요
모든 색인이 레코드의 새로운 힙 위치를 가리키게 갱신 필요 또는, 이전 힙 위치에 전방향 포인터 생성
클러스터드 색인 (clustered index)
색인 → 힙파일 이동은 읽기 성능 저하
색인 안에 색인된 로우를 바로 저장
예) InnoDB 저장소 엔진의 테이블 기본키
커버링 색인 (covering index) / 포괄열이 있는 색인 (index with included column)
클러스터드 색인과 비클러스터드 색인의 사이 절충안
색인 안에 테이블의 칼럼 일부를 저장

2.2. 다중 컬럼 색인

결합 색인 (concatenated index)
하나의 컬럼에 다른 컬럼을 추가하는 방식
하나의 키에 여러 필드를 단순히 결합
다차원 색인은 한번에 여러 컬럼에 질의하는 일반적인 방법
표준 B 트리나 LSM 트리 색인은 다차원 색인에 효율적이지 않음
SELECT * FROM restaurants WHERE lat > 51.49 AND lat < 51.5079 AND lon > -0.1162 AND lon < -0.1004;
SQL
복사
전문 공간 색인(specialized spatial index) 를 사용하는 해결 가능
R 트리

2.3. 전문 검색과 퍼지 색인

유사한 키에 대한 검색은 기존까지 설명한 색인으로 검색 불가
애매모호한 (fuzz) 질의에는 다른 기술 필요
예) 전문 검색 엔진
특정 단어 검색 시, 해당 단어의 동의어로 질의 확장
루씬의 인메모리 색인
용어 사전을 위해 SS 테이블 같은 구조를 사용
여러 키 내 문자에 대한 유한 상태 오토마톤으로 트라이와 유사
레벤슈타인 오토마톤
특정 편집 거리 내 효율적인 단어 검색 제공

2.4. 모든 것을 메모리 보관

개요
지금까지의 모든 색인 및 데이터 구조는 디스크 한계에 대한 해결책임
디스크 / SSD는 메인 메모리에 비교해 다루기 어려움
디스크의 지속성, 램보다 기가바이트당 가격이 저렴한 이유로 디스크 활용
램 가격이 저렴해지면서 인메모리 데이터베이스 개발
지속성
디스크에 변경사항의 로그 기록 / 디스크에 주기적으로 스냅샷 기록
인메모리 DB가 재시작 되는 경우, 디스크나 네트워크를 통해 복제본에서 상태를 다시 적재
디스크에 기록하더라도, 읽기는 전적으로 메모리에서 제공됨
안티 캐싱 접근 방식
메모리가 충분하지 않을 때, 가장 최근에 사용하지 않은 데이터를 메모리에서 디스크로 보냄
나중에 다시 접근할 때 메모리에 적재

3. 트랜잭션 처리와 분석

3.1. 고수준에서의 저장소 엔진의 분류

1.
트랜잭션 처리 최적화 (OLTP: Online Transaction Processing)
최종 사용자가 사용하므로 대량의 요청을 받을 수 있음
부하 처리를 위해 애플리케이션은 보통 각 질의마다 작은 수의 레코드만 다룸
애플리케이션은 키의 일부만 사용하는 레코드를 요청
저장소 엔진은 요청한 키의 데이터를 찾기 위해 색인을 사용
디스크 탐색이 병목
2.
분석 최적화(OLAP: Online Analytic Processing)
비즈니스 분석가가 주로 사용
훨씬 더 적은 수의 질의를 다루나 각 질의는 매우 다루기 어려움
짧은 시간에 수백만 개의 레코드를 스캔해야함
일반적으로 디스크 대역폭이 병목
칼럼 지향저장소는 작업 부하 처리할때 사용가능한 솔루션

3.2 데이터 웨어하우스

OLTP 작업에 영향을 주지 않고 분석가들일 마음껏 질의 할 수 있는 개별 데이터베이스
OLTP 시스템에 있는 데이터의 읽기 전용 복사본
ETL - 데이터 웨어하우스로 데이터를 가져오는 과정
Extract - OLTP 데이터베이스에서 주기적인 데이터 덤프나 지속적인 갱신 스트림을 사용하여 추출
Transform - 분석 친화적인 스키마로 변환
Load - 깨끗하게 정리한 다음 데이터 웨어하우스에 적재
OLTP 데이터베이스 vs 데이터 웨어하우스
데이터 웨어하우스의 데이터 모델: 관계형 모델
SQL이 일반적으로 분석 질의에 적합
SQL 질의 생성 후 결과를 시각화하고 데이터 탐색을 도와주는 그래픽 데이터 분석 도구 존재
드릴 다운 (drill-down)
슬라이싱 (slicing)
다이싱(dicing)
표면적으로는 둘다, SQL 질의 인터페이스를 지원하므로 비슷해보임
그러나, 각각 매우 다른 질의 패턴에 맞게 최적화 됐기 때문에 시스템 내부는 다름

3.3. 분석용 스키마: 별 모양 스키마 & 눈꽃송이 모양 스키마

별모양 스키마(star schema)
사실 테이블 (fact table)
스키마의 중심에는 이 존재
사실 테이블의 각 로우는 특정 시간에 발생한 이벤트를 의미함
개별 이벤트를 담음
분석의 유연성을 극대화 가능
다만, 사실 테이블이 매우 커질 수도 있음
차원 테이블 (dimemnsion table)
사실 테이블의 다른 칼럼들이 가리키는 다른 테이블 (외래키 참조)
이벤트의 속성인 누가(who), 언제(when), 어디서(where), 무엇을(what), 어떻게(how), 왜(why)를 나타냄
눈꽃송이 모양 스키마 (snowflake schema)
별 모양 스키마를 발전 시킨 것
차원을 하위차원으로 더 세분화 한 것

4. 칼럼 지향 저장소

데이터 웨어하우스 질의는 일반적으로 한번에 4~5개의 컬럼에만 접근
로우의 모든 컬럼의 데이터가 분석용으로 필요하지 않음
대부분의 OLTP 데이터베이스에서 저장소는 로우 지향 방식의 데이터를 배치함
예시)
fact_sales.date_key, fact_sales.product_sk 컬럼 모두 혹은 둘중 하나에 색인이 있다고 가정할 경우, 로우 지향 저장소 엔진에서는 모든 로우를 메모리로 적재 한 후, 필요한 후 조건을 충족시키는 로우만 필터링을 해야 한다.

4.1. 정의

모든 값을 하나의 로우에 함께 저장하지 않는 대신 각 칼럼별로 모든 값을 저장
각 칼럼을 개별 파일에 저장하여 질의에 사용되는 칼럼만 읽고 구분 분석 진행
작업량 대폭 감소 가능
컬럼 지향 저장소 배치는 각 칼럼 파일에 포함된 로우가 모두 같은 순서임
로우의 전체 값을 다시 모우려면 개별 칼럼 파일의 동일한 인덱스에 위치한 데이터를 모아 구성 가능
예시

4.2. 칼럼 압축

데이터 압축을 통해 디스크 처리량 감소
칼럼 지향 저장소는 압축에 적합함
비트맵 부호화
보통 컬럼의 고유 값 수는 로우수에 비해 적음
N개의 고유값을 가진 컬럼을 가져와 N개의 개별 비트맵으로 변환
벡터화 처리

4.3. 칼럼 저장소의 순서 정렬

칼럼 저장소에서 로우가 저장되는 순서가 반드시 중요하지는 않음
삽입된 순서로 저장하는 방식이 가장 쉬움
SS 테이블처럼 순서를 도입해 색인 매커니즘으로 사용할 수 있음
각 칼럼별로 독립적으로 정렬할 수 없음 → 데이터를 한번에 전체 로우를 정렬해야 함
정렬된 순서는 칼럼 압축에 도움이 됨
정렬후 기본 정렬 칼럼은 연속해서 같은 값이 길게 반복됨
런 렝스 부호화 등으로 칼럼 압축 가능
첫번째 정렬키에서 가장 강력함
두번째 또는 세번째 정렬 키는 그보다 뒤섞여 있어 반복 값이 그렇게 길지 않음

4.4. 칼럼 지향 저장소의 쓰기

칼럼 지향 저장소, 압축, 정렬은 모두 읽기 질의에 최적화 되어있음
따라서 쓰기를 어렵게 한다는 단점이 있음
B 트리 사용과 같은 제자리 갱신(update-in-place) 접근 방식은 압축된 컬럼에서 불가능
정렬된 테이블 중간에 로우를 삽입하는 경우, 모든 칼럼 파일을 재작성 해야함
LSM 트리 활용 가능

4.5. 집계: 데이터 큐브와 구체화 뷰

구체화 집계 (materialized aggregate)
count, sum, avg, min, max 등 집계 함수
구체화 뷰 (materizalized view)
질의가 자주 사용되는 집계 함수의 결과 값을 캐싱
디스크에 기록된 질의 결과의 실제 복사본
원본 데이터를 변경하면 구체화 뷰를 갱신해야 함
구체화 뷰는 원본 데이터의 비정규화된 복사본이기 때문
데이터베이스가 이 작업을 자동으로 수행 가능
그러나, 갱신으로 인한 쓰기는 비용이 비싸므로 OLTP 데이터베이스에서 구체화 뷰는 자주 사용되지 않음
데이터 웨어하우스는 읽기 비중이 크므로 구체화 뷰 사용 전략은 합리적일 수있음
표준 뷰 (= 구체화 뷰)
테이블 같은 객체로 일부 질의 의 결과가 내용임
가상 뷰 (=일반적으로 생각하는 뷰)
질의를 작성하는 단축 키
말 그대로 쿼리 단축키
SQL 엔진은 뷰의 원래 질의로 즉석에서 확장하고 나서 질의를 처리
데이터 큐브 (data cube, OLAP 큐브)
일반화된 구체화 뷰의 특별 사례임. 다양한 차원으로 그룹화한 집계 테이블
특정 질의를 효과적으로 미리 계산 했기 때문에 해당 질의를 수행할 때 매우 빠름

스터디

Harry

쓰기 증폭이란?
색인의 값이 저장되는 방식 2가지를 비교하여 설명하시오
OLTP와 OLAP의 특징을 비교하시오
구체화 뷰를 OLTP에서 잘 쓰이지 않는 이유는?

Matthew

B 트리 구조의 설계 철학과 LSM 트리 구조 설계 철학의 차이점은?
B 트리에서 데이터 베이스 고장 상황에 대비하기 위해 무엇을 하는가?
안티캐싱 접근 방식이란?
(optional) 색인 알고리즘이 OLTP 에서 잘 동작하지만 분석 질의의 응답에선 별로 좋지 않은 이유는?