3장. 저장소와 검색

개요

---

• 데이베이스가 데이터를 저장하는 방법과 데이터를 요청했을 때 다시 찾을 수 있는 방법을 확인한다.
• 로그 구조 저장소 엔진과 페이지 지향 저장소 엔진에 대해서 알아본다.

 

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

---

• 색인(Index)은 데이터베이스에서 특정 키의 값을 효율적으로 찾을 수 있는 방법이다.
• 색인은 기본 데이터에서 파생된 추가적인 구조이기 때 쓰기 과정에서 오버헤드가 주로 발생한다. (데이터를 쓸 때마다 색인도 함께 갱신해야 하기 때문이다.)

해시 색인

---

• 데이터 파일에 오프셋을 추가하는 전략
  • 키/값 저장소에서 가장 간단한 색인 전략은 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 유지하는 전략이다.
    • 키/값 쌍이 추가될 때마다 방금 기록한 데이터의 오프셋을 반영하고 맵을 갱신한다.
    • 디스크 공간이 유한하기 때문에 무한정 쓰기가 불가능하다.

• 세그먼트 전략
  • 특정 크기의 세그먼트로 로그를 나누는 전략이다.
  • 특정 크기에 도달하면 세그먼트를 닫고 새로운 세그먼트 파일에 쓰기를 수행한다.
  • 각 세그먼트 파일에서 동일한 키(중복된 키)에 대해서 가장 최신 값만 유지하도록 컴팩션을 수행할 수 있다.단일 세그먼트에서 컴팩션 (yawn이라는 키에 대해서 최신 오프셋만 유지)  

• 여러 세그먼트 파일을 동시에 병합할 수 있다.
  • 컴팩션 수행은 백그라운드 스레드가 처리하며, 컴팩션 수행 시 데이터 읽기 요청이 온 경우 이전 세그먼트에서 데이터를 읽는다.
  • 모든 세그먼트에 대해서 컴팩션이 완료되면, 병합된 세그먼트에서 데이터를 읽고 이전 세그먼트는 삭제한다.

세그먼트 전략 구현 주의사항

1. 레코드 삭제: 키와 관련된 값을 삭제하려면 특수한 삭제 레코드(툼스톤)을 추가해야 한다. 세그먼트 병합 시 툼스톤이 세워진 키는 무시하도록 구현한다.
2. 크래시복구: 세그먼트 해시 맵을 빠르게 복구하기 위해 스냅샷을 디스크에 저장한다.
3. 동시성 제어: 쓰기 순서를 보장하기 위해 하나의 쓰기 스레드만 유지한다.

 

 

SS테이블과 LSM 트리

---

 

• SS Table (정렬된 문자열 테이블, Sorted String Table)
  • 각 키는 각 병합된 세그먼트 파일 내에 한 번만 나타나야 한다.
  • 키로 정렬된 형식을 갖는다.
• SS 테이블의 장점
  • 각 세그먼트를 보면서 가장 낮은 키를 새로운 세그먼트에 복사한다.
  • 동일한 키가 있는 경우 가장 최근의 세그먼트에 있는 키 값을 사용한다.erge Sort 형식처럼 세그먼트 병합을 진행해 효율적이다.

1 -> 3 세그먼트로 갈 수록 최신 세그먼트. 동일한 키는 더 최신의 세그먼트에 병합되는 것을 확인할 수 있다.

• 파일에서 특정 키를 찾기 위해 메모리에 모든 키의 색인을 유지할 필요가 없다.
  • handbag < handiwork < handsome → handbag 오프셋으로 이동해 handiwork까지 스캔
  • 일부 키에 대한 오프셋은 유지해야 하지만 세그먼트 크기를 작게 유지할 수 있다.
• 레코드들을 블록화하고 디스크에 쓰기전에 압축하고 블록의 첫 번째 키를 인메모리 색인에 저장한다.
  • 읽기 요청 시 키/값 쌍 스캔에 필요한 I/O가 감소할 수 있으며 디스크 공간을 절약할 수 있다.handbag이 블록의 첫 번째 레코드. 인메모리 인덱스에 handbag을 유지한다.

handbag 이 블록의 첫 번째 레코드. 인메모리 인덱스에 handbag 을 유지한다.

SS테이블 생성과 유지

---

