[데이터설계] 3장, 저장소와 검색

목표: 단순한 정리가 아니라 남에게 설명할 수 있는 글이 되자

---

3장, 저장소와 검색

로그

- 로그는 append-only 파일로, 연속된 추가 전용 레코드를 의미한다.

- read시, 검색비용에 O(n)이 소모된다.

---

검색비용을 줄이기 위한 효과적인 방법

색인

어떤 부가적인 메타데이터를 유지하는 것

색인은 데이터베이스의 내용에 영향을 미치지 않는, 파생된 추가적인 구조이다.

특징

- 쓰기 과정에서 오버헤드 발생: 데이터를 추가할 시, 매 번 색인도 갱신해야 한다.

- 필요이상으로 오버헤드를 발생시키지 않으면서 읽기 질의 속도를 향샹시키는 색인을 선택해야 한다.

 

1. 해시색인

Bitcask(Riak의 기본 저장소 엔진)

- 인메모리 해시 맵: 사용 가능한 램에 모든 키가 저장

 > 한 번의 디스크 탐색으로 디시크에 적재할 수 있음 -> 실제 메모리보다 더 많은 공간 사용

- 해시테이블을 이용하여 구현

- 데이터 추가 시, 데이터의 off-set을 반영하기 위해 해시맵을 갱신해야 함

- 키 값이 자주 갱신되는 상황에 적합 ex) 비디오 재생 횟수

 

But, 디크스 공간 문제가 발생할 때의 해결법은?

특정 크기의 세그먼트로 로그를 나눈다.

 - 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일 이후에 쓰기 수행

 - Compaction: 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것

Comapction 방법
1. 병합할 세그먼트 새로 생성(한 번 쓰여진 세그먼트는 변경이 불가능하기 때문)
2. 고정된 세그먼트 병합과 컴팩션을 백그라운드에서 진행
3. 컴팩션 수행 동안, 이전 세그먼트 파일을 사용해 읽기와 쓰기 요청을 정상적으로 처리
4. 병합이 끝난 후, 새로 병합한 세그먼트를 사용하도록 전환
5. 세그먼트: 키를 파일오프셋에 매핑한 자체 인메모리 해시 테이블을 가짐

 

구현 시 문제점

1. 파일형식: CSV는 로그에 적합하지 않음

2. 레코드 삭제: 키와 관련된 값을 삭제하려면 데이터 파일에 특수한 삭제 레코드를 추가해야 함(= 톰스톤)

3. 고장(Crash) 복구: 데이터베이스 재시작 시, 인메모리 해시 맵 손실

 - 비트캐스크: 세그먼트 해시 맵 메모리로 좀 더 빠르게 로딩할 수 있는 스냅숏을 디스크에 저장하여 복구 속도를 높힘

4. 부분적 레코드 쓰기: 로그에 레코드를 추가하는 도중 죽을 수 있음

 - 비트캐스크: 체크서을 포함하여 손상된 부분 무시

5. 동시성 제어: 하나의 쓰기 스레드만 사용

 

해결: 추가 전용 로그 사용

- 추가와 세그먼트 병합은 순차적 쓰기 작업이므로 무작위 쓰기보다 빠름

- 이전값과 새로운값을 포함한 파일을 나누어 남겨둠 ▶ 동시성과 고장 복구가 간단

 

단점

- 디스크 상 해시 맵을 유지해야 함 ▶ 많은 데이터 저장X, 확장 비용이 비쌈, 해시 충돌 시 복잡한 로직

- 범위 질의에 효율적이지 않음, 모든 키 스캔X

 

 

2. SS테이블과 LSM 트리

SS테이블이란? 키로 정렬된 문자열 테이블(Sorted String Table)

- 각 키는 병합된 세그펀트 파일 내에 한 번만 나타남

 

장점

* 병합정렬: 세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적이다.

 1. 입력 파일을 읽은 후 각 파일의 첫번째 키를 본다.
 2. 가장 낮은 키를 출력파일로 복사 후 과정 반복
 3. 새로운 병합 세그먼트 파일 생성
 4. 동일한 키가 있는 경우, 최신 세그먼트 값은 유지하고 오래된 세그먼트 값을 버림(입력 세그먼트는 항상 최신값)

 

