Chapter 3. Storage and Search

소개

본 글은 데이터 중심 어플리케이션(마틴 클레프만)으로 스터디하며 해당 책의 내용을 요약 정리한 내용입니다.

https://github.com/ddia-study/ddia-study

GitHub - ddia-study/ddia-study: 데이터 중심 어플리케이션 설계

 

서론

데이터베이스가 데이터를 저장하는 방법과 데이터를 요청했을 때 다시 찾을 수 있는 방법에 대해 알아보자.

특정 작업부하(workload) 유형에서 좋은 성능을 내게끔 저장소 엔진을 조정하려면 저장소 엔진이 내부에서 수행되는 작업에 대해 대략적인 개념을 이해할 필요가 있다.

 

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

많은 데이터베이스는 내부적으로 추가 전용(append-only) 데이터 파일인 로그(log)를 사용한다.

본 책에서 로그는 연속된 추가 전용 레코드다.

데이터베이스에서 특정 키의 값을 효율적으로 찾기 위해서는 색인(index)이 필요하다.

Index는 어떤 부가적인 메타데이터를 유지하고, 이를 통해 원하는 데이터 위치를 찾는데 도움을 받는다.

어떤 종류의 색인이라도 대개 쓰기 속도를 느리게 만든다. 이는 데이터를 쓸 때마다 매번 색인도 갱신해야 하기 때문이다.

색인을 잘 선택했다면 읽기 질의 속도가 향상되지만 모든 색인은 쓰기 속도를 떨어뜨린다.

 

해시 색인

key-value 형식으로 바이트 오프셋에 맵핑해 인메모리 해시 맵을 유지하는 방식.

파일에 key-value pair를 추가할 때마다 방금 기록한 데이터의 오프셋을 반영하기 위해 해시 맵도 갱신해야 한다.

해시 맵을 전부 메모리에 유지하는 방식은 키당 쓰기가 아주 많지만 고유 키는 많지 않은 경우에 유리하다. (e.g. 비디오 재생 횟수)

하지만 파일에 항상 추가만 한다면 디스크 공간이 부족해지기 때문에, segment로 로그를 나눠서 해결한다.

또한 세그먼트 파일들에 대해 compaction을 수행할 수 있다.

중복 키를 버리고 각 키의 최신 갱신 값만 유지하는 것을 의미한다.

각 세그먼트는 키를 파일 오프셋에 매핑한 자체 인메모리 해시 테이블을 갖는다.

java의 hashmap 관련 : https://d2.naver.com/helloworld/831311

 

고민 요소

• 파일 형식
• 레코드 삭제
• 고장 복구
• 부분적 레코드 쓰기
• 동시성 제어

 

Is "Append-Only" Waste?

• 순차 쓰기 작업이라 무작위 쓰기보다 빠르다
• 동시성, 고장 복구가 훨씬 간단하다.
• 병합을 통해 파일 조각화 문제 해결

 

Restrictions about Hash Table Index

• 키가 너무 많으면 문제가 되고, 디스크에 유지할 수도 있으나 좋은 성능을 기대하기 어렵다.
• 범위 질의(range query)에 효율적이지 않다.

 

SS Table and LSM Tree

key-value pairs를 key로 정렬하는 것 == Sorted String Table(SS Table)

각 키는 각 병합된 세그먼트 파일 내에 한 번만 나타나야 한다.(compaction에서 이를 보장)

 

Advantages of SS Table

• 병합이 간단하고 효율적(병합정렬 유사)
• 메모리에 모든 키 색인 유지 불필요 (희소 색인)
• 희소 인메모리 색인의 각 항목은 압축된 블록의 시작. 따라서 디스크 공간 절약 & I/O 대역폭 사용도 줄임.

 

저장소 엔진 만들기

쓰기는 임의 순서인데, 데이터를 어떻게 정렬할 것인가?

RB Tree, AVL Tree 등을 통해 메모리에 유지한다.

• 쓰기가 들어오면 balanced tree에 추가한다. 이 in-mem tree는 memtable이라고도 한다.
• memtable이 보통 수 메가바이트 정도의 임계값보다 커지면 SS테이블 파일로 디스크에 기록한다. 이미 정렬되어 있어서 효율적으로 수행할 수 있다.
• 읽기 요청을 제공하려면 memtable에서 키를 찾고, 디스크 상의 가장 최신 세그먼트에서 찾는다.
• 세그먼트 파일을 합치고 덮어 쓰여지거나 삭제된 값을 버리는 병합, compaction을 백그라운드에서 가끔 수행한다.

DB가 고장나면 memtable의 최신 쓰기는 손실되기 때문에, 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크 상에 유지해야 한다.
(for 복원)

 

SS Table to LSM Tree

Log-Structured Merge-Tree.

정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라고 부른다.

LSM 트리의 기본 개념은 백그라운드에서 연쇄적으로 SS 테이블을 지속적 병합하는 것.

e.g. Lucene's term dictionary

LSM 트리 관련 더 구체적이지만 간단한 설명 : https://www.secmem.org/blog/2021/02/21/lsm-tree/

LSM Tree

 

Optimizing performance

