Chapter 3. Storage and Retrieval

이번 챕터에서는 데이터베이스에 저장되는 데이터의 형태와 저장 방식에 따른 장단점에 대해 살펴보겠습니다. 데이터베이스는 데이터를 효율적으로 저장하고 찾기 위해 인덱스를 활용합니다. 이러한 인덱스를 저장하는 방식을 크게 분류하면 log-structured 형태와 page-oriented 형태의 저장방식으로 구분됩니다. 

 

Log Structured Indexes 

Hash Table 

가장 기초적인 데이터 저장 및 조회 방법으로는 해시 테이블을 사용할 수 있습니다. 이 방법은 Key-value 형태의 데이터를 메모리 상에 유지하면서 주기적으로 디스크로 플러시합니다. 데이터는 append 형식으로 디스크 파일 끝에 추가됩니다. 디스크에 저장된 데이터는 segment 단위로 구분하며, 더 이상 쓰기 작업이 없는 segment에 대해서는 압축(compaction)을 통해 디스크 저장 공간을 확보할 수 있습니다. 또한, 여러 segment를 하나로 병합(merge)함으로써 디스크 공간을 추가로 확보할 수 있습니다.

 

압축(Compaction) 

A : 50

B : 30

C : 40

A : 20

A : 30

B: 10

B: 60

Segment 압축은 다음과 같은 과정으로 수행됩니다. 위에 표시된 segment는 왼쪽에 위치한 데이터일수록 최근 데이터라고 가정했을 때 압축 후 형태는 다음과 같습니다. 

A: 50

B: 30

C: 40

 

병합(Merge) 

A: 30

B: 40

C: 20

E: 50

B: 100

C: 50

F: 10

Z: 30

위 두 segment를 병합하면 다음과 같은 새로운 segment가 생성됩니다. 

A: 30

B: 100

C: 50

E: 50

F: 10

Z: 30

 

위 방식의 hash index는 다음과 같은 특징을 가지고 있습니다. 

• 데이터가 삭제됐음을 나타내기 위해 데이터(tombstone)를 추가합니다. 해당 데이터는 병합 과정에서 tombstone을 참조하여 삭제됩니다. 
• 로그가 추가되는 과정에서 데이터베이스 시스템이 다운되면 데이터가 부분적으로 저장되는 현상이 발생할 수 있습니다. 이를 방지하기 위해서 checksum을 활용하여 유효하지 않은 데이터를 식별할 수 있습니다. 
• 로그를 추가하는 형태의 이 방식은 동시성 제어가 어렵지 않습니다. 쓰기 동시성 제어는 로그 추가를 수행하는 writer를 동기적으로 동작함으로써 동시성 제어가 가능합니다. 위 방식에서 데이터가 저장되는 방식은 immutable, 즉 저장된 데이터에 update가 발생하지 않기 때문에 다수의 reader가 동시에 접근하더라도 동시성 문제가 발생하지 않습니다. 

그럼 왜 위와 같은 로그를 append하는 방식을 활용할까요? 위 방식은 다음과 같은 장점이 있기 때문에 활용합니다. 

• 랜덤 한 위치에 데이터를 쓰거나 업데이트하는 것보다 파일 뒤에 추가하는 것이 HDD 또는 SDD 모두 성능면에서 우수합니다. 
• 동시성 제어가 용이합니다. 
• 시스템 다운 후 복구가 용이합니다. In-place update를 지원했다면 시스템 다운 후 어떤 데이터가 부분적으로 쓰였는지 확인하는 과정이 필요합니다. 로그를 추가하는 방식은 로그 파일의 가장 마지막 데이터만 확인하면 됩니다. 

하지만 모든 시스템에 그러하듯 장점만 존재하는 것은 아닙니다. 로그 추가 방식에는 다음과 같은 단점이 존재합니다. 

• 해시 테이블 전체를 메모리에 적재해야 사용 가능합니다. 일부 해시 테이블만 메모리에 적재한다면 메모리에 없는 데이터를 조회하기 위해서 발생하는 random I/O로 인해 성능저하가 클 수 있습니다. 
• 기본적으로 해시 테이블은 정렬되지 않은 상태이므로 범위 쿼리(range query) 성능이 좋지 않습니다. 

 

