데이터베이스 관점에서 데이터를 저장하는 방법과 데이터를 요청했을 때 다시 찾을 수 있는 방법에 대해 알아보자.
0. 개발자가 주의해야하는 이유
- 사용 가능한 여러 저장소 엔진 중에 어플리케이션에 적합한 엔진을 선택하는 것이 필요
- 특정 작업부하 유형에서 좋은 성능을 내게끔 저장소 엔진을 조정하려면 저장소 엔진이 내부에서 수행되는 작업에 대해 대략적인 개념을 이해할 필요가 있음 (트랜잭션 / 분석)
- 관계형 vs NoSQL
1. 데이터베이스를 강력하게 만드는 데이터 구조
1.0. 색인
- 데이터베이스에서 특정 키의 값을 효율적으로 찾기 위해서는 다른 데이터 구조가 필요 -> 색인
- 색인의 일반적인 개념은 어떤 부가적인 메타데이터를 유지하는 것
- 이정표 역할을 하여 원하는 데이터의 위치를 찾는데 도움을 줌
- 기본 데이터에서 파생된 추가적인 구조
- 트레이드 오프
- 색인을 잘 설계하여 읽기 성능의 향상
- 색인의 구조에 따라 데이터 쓰기 성능 하락
- 어플리케이션에서 질의 패턴을 이해하고 개발자와 DBA가 잘 협의하여 결정
1.1. 해시 색인
- 키-값 색인
- 매우 일반적이고 복잡한 색인을 위한 구성 요소로 유용
- 사전 타입과 유사
- 해시맵, 해시테이블
1.1.1. 파일에 추가하는 전략
- 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시맵을 유지하는 전략
- 새로운 키-값을 추가할 때마다 데이터의 오프셋을 반영하기 위해 해시맵도 갱신해야함
- 값을 조회하려면 해시맵을 이용해 데이터 파일에서 오프셋을 찾아 해당 위치를 구하고 값을 읽음
- 비트캐스크 (Bitcask)
- 키를 저장하고 검색하기 위한 API를 제공하는 Erlang 어플리케이션
- 해시맵을 전부 메모리에 유지하기 때문에 램에 모든 키가 저장된다는 조건을 전제로 고성능 쓰기, 읽기 가능
- 한 번의 디스크 탐색으로 디스크에서 적재할 수 있기 때문에 사용 가능 메모리보다 더 많은 공간 사용 가능
- 데이터 파일의 일부가 이미 파일 시스템 캐시에 있다면 읽기에 디스크 입출력이 필요하지 않음
- 각 키의 값이 자주 갱신되는 상황에 적합
- 파일에 항상 추가만 한다면 결국 디스크 공간이 부족해짐
1.1.2. 세그먼트 로그
- 특정 크기의 세그먼트로 로그를 나누는 방식
- 특정 크기의 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 쓰기 수행
- 컴팩션(compaction): 중복 키를 버리고 최신 갱신값만 유지
- 동시의 여러 세그먼트의 컴팩션이 가능
- 세그먼트가 쓰여진 후 변경할 수 없기 때문에 병합할 세그먼트는 새로운 파일에 수행
- 고정된 세그먼트 병합과 컴팩션은 백그라운드 스레드에서 수행
- 병합 후 병합된 세그먼트로 사용을 전환하고 이전 세그먼트 파일은 삭제
- 키를 파일 오프셋에 매핑한 자체 인메모리 해시 테이블을 갖음
- 키를 찾을 대 최신화된 순으로 세그먼트 해시맵을 확인
- 병합으로 적은 세그먼트 수를 유지하여 많은 해시맵을 확인할 필요 없음
1.1.3. 실제 구현에서 중요한 문제
- 파일 형식
- 레코드 삭제
- 고장 복구
- 부분적으로 레코드 쓰기
- 동시성 제어
1.1.4. 제한 사항
- 메모리에 저장하기 대문에 키가 너무 많으면 문제가 됨
- 디스크를 사용하면?
- 성능 이슈
- 확장 비용 이슈
- 해시 충돌 이슈
- 디스크를 사용하면?
- 범위 질의에 효율적이지 않음
- 개별 키 조회 필요
1.2. SS 테이블과 LSM 트리
1.2.1. SS 테이블
- 정렬된 문자열 테이블 (Sorted String Table)
- 각 키는 병합된 세그먼트 파일 내에 한 번만 나타나야함
- 장점 (vs 해시 색인)
- 정렬된 순서로 세그먼트를 병합하고 새로운 세그먼트 파일도 키로 정렬되어 있음
- 파일에서 특정 키를 찾기 위해 메모리에 모든 키의 색인을 유지할 필요가 없음
- 정렬이 되어 있기 때문에 특정 키의 오프셋만 알고 있으면 대략적인 위치를 알 수 있음
- 읽기 요청은 요청 범위 내에서 여러 키값 쌍을 스캔해야 하기 때문에 해당 레코드들을 블록으로 그룹화하고 디스크에 쓰기 전에 압축하여 색인의 각 항목은 압축된 블록의 시작을 가르킴
- 디스크 공간을 절약하고 압축은 I/O 대역폭 사용도 줄임
1.2.2. SS 테이블 생성과 유지
- 메모리에 정렬된 구조를 저장
- 레드 블랙 트리 / AVL 트리
- 임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 다시 읽을 수 있음
- 쓰기가 들어오면 인메모리 균형 트리 데이터구조에 추가
- 멤테이블 (memtable)
- 멤테이블이 커지면 SS테이블 파일로 디스크에 기록
- 멤테이블이 이미 정렬된 키값쌍을 유지하고 있기 때문에 효율적으로 수행 가능
- 새로운 SS테이블 파일은 가장 최신 세그먼트가 됨
- 디스크에 기록하는 동안 쓰기는 새로운 멤테이블 인스턴스에 기록
- 읽기 요청하면 멤테이블에서 키를 찾음 -> 디스크 최신 세그먼트 순서
- 가끔 세그먼트 병합, 컴팩션을 백그라운드에서 수행
- 데이터베이스가 고장나면 디스크로 기록되지 않은 최신 쓰기가 손실됨
- 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크에 유지해야함
- 복원할 때만 필요하기 때문에 순서 정렬 필요 없음
- 멤테이블을 SS테이블에 기록하면 해당 로그는 버릴 수 있음
1.2.3. SS 테이블에서 LSM 트리 만들기
- LSM 트리
- 로그 구조화 병합 트리 (Log Structured Merge Tree)
- 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진 -> LSM 저장소 엔진
- 루씬(Lucene)
- 엘라스틱서치나 솔라에서 사용하는 전문 검색 색인 엔진
- 용어 사전을 저장하기 위한 방법으로 LSM 트리 사용
- 키(용어) - 값(문서의 ID / 포스팅 목록)
- 용어와 포스팅 목록의 매핑은 SS 테이블 같은 정렬 파일에 유지
- 필요에 따라 백그라운드에서 병합
1.2.4. 성능 최적화
- 블룸 필터 (Bloom filter)
- 크기 계층 (Size Tiered)
- 레벨 컴팩션 (Leveled Compaction)
1.3. B 트리
- 거의 대부분의 관계형 데이터베이스에서 표준 색인 구현으로 사용
- 많은 비관계형 데이터베이스에서도 사용
- 정렬된 키값 쌍을 유지하여 키값 검색과 범위 질의에 효율적
- 4KB의 고정 크기 블록이나 페이지로 세그먼트를 나누고 한 번에 하나의 페이지에 읽기/쓰기 수행
- 디스크가 고정 크기 블록으로 배열되기 때문에 하드웨어와 밀접한 관련이 있음
- 각 페이지는 주소나 위치를 이용해 식별 -> 하나의 페이지가 다른 페이지를 참조할 수 있음
- 색인에서 키를 찾기 시작하는 루트가 존재함
- 페이지는 여러 키와 하위 페이지의 참조 포함
- 각 하위 페이지는 키가 계속 이어지는 범위를 담당
- 참조 사이의 키는 해당 범위 경계가 어디인지 나타냄
1.3.1. 신뢰할 수 있는 B 트리 만들기
- B 트리의 기본적인 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어 씀
- 데이터베이스 고장 상황에서 스스로 복구할 수 있게 만들려면 디스크 상에 쓰기 전 로그를 추가해 B 트리 구현
- 동시성 제어는 래치 (가벼운 잠금) 로 트리의 데이터 구조를 보호
1.3.2. B 트리 최적화
- 페이지 덮어 쓰기와 고장 복구를 위해 쓰기 시 복사 방식을 사용
- 변경된 페이지는 다른 위치에 기록하고 트리에 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가리키게 함
- 동시성 제어에도 유용
- 페이지에 전체 키를 저장하지 않고 축약하여 공간 절약
- 패이지 하나에 키를 더 많이 채우면 더 높은 분기 계수를 얻어 트리 깊이 수준을 낮을 수 있음 (B+ 트리)
- 리프 페이지를 디스크 상에 연속된 순서로 나타나게끔 트리를 배치하려 시도
- 트리가 커지면 순서 유지에 어려움이 있음
- LSM 트리는 병합 과정에서 저장소의 큰 세그먼트를 한 번에 다시 쓰기 때문에 디스크에서 연속된 키를 서로 가깝게 유지하기 더쉬움
- 트리에 포인터를 추가하여 양쪽 형제 페이지에 대한 참조를 가져 상위로 가지 않고 순서대로 키를 스캔할 수 있음
1.3.3. B 트리와 LSM 트리 비교
- 구현 성숙도: B트리
- 쓰기: LSM 트리
- 읽기: B트리
- 어플리케이션에서 필요한 부하를 주고 적절하게 필요한 저장소 엔진을 선택해야함
1.4. 기타 색인
- 기본키 색인
- 보조 색인
- 클러스터드 색인
- 커버링 색인
- 다중 컬럼 색인
- 전문 검색과 퍼지 색인
2. 트랜잭션 처리나 분석?
- 트랜잭션
- 커머셜 트랜잭션: 판매, 공급 업체에 발주, 직원 급여 등
- 읽기, 쓰기 그룹 단위
- 트랜잭션이 반드시 ACID 속성을 가질 필요는 없음
- 지연 시간이 낮은 읽기아 쓰기를 가능하게 한다는 의미
- OLTP
- OnLine Transaction Processing
- 어플리케이션에서 색인을 사용해 적은 수의 레코드를 찾을 때
- 사용자 입력을 기반으로 삽입/갱신할 때
- OLAP
- OnLine Analytic Processing
- 많은 수의 레코드를 스캔해 해당 레코드의 일부 컬럼을 읽고 집계 통계를 계산할 때
2.1. 데이터 웨어하우징
- OLTP는 어플리케이션에 직접 사용되므로 높은 가용성과 낮은 지연 시간의 트랜잭션이 기대됨
- 다양한 분석 질의를 위해 OLTP를 추출하고 변환하고 데이터웨어 하우스에 적재 -> ETL
2.2. 분석용 스키마: 별 모양 스키마와 눈꽃송이 모양 스키마
- 별모양 스키마
- 대부분 데이터 웨어하우스는 별 모양 스키마 (star schema) 사용
- 사실 테이블 (fact table): 특정 시각에 발생한 이벤트
- 차원 테이블 (demension table): 이벤트의 속성을 나타냄 (육하원칙)
- 사실 테이블은 일부 데이터와 차원 테이블의 외래키 참조들을 가지고 있음
- 눈꽃송이 모양 스키마
- 별 모양 스키마보다 더 정규화 되어 있음
2.3. 칼럼 지향 저장소
1
2
3
4
5
6
7
8
9
10
11
SELECT
dim_date.weekday, dim_product.category,
SUM (fact_sales.quantity ) AS quantity_sold
FROM fact_sales
JOIN dim_date ON fact_sales.date_key = dim_date.date_key
JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
dim_date.year = 2013 AND
dim_product.category IN ( 'Fresh fruit' , 'Candy' )
GROUP BY
dim_date.weekday, dim_product.category;
- OLTP
- row 지향 데이터 배치하고 한 row의 모든 값은 서로 인접하게 저장
- 문서 데이터베이스에서 전체 문서는 보통 하나의 연속된 바이트 열로 저장
- 위 쿼리 시 모든 컬럼을 포함한 로우를 메모리 적재하고 필터링해야하여 비효율적임
- 데이터 웨어하우스의 사실 테이블은 100개 이상의 컬럼을 가지고 있지만 분석 질의에는 4~5개 컬럼만 사용함
- 컬럼 지향 저장소
- 모든 값을 하나의 로우에 함께 저장하지 않고 컬럼별로 모든 값을 함께 저장
- 질의에 사용되는 컬럼만 읽고 구분 분석이 가능하여 작업량이 줄어듬
2.3.1. 컬럼 압축
- 100p: 데이터를 압축하면 디스크 처리량을 더 줄일 수 있다. ?????
- 컬럼 지향 저장소의 많은 값은 반복해서 나타날 수 있기 때문에 압축하기 좋음
- 비트맵 부호화 (bitmap encoding)
- 컬럼에서 고유 값의 수는 로우 수에 비해 적음
- n개의 고유 값을 가진 컬럼을 가져와 n개의 개별 비트맵으로 변환
- 고유값 하나가 하나의 비트맵이고 각 로우는 한 비트를 가짐
- 로우가 해당 값을 가지면 비트는 1, 아니면 0
- n이 매우 작으면 로우당 하나의 비트로 저장 가능
- n이 더 크면 대부분의 비트맵은 0이 더 많음 (희소 / sparse)
- 비트맵 색인은 데이터웨어하우스에서 일반적으로 사용되는 질의 종류에 매우 적합
2.3.2. 메모리 대역폭과 벡터화 처리
- 데이터 웨어하우스 질의는 디스크로부터 메모리로 데이터를 가져오는 대역폭이 큰 병목
- 메인 메모리에서 CPU 캐시로 가는 대역폭을 효율적으로 사용하고 CPU 명령 처리 파이프라인에서 분기 예측 실패와 버블을 피하며 최신 CPU에서 단일 명령 다중 데이터 명령(SIMD)을 사용하게끔 신경써야함
- 컬럼 저장소 배치는 CPU 주기를 효율적으로 사용하기에 적합
- 질의 엔진은 압축된 컬럼 데이터를 CPU L1 캐시에 덩어리로 나누어 가져오고 타이트 루프에서 반복
- CPU는 함수 호출이 많이 필요한 코드나 각 레코드 처리를 위해 분기가 필요한 코드보다 타이트 루프를 훨씬 빨리 실행 가능
- 컬럼 압축을 사용하면 같은 양의 L1 캐시에 더 많은 로우를 저장할 수 있음
- 비트 AND, OR 같은 연산자는 압축된 컬럼 데이터 덩어리를 바로 연산할 수 있게 설계할 수 있음
- 벡터화 처리
2.3.3. 컬럼 저장소의 순서 정렬
- 로우가 저장되는 순서가 반드시 중요하지는 않고 삽입된 순서로 저장하는 방식이 가장 쉬움
- SS 테이블에서 했던 것 처럼 순서를 도입해 색인 메커니즘으로 사용할 수도 있음
- 각 컬럼을 독립적으로 정렬할 수는 없음 -> 동일한 로우를 알 수 없음
- 컬럼별로 저장되었지만 한번에 전체 로우를 정렬해야함
- 정렬된 순서가 있다면 컬럼 압축에 도움이 됨
- 기본 정렬 컬럼에 고유 값을 많이 포함하지 않는다면 정렬 후 기본 정렬 컬럼은 연속해서 같은 값이 길게 반복됨
- 첫 번째 정렬 키에서 압축 효과가 가장 강력하고 이후 정렬 키는 그보다 뒤섞여 있어 반복된 값이 그렇게 길지 않음
- 초반 정렬된 몇 개의 컬럼을 합축하는 것은 전체적으로 여전히 이득임
2.3.4. 다양한 정렬 순서
- OLAP에서 여러 정렬 순서를 갖는 것은 OLTP에서 여러 2차 색인을 갖는 것과 약간 비슷
- OLTP
- 한 곳에 모든 로우를 유지하고 2차 색인은 포인터만 포함
- OLAP
- 포인터가 없고 값을 포함한 컬럼만 존재
2.3.5. 컬럼 지향 저장소에 쓰기
- 컬럼 지향 저장소는 일반적으로 읽기 질의를 더 빠르게 하지만 쓰기를 더 어렵게한다는 단점 존재
- LSM 트리 처럼
- 모든 쓰기를 인 메모리 저장소로 이동해 정렬된 구조에 추가하고 디스크에 쓸 준비를 함
- 인 메모리 저장소는 로우 지향, 컬럼 지향 인지 중요하지 않음
- 충분히 쓰기를 모으면 컬럼 파일에 병합하고 대량으로 새로운 파일에 기록
- 질의는 디스크의 컬럼 데이터와 메모리의 최근 쓰기를 결합해야함
- 질의 최적화기는 이런 구별을 사용자에게 드러내지 않음
2.3.6. 집계: 데이터 큐브와 구체화 뷰
- 구체화 뷰
- 자주 사용하는 일부 집계 (count, sum, …)를 캐시해둠
- 관계형 모델에서는 이런 캐시를 가상 뷰로 정의 (질의를 작성하는 단축키)
- 구체화 뷰(materialized view)는 디스크에 기록된 질의 결과의 복사본
- 원본 데이터를 변경하면 구체화 뷰 갱신이 필요해 쓰기 비용이 비쌈
- 데이터 큐브 (OLAP 큐브)
- 일반화된 구체화 뷰의 특별 사례
- 차원에 따라 특정 속성의 집계를 캐시함
- 특정 질의를 미리 계산했기 때문에 실제 질의 시 수행이 매우 빠름
- 특정 차원에 데이터가 존재하지 않으면 원시 데이터를 질의하는 것보다 유연성이 떨어짐
- 데이터 큐브와 같은 집계 값은 특정 질의에 대한 성능 향상에만 사용됨