• 인메모리 균형 트리 (레드블랙트리, AVL 트리)와 같은 자료구조를 이용해 임의 순서로 키를 삽입해도 정렬된 순서로 키를 읽을 수 있다.
• SS 테이블 생성/유지 방법
  • 쓰기 요청
    • 멤테이블 (인메모리 균형 트리, e.g 레드블랙트리)에 데이터를 쓰고 임계값을 넘어가면 SS테이블 파일로 디스크에 기록한다.
    • SS 테이블을 디스크에 기록하는 동안 새로운 멤테이블 인스턴스에 데이터를 쓴다.
  • 읽기 요청
    • 멤테이블에서 1차적으로 데이터를 조회하고, 없는 경우 디스크의 최신 세그먼트부터 차례로 탐색한다.
  • 세그먼트 파일에 대해서 병합하고 컴팩션하는 과정을 수행한다.
• 디스크로 기록되지 않은 멤테이블 내 데이터는 장애 발생 시 유실된다.
  • 쓰기를 즉시 추가할 수 있는 로그를 디스크 상에서 추가로 유지해야 한다
• LSM(Log-Structured Merge Tree) 저장소 엔진: 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진

LSM 저장소 엔진의 성능 최적화

---

 

• 블룸 필터를 이용해 키가 없는 경우 불필요한 읽기 연산을 제외시킨다.
• Size-Tiered 컴팩션과 Leveled 컴팩션 전략을 사용한다.
  • Size-Tiered Compaction: 상대적으로 최신이고 작은 SS테이블 → 상대적으로 오래되고 큰 SS테이블에 병합
  • Leveled Compaction: 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 레벨로 이동시켜 컴팩션을 전진적으로 진행
• 기본적으로 백그라운드에서 SS테이블을 지속적으로 병합하는 것이 중요하다.

 

B 트리

---

• 4KB 고정 크기 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기/쓰기 연산을 진행한다.
• 각 페이지는 주소나 위치를 이용해 식별할 수 있으며, 하나의 페이지가 다른 페이지를 참조할 수 있다.
  • 한 페이지는 B 트리의 루트로 지정되며, 색인에서 키를 찾기 위해선 루트 페이지부터 탐색한다.
  • 각 하위 페이지는 키가 계속 이어지는 범위를 담당하고 키의 범위 경계
  • 리프 페이지는 실제 값을 갖거나 값이 존재하는 페이지의 참조를 갖는다.

• 분기 계수: 한 페이지에서 하위 페이지를 참조하는 수
• 키의 값 갱신
  • 리프 페이지를 검색해 페이지의 값을 갱신하고 페이지를 디스크에 다시 기록한다.
• 새로운 키 추가
  • 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키/값을 추가한다.
  • 새로운 키가 추가되는 페이지가 가득 찬 경우 페이지 하나를 반쯤 채워진 페이지 둘로 분기하고 상위 페이지가 새로운 키 범위의 하위 부분을 알수 있도록 갱신한다.

• B 트리는 항상 균형 유지하며, n개의 키에 대해 항상 O(logN)을 보장한다.

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

---

• 페이지가 가리키는 참조가 깨지지 않도록 하는 것이 중요하다.
• 페이지 분할로 인해 여러 페이지에 덮어쓰기가 필요한 경우 일부만 갱신되지 않도록 주의해야 한다.
  • 일부만 기록되는 경우 부모 페이지 참조가 사라져 고아 페이지가 발생할 수 있다.
• 크래시 복구를 위해 디스크 상에 WAL (Write-ahead-log, Redo Log)로그를 추가해 B 트리의 변경사항을 추가로 기록한다.
• 같은 자리 페이지를 갱신하는 작업은 래치와 같은 락을 통해 동시성 제어가 필요하다.

B 트리 최적화

---

• Copy-on-write scheme: 변경된 페이지는 다른 위치에 기록 후 트리에 상위 페이지의 새로운 버전을 생성해 새로운 위치를 가리키게 만든다.
• 페이지 내 키 기록 시 키 범위의 경계역할만 하는 정보로 축약해서 저장한다. → 분기 계수를 높여 트리 깊이를 낮출 수 있다.
• 리프 페이지를 연속된 순서로 나타나게 배치한다.
• 트리에 포인터를 추가해 리프 페이지가 양쪽 형제 페이지에 대한 참조를 갖도록 구성해 상위 페이지 이동 없이 키를 스캔하도록 구현한다.

 

