데이터베이스와 색인
데이터베이스의 기본은 특정 데이터를 write & read 하는 데 있다. 값을 특정 저장소에 넣어두고 필요할 때 꺼내쓰는 것이다.
일반적으로 하나의 파일 끝에 write만 하는 작업은 매우 효율적이기 때문에 많은 데이터베이스가 내부적으로 추가 전용(append-only) 데이터 파일인 로그(log)를 사용한다. 하지만 원하는 데이터 값을 읽어오려면 전체 파일을 스캔해서 찾아와 읽어야 한다. 검색 비용이 O(n)이다.
read를 효율적으로 수행하기 위해서 색인(index)라는 데이터 구조가 필요하다. 하지만 별도의 index를 관리해야 하기 때문에 특히 write 할 때 오버헤드가 발생한다. 이러한 작업은 단순히 파일 끝에 write 하는 것보다 쓰기 속도를 느리게 한다. 데이터를 쓰면서 색인도 갱신해야 하기 때문이다.
저장소 시스템에서 indexing 하는 것은 중요한 trade-off다. 색인을 잘 선택해야만 write 시 오버헤드를 최소화하고 read 성능을 향상시킬 수 있다.
해시 색인
위 그림처럼 키를 파일의 바이트 오프셋에 매핑해서 인메모리 해시 맵을 유지하는 전략이다. 모든 키가 메모리에 저장되어 있다는 조건을 전제로 고성능의 write, read를 지원한다.
하지만 키의 갯수가 부족해지면 메모리에 모든 키를 저장할 수 없게 되고, 디스크 공간도 부족해질 수 있다.
디스크 공간 부족은 segment 단위로 파일을 나누어 로그를 관리하고, 분리된 segment들을 compaction 함으로써 해결한다. 아래 그림과 같이 segment1, 2를 유지하다 특정 시점에 이를 merge 하여 중복된 값을 제거하고 유일한 값만 남겨서 새로운 로그 파일로 만든다. 이후 필요 없어진 segment들은 삭제하여 디스크 공간을 확보한다.
장점
- 키의 갯수는 적지만 각 키의 값이 자주 갱신되는 상황에 적합하다. 키당 쓰기 부하가 많더라도 메모리에 모든 키를 보관할 수 있다.
단점
- 키의 갯수가 많아지면 메모리에 모든 키를 저장해둘 수 없고 결국 디스크 공간도 부족해질 수 있다.
- 디스크 공간을 계속 늘리더라도 디스크 상의 해시 맵은 좋은 성능을 기대하기 어렵다.(랜덤 I/O가 많이 필요하고 디스크가 가득 차면 확장 비용이나 해시 충돌을 위한 로직이 추가로 필요)
- 범위 질의(range scan)에 효율적이지 않다. 많은 키를 조회하려면 full scan 해야 한다.
LSM 트리 색인
LSM 트리의 핵심은 백그라운드에서 연쇄적으로 SS(Sorted String)테이블을 지속적으로 병합하는 것
해시 색인의 문제는 키의 갯수가 많아지거나 범위 질의에 있었다. 모든 키를 메모리에 유지해야 한다거나 범위 질의가 불가능했던 이유는 정렬되어 있지 않기 때문이다. 이를 SS 테이블 구조와 메모리에 balnaced tree로 관리하여 해결한다.
SS(Sorted String) 테이블
SS테이블은 아래 그림과 같이 각 segment의 key값이 정렬되어 있는 것을 말한다.
LSM(Log-Structured Merge-Tree) 색인 구조는 SS 테이블에 기반한다. 각 segment들을 병합한 결과가 키 기준으로 정렬되어 있고 merge된 키는 유일하다면 어떨까.
- merge는 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적이다. 각 segment 파일이 정렬되어 있다는 전제로 첫번째 키를 낮은 순서대로 읽어서 병합하면 중복이 제거된 키 정렬 병합 파일이 생성된다.(동일키는 최신 segment를 기준으로 함)
- 특정 키를 read 하기 위해 메모리에 모든 키의 색인을 유지할 필요가 없다. 중간에 비어 있는 키가 있다고 하더라도 키가 정렬되어 있으므로 해당 키가 위치하는 offset을 추정할 수 있다.
위의 작업을 메모리에서 수행한다면 훨씬 효율적이다.
- 쓰기가 들어오면 in-memory balanced tree에 추가한다.(memtable이라고도 함)
- memtable이 특정 크기를 넘어가면 SS테이블 파일로 디스크에 기록한다. 트리가 이미 정렬되어 있으므로 효율적으로 수행된다.
- read 시 memtable -> disk segment(최신) -> disk segment(old)... 순으로 수행한다.
- 컴팩션 작업을 백그라운드에서 수행한다.
위처럼 메모리에서 memtable을 유지하면 효율적으로 read & write를 수행할 수 있다. 하지만 메모리에만 존재하는 데이터를 디스크에 동기화하기 전에 crash가 발생하면 해당 데이터는 소실될 수도 있다. 이 문제는 WAL(Write Ahead Log) 파일을 항상 메모리와 함께 기록하는 것으로 해결한다.
여전히 문제점은 존재한다. 만약 memtable과 디스크 모두에 존재하지 않는 키를 read 해야 하는 경우에는 모든 파일을 full scan 해서야 키가 없다는 것을 발견해야 한다. 이를 최적화하기 위해 블룸 필터(Bloom filter)를 추가적으로 사용한다.
블룸 필터
블룸 필터는 집합 내용을 근사한 메모리 효율적 데이터 구조다. 키가 데이터베이스에 존재하지 않는 것을 알려주어 불필요한 읽기를 절약한다.
블룸필터는 확률적인 자료구조로 다음의 두가지 결론을 도출할 수 있다.
- 특정 element가 set 안에 존재하지 않는다.
- 특정 element가 set 안에 존재할 수도 있다.
블룸필터는 K개의 hash functions와 1개의 배열로 구성된다. 0으로 초기화한 배열이 있고, 특정 element를 hash 함수로 돌려서 배열에서 해당 값의 index를 1로 변경한다. 이후 element가 있는지 확인하려면, k개의 hash 함수를 돌려서 나온 값의 index를 찾았을 때 하나라도 0이 존재하면 그 값은 확실히 존재하지 않고, 모두 1이라면 존재할 수도 있는 것이다.
반드시 해당 데이터가 존재하는 것은 아니다. 단지 확률적이기 때문에 디스크에서 full scan을 할 수도 있지만, 확률적으로 유의미하게 case가 줄어들어 코스트를 낮출 수 있다.
추가적으로 컴팩션 작업이 오버헤드를 많이 발생시킬 수도 있다. 이를 최적화하는 전략들이 있는데, 크기 계층 컴팩션(size-tiered compaction)과 레벨 컴팩션(level compaction)이 그것이다.
레벨 컴팩션
- segment들을 각 레벨로 나눈다. 각 레벨에서 컴팩션 작업을 거친 후에 상위 레벨로 올려 연쇄적으로 수행하게 한다.
- 이를 통해 다른 레벨에 존재하는 데이터는 중복될 가능성이 낮아진다. 이를 통해 불필요한 read 작업을 줄일 수 있다.
- 하지만 레벨이 높을수록 많은 데이터를 포함하고 있기 때문에 병합하는 과정에서 복사해두어야 하는 데이터 양이 늘어나서 write I/O가 높아질 수 있다.
크기 계층 컴팩션
- 특정 레벨에서 모든 segment들을 한 번에 병합한다.
- 컴팩션이 한 번에 이루어지므로 같은 데이터를 여러 번 메모리나 디스크에 복사하여 유지해둘 필요가 없다.
- 하지만 한 번에 컴팩션을 하므로 데이터 중복성은 높아질 수 있으므로 데이터를 읽을 때 read I/O가 높아질 수 있다.
[참고자료]
https://disc-projects.bu.edu/compactionary/
'database' 카테고리의 다른 글
| [DB] 샤딩(Sharding)이란? (0) | 2023.06.28 |
|---|---|
| [DB] 트랜잭션(3) - 격리 수준과 동시성 문제, 그 해결 (0) | 2023.05.09 |
| [DB] 트랜잭션(2) - repeatable read 격리 수준에서의 phantom read 현상 (0) | 2023.05.08 |
| [DB] 트랜잭션(1) - ACID와 격리 수준(isolation level) (0) | 2023.05.08 |
| HikariCP - max lifetime과 DB wait_timeout의 관계 (0) | 2023.05.03 |
