3장 저장소와 검색 - 전반부

항상 주변을 단정히 정돈하는 사람은 단지 찾기를 너무 귀찮아하는 사람이다.
- 독일 속담

가장 기본적인 수준에서 데이터베이스는 두 가지 작업을 수행한다. 어떤 데이터를 받으면 데이터를 저장하고 나중에 그 데이터를 요청하면 다시 데이터를 제공한다.

2장에서 애플리케이션 개발자가 데이터베이스에 데이터를 제공하는 형식을 설명했다. 그리고 나중에 다시 요청할 수 있는 메커니즘인 데이터 모델과 질의 언어도 살펴봤다. 이번 장에서는 같은 내용을 데이터베이스 관점에서 살펴본다. 즉, 데이터베이스가 데이터를 저장하는 방법과 데이터를 요청했을 때 다시 찾을 수 있는 방법을 설명하겠다.

데이터베이스가 저장과 검색을 내부적으로 처리하는 방법을 애플리케이션 개발자가 주의해야 하는 이유는 무엇일까? 대개 애플리케이션 개발자가 처음부터 자신의 저장소 엔진을 구현하기보다는 사용 가능한 여러 저장소 엔진을 구현하기 보다는 사용 가능한 여러 저장소 엔진 중에 애플리케이션에 적합한 엔진을 선택하는 작업이 필요하다. 특정 작업부하(workload) 유형에서 좋은 성능을 내게끔 저장소 엔진을 조정하려면 저장소 엔진이 내부에서 수행되는 작업에 대해 대략적인 개념을 이해할 필요가 있다. 

특히 트랜잭션 작업부하에 맞춰 최적화된 저장소 엔진과 분석을 위해 최적화된 엔진 간에는 큰 차이가 있다. "트랜잭션 처리나 분석?"에서 이 뚜렷한 차이를 설명한다. 그리고 "칼럼 지향 저장소"에서는 분석에 최적화된 저장소 엔진 제품군을 살펴본다.

우선 장에서는 익숙한 데이터베이스 종류인 관계형 데이터베이스와 소위 NoSQL라 불리는 데이터베이스에 사용되는 저장소 엔진에 대해 설명한다. 그리고 로그 구조(log-structured) 계열 저장소 엔진과 (B트리(B-tree) 같은) 페이지 지향(page-oriented) 계열 저장소 엔진을 검토한다.

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

세상에서 제일 간단한 데이터베이스를 생각해보자. 이 데이터베이스는 두 개의 Bash 함수로 구현했다.

#!/bin/bash

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

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

키-값 저장소를 함수 두 개로 구현했다. db_set key value를 호출하면 데이터베이스에 key와 value를 저장할 수 있다. 키와 값은 어떤 것이든 (대부분) 가능하다. 예를 들어 값이 JSON 문서가 될수도 있다. db_get key를 호출하면 해당 키와 연관된 가장 최근 값을 찾아 반환 할 수 있다.

다음은 작동 예시다.

$ db_set 123456 '{"name":"London", "attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco", "attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco", "attractions":["Golden Gate Bridge"]}