* 특정 키를 찾기 위해 모든 키의 색인을 유지하지 않아도 된다.

handiwork의 키를 몰라도 handbag과 hansome을 알고 있으면 handiwork를 찾을 수 있음 (정렬)

 

* 디스크 공간 절약

레코드를 블록으로 그룹화 후, 시압축된 블록의 시작

 

 

정렬방법: LSM 트리

✖ AVL 트리/ 레드 블랙트리

1. 쓰기가 들어오면 균형 트리 데이터 구조(인메모리 트리 = 멤테이블)에 추가

 > 임곗값보다 커지면 SS테이블 파일로 디스크에 기록

2. 읽기 요청 시, 멤테이블에서 키를 찾은 후, 최신 세그먼트를 찾음

3. 컴팩션 과정 수행(백그라운드)

💢 문제점: 데이터베이스가 고장났을 때, 디스크로 기록되지 않고 멤테이블에 있는 가장 최신 쓰기가 손실됨

      ▶ 매번 쓰기를 즉시 추가하기 위해 분리된 로그를 디스크 상에 유지해야 함

 

❣ LSM트리: 로그 구조화 병합 트리(Log-Structured Merget Tree)

백그라운드에서 연쇄적으로 SS테이블을 지속적으로 병합하는 것

- LSM 저장소 엔진: 정렬된 파일 병합과 컴팩션 원리 기반

 

 

성능 최적화

1. DB에 없는 값을 찾을 때 느린 경우: 멤테이블과 모든 세그멘테이션 확인(디스크 읽기)

 ▶ 볼륨필터: 키가 데이터베이스에 존재하지 않음을 알려주는 것

 

2. 압축 및 병합

- 크기계층, HBase, 카산드라

- 레벨 컴팩션: 레벨DB, 록스DB, 카산드라

 

 

3. B 트리

가장 널리 사용되는 색인 구조

- 키-값

- 4KB 크기의 고정 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기 진행

➕ page: 주소나 위치를 이용하여 식별, 페이지가 다른 페이지를 참조할 수 있음
     > 하위페이지는 키가 이어지는 범위를 담당
➕ root: 색인에서 키를 찾기 위한 시작
➕ leaf page: 개별 키를 포함하는 페이지에 도달하여 키의 값을 찾음
➕ 분기계수: 한 페이지에서 하위 페이지를 참조하는 수

키 값 갱신

- 키를 포함한 리프 페이지를 검색하여 페이지의 값을 바꾼 후, 다음 페이지를 디스크에 다시 기록

- 새로운 키를 수용한 페이지에 여유 공간이 없으면, 페이지 하나를 반쯤 채워진 페이지 둘로 나누어 상위 페이지가 새로운 키 범위의 하위 부분을 알 수 있도록 갱신

 

균형

- 항상 균형을 유지

- n개의 키를 가진 B 트리의 깊이: 항상 O(log n)

 > 깊이가 4인 경우 256TB를 저장할 수 있으므로 많은 깊이를 필요로 하지 않음)

 

구현

- 새로운 데이터를 디스크 상의 페이지에 덮어씀 -> 페이지의 위치를 변경하지 않음

 > 상위 페이지가 덮어쓰기가 되다가 중단되면 고아페이지(orphan page, 부모와 관계없는 페이지)가 발생 할 수 있다.

- WAL(쓰기 전 로그) 데이터 구조를 추가:트리 페이지에 변경 내용을 적용하기 전, 모든 B트리의 변경사항을 기록하는 추가 전용 파일

- Latch(래치): 가벼운 잠금, 트리의 데이터 구조 보호, 질의의 간섭 없이 백그라운드에서 모든 병합을 수행

 

최적화

- WAL대신 copy-on-write schmem 사용: 변경된 페이지는 다른 위치에 기록하고 트리에 상위 페이지의 새로운 버전 생성