SSTables and LSM-Trees 

해시 테이블을 사용하는 구조는 메모리에 해시 테이블을 모두 적재해야 하고 범위 쿼리 성능이 좋지 않다는 단점이 있다고 말씀드렸습니다. 이 단점을 극복할 수 있는 자료구조로 SSTable이 있습니다. SSTable은 키를 기준으로 정렬된 자료구조를 메모리와 디스크에 저장합니다. 메모리에 위치한 이 자료구조를 memtable이라 부르기도 합니다. 

SSTable이 해시 테이블의 단점을 어떻게 극복했는지 살펴보겠습니다. 기본적으로 SSTable은 key를 기준으로 정렬되기 때문에 메모리에 모든 key-value를 적재하지 않아도 됩니다. "정렬된 상태 -> Binary search"가 떠오르는 구조입니다. 만약 특정 key에 대응되는 value를 찾고자 할 때, 해당 key-value가 메모리에 적재되지 않았더라도 메모리에 위치한 key를 통해 해당 key가 위치한 디스크의 위치를 예측할 수 있습니다. 두 번째로 SSTable은 key를 기준으로 정렬되기 때문에 해시 테이블과 다르게 범위 쿼리 성능이 우수합니다. 

SSTable은 전체 key-value를 메모리에 적재할 필요가 없다.

SSTable은 merge sort 정렬 방법으로 메모리의 데이터와 디스크상의 데이터를 병합합니다. 메모리의 데이터와 디스크상의 데이터 모두 정렬된 상태이므로 서로 값을 비교하면서 더 작은 데이터를 순차적으로 선택하는 방법으로 병합을 수행할 수 있습니다. 

다음으로는 SSTable에서 쓰기와 읽기를 어떻게 처리하는지 살펴보겠습니다. 

• 쓰기 요청은 메모리상의 memtable에서 처리합니다. 
• Memtable이 일정 크기 이상이 되면 디스크에 플러쉬합니다. 
• 읽기 요청은 memtable -> 디스크의 SSTable1 -> 디스크의 SSTable2.... 형태로 해당 데이터를 찾을 때까지 진행합니다. 
  • 만약 존재하지 않는 데이터에 대한 읽기 요청이 수행되면 여러번의 random I/O가 발생할 수 있습니다. 해당 데이터가 존재하는지 여부를 빠르게 확인할 수 있는 Bloom filter을 사용해 최적화를 수행하기도 합니다. 
• 압축과 병합과정은 백그라운드에서 수행됩니다. 
• 쓰기 과정에서 시스템이 다운되면 데이터가 유실될 수 있습니다. 이를 방지하기 위해서 별도의 정렬되지 않는 append-only 로그파일을 추가적으로 사용할 수 있습니다. 

SSTable의 동작원리와 LSM Tree의 동작원리는 유사합니다. LSM Tree의 개념이 먼저 등장했고 이후 Google의 "Bigtable: A Distributed Storage System for Structured Data"에서 SSTable이 소개됩니다. Google의 BigTable 시스템은 데이터를 저장하기 위한 일종의 file format으로 SSTable을 활용합니다. 

The Google SSTable file format is used internally to store Bigtable data. An SSTable provides a persistent, ordered immutable map from keys to values, where both keys and values are arbitrary byte strings

 

LSM 트리의 동작원리에 대해 궁금하시다면 아래의 포스팅을 참고해주세요. 

LSM-Tree는 왜 사용할까

 

Performance Optimization 

SSTable이나 LSM-Tree에 저장되지 않은 데이터를 조회하고자하는 요청이 들어오면 어떻게 될까요? 존재하지 않는 데이터를 찾기 위해 memtable부터 디스크에 위치한 모든 SSTable를 조회합니다. 이와 같은 불필요한 탐색을 줄이기 위해 Bloom filter을 사용할 수 있습니다. Bloom filter을 활용하면 SSTable에 저장되지 않았음을 바로 식별할 수 있기 때문입니다. 

SSTable이나 LSM-Tree는 압축을 통해 공간 효율성을 높입니다. SSTable은 size-tiered compaction을, LSM-Tree는 leveled compaction을 지원합니다. 

