저장소와 검색

데이터베이스의 가장 중요한 두가지 추상화는 쓰기/읽기이다. 그리고 이 두가지 성능은 항상 Trade-off 관계에 있다. 그 Trade-off 관계를 이해하는 것과, 가장 대표적인 저장소 엔진인 로그구조(Log-Structured) 저장소 엔진과 B-트리 같은 페이지지향(page-oriented) 저장소 엔진을 비교하는 것이 이 장의 목표이다.

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

#!/bin/bash

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

db_get () {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1 // 특정 키에 대한 마지막 값을 가져온다.
}
  • 가장 간단한 데이터 베이스의 구조
> db_set "small" '{"name": "SmallzooDev", "email": "helloWorld@helloWorld.com"}'
> db set "big" '{"name": "BigzooDev", "email": "helloWorld2@helloWorld.com"}'
> db set "small" '{"name": "SmallzooDev", "email": "foo@bar.com"}'

> cat database
"small","{"name": "SmallzooDev", "email": "helloWorld@helloWorld.com'}"
"big","{"name": "BigzooDev", "email": "hellowWorld@helloWorld.com"}"
"small","{"name": "SmallzooDev", "email": "foo@bar.com"}"

  • 언뜻 장난같지만 이 데이터베이스는 실제로 매우 강력하다.

  • 쓰기 작업은 성능이 특히 뛰어나다. (그냥 파일에 append만 하면 되기 때문)

  • 읽기 작업은 키를 찾아서 파일을 끝까지 읽어야 하기 때문에 성능이 좋지 않다.(O(n))

  • 좋은 쓰기 성능 대비 나쁜 읽기성능을 보완하기 위해 다른 데이터 구조를 추가하는데, 바로 Index이다.

색인은 기본ㄷ 데이터에서 파생된 추가적인 구조다. 많은 데이터베이스는 색인의 추가오 삭제를 허용한다. 이 작업은 데이터베이스의 내용에는 영향을 미치지 않는다. 단지 질의 성능에만 영향을 준다. 특히 쓰기 과정에서의 오버헤드가 발생한다. 쓰는 시점에 인덱스를 갱신하기 때문이다.

해시 색인

  • 먼저 키-값 데이터를 색인하는 가장 간단한 방법은 해시 테이블을 사용하는 것이다.
  • 실제로 인메모리에 해시테이블을 사용하는건 굉장히 흔한 방식이고, 비트캐스크(Riak의 엔진)도 이 방식을 사용한다고 한다.
(newline은 없고 디스크 상에 일렬로 저장된다고 가정한다.)
"small","{"name": "SmallzooDev", "email": "helloWorld@helloWorld.com'}" 
"big","{"name": "BigzooDev", "email": "hellowWorld@helloWorld.com"}"
"small","{"name": "SmallzooDev", "email": "foo@bar.com"}"


// key : value 
small : (가장 최근에 추가된 small이 시작되는 위치)
big : (가장 최근에 추가된 big이 시작되는 위치)

이렇게 빠르게 조회를 달성하고 나면 위의 구조(모든 추가 데이터를 파일에 append, 해시테이블에 키-값을 저장)는 여러가지 장점을 가진다. 첫 번째로 아직 쓰기 성능이 뛰어나다. (파일에 append만 하면 되기 때문) 두 번째로 해시테이블을 사용하면 키를 찾는데 O(1)의 시간이 걸린다.

  • 하지만 한가지 문제가 있는데, 바로 디스크의 용량이 결국 부족해진다는 것이다.

위의 예시에서, 계속 append된 데이터를 실제로 데이터베이스에서도 매우 유용하게 사용하며, 이를 database 로그라고 일컫는다. 지금 상황은 로그 자체를 데이터베이스로 사용하고 있는 것이다.

  • 이 문제를 해결하기 위해 컴팩션이라는 개념이 등장한다.
  • 먼제 세그먼트를 도입해서 로그가 특정 크기에 도달하면 이를 나눠담는다.
  • 그리고 이 세그먼트를 더 작게 만들기 위해서 하는 작업이 컴팩션 이다.
  • 사실 컴팩션 자체는 매우 간단한데, 세그먼트를 읽어서 중복된 키를 제거하고, 가장 최근의 값을 유지하는 것이다.
  • 컴팩션은 다른 쓰레드에서 진행해도 무방하고, 아직도 안전한 append 로그 작업을 계속할 수 있다. (append 로그 방식이 얼마나 안전한지 모르겠다면, 값을 갱신하는 방식으로 db를 구현했을때 갱신중 꺼지는 상황을 떠울리면 된다)

하지만 해시 테이블 역시 제약 사항이 있다.

  1. 메모리에 키를 저장해야 하기 때문에, 키가 매우 많아지면 메모리가 부족해진다.
  2. 범의 질의를 지원하지 않는다.