B 트리와 LSM 트리 비교

---

• 일반적으로 B 트리는 읽기 연산에서 빠르고, LSM 트리는 쓰기 연산에서 빠르다.

LSM 트리의 장점

---

• B 트리에 비해 쓰기 처리량이 높다.
  • 쓰기 증폭 (1번의 쓰기에서 여러 번의 쓰기가 필요)이 낮고, 순차적으로 컴팩션된 SS 테이블 파일을 쓰기 때문이다.
• B 트리에 비해 압축률이 좋다.
  • B 트리가 페이지 일부 공간이 파편화되는 것에 반해 LSM 트리는 주기적으로 SS 테이블을 다시 기록하기 때문에 저장소 오버헤드가 더 낮다.

LSM 트리의 단점

---

• 컴팩션 과정이 읽기/쓰기 연산에 영향을 미친다.
• 유한한 디스크 대역폭을 초기 쓰기 연산(로깅, 멤테이블 → 디스크 Flush)과 컴팩션이 공유한다.
• 컴팩션이 유입 속도를 따라가지 못하는 경우 세그먼트가 많아지면서 읽기 연산도 세그먼트 확인을 위해 느려진다.
• 여러 세그먼트에 동일한 키에 대한 데이터가 들어있을 수 있으므로 트랜잭션 시멘틱을 구현하기 어렵다.

 

기타 색인 구조

---

• 키/값 색인의 일반적인 예시
  • 기본키 색인: 데이터베이스에서 특정 데이터를 고유하게 식별 가능한 색인
  • 보조키 색인: 기본키 색인과 역할은 동일하지만 데이터 고유성을 보장하지 않는다.
• 보조키 색인의 데이터 고유성 보장 문제를 해결하는 방법
  • 색인의 값에 일치하는 로우 식별자 목록을 새롭게 추가
  • 로우 식별자를 추가해 각 키를 고유하게 만듬

색인 안에 값 저장하기

---

• Non-Clustered Index: 색인 안에 데이터 참조를 저장하며 힙 파일에 순서를 보장하지 않고 데이터를 저장한다.
  • 데이터 갱신 시 이전 값 보다 작으면 기존 공간에 덮어쓰기가 가능하며 참조는 유지된다.
  • 새로운 공간이 필요한 경우 모든 색인이 레코드의 새로운 힙 참조 위치를 갱신하거나 이전 힙의 위치에 대한 포인터를 유지해야 한다.
• Clustered Index: 색인에 색인된 로우를 직접 저장한 인덱스
• Covering Index/Index With Included Column: 색인 안에 일부 데이터만 저장하는 하이브리드 방식
  • 읽기 성능은 높아지지만, 추가적인 저장소가 필요하고 쓰기 과정에서 오버헤드 발생

다중 컬럼 색인

---

• 결합 색인(Concaatenated Index): 하나의 컬럼에 다른 컬럼을 추가해 하나의 키에 여러 필드를 결합하는 방법
• 다차원 색인: 한 번에 여러 컬럼에 질의하는 방법
  • 일반적인 B 트리/LSM 트리는 latitude, longitude 에 대한 인덱스를 동시에 주는 것이 불가능하다.

SELECT * 
FROM restaurants 
WHERE latitude > 51.4946 AND latitude < 51.5079 
AND longitude > -0.1162 AND longitude < -0.1004;

전문 검색과 퍼지 색인

---

• 문자 검색과 같이 정확한 값에 대한 질의가 아닌 경우에는 전문 검색 엔진(특정 편집 거리), 퍼지 검색 기술을 사용한다.

모든 것을 메모리에 보관

---

• 디스크, 램 사이의 비용 차이가 줄어들고, 데이터 셋이 크지 않기 때문에 메모리에 데이터를 저장하는 인메모리 데이터베이스가 등장했다.
• 일부 인메모리 데이터베이스는 지속성을 목표로 갖는다.
  • 디스크에 변경 사항을 기록하는 방법
  • 디스크에 주기적으로 스냅샷을 기록하는 방법
  • 인메모리 데이터베이스의 상태를 다른 장비에 복제하는 방법
