데이터중심 애플리케이션 설계 - 3장 [저장소와 검색] 리뷰 - 1

728x90

3장을 읽으며 발췌 및 정리하면 좋을 내용들에 대해서만 정리하였다.

DB의 작업

data 저장
data 요청시, 제공

개발자가 DB 내 저장 및 검색 처리 방법을 주의해야 하는 이유 :

- 처음부터 저장소 엔진을 구현하는 것이 아닌, 사용 가능한 여러 저장소 엔진 중 가장 적합한 엔진을 선택해야 하기 때문

ex_ transaction 작업 부하에 맞추어 최적화된 저장소 엔진과 분석을 위해 최적화된 엔진 간의 차이는 크다.

로그 구조 계열 저장소 엔진(Log-structured) - ex) B-tree
페이지 지향 계열 저장소 엔진(Page-Oriented)

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

일반적으로 많은 DB는 내부적으로 추가 전용(append-only) 데이터 파일인 로그(log)를 사용
- 로그 - 일반적인 의미 : 연속된 추가 전용 레코드 (binary 파일인 경우 많음)
DB에서 다뤄야할 문제들
- 동시성 제어
- 로그 compaction을 통한 디스크 공간 회수
- 오류 처리 (오류로 인한 부분적 기록 레코드 ... )
- ...

색인(index) : DB의 특정 키의 값을 효율적으로 찾기 위한 데이터 구조

일반적인 개념 : 부가적인 metadata 유지
기본 데이터(primary data)에서 파생된 추가적인 구조
색인 추가/삭제 작업은 DB 내용에 대해서는 영향을 미치지 않는다.
But 질의(Query) 성능에 대해서 영향
추가적인 구조에 대해 유지보수 - write 과정에서 상대적으로 오버헤드가 크다 (DB의 trade-off)
- 기본적인 쓰기작업은 가장 간단한 작업임에 반해, 색인에 대한 쓰기작업은 자체적으로 부가작업이기 때문
- 이는 데이터를 쓸 때마다 매번 색인도 갱신해야 하기 때문 ( ∴ 어떤 종류의 색인이라도 대개 쓰기 속도를 느리게 만든다)
- 색인 선택 => read Query 속도 향상 / 모든 색인 write 속도 하락

Hash Index

Key - Value 색인 구조 (a.k.a dictionary Type)
가장 간단한 색인 전략 - key 값 데이터 파일의 byte offset에 매핑해 Inmemory HashMap 유지
- byte-offset을 통해 값을 바로 찾을 수 있음
- but 파일에 k-v를 추가할 때마다 직전 data offset을 반영하기 위해서는 메모리의 HashMap도 갱신해야함

해당 방식 : Bitcask(비트캐스크) - 리악(Riak)의 기본 저장소 엔진에서 근본적으로 사용하는 방식
- 비트캐스크 : HashMap을 전부 메모리 유지 -> 고성능의 읽기 쓰기 보장
해당 방식은 key 별 value가 자주 갱신되는 상황에 매우 적합하다
즉 쓰기가 많지만, 고유 key 값이 많지 않은 상황(key 당 쓰기 수가 많지만 메모리에 모든 키 보관이 가능할 때)

File에 지속적인 write으로 인해 디스크의 공간이 부족해질 때의 방법

특정 크기 segment 유지 + compaction

특정 크기의 세크먼트로 로그를 나누어 쓴다. (특정 크기 도달 시 새로운 세그먼트에 작성)
이후 세크먼트 파일들에 대해 compaction 진행 (동시 여러 세그먼트도 병합)
- log에서 중복된 키를 버리고 키별 최신 value만 유지

세그먼트 병합은 백그라운드 스레드에서 수행, 이를 통해 이전 세그먼트에 읽기/쓰기 처리 정상 수행 가능
병합 과정을 통해 세그먼트 수를 더 적게 유지하기 때문에 조회할 때 많은 해시 맵을 확인할 필요 X

실제 구현에서의 고려사항들

1. 파일 형식 - 바이너리 형식을 사용하는 편이 더 빠르고 간단
2. 레코드 삭제 - key와 관련한 값 삭제시, 특수 삭제 레코드(ex_툼스톤)을 추가. 툼스톤은 세그먼트 병합할 때 삭제된 키의 이전 값 무시하게 함
3. 고장 복구 - DB 재시작 = 인메모리 해시 맵 손실 / 비트캐스크는 각 세그먼트 해시 맵을 통해 스냅숏을 디스크에 저장하여 복구 성능 향상
4. 부분적 레코드 write - 비트캐스크 파일 내 체크섬을 통해 로그의 손상된 부분 탐지
5. 동시성 제어 - 데이터 파일 세그먼트는 추가 전용 혹은 불변이므로 다중 스레드로 동시 읽기 가능