• 존재하지 않는 키 찾을 때 오래 걸림. 따라서 Bloom Filter(집합 내용을 approximating한 구조. 키 유무를 알려줌)
• SS Table을 압축 병합하는 순서와 시기를 결정하는 다양한 전략 존재. (Size-tiered, Leveled compaction)

 

B Tree

B Tree는 SS Table 같이 키로 정렬된 key-value pari를 유지하기 때문에 key-value 검색과 range query에 효율적이다.

하지만 설계 철학은 매우 다르다.

B Tree는 4KB 정도의 고정 크기의 블록이나 페이졸 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 한다.

디스크가 고정 크기 블록으로 배열되어 있기 때문에 이런 설계는 근본적으로 하드웨어와 조금 더 밀접한 관련이 있다.

트리의 루트 페이지는 여러 키와 하위 페이지의 참조를 포함한다.

페이지 참조를 따라가다가 최종적으로는 개별 키를 포함하는 leaf page에 도달한다.

B Tree의 한 페이지에서 하위 페이지를 참조하는 수를 branching factor라고 부른다.

B Tree에 존재하는 키 값 갱신은, 리프 페이지를 찾고 페이지 값을 바꾼 다음 페이지를 디스크에 기록한다.

새로운 키 추가는 페이지를 찾고, 해당 페이지에 키와 값을 추가한다.

새로운 키를 수용한 페이지에 여유공간이 없다면 페이지 하나를 반쯤 채워진 페이지 둘로 나누고 상위 페이지가 새로운 키 범위의 하위 부분들을 알 수 있게 갱신한다.

B-tree visualization : https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree Visualization

트리는 계속 균형을 유지하며 depth는 $O(logn)$이다.

 

신뢰할 수 있는 B Tree

B tree는 기본적으로 새 데이터를 디스크 상의 페이지에 덮어쓴다.

orphan page, 어떤 페이지와도 부모 관계가 없는 페이지, 가 발생할 수도 있다.

따라서 DB가 스스로 복구할 수 있게 하려면 디스크 상에 쓰기 전 로그(WAL, write-ahead log 혹은 redo log)를 추가해 B tree를 구현한다.

모든 B Tree의 변경 사항을 기록하고 있는 append-only 파일이며, 이 로그는 DB 고장 이후 복구될 때 일관성 있는 상태로 B 트리를 복원할 때 사용한다.

 

Optimizing B Tree

• WAL 대신 copy-on-write-scheme를 사용한다. 변경된 페이지를 다른 곳에 기록하고 트리에 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가리키게 한다.
• 페이지에 전체 키를 쓰지 않고 키를 축약해 쓰면 공간을 절약할 수 있다. 경계 역할만 하도록 정보를 제공한다.
• 리프 페이지를 디스크 상에서 연속된 순서로 나타나게끔 트리를 배치하려 시도
• 트리에 포인터를 추가한다. 리프 페이지가 형제 페이지에 대한 참조를 가지면, 스캔하기 더 편하다.
• 프랙탈 트리 같은 변형은 디스크 찾기를 줄이기 위해 로그 구조화 개념을 일부 빌렸다.

 

B tree vs LSM

• 쓰기 증폭(write amplifcation) issue (LSM 우세)
• 압축률 & 파편화 (LSM 우세)
• 예측 가능한 성능 (B Tree 우세)
• For Transaction (B Tree 우세)

 

기타 색인 구조

• Secondary Index
• Clustered Index
• Covering Index
• Concatenated Index
• Fuzzy Index(levenshtein automaton etc)

 

Disk 관련을 마치며

지금까지 설명한 데이터 구조는 모두 디스크 한계에 대한 해결책이다.

디스크는 지속성이 있고 램보다 가격이 저렴하다.

하지만 램이 점점 저렴해졌고, 데이터셋 대부분은 그다지 크지 않기 때문에 메모리에 전체를 보관하는 방식도 현실적이다.

In-memory database

직관에 어긋나지만 인메모리 데이터베이스의 성능 장점은 디스크에서 읽지 않아도 된다는 사실 때문은 아니다.

디스크 기반 저장소 엔진도 운영체제가 최근에 사용한 디스크 블록을 메모리에 캐시 하기 때문에 충분한 메모리를 가진 경우 디스크에서 읽을 필요 없다.

인메모리 디비는 디스크 기반 색인으로 구현하기 어려운 데이터 모델(Set, Priority Queue)과 같은 다양한 데이터 구조를 제공한다. 또한 메모리에 모든 데이터를 유지하기 때문에 구현이 비교적 간단하다.

최근 연구에서는 인메모리 디비 구조가 오버헤드 없이 가용한 메모리보다 더 큰 데이터셋을 지원하게끔 확장할 수 있다.

Anti-caching 접근 방식은 메모리가 충분하지 않을 때 가장 최근에 사용하지 않은 데이터를 메모리에서 디스크로 내보내고 나중에 다시 접근할 때 메모리에 적재하는 방식으로 동작한다.

 

트랜잭션 처리나 분석?