##SS테이블과 LSM트리

  • 먼지 키를 특정 기준으로 정렬한다.
  • 정렬을 위해서 merge-sort를 사용하는데, (세그먼트로 나누어서 정렬하고, 이를 합치는 방식) 메모리보다 파일이 커도 정렬이 가능하다.
  • 이렇게 키로 정렬된 테이블을 SS테이블(sorted string table)이라고 한다.
  • 이렇게 SS테이블을 만들면 해당 테이블을 이용해 범위 질의도 할 수 있고, 모든 키를 메모리에 저장하지 않아도 된다(정렬의 특성상, 없으면 범위를 찾을 수 있기 때문)
  • 여기까지는 괜찮은데 그렇다면 데이터를 정렬하려면 어떻게 해야할까?
    1. 일단 이것도 디스크에 정렬을 유지하는것은 쉽지않다. 유입되는 쓰기는 임의 순서로 발생하기 때문이다. (B트리를 이용하면 가능하지만, 이는 다음에 설명)
    2. 그래서 메모리에 AVL트리나 레드블랙트리를 사용해서 정렬을 유지한다.
    3. 이런 구조들로 임의 순서로 키를 삽입하고, 정렬된 순서로 키를 읽는다.
  1. 쓰기가 들어오면 인메모리 균형 트리 데이터구조(레드블랙트리나 AVL트리)에 추가한다. 이걸 멤테이블(memtable)이라고 부른다.
  2. 멤테이블이 일정 크기에 도달하면 SS테이블로 변환하고, 디스크에 기록한다. 새로운 SS테이블파일은 데이터베이스의 가장 최신 세그먼트가 된다. SS테이블을 디스크에 쓰는동한 새로운 쓰기는 멤테이블 인스턴스에 기록한다.
  3. 읽기 요청을 제공하려면 먼저 멤테이블에서 키를 찾아야한다. 그리고 그 다음에는 가장 최신의 SS테이블부터 가장 오래된 SS테이블까지 차례로 검색한다.
  4. 가끔 세그먼트 파일을 합치고 덮어 쓰여지거나 삭제된 값을 버리는 병합과 컴팩션 작업을 수행한다.(이 작업은 백그라운드에서 수행된다.) (데이터베이스가 고장난경우 쓰기중인 데이터가 날아갈 수 있지만, 로그를 유지하고 있기 때문에 복구가 가능하다.)

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

LSM트리는 Log-Structured Merge-Tree의 약자로, SS테이블을 이용해서 만들어진다. 이러한 방식은 구글의 빅테이블 논문에서 처음 소개되었다. 루신과 같은 검색엔진에서도 사용되는 방식인데, 용어 사전(term dictionary)을 만들때 사용한다. (검색 질의가 들어오면, 단어가 언급된 모든 문서를 찾는데, 이 접근법을 키를 단어로 값은 단어를 포함한 모든 문서의 포스팅 목록으로하는 키-값구조로 저장하게된다.)

  • LSM트리는 블룸필터등을 사용해서 키 존재 여부를 빠르게 확인하며 최적화하고
  • SS테이블 병합도 크기 계층, 레벨 컴팩션을 통해 최적화한다.

##B트리

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

  • 기본적인 b트리로직과 똑같다. 루트 페이지에 여러 키와 하위페이지의 참조를 저장하고, 이어서 두 번째 페이지에도 키와 참조를 저장한다.

  • 그러다 리프페이지에 도달하면, 값의 참조를 저장한다.

  • B트리의 한 페이지에서 하위 페이지를 참조하는 수를 분기계수라고 부른다.

  • 갱신과 추가는 쉽지만 삭제는 조금 복잡하다.

  • 삭제시에는 키를 삭제하고, 빈 공간을 채우기 위해 인접한 키를 이동시키거나, 인접한 페이지와 병합하는 작업을 수행한다.

신뢰 할 수 있는 B트리 구현하기

  • 로그 구조화 색인과 달리 B트리는 쓰기작업시 데이터를 디스크상의 페이지에 덮어쓴다.
  • 이 동작이 덮어쓰기가 페이지 위치를 변경하지 않는다고 가정한다. 즉 페이지를 덮어써도 참조는 온전히 남는다.
  • 이런 이유로 동시성 제어가 필요하고, 트랜잭션 로그를 사용해서 데이터베이스를 복구할 수 있어야 한다.

B트리는 여러가지 최적화 기법이 있다.

  1. 페이지 덮어쓰기와 WAL유지 대신 변경된 페이지는 다른위치에 기록하고, 변경된 페이지를 가리키는 로그를 유지한다.
  2. 전체키를 쓰는게 아니라, 키의 일부만 쓰는 방식을 사용한다.
  3. 디스크에 순서대로 저장할 제약을 두지 않는다.
  4. 여기저기 포인터로 최적화(리프노드에 양쪽 페이지의 포인터를 저장하는 방식)를 사용한다.

기타 색인 구조

키-값 색인에 대해서 살펴봤고, 번역이 이상한지 해당 인덱스를 사용하는 사용예시를 보여준다.

다중 칼럼 색인

SELECT * FROM restaurans WHERE latitute BETWEEN 37.0 AND 37.1 AND longitude BETWEEN -122.0 AND -121.9;
  • 위와 같은 쿼리가 있을 때 지금까지 언급된 인덱스는 효율적으로 응답 할 수 없다.
  • 이런 경우 2차원 채움 곡선과 같이 단일 숫자로 변환하는 방법이 있다고 한다.
  • 그외에 R트리 색인 같은게 있고 postgresql에서는 구현되어있다고 하는데 설명은 없다.