기본적인 저장소 형식은 매우 간단하다. 매 라인마다 쉼표로 구분된 키-값 쌍을 포함한 텍스트 파일(CSV 파일과 유사하며 이스케이핑 문제는 무시함)이다. db_set을 호출할 때마다 파일의 끝에 추가하므로 키를 여러 번 갱신해도 값의 예전 버전을 덮어 쓰지 않는다. 최신 값을 찾기 위해서는 파일에서 키의 마지막 항목을 살펴봐야 한다(그래서 db_get에서 tail -n 1을 실행한다).

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Exploratorium"]}
$ cat database
123456,{"name":"London","attractions":["Big Ben", "London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

 일반적으로 파일 추가 작업은 매우 효율적이기 때문에 DB_SET 함수는 매우 간단한 작업의 경우에는 실제로 꽤 좋은 성능을 보여준다. DB_SET과 마찬가지로 많은 데이터베이스 내부적으로 추가전용(append-only) 데이터 파일인 로그(log)를 사용한다. 실제 데이터베이스는 다뤄야 할 더 많은 문제(예: 동시성 제어, 로그가 영원히 커지지 않게끔 디스크 공간을 회수, 오류 처리, 부분적으로 기록된 레코드 처리)가 있지만 기본 원리는 같다. 로그는 믿기지 않을 정도로 유용하다. 이 사실은 책 나머지 부분에서 여러 번 확인할 수 있다.

로그라는 단어는 애플리케이션 로그를 언급할 때 종종 사용되기도 한다. 이 때 로그는 애플리케이션에서 무슨 일이 일어났는지 기술한 텍스트를 출력한다. 이 책에서 로그는 조금 더 일반적인 의미로 연속 된 추가 전용 레코드다. 로그는 사람이 읽을 수 있는 형식일 필요는 없다. 특정 읽기 전용 프로그램만 읽을 수 있는 바이너리 일수도 있다.

반면 db_get 함수는 데이터베이스에 많은 레코드가 있으면 성능이 매우 좋지 않다. 매번 키를 찾을 때마다 db_get은 키가 있는지 찾기 위해 전체 데이터베이스 파일을 처음부터 끝까지 스캔해야 한다. 알고리즘 용어로 검색 비용이 O(n)이다. 데이터베이스의 레코드 수가 두배로 늘면 검색도 두 배로 오래 걸린다. 바람직 하지 않다.

데이터베이스에서 특정 키의 값을 효율적으로 찾기 위해서는 다른 데이터 구조가 필요하다. 바로 색인이다. 이번 장에서는 다양한 색인 구조를 살펴보고 여러 색인 구조를 비교하는 방법을 알아본다.

색인의 일반적인 개념은 어떤 부가적인 메타데이터를 유지하는 것이다. 이 메타데이터는 이정표 역할을 해서원하는 데이터의 위치를 찾는데 도움을 준다. 동일한 데이터를 여러 가지 다양한 방법으로 검색하고자 한다면 데이터의 각 부분에 여러 가지 다양한 색인이 필요하다.

색인은 기본 데이터(primary data)에서 파생된 추가적인 구조다. 많은 데이터베이스는 색인의 추가와 삭제를 허용한다. 이 작업은 데이터베이스의 내용에는 영향을 미치지 않는다. 단지 질의 성능에만 영향을 준다. 추가적인 구조의 유지보수는 특히 쓰기 과정에서 오버헤드가 발생한다. 쓰기의 경우 단순히 파일에 추가할 때의 성능을 앞서기 어렵다. 왜냐하면 단순히 파일에 추가하는 작업이 제일 간단한 쓰기 작업이기 때문이다. 어떤 종류의 색인이라도 대개 쓰기 속도를 느리게 만든다. 이는 데이터를  쓸 때마다 매번 색인도 갱신해야 하기 때문이다.

이것은 저장소 시스템에서 주요한 트레이드오프다. 색인을 잘 선택했다면 읽기 질의 속도가 향상된다. 하지만 모든 색인은 쓰기 속도를 떨어뜨린다. 이런 이유로 데이터베이스는 보통 자동으로 몯느 것을 색인하지 않는다. 애플리케이션 개발자나 데이터베이스 관리자가 애플리케이션의 전형적인 질의 패턴에 대한 지식을 활용해 수동으로 색인을 선택해야 한다. 그래야 필요 이상으로 오버헤드를 발생시키지 않으면서 애플리케이션에 가장 큰 이익을 안겨주는 색인을 선택할 수 있다.

해시 색인

먼저 키-값 데이터를 색인해보자. 키-값 데이터가 색인할 수 있는 유일한 종류의 데이터는 아니지만 매우 일반적이고 더욱 복잡한 색인을 위한 구성 요소로 유용하다.

키-값 저장소는 대부분의 프로그래밍 언어에서 볼 수 있는 사전 타입(dictionary type)과 매우 유사하다. 보통 해시 맵(hash map)(해시 테이블(hash table))으로 구현한다. 해시 맵은 많은 알고리즘 교과서에서 설명하고 있어 여기서 동작 방식을 자세히 설명하지 않는다. 인메모리 데이터 구조를 위한 해시 맵이 이미 있으니 디스크 상의 데이터를 색인하기 위해 인메모리 데이터 구조를 사용하는 것은 어떨까?

앞의 예제처럼 단순히 파일에 추가하는 방식으로 데이터 저장소를 구성한다고 가정해보자. 그러면 가장 간단하게 가능한 색인 전략은 다음과 같다. 키를 데이터 파일의 바이트 오프셋에 매핑해 인메모리 해시 맵을 유지하는 전략이다. 바이트 오프셋은 다음 그림과 같이 값을 바로 찾을 수 있는 위치다. 파일에 새로운 키-값 쌍을 추가할 때마다 방금 기록한 데이터의 오프셋을 반영하기 위해 해시맵도 갱신해야 한다.(새로운 키를 삽입할 때와 존재하는 키를 갱신할 때 모두 적용된다). 값을 조회하려면 해시 맵을 사용해 데이터파일에서 오프셋을 찾아 해당 위치를 구하고 값을 읽는다.

이 방식은 매우 단순해 보이지만 실제로 많이 사용하는 접근법이다. 사실 이 방식은 비트캐스크(Bitcask)(리악(Riak)의 기본 저장소 엔진)가 근본적으로 사용하는 방식이다. 비트캐스크는 해시 맵을 전부 메모리에 유지하기 때문에 사용 가능한 램(RAM)에 모든 키가 저장된다는 조건을 전제로 고성능으로 읽기, 쓰기를 보장한다. 값은 한 번의 디스크 탐색으로 디스크에서 적재할 수 있기 때문에 사용 가능한 메모리보다 더 많은 공간을 사용할 수 있다. 만약 데이터 파일의 일부가 이미 파일 시스템 캐시에 있다면 읽기에 디스크 입출력이 필요하지 않다. (https://github.com/basho/bitcask)

비트캐스크 같은 저장소 엔진은 각 키의 값이 자주 갱신되는 상황에 매우 적합하다. 예를 들어 키는 고양이 동영상의 URL이고 값은 비디오 재생된 횟수(재생 버튼을 누를 때마다 증가함)인 경우다. 이런 유형의 작업부하에서는 쓰기가 아주 많지만 고유 키는 많지 않다. 즉, 키당 쓰기 수가 많지만 메모리에 모든 키를 보관할 수 있다.

지금까지 설명한 것처럼 파일에 항상 추가만 한다면 결국 디스크 공간이 부족해진다. 이상황은 어떻게 피할 수 있을까? 특정 크기의 세그먼트(segment)로 로그를 나누는 방식이 좋은 해결책이다. 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행한다. 다음 그림과 같이 세그먼트 파일들에 대한 컴팩션(compaction)을 수행할 수 있다. 컴팩션은 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것을 의미한다.

더욱이 컴팩션은 보통 세그먼트를 더 작게 만들기 때문에(하나의 키는 세그먼트 내에서 대체로 여러번 덮어쓰기 된 것을 가정함) 다음 그림에서 보는 것 처럼 컴팩션을 수행할 때 동시에 여러 세그먼트들을 병합할 수 있다.

세그먼트가 쓰여진 후에는 절대 변경할 수 없기 떄문에 병합할 세그먼트는 새로운 파일로 만든다. 고정된 세그먼트의 병합과 컴팩션은 백그라운드 스레드에서 수행할 수 있다. 컴팩션을 수행하는 동안 이전 세그먼트 파일을 사용해 읽기와 쓰기 요청의 처리를 정상적으로 계속 수행할 수 있다. 병합 과정이 끝난 이후에는 읽기 요청은 이전 세그먼트 대신 새로 병합한 세그먼트를 사용하게끔 전환한다. 전환 후에는 이전 세그먼트 파일을 간단히 삭제하면 된다.

이제 각 세그먼트는 키를 파일 오프셋에 매핑한 자체 인메모리 해시 테이블을 갖는다. 키의 값을 찾으려면 최신 세그먼트 해시 맵을 먼저 확인한다. 만약 키가 없다면 두 번째 최신 세그먼트 등을 확인한다. 병합 과정을 통해 세그먼트 수를 적게 유지하기 때문에 조회할 때 많은 해시 맵을 확인할 필요가 없다.

이런 간단한 생각을 실제로 구현하려면 세부적으로 많은 사항을 고려해야 한다. 실제 구현에서 중요한 문제 몇 가지만 간략히 들자면 다음과 같다.

파일 형식

CSV는 로그에 가장 적합한 형식이 아니다. 바이트 단위의 문자열 길이를 부호화한 다음 원시 문자열(이스케이핑 필요 없이)을 부호화하는 바이너리 형식을 사용하는 편이 더 빠르고 간단하다.

레코드 삭제

키와 관련된 값을 삭제하려면 데이터 파일에 특수한 삭제 레코드(때로는 툼스톤(tombstone)이라 불림)를 추가해야한다. 로그 세그먼트가 병합될 때툼스톤은병합 과정에서 삭제된 키의 이전 값을 무시하게 된다.

고장(Crash) 복구

데이터베이스가 재시작되면 인메모리 해시 맵은 손실된다. 원칙적으로는 전체 세그먼트 파일을 처음부터 끝까지 읽고 각 키에 대한 최신 값의 오프셋을 확인해서 각 세그먼트 해시 맵을 복원할 수 있다. 하지만 세그먼트 파일이 크면 해시 맵 복원은 오랜 시간이 걸릴 수 있고 이는 서버 재시작을 고통스럽게 만든다. 비트캐스크는 각세그먼트 해시 맵을 메모리로 조금 더 빠르게 로딩할 수 있게 스냅숏을 디스크에 저장해 복구속도를 높인다.

부분적으로 레코드 쓰기

데이터베이스는 로그에 레코드를 추가하는 도중에도 죽을 수 있다. 비트캐스크 파일은 체크섬을 포함하고 있어 로그의 손상된 부분을 탐지해 무시할 수 있다.

동시성 제어

쓰기를 엄격하게 순차적으로 로그에 추가할 떄 일반적인 구현 방법은 하나의 쓰기 스레드만 사용하는 것이다. 데이터 팡리 세그먼트 추가 전용이거나 불변(immutable)이므로 다중 스레드로 동시에 읽기를 할 수 있다.

추가 전용 로그는 언뜻 보면 낭비처럼 보인다. 예전 값을 새로운 값으로 덮어써 정해진 자리에 파일을 갱신하는 방법은 어떨까? 하지만 추가 전용 설계는 여러 측면에서 좋은 설계다.

- 추가와 세그먼트 병합은 순차적인 쓰기 작업이기 때문에 보통 무작위 쓰기보다 훨씬 빠르다. 특히 자기 회전 디스크 하드드라이브에서 그렇다. 일부 확장된 순차 쓰기는 플래시 기반 솔리드 스테이트 드라이브(SSD)도 선호한다. "B 트리와 LSM 트리 비교"에서 더 자세히 설명하겠다.

- 세그먼트 파일이 추가 전용이나 불변이면 동시성과 고장 복구는 훨씬 간단하다. 예를 들어 값을 덮어쓰는 동안 데이터베이스가 죽는 경우에 대해 걱정할 필요가 없다. 이전 값 부분과 새로운 값 부분을 포함한 파일을 나누어 함께 남겨두기 때문이다.

- 오래된 세그먼트 병합은 시간이 지남에 따라 조각화되는 데이터 파일 문제를 피할 수 있다.

하지만 해시 테이블 색인 또한 제한 사항이 있다.

- 해시 테이블은 메모리에 저장해야 하므로 키가 너무 많으면 문제가 된다. 원칙적으로는 디스크에 해시 맵을 유지할 수 있지만 불행하게도 디스크 상의 해시 맵에 좋은 성능을 기대하기란 어렵다. 이는 무작위 접근 I/O가 많이 필요하고 디스크가 가득 찼을 때 확장하는 비용이 비싸며 해시 충돌 해소를 위해 성가신 로직이 필요하다.

- 해시 텡테이블은 범위 질의(range query)에 효율적이지 않다. 예를 들어 kitty00000과 kitty99999 사이 모든 키를 쉽게 스캔할 수 없다. 해시 맵에서 모든 개별 키를 조회해야한다.

다음 절에서는 이런 제한이 없는 색인 구조를 살펴본다.

SS테이블과 LSM트리

이전 그림에서 각 로그 구조화 저장소 세그먼트는 키-값 쌍의 연속이다. 이 쌍은 쓰여진 순서대로 나타나며 로그에서 같은 키를 갖는 값은 나중의 값이 이전 값보다 우선한다. 이 점만 제외하면 파일에서 키-값 쌍의 순서는 문제가 되지 않는다.

이제 세그먼트 파일의 형식에 간단한 변경 사항 한 가지를 적용해보자. 변경 요구사항은 일반적으로 키-값 쌍을 키로 정렬하는 것이다. 언뜻 보기에 이 요구사항은 순차  쓰기를 사용할 수 없게 만드는 것 같지만 잠시 후 이 점에 대해 알아본다.

이처럼 키로 정렬된 형식을 정렬된 문자열 테이블(Sorted String Table) 또는 짧게 SS테이블이라고 부른다. 그리고 각 키는 각 병합된 세그먼트 파일 내에 한번만 나타나야 한다.(컴팩션 과정은 이를 이미 보장한다). SS테이블은 해시 색인을 가진 로그 세그먼트보다 몇 가지 큰 장점이 있다.

1. 세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적이다. 이 접근법은 병합정렬(mergesort) 알고리즘에서 사용하는 방시고가 유사하다. 다음 그림에서 이 방식을 볼 수 있다. 먼저 입력 파일을 함께 읽고 각 파일의 첫번째 키를 본다(정렬된 순서에 따라). 그리고 가장 낮은 키를 출력 파일로 복사한 뒤 이 과정을 반복한다. 이 과정에서 새로운 병합 세그먼트 파일이 생성된다. 새로 만든 세그먼트 파일도 역시 키로 정렬돼 있다.

여러 입력 세그먼트에 동일한 키가 있으면 어떻게 해야 할까? 각 세그먼트에는 일정 기간 동안 데이터베이스에 쓰여진 모든 값이 포함된다는 점에 유의하자. 이것은 입력 세그먼트 하나의 모든 값이 다른 세그먼트의 모든 값보다 최신 값이라는 점을 의미한다(항상 인접한 세그먼트의 병합을 가정한다). 다중 세그먼트가 동일한 키를 포함하는 경우 가장 최근 세그먼트의 값은 유지하고 오래된 세그먼트의 값은 버린다.

2. 파일에서 특정 키를 찾기 위해 더는 메모리에 모든 키의 색인을 유지할 필요가 없다. 예를 들어 다음 그림을 보자. Handiwork 키를 찾으려 하지만 세그먼트 파일에서 키의 정확한 오프셋을 알지 못한다고 가정해보자. 그래도 handbag과 handsome 키의 오프셋을 알고 있고 정렬돼 있으므로 handiwork는 두 키 사이에 있다는 사실을 알 수 있다. 즉 handbag 오프셋으로 이동해 handiwork가 나올 때까지 스캔하면 된다(만약 키가 파일에 존재하지 않는 경우에는 찾지 못한다).

일부 키에 대한 오프셋을 알려주는 인메모리에 색인이 여전히 필요하다. 하지만 색인 내용이 드문드문 희소할 수 있다. 수 킬로바이트 정도는 매우 빠르게 스캔할 수 있기 때문에 세그먼트 파일 내 수 킬로바이트 당 키 하나로 충분하다. 모든 키와 값이 고정 크기라면 세그먼트 파일에서 이진 검색을 사용하면 되기 때문에 인 메모리 색인을 전혀 사용하지 않아도 된다. 하지만 현실적으로 키-값은 가변 길이이므로 색인이 없다면 하나의 레코드가 끝나고 다음 레코드가 시작하는 곳을 알기 어렵다.

3. 읽기 요청은 요청 범위 내에서 여러 키-값 쌍을 스캔해야 하기 때문에 해당 레코드들을 블록으로 그룹화하고 디스크에 쓰기 전에 압축한다. 그림에서 음영 영역을 나타낸다. 그러면 희소 인메모리 색인의 각 항목은 압축된 블록의 시작을 가리키게 된다. 디스크 공간을 절약한다는 점 외에도 압축은 I/O 대역폭 사용도 줄인다.

SS테이블 생성과 유지

지금까지는 괜찮았지만 데이터를 키로 정렬하려면 어떻게 해야할까? 유입되는 쓰기는 임의 순서로 발생한다. 디스크 상에 정렬된 구조를 유지하는 일은 가능하지만(추후의 B트리 참고) 메모리에 유지하는 편이 훨씬 쉽다. 레드 블랙 트리(red-black tree)나 AVL 트리와 같이 잘 알려졌고 사용가능한 트리 데이터 구조는 많이있다. 이런 데이터 구조를 이용하면 임의 순서로 키를 삽입하고 정렬된 순서로 해당 키를 다시 읽을 수 있다.

이제 저장소 엔진을 다음과 같이 만들 수 있다.

- 쓰기가 들어오면 인 메모리 균형 트리(balanced tree) 데이터 구조(예를 들어 레드 블랙 트리)에 추가한다. 이 인메모리 트리는 멤테이블(memtable)이라고도 한다.

- 멤테이블이 보통 수 메가바이트 정도의 임계값보다 커지면 SS테이블 파일로 디스크에 기록한다. 트리가 이미 키로 정렬된 키-값 쌍을 유지하고 있기 때문에 효율적으로 수행할 수 있다. 새로운 SS테이블 파일은 데이터베이스의 가장 최신 세그먼트가 된다. SS테이블을 디스크에 기록하는 동안 쓰기는 새로운 멤테이블 인스턴스에 기록한다. 

- 읽기 요청을 제공하려면 먼저 멤테이블에서 키를 찾아야한다. 그다음 디스크 상의 가장 최신 세그먼트에서 찾는다. 그다음으로 두 번째 오래된 세그먼트, 세번째 오래된 세그먼트 등에서 찾는다.

- 가끔 세그먼트 파일을 합치고 덮어 쓰여지거나 삭제된 값을 버리는 병합과 컴팩션 과정을 수행한다. 이 과정은 백그라운드에서 수행된다.

이 계획은 아주 잘 동작하지만 한 가지 문제가 있다. 만약 데이터베이스가 고장나면 아직 디스크로 기록되지 않고 멤테이블에 있는 가장 최신 쓰기는 손실된다. 이런 문제를 피하기 위해서는 이전 절과 같이 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크 상에 유지해야 한다. 이 로그는 손상 후 멤테이블을 복원할 때만 필요하기 때문에 순서가 정렬되지 않아도 문제되지 않는다. 멤테이블을 SS테이블로 기록하고 나면 해당 로그는 버릴 수 있다.

SS 테이블에서 LSM 트리 만들기

여기에 기술된 알고리즘은 기본적으로 레벨DB(LevelDB)와 록스DB(RocksDB), 그리고 다른 애플리케이션에 내장하기 위해 설계된 키-값 저장소 엔진 라이브러리에서 사용한다. 이 중에서 리악에서는 비트캐스크의 대안으로 레벨DB를 사용할 수 있고 구글의 빅테이블(Bigtable) 논문(SS테이블과 멤테이블이라는 용어가 소개됐다)에서 영감을 얻은 카산드라와 HBase에서도 유사한 저장소 엔진을 사용한다.

원래 이 색인 구조는 로그 구조화 병합 트리(Log-Structured Merge-Tree)(또는 LSM 트리)란 이름으로 패트릭 오닐(Patrick O'Neil) 등이 발표했다. 이 색인 구조는 로그 구조화 파일 시스템의 초기 작업의 기반이 됐다. 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진을 LSM 저장소 엔진이라 부른다.

루씬(Lucene)은 엘라스틱서치나 솔라에서 사용하는 전문 검색 색인 엔진이다. 루씬은 용어 사전(term dictionary)을 저장하기 위해 유사한 방법을 사용한다. 전문 색인은 키-값 색인보다 훨신 더 복잡하지만 이와 유사한 개념을 기반으로 한다. 검색질의로 단어가 들어오면 단어가 언급된 모든 문서(웹 페이지, 제품 설명 등)를 찾는다. 이 접근법은 키를 단어(용어)로, 값은 단어를 포함한 모든 문서의 ID 목록(포스팅 목록(posting list)) 으로 하는 키-값 구조로 구현한다. 루씬에서 용어와 포스팅 목록의 매핑은 SS테이블 같은 정렬 파일에 유지하고 필요에 따라 백그라운드에서 병합한다.

성능 최적화

언제나 처럼 실제로는 많은 세부 사항이 저장소 엔진을 잘 동작하게 만든다. 예를 들어, LSM 트리 알고리즘은 데이터베이스에 존재하지 않는 키를 찾는 경우 느릴 수 있다. 멤테이블을 확인한 다음 키가 존재하지 않는다는 사실을 확인하기 전에는 가장 오래된 세그먼트까지 거슬러 올라가야 한다(디스크에서 읽기를 해야 할 가능성이 있다). 이런 종류의 접근을 최적화하기 위해 저장소 엔진은 보통 블룸 필터(Bloom filter)를 추가적으로 사용한다. (블룸 필터는 집합 내용을 근사(approximation) 메모리 효율적 데이터 구조다. 블룸 필터는 키가 데이터베이스에 존재하지 않음을 알려주므로 존재하지 않는 키를 위한 불필요한 디스크 읽기를 많이 절약할 수 있다.)

또한 SS테이블을 압축하고 병합하는 순서와 시기를 결정하는 다양한 전략이 있다. 가장 일반적으로 선택하는 전략은 크기 계층(size-tiered)과 레벨 컴팩션(leveled compaction)이다. 레벨DB와 록스DB는 레벨 컴팩션(레벨DB의 이름이 여기서 유래했다)을 사용하고 HBase 사이즈 계층을, 카산드라는 둘 다 지원한다. 사이즈 계층 컴팩션은 상대적으로 좀 더 새롭고 작은 SS테이블을 상대적으로 오래됐고 큰 SS테이블에 연이어 병합한다. 레벨 컴팩션은 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 '레벨'로 이동하기 때문에 컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용한다.

물론 여러 중요한 세부 사항이 있지만 LSM 트리의 기본 개념은 간단하고 효과적이다. LSM 트리의 기본 개념은 백그라운드에서 연쇄적으로 SS테이블을 지속적으로 병합하는 것이다 .이 개념은 데이터셋이 가능한 메모리보다 훨씬 더 크더라도 여전히 효과적이다. 데이터가 정렬된 순서로 저장돼 있다면 범위 질의를 효율적으로 실행할 수 있다(최소에서 최대까지 모든 키를 스캔). 이 접근법의 디스크 쓰기는 순차적이기 때문에 LSM 트리가 매우 높은 쓰기 처리량을 보장할 수 있다.

B 트리

지금까지 설명한 로그 구조화 색인이 점점 보폏놔되고 있지만 가장 일반적인 색인 유형은 아니다. 가장 널리 사용되는 색인 구조는 B 트리(B tree)로 구조가 로그 구조화 색인과는 상당히 다르다.

 B 트리는 1970년대에 등장했다. B 트리는 이후 10년도 안 돼 "보편적인 색인 구조"라 불렸고 B 트리는 이 기간 동안 테스트를 잘 견뎌냈다. 여전히 거의 대부분의 관계형 데이터베이스에서 표준 색인 구현으로 B 트리를 사용할 뿐 아니라 많은 비관계형 데이터베이스에서도 사용한다.

B 트리는 SS테이블과 같이 키로 정렬된 키-값 쌍을 유지하기 때문에 키-값 검색과 범위 질의에 효율적이다. 하지만 비슷한 점은 이 정도가 전부다. B 트리는 설계 철학이 매우 다르다.

앞에서 살펴본 로그 구조화 색인은 데이터베이스를 일반적으로 수 메가 바이트 이상의 가변 크기를 가진 세그먼트로 나누고 항상 순차적으로 세그먼트를 기록한다. 반면 B 트리는 전통적으로 4KB 크기(때로는 더 큰)의 고정 크기 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 한다. 디스크가 고정 크기 블록으로 배열되기 때문에 이런 설계는 근본적으로 하드웨어와 조금 더 밀접한 관련이 있다.

각 페이지는 주소나 위치를 이용해 식별할 수 있다. 이 방식으로 하나의 페이지가 다른 페이지를 참조할 수 있다(포인터와 비슷하지만 메모리 대신 디스크에 있음). 이 페이지 참조는 다음 그림과 같이 페이지 트리를 구성하는데 사용할 수 있다.

한 페이지는 B 트리의 루트(root)로 지정된다. 색인에서 키를 찾으려면 루트에서 시작한다. 페이지는 여러 키와 하위 페이지의 참조를 포함한다. 각 하위 페이지는 키가 계속 이어지는 범위를 담당하고 참조 사이의 키는 해당 범위 경계가 어디인지 나타낸다.

그림 예제에서는 키 251을 찾고 있었기 때문에 200과 300 경계 사이의 페이지 참조를 따라가야 한다는 사실을 알 수 있다. 그러면 200~300 범위와 비슷하게 생겼지만 좀 더 작은 범위로 더 나눈 페이지로 이동한다.

최종적으로는 개별 키(리프 페이지(leaf page))를 포함하는 페이지에 도달한다. 이 페이지는 각 키의 값을 포함하거나 값을 찾을 수 있는 페이지의 참조를 포함한다.

B 트리의 한 페이지에서 하위 페이지를 참조하는 수를 분기 계수(branching factor)라고 부른다. 예를 들어 그림에서는 분기 계수는 6이다. 실제로 분기 계수는 페이지 참조와 범위 경계를 저장할 공간의 양에 의존적인데, 보통 수백개에 달한다.

 B 트리에 존재하는 키의 값을 갱신하려면 키를 포함하고 있는 리프 페이지를 검색하고 페이지의 값을 바꾼 다음 페이지를 디스크에 다시 기록한다.(페이지에 대한 모든 참조는 계속 유효하다). 새로운 키를 추가하려면 새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가한다. 새로운 키를 수용한 페이지에 충분한 여유 공간이 없다면 페이지 하나를 반쯤 채워진 페이지 둘로 나누고 상위 페이지가 새로운 키 범위의 하위 부분들을 알 수 있게 갱신한다. 다음 그림을 참고하라.

이 알고리즘은 트리가 계속 균형을 유지하는 것을 보장한다. n 개의 키를 가진 B 트리는 깊이가 항상 O(log n)이다. 대부분의 데이터베이스는 B 트리의 깊이가 3이나 4단계 정도면 충분하므로 검색하려는 페이지를 찾기 위해 많은 페이지 참조를 따라가지 않아도 된다(분기 계수 500의 4KB 페이지의 4단계 트리는 256TB 까지 저장할 수 있다) 500^4 * 4096B = 256 TB

신뢰할 수 있는 B 트리 만들기

B 트리의 기본적인 쓰기 동작은 새로운 데이터를 디스크 상의 페이지에 덮어쓴다. 이 동작은 덮어쓰기가 페이지 위치를 변경하지 않는다고 가정한다. 즉 페이지를 덮어쓰더라도 페이지를 가리키는 모든 참조는 온전하게 남는다. LSM 트리와 같은 로그 구조화 색인과는 아주 대조적인 점이다. 로그 구조화 색인은 파일에 추가만 할 뿐(결국 더 이상 쓸모없는 파일은 삭제됨) 같은 위치의 파일은 변경하지 않는다.

디스크의 페이지를 덮어쓰는 일은 실제 하드웨어 동작이라고 생각 할 수 있다. 자성의 하드드라이브의 경우 디스크 헤드를 적절한 곳으로 옮기고 회전하는 플래터의 올바른 위치가 돌아올 때까지 기다린 다음 적합한 섹터에 새로운 데이터를 덮어쓴다. SSD의 경우는 SSD가 저장소 칩의 상당한 블록을 한번에 지우고 다시 쓰기를 해야하기 때문에 조금 더 복잡하다.

더욱이 일부 동작은 여러 다양한 페이지의 덮어쓰기를 필요로 한다. 예를 들어 삽입 때문에 페이지가 너무 만항져 페이지를 나눠야 한다면 분할된 두 페이지를 기록하고 두 하위 페이지의 참조를 갱신하게끔 상위 페이지를 덮어쓰기 해야한다. 일부페이지만 기록하고 데이터베이스가 고장 난다면 결국 색인이 훼손되기 때문에 이것은 매우 위험한 동작이다(예로 고아 페이지(orphan page)가 발생할 수있다. 고아 페이지는 어떤 페이지와도 부모 관계가 없는 페이지를 말한다)

데이터베이스가 고장 상황에서 스스로 복구할 수 있게 만들려면 일반적으로 디스크 상에 쓰기 전 로그(write-ahead log, WAL)(재실행 로그(redo log)라고도 함)라고 하는 데이터 구조를 추가해 B 트리를 구현한다. 쓰기 전 로그는 트리페이지에 변경된 내용을 적용하기 전에 모든 B트리의 변경사항을 기록하는 추가 전용 파일이다. 이 로그는 데이터베이스가 고장 이후 복구될때 일관성있는 상태로 B 트리를 다시 복원하는 데 사용한다.

같은 자리의 페이지를 갱신하는 작업은 추가적인 골칫거리다. 다중 스레드가 동시에 B 트리에 접근한다면 주의 깊게 동시성 제어를 해야 한다. 그렇지 않으면 스레드 일관성이 깨진 상태의 트리에 접근할 수 있다. 동시성 제어는 보통 래치(latch)(가벼운 잠근(Lock))로 트리의 데이터 구조를 보호한다. 이런 상황에서 로그 구조화 접근 방식은 훨씬 간단하다. 유의 질의의 간섭없이 백그라운드에서 모든 병합을 수행하고 이따금 원자적으로 새로운 세그먼트를 이전 세그먼트로 바꾸기 때문이다.

B 트리 최적화

B 트리는 오랫동안 사용됐기 때문에 그 기간에 걸쳐 개발된 많은 최적화 기법이 있다는 점은 놀랍지 않다. 최적화 기법을 몇 가지를 언급하자면 다음과 같다.

- 페이지 덮어 쓰기와 고장 복구를 위한 WAL 유지 대신 (LMDB 같은) 일부 데이터베이스는 쓰기 시 복사 방식(copy-on-write scheme)을 사용한다. 변경된 페이지는 다른 위치에 기록하고 트리에 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가리키게 한다. 이 접근 방식은 동시성 제어에도 유용하다. 이후 "스냅숏 격리와 반복 읽기" 에서 볼 수 있다.

- 페이지에 전체 키를 저장하는게 아니라 키를 축약해 쓰면 공간을 절약할 수 있다. 트리 내부 페이지에서 키가 키 범위 사이의 경계역할을 하는데 충분한 정보만 제공하면 된다. 페이지 하나에 키를 더 많이 채우면 트리는 더 높은 분기 계수를 얻는다. 그러면 트리 깊이 수준을 낮출 수 있다.

- 일반적으로 페이지는 디스크 상 어디에나 위치할 수 있다. 키 범위가 가까운 페이지들이 디스크 상에 가까이 있어야 할 피룡가 없기 때문이다. 질의가 정렬된 순서로 키 범위의 상당 부분을 스캔해야 한다면 모든 페이지에 대해 디스크 찾기가 필요하기 때문에 페이지 단위 배치는 비효율적이다. 따라서 많은 B 트리 구현에서 리프(leaf) 페이지를 디스크 상에 연속된 순서로 나타나게끔 트리를 배치하려 시도한다. 하지만 트리가 커지면 순서를 유지하기가 어렵다. 반대로 LSM 트리는 병합하는 과정에서 저장소의 큰 세그먼트를 한 번에 다시 쓰기 때문에 디스크에서 연속된 키를 서로 가깝게 유지하기가 더 쉽다.

- 트리에 포인터를 추가한다. 예를 들어 각 리프 페이지가 양쪽 형제 페이지에 대한 참조를 가지면 상위 페이지로 다시 이동하지 않아도 순서대로 키를 스캔할 수 있다.

- 프랙탈 트리(fractal tree) 같은 B 트리 변형은 디스크 찾기를 줄이기 위해 로그 구조화 개념을 일부 빌렸다(프랙탈 트리는 기하학의 프랙탈과 아무련 관련이 없다).

B 트리와 LSM 트리 비교

B 트리가 LSM 트리보다 일반적으로 구현 성숙도가 더 높지만 LSM 트리도 그 성능 특성 때문에 관심을 받고 있다. 경험적으로 LSM 트리는 보통 쓰기에서 더 빠른 반면 B 트리는 읽기에서 더 빠르다고 여긴다. 읽기가 보통 LSM 트리에서 더 느린 이유는 각 컴팩션 단계에 있는 여러가지 데이터 구조와 SS 테이블을 확인해야 하기 때문이다.

하지만 벤치마크는 보통 결정적이지 않고 작업부하의 세부 사항에 민감하다 .비교가 유효하려면 실제 필요한 작업부하로 시스템을 테스트해야 한다. 이번 절에서는 저장소 엔진의 성능을 측정할 때 고려하면 좋은 사항 몇 가지를 간략히 설명한다.

LSM 트리의 장점

B 트리 색인은 모든 데이터 조각을 최소한 두 번 기록해야 한다. 쓰기 전 로그 한 번과 트리 페이지에 한 번(페이지가 분리될 때 다시 기록)이다. 해당 페이지 내 몇 바이트만 바뀌어도 한 번에 전체 페이지를 기록해야 하는 오버헤드도 있다. 일부 저장소 엔진은 심지어 전원에 장애가 발생했을 때 일부만 갱신된 페이지로 끝나지 않게 동일한 페이지를 두 번 덮어쓴다.

로그 구조화 색인 또한 SS테이블의 반복된 컴팩션과 병합으로 인해 여러 번 데이터를 다시 쓴다. 데이터베이스에 쓰기 한 번이 데이터베이스 수명 동안 디스크에 여러 번의 쓰기를 야기하는 이런 효과를 쓰기 증폭(write amplification)이라 한다. SSD는 수명이 다할 때가지 블록 덮어쓰기 횟수가 제한되기 때문에 쓰기 증폭은 SSD의 경우 특별한 관심사다.

쓰기가 많은 애플리케이션에서 성능 병목은 데이터베이스가 디스크에 쓰는 속도일 수 있따. 이 경우 쓰기 증폭은 바로 성능 비용이다. 저장소 엔진이 디스크에 기록할수록 디스크 대역폭 내 처리할 수 있는 초당  쓰기는 점점 줄어든다.

더욱이 LSM 트리는 보통 B 트리보다 쓰기 처리량을 높게 유지할 수 있다. (저장소 엔진 설정과 작업 부하에 따라 다르긴 하지만) LSM 트리가 상대적으로 쓰기 증폭이 더 낮고 트리에서 여러 페이지를 덮어쓰는 것이 아니라 순차적으로 컴팩션된 SS테이블 파일을 쓰기 때문이다. 이런 차이는 자기 하드드라이브에서 특히 중요하다. 자기 하드드라이브는 순차 쓰기가 임의 쓰기보다 훨씬 더 빠르다.

LSM 트리는 압축률이 더 좋다. 그래서 보통 B 트리보다 디스크에 더 적은 파일을 생성한다. B 트리 저장소 엔진은 파편화로 인해 사용하지 안흔 디스크 공간 일부가 남는다. 페이지를 나누거나 로우가 기존 페이지에 맞지 않을 때 페이지의 일부 공간은 사용하지 않게 된다. LSM 트리는 페이지 지향적이지 않고 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하기 때문에 저장소 오버헤드가 더 낮다. 레벨 컴팩션(leveled compaction)을 사용하면 특히 그렇다.

대다수의 SSD의 펌웨어는 내장 저장소 칩에서 임의 쓰기를 순차 쓰기로 전환하기 위해 내부적으로 로그 구조화 알고리즘을 사용한다. 그래서 저장소 엔진의 쓰기 패턴이 SSD에 미치는 영향은 분명하지 않다. 하지만 낮은 쓰기 증폭과 파편화 감소는 SSD의 경우 훨씬 유리하다. 데이터를 더 밀접해 표현하면 가능한 I/O 대역폭 내에서 더 많은 읽기와 쓰기 요청이 가능하다.

LSM 트리의 단점

로그 구조화 저장소의 단점은 컴팩션 과정이 때로는 진행 중인 읽기와 쓰기의 성능에 영향을 준다는 점이다. 저장소 엔진은 컴팩션을 점진적으로 수행하고 동시 접근의 영향이 없게 수행하려 한다. 하지만 디스크가 가진 자원은 한계가 있다. 그래서 디스크에서 비싼 컴팩션 연산이 끝날 때까지 요청이 대기해야 하는 상황이 발생하기 쉽다. 처리량과 평균 응답 시간이 성능에 미치는 영향은 대개 작다. 하지만 로그 구조화 저장소 엔진의 상위 백분위 질의의 응답시간은 때때로 꽤 길다. 반면 B 트리의 성능은 로그 구조화 저장소 엔진보다 예측하기 쉽다.

또 다른 컴팩션 문제는 높은 쓰기 처리량에서 발생한다. 디스크의 쓰기 대역폭은 유한하다. 초기 쓰기(로깅(logging)과 멤테이블을 디스크로 방출(flushing))와 백그라운드에서 수행되는 컴팩션 스레드가 이 대역폭을 공유해야 한다. 빈 데이터베이스에 쓰는 경우 전체 디스크 대역폭은 초기 쓰기만을 위해 사용할 수 있지만 데이터베이스가 점점 커질수록 컴팩션을 위해 더 많은 디스크 대역폭이 필요하다.

쓰기 처리량이 높음에도 컴팩션 설정을 주의 깊게 하지 않으면 컴팩션이 유입 쓰기 속도를 따라 갈 수 없다. 이 경우 디스크 상에 병합되지 않은 세그먼트 수는 디스크 공간이 부족할 때까지 증가한다. 그리고 더 많은 세그먼트 파일을 확인해야 하기 때문에 읽기 또한 느려진다. 보통 SS테이블 기반 저장소 엔진은 컴팩션이 유입 속도를 따라가지 못해도 유입 쓰기의 속도를 조절하지 않으므로 이런 상황을 감지하기 위한 명시적 모니터링이 필요하다.

B 트리의 장점은 각 키가 색인의 한 곳에만 정확하게 존재한다는 점이다. 반면 로그 구조화 저장소 엔진은 다른 세그먼트에 같은 키의 다중 복사본이 존재할 수 있다. 이런 측면 때문에 강력한 트랜잭션 시멘틱(semantic)을 제공하는 데이터베이스에는 B 트리가 훨씬 매력적이다. 많은 관계형 데이터베이스에서 트랜잭션 격리(transactional isolation)는 키 범위의 잠금을 사용해 구현한 반면 B 트리 색인에서는 트리에 직접 잠금을 포함시킨다. 7장에서 이 점을 좀 더 자세히 살펴보겠다.

B 트리는 데이터베이스 아키텍처에 아주 깊게 뿌리내렸다. 그리고 많은 작업부하에 대해 지속적으로 좋은 성능을 제공하므로 B 트리가 곧 사라질 가능성은 거의 없다. 새로운 데이터 저장소에는 로그 구조화 색인이 점점 인기를 얻고 있다. 사용 사례에 적합한 저장소 엔진의 유형을 결정하기 위한 빠르고 쉬운 규칙은 없기 때문에 테스트를 통해 경험적으로 결정하는 방법도 나쁘지 않다.

기타 색인 구조

지금까지는 키-값 색인을 살펴봤다. 키-값 색인의 대표적인 예는 관계형 모델의 기본키(primary key) 색인이다. 기본키로 관계형 테이블에서 하나의 로우를, 문서 데이터베이스에서 하나의 문서를,  그래프 데이터베이스에서 하나의 정점을 고유하게 식별할 수 있다. 데이터베이스에서 다른 레코드는 기본키(또는 ID)로 로우/문서/정점을 참조할 수 있다. 색인은 이런 참조를 찾을 때 사용한다.

보조 색인(secondary index)을 사용하는 방식도 매우 일반적이다. 관계형 데이터베이스에서는 CREATE INDEX 명령을 사용해 같은 테이블에 다양한 보조 색인을 생성할 수 있다. 보조 색인은 보통 효율적으로 조인을 수행하는 데 결정적인 역할을 한다.

보조 색인은 키-값 색인에서 쉽게 생성할 수 있다. 기본키 색인과 주요 차이점은 키가 고유하지 않다는 점이다. 즉 같은 키를 가진 많은 로우(문서, 정점)가 있을 수 있다. 이 점은 두 가지 방법으로 해결할 수 있다. 색인의 각 값에 일치하는 로우 식별자 목록(전문 색인에서 포스팅 목록과 같음)을 만드는 방법 또는 로우 식별자를 추가해 각 키를 고유하게 만드는 방법이 있다. 어느 쪽이든 보조 색인으로 B 트리와 로그 구조화 색인 둘 다 사용할 수 있다.

색인 안에 값 저장하기

색인에서 키는 질의가 검색하는 대상이지만 값은 다음의 두 가지 중 하나에 해당한다. 값은 질문의 실제 로우(문서, 정점)거나 다른 곳에 저장된 로우를 가리키는 참조다. 후자의 경우 로우가 저장된 곳을 힙 파일(heap file)이라 하고 특정 순서 없이 데이터를 저장한다(추가 전용이거나 나중에 새로운 데이터로 덮어쓰기 위해 삭제된 로우를 기록할 수 있다). 힙 파일 접근은 일반적인 방식이다. 여러 보조 색인이 존재할 때 데이터 중복을 피할수 있기 때문이다. 각 색인은 힙파일에서 위치만 참조하고 실제 데이터는 일정한 곳에 유지한다.

 파일 접근 방식은 키를 변경하지 않고 값을 갱신할 때 꽤 효율적이다. 새로운 값이 이전 값보다 많은 공간을 필요로 하지 않으면 레코드를 제자리에 덮어쓸 수 있다. 새로운 값이 많은 공간을 필요로 한다면 상황은 조금 더 복잡해진다. 힙에서 충분한 공간이 있는 새로운 곳으로 위치를 이동해야 하기 때문이다. 이런 경우 모든 색인이 레코드의 새로운 힙 위치를 가리키게끔 갱신하거나 이전 힙 위치에 전방향 포인터를 남겨둬야한다.

색인에서 힙 파일로 다시 이동하는 일은 읽기 성능에 불이익이 너무 많기 때문에 어떤 상황에서는 색인 안에 바로 색인된 로우를 저장하는 편이 바람직하다. 이를 클러스터드 색인(clustered index)라고 한다. 예를 들어 mysql의 InnoDB 저장소 엔진에서는 테이블의 기본키가 언제나 클서스터드 색인이고 보조 색인은 (힙 파일의 위치가 아닌) 기본키를 참조한다. 마이크로소프트 SQL 서버에서는 테이블당 하나의 클러스터드 색인을 지정할 수 있다.

클러스터드 색인(색인 안에 모든 로우 데이터를 저장)과 비클러스터드 색인(색인 안에 데이터의 참조만 저장) 사이의 절충안을 커버링 색인(covering index)이나 포괄열이 있는 색인(index with included column)이라 한다. 이 색인은 색인 안에 테이블의 칼럼 일부를 저장한다. 이렇게 하면 색인만 사용에 일부 질의에 응답이 가능하다(이런 경우를 색인이 질의를 커버했다고 말한다)

모든 종류의 데이터 복제와 마찬가지로 클러스터드 색인과 커버링 색인은 읽기 성능을 높일 수 있지만 추가적인 저장소가 필요하고 쓰기 과정에서 오버헤드가 발생한다. 또한 애플리케이션 단에서 복제로 인한 불일치를 파악할 수 없기 때문에 데이터베이스는 트랜잭션 보장을 강화하기 위해 별도의 노력이 필요하다.

다중 칼럼 색인

지금까지 설명한 색인은 하나의 키만 값에 대응한다. 이 방식은 테이블의 다중 칼럼(multi-column)(또는 문서의 다중 필드)에 동시에 질의를 해야 한다면 충분하지 않다.

다중 칼럼 색인의 가장 일반적인 유형은 결합 색인(concatenated indeex)이라고 한다. 색인은 하나의 칼럼에 다른 칼럼을 추가하는 방식으로 하나의 키에 여러 필드를 단순히 결합한다(필드가 연결되는 순서는 색인 정의에 명시한다). 이 방법은 (성, 이름)을 키로 전화번호를 값으로 하는 색인을 제공하는 구식 종이 전화번호부와 유사하다. 순서가 정렬돼 있기 때문에 특정 성을 가진 모든 사람을 찾거나 특정 성 이름 조합을 가진 모든 사람을 찾을 때도 이 색인을 사용할 수 있다. 하지만 특정 이름을 가진 모든 사람을 찾을 때는 쓸모가 없다.

다차원 색인은 한 번에 여러 칼럼에 질의하는 조금 더 일반적인 방법이다. 특히 지리 공간 데이터에 중요하게 사용된다. 예를 들어 레스토랑 검색 웹 사이트에 각 레스토랑 위도와 경도를 포함한 데이터베이스가 있다고 가정하자. 사용자가 지도에서 레스토랑을 찾는 다면 웹 사이트는 사용자가 현재 보는 네모난 지도 지역 내 모든 레스토랑을 찾아야 한다. 이를 위해 다음과 같이 이차원 범위 질의가 필요하다.

SELECT * FROM restaurants WHERE latitude > 51.4946 AND latitude < 51.5079
						  AND longitude > -0.1162 AND longitude < -0.1004;

표준 B 트리나 LSM 트리 색인은 이런 유형의 질의에 효율적으로 응답할 ㅅ ㅜ없다. 위도 범위 안의 모든 레스토랑(모든 경도에서)이나 경도 범위 안의 모든 레스토랑(남극과 북극 사이의 모든곳)을 줄수 있지만 둘을 동시에 주진 못한다.

한 가지 방법은 이차원 위치를 공간 채움 곡선(space-filling curve)을 이용해 단일 숫자로 변환한 다음 일반 B 트리 색인을 사용하는 것이다. 좀 더 일반적인 방법은 R 트리처럼 전문 공간 색인(specialized spatial index)을 사용하는 것이다. 예를 들면 포스트GIS(PostGIS)는 R 트리 같은 지리 공간 색인을 구현했다. 지리 공간 색인 구현에는 postgreSQL 같은 일반화된 검색 트리(Generalized Search Tree) 색인 기능을 사용했다. R 트리에 대한 문헌은 많이 있기 때문에 이 책에서는 R 트리를 자세히 설명하지 않는다.

흥미로운 점은 다차원 색인의 활용이 지리학적인 위치에만 국한되지 않는다는 점이다. 에를 들어 전자상거래 웹 사이트에서 특정 색상 범위의 제품을 검색 하기 위해 (빨강, 초록, 파랑)의 3차원 색인을 사용한다거나 날씨 관측 데이터베이스에서 2013년에 기온이 25도에서 30도 사이인 모든 관측을 효율적으로 찾기 위해 (날짜, 기온)의 2차원 색인을 사용할 수 있다. 1차원 색인을 사용하면 기온과 상관없이 2013년의 모든 레코드를 스캔한 다음 기온으로 필터링하거나 반대로 기온을 스캔하고 연도로 필터링해야 한다. 2차원 색인은 타임스탬프와 기온으로 동시에 범위를 줄일 수있다. 하이퍼덱스(HyperDex)가 이 기법을 사용한다.

전문 검색과 퍼지 색인 

지금까지 설명한 모든 색인은 정확한 데이터를 대상으로 키의 정확한 값이나 정렬된 키의 값의 범위를 질의할 수 있다고 가정한다. 이 색인으로는 철자가 틀린 단어와 같이 유사한 키에 대해서는 검색 할 수 없다. 이처럼 애매모호한(fuzzy) 질의에는 다른 기술이 필요하다.

예를 들어 전문 검색 엔진은 일반적으로 특정 단어를 검색할 때 해당 단어의 동의어로 질의를 확장 한다. 그리고 단어의 문법적 활용을 무시하고 동일한 문서에서 서로 인접해 나타난 단어를 검색하거나 언어학적으로 텍스트를 분석해 사용하는 등 다양한 기능을 제공한다. 루씬은 문서나 질의의 오타에 대처하기 위해 특정 편집 거리(edit distance)(편집 거리1은 한 글자가 추가되거나 삭제되거나 교체됐음을 의미) 내 단어를 검색할 수 있다.

"SS테이블에스 LSM 트리 만들기"에서 언급했듯이 루씬은 용어 사전을 위해 SS 테이블 같은 구조를 사용한다. 이 구조는 작은 인메모리 색인이 필요하다. 이 인메모리 색인은 키를 찾는 데 필요한 정렬 파일의 오프셋을 질의에 알려주는 데 사용된다. 레벨DB에서 이 인메모리 색인은 일부 키의 희소 컬렉션이다. 하지만 루씬에서 인메모리 색인은 여러 키 내 문자에 대한 유한 상태 오토마톤(finites state automaton)으로 트라이(trie)와 유사하다. 이 오토마톤은 레벤슈타인 오토마톤(levenshtein automaton)으로 변환할 수 있다. 레벤슈타인 오토마톤은 특정 편집 거리 내에서 효율적인 단어 검색을 제공한다.

그 밖의 퍼지 검색 기술은 문서 분류 및 머신러닝의 방향으로 진행되고 있다. 자세한 사항은 정보 검색 교과서를 참고하길 바란다.

모든 것을 메모리에 보관

이번 장에서 지금까지 설명한 데이터 구조는 모두 디스크 한계에 대한 해결책이었다. 디스크는 메인 메모리와 비교해 다루기 어렵다. 자기 디스크와 SSD를 사용할 때 읽기와 쓰기에서 좋은 성능을 원한다면 주의해서 데이터를 디스크에 배치해야 한다. 이런 이상함을 참을 수 있는 이유는 디스크에는 주요한 두 가지 장점이 있기 때문이다. 디스크는 지속성(디스크 내용은 전원이 꺼져도 손실되지 않는다)이 있고 램보다 기가바이트당 가격이 더 저렴하다.

램이 점점 저렴해져서 기가바이트당 가격 논쟁은 약해졌다. 데이터셋 대부분은 그다지 크지 않기 때문에 메모리에 전체를 보관하는 방식도 꽤 현실적이다. 혹은 여러 장비 간 분산해서 보관할 수도 있다. 이런 이유로 인메모리 데이터베이스가 개발됐다.

멤 캐시드 같은 일부 인메모리 키-값 저장소는 장비가 재시작되면 데이터 손실을 허용하는 캐시 용도로만 사용된다. 하지만 다른 인메모리 데이터베이스는 지속성을 목표로 한다. 이 목표를 달성하는 방법은 (배터리 전원 공급 RAM과 같은) 특수 하드웨어를 사용하거나 디스크에 변경 사항의 로그를 기록하거나 디스크에 주기적인 스냅숏을 기록하거나 다른 장비에 인메모리 상태를 복제하는 방법이 있다.

인메모리 데이터베이스가 재시작되는 경우 특수 하드웨어를 사용하지 않는다면 디스크나 네트워크를 통해 복제본에서 상태를 다시 적재해야 한다. 디스크에 기록하더라도 여전히 인메모리 데이터베이스다. 왜냐하면 디스크는 저적으로 지속성을 위한 추가 전용 로그로 사용되고 읽기는 전적으로 메모리에서 제공되기 때문이다. 디스크에 기록하는 방식은 운영상의 장점도 있다. 디스크 상의 파일은 쉽게 백업이 가능하고 외부 유틸리티를 이용해 검사와 분석을 할 수 있다.

VoltDB, MemSQL, Oracle TimesTen 같은 제품은 관계형 모델의 인메모리 데이터베이스다. 이런 제품 벤더는 디스크 상 데이터 구조 관리와 관련된 오버헤드를 모두 없앴기 떄문에 성능을 크게 개선했다고 주장한다. 램클라우드(RAMCloud)는 지속성 있는 오픈소스 인메모리 키-값 저장소다(메모리 데이터뿐 아니라 디스크 데이터도 로그 구조화 접근 방식을 사용한다). Redis와 Couchbase는 비동기로 디스크에 기록하기 때문에 약한 지속성을 제공한다.

직관에 어긋나지만 인메모리 데이터베이스의 성능 장점은 디스크에서 읽지 않아도 된다는 사실 때문은 아니다. 심지어 디스크 기반 저장소 엔진도 운영체제가 최근에 사용한 디스크 블록을 메모리에 캐시하기 때문에 충분한 메모리를 가진 경우에는 디스크에서 읽을 필요가 없다. 오히려 인메모리 데이터 구조를 디스크에 기록하기 위한 형태로 부호화하는 오버헤드를 피할 수 있어 더 빠를수도 있다.

성능 외에도 인메모리 데이터베이스는 또 다른 재미있는 영역으로서 디스크 기반 색인으로 구현하기 어려운 데이터 모델을 제공한다. 예를 들어 레디스는 우선순위 큐와 셋 같은 다양한 데이터 구조를 데이터베이스 같은 인터페이스로 제공한다. 또한 메모리에 모든 데이터를 유지하기 때문에 구현이 비교적 간단하다.

최근연구에 따르면 인메모리 데이터베이스 아키텍처가 디스크 중심 아키텍처에서 발생하는 오버헤드 없이 가용한 메모리보다 더 큰 데이터셋을 지원하게끔 확장할 수 있다. 소위 안티 캐싱(anti caching) 접근 방식은 메모리가 충분하지 않을 때 가장 최근에 사용하지 않은 데이터를 메모리에서 디스크로 내보내고 나중에 다시 접근할 때 메모리에 적재하는 방식으로 동작한다. 이것은 운영체제가 가상 메모리와 스왑 파일에서 수행하는 방식과 유사하지만 데이터베이스는 전체 메모리 페이지보다 개별 레코드 단위로 작업할 수 있기 때문에 OS보다 더 효율적으로 메모리를 관리할 수 있다 하지만 이 접근 방식은 (이번 장 시작 부분의 비트캐스크 예와 같이) 여전히 전체 새깅ㄴ이 메모리에 있어야 한다.

나아가 비휘발성 메모리(non-volatile memory, NVM) 기술이 더 널리 채택되면 저장소 엔진 설계의 변경이 필요할 것이다. 현재 비휘발성 메모리 기술은 새로운 연구 분야지만 앞으로 계속 주목할 가치가있다.