• 인메모리 데이터베이스는 디스크 기반 색인에서 구현하기 힘든 데이터 모델을 제공한다.
• 안티 캐싱 기법을 통해 오버헤드 없이 가용 메모리보다 더 큰 데이터셋을 지원하게 할 수 있다.

안티 캐싱(Anti-Caching): 메모리가 충분하지 않을 때 최근에 사용하지 않은 데이터를 디스크로 내보내고, 나중에 다시 접근할 때 메모리에 적재하는 방식

 

트랜잭션 처리, 분석

---

 

• OLTP(Online tnrasacion processing): 실시간으로 데이터 읽기/쓰기 처리가 필요한 패턴
• OLAP(Online Analytic Processing): 대규모 데이터 분석, 통계를 위한 패턴
• OLAP를 위한 데이터베이스를 데이터 웨어하우스라고 한다.

데이터 웨어하우징

---

 

• 데이터 웨어하우스: 분석가들이 OLTP 작업에 영향을 주지 않고 질의할 수 있는 데이터베이스
• OLTP 데이터베이스 내 데이터를 ETL 처리를 통해 데이터 웨어하우스에 적재한다.

OLTP 데이터베이스, 데이터 웨어하우스의 차이점

---

 

• 대부분의 데이터베이스 벤더는 트랜잭션 처리 혹은 분석 작업부하 둘 중 하나만 지원한다.

OLTP 데이터베이스	데이터 웨어하우스
실시간 트랜잭션 처리	대용량 데이터 분석 처리
CRUD 작업	읽기 작업 (SELECT, GROUP BY)
데이터 실시간 처리	OLTP 데이터베이스의 데이터를 ETL

 

 

분석용 스키마: Star Schema, Snowflake Schema

---

• 일반적인 데이터 웨어하우스는 Star Schema로 정형화된 방식을 사용한다.
  • 사실 테이블: 특정 시각에 발생한 개별 이벤트를 담는 테이블
  • 차원 테이블: 사실을 구성하는 각 데이터를 저장하는 테이블
  • 사실 테이블은 각각의 이벤트를 나타내며, 이 이벤트는 차원 테이블의 데이터를 이용해 표현한다.
  • 사실 테이블 하나를 중심으로 주변의 차원 테이블이 구성됨 = 별 모양 스키마사실 테이블 주위에 차원 테이블이 각각의 컬럼을 구성한다.

사실 테이블 주위에 차원 테이블이 각각의 컬럼을 구성한다.

• Snowflake Schema는 Star Schema보다 차원이 하위 차원으로 세분화된 형태이다.

 

칼럼 지향 저장소

---

• 모든 값을 하나의 로우에 함께 저장하는 것이 아닌 각 컬럼별로 모든 값을 함께 저장하는 방식이다.
• 각 컬럼을 개별 저장하고 질의에 사용되는 컬럼만 읽어서 구분 분석한다.

각 컬럼 저장소의 로우는 모두 같은 순서에 해당하는 데이터이다.

• 칼럼 지향 저장소의 각 로우 배치는 각 컬럼 파일에 포함된 로우가 모두 같은 순서여야 데이터 정합성 보장이 가능하다.

칼럼 압축

---

• 칼럼 지향 저장소에서 대표적으로 사용되는 칼럼 압축 기법은 비트맵 부호화이다.
  • 칼럼에서 n개의 고유값을 각각 하나의 비트맵으로 구성한다.
  • 각 비트맵은 해당 값을 가지면 1로 표기하고 갖지 않으면 0으로 표기한다.
  • 위의 예시에서 각 product_sk에 해당하는 값을 각각의 비트맵으로 만들고 1, 0으로 구분하고 있다.
• n 값이 커질 수록 대부분의 비트맵 값은 0이 더 많다.
  • run-length 부호화를 통해서 압축하는 것이 가능하다.
  • 위의 예시에서 30에 해당하는 값은 11번째, 12번째에 존재한다. 이를 런-렝스 부호화를 진행하면 10, 2가 된다. 이는 10번째까진 0 이후 연속된 2개는 1이라는 의미이며, 나머지는 모두 0이란 것을 의미한다.

메모리 대역폭과 벡터화 처리

---