• Size-tiered compaction: Memtable은 일정 시간마다 데이터를 디스크로 flush합니다. 디스크는 여러 레벨로 구성되고 각 레벨은 여러 개의 SSTable(run으로 부르기도 합니다)을 가지며, 가장 하위 레벨에 위치한 SSTable들의 크기가 가장 큽니다. Size-tiered compaction은 동일한 레벨에서 SSTable의 크기를 비슷하게 유지하려고 노력합니다. 하나의 레벨에 포함된 SSTable들의 크기의 총합이 한도에 도달하면 전체 레벨이 병합되어 다음 레벨로 flush 됩니다. 병합은 해당 레벨에 포함된 런의 크기의 총합이 한도보다 작아질 때까지 재귀적으로 수행됩니다. 

Size-tiered compaction

• Leveled compaction: Size-tiered compaction과 유사하지만 약간의 차이가 있습니다. 유사한 점은 각 레벨별로 포함할 수 있는 데이터의 threshold가 정해져있고 레벨이 높을수록 threshold가 큽니다. 다른점은 threshold를 초과했을 때 해당 레벨에서 하나의 SSTable이 선택돼서 다음 레벨의 SSTable과 합쳐집니다. 

Leveled compaction

 

B-Trees

위에서 살펴본 로그 형태의 저장방식은 디스크에 데이터를 순차적으로 flush합니다. B-tree는 디스크를 page 단위로 읽고 쓰며 디스크의 데이터를 업데이트하는 방식으로 동작합니다. 상용 데이터베이스가 활용하는 B-tree는 주로 B+tree를 의미합니다. B+tree의 특성과 동작원리를 자세히 알고 싶다면 아래 포스팅을 참고해주세요. 

[Database] DBA급 개발자로 - #7 B+Tree

B-tree는 디스크에 데이터를 쓰기 위해 최소 2번의 쓰기 작업이 필요하고, 작은 데이터 수정 역시 페이지 전체를 업데이트해야하는 오버헤드가 존재합니다. 하지만 LSM-tree는 데이터를 순차적으로 쓰기 때문에 쓰기 성능이 비교적 우수합니다. 단, compaction과 merge 과정이 있어 B-tree와 유사하게 하나의 데이터에 쓰기 작업을 여러번 수행하기도 합니다.

B-tree는 노드간 split, merge 등 fragmentation이 발생할 수 있는 작업이 많아 사용되지 않는 빈 공간이 생길 수 있습니다. 반면 LSM-tree는 순차적으로 디스크에 쓰기 작업을 수행하므로 fragmentation 걱정이 적습니다.

하지만 LSM-tree도 단점이 존재합니다. Compaction 과정에서 다른 작업에 영향을 줄 수 있으며, compaction 속도가 쓰기 작업을 처리하는 속도보다 느릴 경우 디스크가 꽉 찰 수 있습니다.

결론적으로, B-tree와 LSM-tree는 각각의 장단점이 있으며, 사용하는 데이터베이스 시스템의 용도와 요구 사항에 따라 적절한 자료구조를 선택해야합니다.

 

Others 

Clustered index 

Clustered index는 index의 저장 순서와 실제 테이블의 행(row)이 저장된 순서가 동일한 인덱스입니다. RDBMS의 대표적인 clusterd index는 primary index입니다. Primary index는 디스크에 저장된 순서와 실제 테이블의 row가 저장된 순서는 동일합니다. 

Secondary index 

Secondary index는 primary index 이외의 인덱스를 의미합니다. Secondary index는 인덱스를 구성하기 위한 값과 primary index값을 함께 저장합니다. 디스크 상의 실제 테이블 행(row)의 위치(heap file)가 아니라 primary key를 가리키는 이유는 테이블의 행(row)이 저장된 위치가 변경될 수 있기 때문입니다. 테이블의 행(row) 위치가 변경될 때마다 secondary index를 업데이트해야 한다면 성능면에서 불리할 것이기 때문입니다. 

Full-text search and Fuzzy index 

검색어와 일치하거나 유사한 값을 찾기 위해 사용하는 인덱스입니다. 대표적으로 Elastic Search에서는 이러한 인덱스를 활용하여 전문 검색(full-text search) 기능을 제공합니다.

Everything in Memory 