추가 전용 로그의 장점

1. 추가와 세그먼트 병합은 순차적인 write 작업이므로 무작위 쓰기보다 빠르다.
2. 세그먼트 파일이 추가 전용이나 불변일 때, 동시성과 고장 복구에 대해서 간단하다
(이전 값 부분과 새로운 값 부분을 포함한 파일이 나뉘어져 있기 때문)
3. 오래된 세그먼트 병합은 파편화 문제를 방지할 수 있다.

HashTable Index 제약사항

키가 너무 많으면 안된다 (메모리에 저장하므로) :
- 무작위 접근 I/O 가 많이 필요하고 디스크가 가득 찾을 때 확장 비용 비쌈 / 해시 충돌에 대해 추가적인 로직 필요
Range Query에 효율적이지 못하다 :
- HashMap에서는 모든 개별 키 조회 필요

제한 없는 색인 구조 : SS TABLE & LSM 트리

- 일련의 Key-Value 쌍을 키로 정렬하는 것이 특징

SS Table (Sorted String Table)

각 키는 병합된 세그먼트 파일 내에 한 번만 나타나야 한다. (컴팩션으로 이를 보장)
- 새로 병합되어 만들어진 세그먼트 파일도 키로 정렬
- 다중 세그먼트가 동일한 키를 가질 시, 최근 세그먼트 값 유지

장점 :

세그먼트 병합은 파일이 사용가능한 메모리보다 크더라도 간단하고 효율적 (병합정렬 방식과 유사)
- 새로 만든 세그먼트 파일도 파일도 역시 키로 정렬 (다중 세그먼트가 동일한 키를 가질시, 최근 값 유지)
파일에서 특정 키를 찾기 위해 더는 메모리에 모든 키의 색인을 유지할 필요 X
- 정렬되어 있기 때문에, 찾고자하는 키와 비슷한 오프셋을 가진 키를 메모리에서 찾으면 된다.
압축을 통해 I/O 대역폭 사용도 줄인다.

생성과 유지 :

데이터 정렬 유지 수월한 편 : 디스크(B-Tree) < 메모리(RB tree / AVL tree)

메모리에 데이터 정렬을 유지하는 구조를 선택할 시, 임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 다시 읽을 수 있음

RB / AVL tree 데이터 정렬 유지 동작 방식

1. write 요청이 들어오면 메모리 내의 균형트리(memtable) 데이터 구조에 추가한다.
2. 멤테이블이 보통 메가바이트 정도의 임계값보다 커질 때, SS테이블 파일로 디스크에 기록 -> 최신 세그먼트
- 기록하는 동안 write 요청은 새로운 멤테이블 인스턴스에 기록
3. read 요청에 대해서는 memtable에서 키를 찾는다. 없다면 디스크 내의 최신 세그먼트 -> 2번째 세그먼트 -> ...
4. 백그라운드에서 세그먼트 병합 및 컴팩션 과정 수행

문제점 : (DB 고장 발생 : 디스크로 기록되지 않고 멤테이블에 있는 가장 최신 쓰기는 손실)
해결책 : 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크에 유지

LSM(log structured merge tree)을 이용한 SS TABLE

Key-Value 저장소 엔진 라이브러리에서 사용
정렬된 파일 병합 + 컴팩션 원리를 기반으로 하는 저장소 엔진 = LSM 저장소 엔진
- ex) Lucene(루씬 - Elasticsearch / Sola 전문 검색 색인 엔진) 의 term dictionary를 저장하기 위해 유사한 방법 사용
LSM 트리 알고리즘 - DB에 존재하지 않는 키를 찾는 경우 느릴 수 있음
- 1. memtable check ... -> 2. 가장 오래된 segment check... -> 3. disk check ...
- 해당 문제점을 최적화하기 위한 방법 : 블룸 필터(Bloom filter) - 집합 내용을 근사처리한 메모리 효율적 데이터 구조
  - 키가 DB에 존재하지 않음을 알려줌

SS Table 병합 전략

1. 크기 계층 (size-tiered) : 상대적 새롭고 작은 SS 테이블을 오래되고 큰 SS 테이블에 병합

2. 레벨 컴팩션(leveled compaction) : 키 범위를 더 작은 SS 테이블로 나누고 오래된 데이터는 개별 레벨로 이동시킨다.
(디스크 공간 낭비 X)

LSM 트리 정리
- 기본 개념 : 백그라운드에서 연쇄적 SS 테이블 병합
- 데이터셋이 메모리보다 훨씬 더 크더라도 효과적
- 데이터 정렬적 저장 -> 범위 Query 효율적 (최소에서 최대까지 모든 키 스캔 가능)
- 디스크 write : 순차적 / 이를 통한 매우 높은 쓰기 처리량 보장