- 키를 축약하여 저장

- 디스크 상에 연속된 순서로 나타나게끔 트리 배치

- 프랙탈 트리: 디스크 찾기를 줄이기 위해 로그 구조화 개념을 일부 사용

 

---

쓰기 증폭: 데이터베이스에 쓰기 한 번이 데이터베이스 수명 동안 디스크에 여러 번의 쓰기를 야기하는 효과

 

B 트리 vs LSM 트리

- 구현성숙도: B > LSM

- 쓰기 속도: LSM > B

- 읽기 속도: B > LSM

 

B 트리 장점

- 각 키가 색인의 한 곳에만 정확하게 존재: 트랜잭션 시맨틱을 제공하는 DB에 유리

- 트리에 잠금을 직접 포함

 

B 트리 단점

- 모든 데이터 조각을 최소 두 번 기록( 쓰기 전 로그 , 트리 페이지)

- 해당 페이지 내 몇 바이트만 바뀌어도 한 번에 전체 페이지를 기록해야하는 오버헤드 발생

- 파편화로 인해 사용하지 않는 디스크 공간 존재

 

 

LSM트리 장점

로그 구조화 색인

- 순차적으로 컴팩션된 SS테이블 파일을 쓰기 때문에 쓰기 증폭이 낮다.

- 압축률이 더 좋음: 주기적으로 파편화를 없애기 위해 SS테이블에 다시 기록 -> 저장소 오버헤드가 낮음

> SSD에서 유리

 

LSM트리 단점

- 컴팩션 과정이 진행중인 읽기와 쓰기 성능에 영향을 줌: 컴팩션 연산이 끝날 때까지 요청 대기 상황 발생

- 데이터베이스가 커질수록 컴팩션을 위해 더 많은 디스크 대역폭 필요

   > 초기 쓰기(로깅, 멤테이블)과 컴팩션 스레드가 디스크 대역폭을 공유하기 때문

- 컴팩션이 유입 쓰기 속도를 따라갈 수 없을 때

   > 디스크 상에 병합되지 않은 세그먼트 수가 디스크 공간이 부족할 때까지 증가

   > 읽기 속도 감소

- 컴팩션이 유입 속도를 따라가지 못해 유입 쓰기의 속도를 조절하지 않으므로 명시적 모니터링이 필요

---

4. 기타 색인 구조

1. 보조 색인

- 다른 레코드에 인덱스 참조

- 키가 고유하지 않음

- B트리와 로그 구조화 색인 둘다 사용 가능

 

힙 파일: 색인의 값이 다른 곳에 저장된 로우를 가리키는 참조

- 특정 순서 없이 데이터 저장

- 키를 변경하지 않고 값을 갱신할 때 효율적

 

클러스터드 색인: 색인 안에 바로 색인된 로우를 저장한 것

 

커버링 색인/포괄열이 있는 색인: 클러스터드 색인과 비클러스터드 색인 사이, 색인 안에 테이블 칼럼 일부를 저장

 

2. 다중 칼럼 색인

결합 색인: 하나의 칼럼에 다른 칼럼을 추가하는 방식, 하나의 키에 여러 필드를 단순히 결합

ex) (성, 이름)을 키로 색인, 다차원 색인(공간)

 

3. 전문 검색과 퍼지 색인

- 애매모호한 질의에 대한 색인, 유사한 키에 대해 검색

- 특정거리 편집

- tri 알고리즘과 유사

 

4. 인메모리 데이터베이스

- 램의 가격 저렴, 여러 장비에 분산하여 보관

- 복제본에 상태를 적재해야 함

- 디스크에 기록하기 위한 형태로 부호화하는 오버헤드를 피할 수 있어서 빠름

- 디스크 기반 색인으로 구현하기 어려운 모델 제공 ex) 우선순위 큐, set

- 디스크 중심 아키텍처에서 발생하는 오버헤드 없이 가용한 메모리보다 더 큰 데이터셋을 지원하도록 확장 가능

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

- OS보다 더 효율적으로 메모리 관리