메모리 기반 데이터베이스는 모든 데이터를 메모리에 저장하는 방식입니다. 이 방식은 디스크를 위한 최적화가 필요 없기 때문에 메모리에서만 효율적인 자료구조를 활용할 수 있습니다. 하지만, 메모리에 저장된 데이터는 전력 공급이 중단되면 영구적으로 손실될 수 있기 때문에 데이터 유실 방지를 위한 다양한 방법을 사용합니다.

Durability를 보장하는 in-memory 데이터베이스는 다음과 같은 기능을 제공하기도 합니다. 
- Battery powered RAM 
- 메모리의 snapshot을 주기적으로 디스크에 저장 
- 복제 

 

Online Analytical Processing 

운영환경의 데이터베이스에 분석을 위해 쿼리를 날려보신 적 있으신가요? 제가 직접 해본적은 없지만 종종 "SELECT column_A.*"과 같은 데이터베이스에 영향을 줄 수 있는 쿼리를 수행했을 때 DBA 분들께 연락이 오는 것을 봤습니다. 되도록이면 무거운 쿼리를 실행하지 말아달라고 말입니다. 하지만 데이터 분석을 위해서는 이와 같은 유형의 쿼리 결과가 필요한 경우가 있습니다. 이에 대응하기 위해 OLAP에 적합한 데이터베이스로 데이터를 복제해서 쿼리를 수행하는 방법을 사용하기도 합니다. 

 

Data warehousing 

Data warehousing이란 조직 내 다양한 소스로부터(shopping app, chat app, news app) 대규모 데이터를 수집, 저장 및 관리하는 과정을 의미합니다. 이후 데이터 분석가는 데이터에 쉽게 액세스해 데이터분석을 위한 쿼리를 수행할 수 있습니다. Data warehousing에는 ETL(extract, transform, load)이 포함되며, 이를 활용해 데이터를 data warehouse로 가져와서 분석을 준비합니다. 이후 데이터는 데이터 분석에 적합한 스키마(Star schema, Snowflake schema) 모델로 구성됩니다. Star schema 와 snowflake schema에 대한 설명은 다른 포스팅에서 다뤘기 때문에 해당 포스팅을 참고해주세요. 

[Database] DBA급 개발자로 - #23 Distributed Database 3/3

 

Writing to Column-Oriented Storage 

컬럼형 데이터베이스는 LSM 트리와 유사하게 동작합니다. In-memory에 데이터를 기록하다 일정 수준 이상으로 커지면 disk의 파일과 병합하는 형태로 데이터가 저장됩니다. 컬럼형 데이터베이스가 어떻게 저장되는지는 아래 포스팅을 참고해주세요. 

[Database] DBA급 개발자로 - #4 Database Storage 2/2

 

Aggregation: Data Cubes and Materialized View 

Materialized view는 쿼리 결과를 디스크에 미리 저장한 물리적인 테이블입니다. 이를 사용하면 복잡한 쿼리 결과를 계산하는 데 필요한 시간을 줄여 쿼리 성능을 개선할 수 있습니다. RDBMS에서 흔히 볼 수 있는 가상 뷰와의 차이점은, 가상 뷰는 디스크에 데이터를 별도로 저장하지 않고, 가상 뷰에 쿼리할 때마다 데이터베이스가 기본 테이블이나 뷰를 기반으로 결과를 생성한다는 점입니다.

Data cube는 데이터 웨어하우징에서 자주 사용되는 다차원 데이터의 표현 방법입니다. 데이터 큐브는 집계 과정을 통해 생성되며, 이는 원시 데이터가 다른 차원을 기반으로 집계 및 요약되어 다차원 구조를 생성합니다.

 

마무리 

이번 챕터에서는 데이터를 저장하는 다양한 방법에 대해 살펴보았습니다. 각 방법은 장단점이 있으므로 목적에 따라 적절하게 선택하는 것이 좋습니다.

Reference 

The Log-Structured Merge-Tree (LSM-Tree)

Bigtable: A Distributed Storage System for Structured Data 

https://www.sobyte.net/post/2022-04/lsm-tree/

https://www.alibabacloud.com/blog/an-in-depth-discussion-on-the-lsm-compaction-mechanism_596780