저장소와 검색 (1)

이 장에서는 데이터베이스가 저장과 검색을 내부적으로 어떻게 처리하는지에 대해 다룬다. JPA나 Typeorm 과 같은 ORM을 사용하는 애플리케이션 개발자들이 이를 알아야하는 이유는 처음부터 자신의 저장소 엔진을 구현하기 위해서라기 보다는 여러 저장소 엔진 중에 애플리케이션에 가장 적합한 엔진을 선택하기 위함이다. 관계형 데이터베이스와 NoSQL 데이터베이스의 저장소 엔진, 그리고 로그 구조 계열 저장소 엔진과 (B-Tree와 같은) 페이지 지향 계열 저장소 엔진을 검토해보도록 하자.

 

 

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

 

아래와 같은 아주 간단한 데이터베이스를 가정해보자.

 

#!/bin/bash

db_set () {
	echo "$1,$2" >> database
}

db_get () {
	grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

 

일반적으로 파일 추가 작업은 매우 효율적이기 때문에 `db_set` 함수는 꽤 좋은 성능을 보여준다. 많은 데이터베이스는 `db_set`처럼 내부적으로 추가 전용 (append-only) 데이터 파일인 로그를 사용한다. 물론 실제 데이터베이스가 다뤄야할 문제는 동시성 처리나 디스크 공간 회수 등 더 크고 복잡하겠지만, 기본 원리는 같다. 

 

반면, `db_get` 함수는 데이터베이스에 레코드가 쌓일 수록 성능이 좋지 않다. 키를 찾을 때마다, 모든 데이터베이스를 순회해야하므로 O(n)의 검색 비용이 발생한다. 

 

따라서 데이터베이스에서는 특정 키 값을 빠르게 찾기 위해 방안이 필요했고, 고안된 것이 인덱스(또는 색인)다. 인덱스의 일반적인 개념은 어떤 부가적인 메타데이터를 유지하는 것이다. 이 메타데이터는 이정표 역할을 해서 데이터를 빠르게 찾는데 도움을 준다. 물론 인덱스는 추가적인 데이터인만큼 이것을 유지하기 위해서는 쓰기 작업 시, 추가적인 오버헤드가 발생한다. 이것은 저장소 시스템에서 중요한 트레이드오프다. 

 

해시 색인

 

키-값 데이터에 대한 색인을 우선 다뤄보자. 키-값 저장소는 대부분의 프로그래밍 언어에서 지원되는 Dictionary 타입과 유사하고, 보통 해시 맵 또는 해시 테이블로 구현한다. 

 

앞선 bash 데이터베이스의 예시처럼 데이터베이스를 구성한다고 하면, 가장 간단한 인덱싱 전략은 다음과 같다. 

 

- 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 유지한다.

 

인메모리 해시맵 전략

 

즉, 특정 키 값이 메모리 내 몇 번째 바이트에 존재하는지를 인덱스로 기록하는 것이다. 이 방식은 매우 단순해보이지만 많이 사용하는 접근법이다. Riak 의 기본 저장소 엔진은 Bitcask도 이 방식을 사용한다.

 

이 간단한 방식의 맹점은, 로그가 추가될 수록 디스크 공간이 부족해진다는 것이다. 이 상황을 타개하기 위한 방안으로 세그먼트(segment) 단위로 로그를 나누고 세그먼트 파일들에 대해 컴팩션(compaction)을 수행하는 것이 등장한다.

 

컴팩션과 세그먼트를 수행한 결과

 

컴팩션은 각 세그먼트별 또는 세그먼트들 전반에 걸쳐서 고유한 키값에 대해 가장 최신의 값을 저장하는 것이다. 위 예시에서 segment1 을 컴팩션하면 purr 의 가장 최신은 2108 이 된다. segment2 를 컴팩션하면 purr 은 2114 가 된다. segment1 과 2를 병합하면, 가장 최신인 2114가 최종적으로 남게된다. 

 

병합 과정을 통해 세그먼트 수를 적게 유지하기에 조회할 때, 많은 해시 맵을 확인할 필요가 없어진다.

 

그럼에도 불구하고, 해시 인덱스가 같은 단점도 명확하다. 해시 테이블은 메모리에 저장해야 하므로 키가 너무 많으면 문제가 된다. 원칙적으로는 디스크에 해시 맵을 유지할 수 있지만 불행하게도 해시 충돌로 인해 디스크 상의 해시 맵에 좋은 성능을 기대하기란 어렵다. 

 

SS 테이블

세그먼트 파일 형식에 간단한 변경 사항 한 가지를 추가해보자. 바로 일련의 키-값 쌍을 키로 정렬하는 것이다. 

 

SS 테이블의 병합

 

이처럼 키로 정렬된 형식을 Sorted String Table 또는 짧게 SS 테이블이라고 지칭한다. 각 키는 각 병합된 세그먼트 파일 내에서 한 번만 나타나야 한다. 

 

SS 테이블 내에서의 세그먼트 병합은 기존보다 효율적이다. 먼저 입력 파일을 병렬적으로 읽고, 각 파일의 첫 번째 키를 본다. 그리고 가장 낮은 키를 출력 파일로 복사한 뒤 이 과정을 반복한다. 이 과정에서 새로운 병합 세그먼트 파일이 생성된다. ( 이 역시 정렬되어 있다 ) 

 

파일의 특정 키를 찾기 위해 더는 메모리에 모든 키의 색인을 유지할 필요가 없다. 아래 그림에서 handiwork 키를 찾을 때, 세그먼트 파일에 키의 오프셋이 나와있지 않더라도 handbag 과 handsome 키의 오프셋 사이에 있다는 사실을 알 수 있다. 즉, 이 두 키 사이만 스캔하면 되는 것이다. 

 

 

그런데, 데이터를 키 순으로 정렬하려면 어떻게 할까? 무작위 쓰기 작업을 해야해서 성능이 낮아지는 건 아닐까 하는 의문이 들 수 있다. 사실 메모리에 정렬된 구조를 유지하는 일은 디스크에서 유지하는 것보다도 쉽다. 레드 블랙 트리(red-black tree) 나 AVL 트리와 같이 잘 알려진 트리 데이터 구조를 사용하면 된다.