특성	OLTP(online transaction processing)	OLAP(online analytic processing)
주요 읽기 패턴	질의당 적은 수의 레코드, 키 기준으로 가져옴	많은 레코드에 대한 집계
주요 쓰기 패턴	임의접근, 사용자 입력을 낮은 지연 시간으로 기록	대규모 불러오기 또는 이벤트 스트림
주요 사용처	웹 애플리케이션을 통한 최종 사용자/소비자	의사결정 지원을 위한 내부 분석가
데이터 표현	데이터의 최신 상태	시간이 지나며 일어난 이벤트 이력
데이터셋 크기	기가바이트에서 테라바이트	테라바이트에서 페타바이트

 

Data warehousing

ad hoc analytic query는 비싸기 때문에 이를 OLTP DB에 실행하는 것을 꺼려함.

반면, 데이터 웨어하우스는 OLTP에 영향을 주지 않고 질의할 수 있는 개별 DB.

데이터는 OLTP 데이터베이스에서 주기적으로 extract하고 분석 친화적인 스키마로 transform하고 깨끗하게 정리한 다음 데이터 웨어하우스에 load한다. (ETL)

 

OLTP DB vs Data Warehouse

둘 다 SQL 인터페이스를 써서 비슷할 거 같지만 서로 다른 질의 패턴으로 인해 내부는 굉장히 다르다.

 

Star schema & Snowflake schema

분석에서는 데이터 모델의 다양성이 훨씬 적으며, 보통 정형화된 방식인 별 모양 스키마를 사용한다.

스키마의 중심에는 소위 Fact table이 있고, 테이블의 각 로우는 특정 시각에 발생한 이벤트에 해당한다.

또한 외래 키 참조가 존재하는데, 참조를 따라가면 나오는 테이블을 dimension table이라고 한다.

차원은 who, when, where, what, how, why를 나타낸다.

Star schema의 변형 == Snowflake schema

차원이 하위 차원으로 더 세분화 된다. 하지만 작업하기 쉽다는 이유로 star schema가 더 선호된다고 한다.

 

Column 지향 저장소

테이블에 엄청나게 많은 로우와 페타바이트 데이터가 있다면 효율적으로 저장하고 질의하는 것은 어려운 문제가 된다.

차원 테이블은 보통 수백만 로우 정도로 훨씬 적어서 "저장"에 집중해보자.

Fact table은 칼럼이 보통 100개 이상이지만 실제 질의는 한 번에 4~5개 컬럼에만 접근한다.

칼럼 지향 저장소 : 모든 값을 하나의 로우에 함께 저장하지 않는 대신 각 칼럼별로 모든 값을 함께 저장한다. 각 칼럼을 개별 파일에 저장하면 질의에 사용되는 칼럼만 읽고 구분 분석하면 된다.

각 칼럼 파일에 포함된 로우가 같은 순서인 점에 의존한다.

 

Column 압축

칼럼에서 고유 수는 로우 수에 비해 적다. 따라서 n개의 고유 값을 가진 칼럼을 가져와 n개의 개별 비트맵으로 변환할 수 있다.

이런 bitmap encoding을 통해 데이터를 효율적으로 압축할 수 있다.

참고 : Run-length encoding

https://ko.wikipedia.org/wiki/%EB%9F%B0_%EB%A0%9D%EC%8A%A4_%EB%B6%80%ED%98%B8%ED%99%94

런 렝스 부호화 - 위키백과, 우리 모두의 백과사전

 

Parquet 관련 글 : https://engineering.vcnc.co.kr/2018/05/parquet-and-spark

Apache Spark에서 컬럼 기반 저장 포맷 Parquet(파케이) 제대로 활용하기

 

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

수백만 로우를 스캔해야 하는 질의는 디스크로부터 메모리로 데이터를 가져오는 대역폭이 큰 병목이다.

분석용 DB 개발자는 메인 메모리에서 CPU 캐시로 가는 대역폭을 사용하고 CPU 명령 파이프라인에서 brnch misprediction, bubble을 피하며 SIMD(single-instruction-multi-data)를 사용하게끔 신경 써야 한다.

또한 압축된 컬럼 데이터 덩어리를 바로 연산할 수 있게 하는 기법을 vectorized processing이라고 한다.

 

칼럼 저장소의 순서 정렬

칼럼 별로 저장됐을지라도 데이터는 한 번에 전체 로우를 정렬해야 한다.

정렬된 순서의 장점

• 그룹화 혹은 필터링 질의에 도움이 됨
• 칼럼 압축에 도움이 됨

 

Aggregation in Data warehouse

데이터 웨어하우스에서는 materialized aggregate, 즉 max, avg 등의 집계 함수를 사용하는 경우가 많다.

따라서 질의가 자주 사용하는 일부 카운트나 합을 캐시 하는 방법으로 materialized view를 사용한다.

보통 OLTP의 경우, 데이터 갱신 시 뷰도 갱신해야 하기 때문에 cost가 높아 잘 사용하지 않는다.

그러나 Data warehouse의 경우 읽기 비중이 훨씬 높기 때문에 합리적이다.

Data cube 혹은 OLAP cube라고 알려진 구체화 뷰는 구체화 뷰의 일종이다.