• 데이터 웨어하우스의 병목은 디스크로부터 메모리로 데이터를 가져오는 대역폭이다.
• 칼럼 압축을 진행하면 디스크 → 메모리로 데이터를 더 많이 가져올 수 있다.
• 또한, 비트 AND/OR 연산은 루핑을 통한 계산이 아닌 비트 연산을 통해 벡터화 처리가 가능하다.
  • OR 연산 예시: product_sk = 29 OR product_sk = 30
    • 000000000100000000 | 00000000001100000 = 0000000001110000 로 루핑 없이 계산 가능

 

칼럼 저장소의 순서 정렬

---

• 칼럼 저장소는 각 컬럼을 구성하는 로우의 순서가 가장 중요하기 때문에 칼럼 정렬하는 경우 모든 칼럼을 정렬해야 한다.
• 공통 질의에 대한 지식을 기반으로 테이블에서 정렬할 컬럼을 선택하는 것이 중요하다.
• 정렬된 순서는 칼럼 압축에 도움이 될 수 있다.
  • 기본 정렬 컬럼에 고유 값을 많이 포함하지 않는 경우 같은 값이 연속해서 길게 반복될 수 있으므로 런-렝스 부호화에 이점이 된다.
  • 첫 번째 정렬이 가장 값이 연속해서 나타날 수 있으므로 영향력이 강하며 다음 정렬로 갈 수록 영향력이 약하다.

다양한 순서 정렬

---

• 같은 데이터를 다양한 방식으로 정렬해 저장하는 방식을 의미한다.
• 복제 데이터를 서로 다른 방식으로 정렬해서 저장하면 질의 패턴에 맞게 적합한 버전을 사용할 수 있다.

 

칼럼 지향 저장소에 쓰기

---

• 칼럼 지향 저장소는 모든 칼럼이 순서가 종속적이기 때문에 테이블 중간에 있는 로우에 삽입을 해야하는 경우 모든 컬럼 파일 재작성이 필요하다.
• 칼럼 지향 저장소는 이상적인 쓰기 방식
  • 인메모리 저장소로 이동해 정렬된 구조(AVL 트리, 레드블랙 트리)에 추가한다.
  • 충분한 쓰기 데이터가 모이면 디스크의 컬럼 파일에 병합하고 대량으로 새로운 파일에 기록한다.
• 질의 시에는 인메모리 저장소와 디스크를 모두 확인해야 한다.

 

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

---

• 구체화 뷰(Materialized View): 데이터 웨어하우스에서 자주 사용되는 데이터를 집계함수로 집계한 값을 캐싱하는 방식이다.
  • sum, count ,avg, min/max 등의 값을 계산해 뷰로 생성하는 방식을 의미한다.
  • 원본 데이터가 변경되면 구체화 뷰를 매번 갱신해야 한다.
• 데이터 큐브(OLAP 큐브): 다차원으로 그룹화한 집계 테이블

날짜 프로덕트 별 집계된 결과

• 구체화 데이터 큐브는 특정 질의를 효과적으로 미리 계산했기 때문에 해당 질의를 수행하는 경우 속도가 매우 빠르다.
• 구체화 데이터 큐브를 구성하지 않는 데이터에 대한 질의는 원시 데이터 질의하는 것과 동일하기 때문에 속도가 느리다.

 

정리

---

• OLTP 시스템: 대량의 요청을 처리하며, 질의마다 작은 수의 레코드만 사용한다.
  • 키의 일부만 사용하는 레코드를 요청하고 키를 탐색하기 위해 색인을 사용한다.
  • 디스크 탐색하는데 병목이 생긴다
• OLAP 시스템: 대규모 데이터 분석을 위해 사용하며, 대용량 레코드를 사용한다.
  • 디스크 대역폭이 병목이다.
  • 칼럼 지향 저장소를 사용해 작업 부하를 줄이는 솔루션이 늘어나고 있다.
• OLTP 측면의 2가지 관점
  • 로그 구조화 관점: 파일에 추가와 오래된 파일의 삭제만 허용하고, 한 번 쓰여진 파일은 절대 갱신하지 않는다.
  • 제자리 갱신 관점: 덮어쓰기 할 수 있는 고정 크기 페이지 셋으로 디스크를 다룬다.
• 데이터 웨어하우스는 디스크에서 읽는 데이터 양을 최소화하기 위해 데이터를 작게 부호화하는 작업이 중요하다.
• 칼럼 지향 저장소를 통해 데이터 웨어하우스에서의 작업 부하를 줄일 수 있다.