데이터베이스와 인덱스(LSM트리과 B트리)

이번 장에서는 데이터베이스의 저장과 검색에 대해 다룬다. B-tree와 LSM-tree을 중심으로 비교한다.

데이터베이스의 구조

• 데이터베이스의 기본 역할

  • 가장 기본적인 데이터베이스의 역할은 데이터를 저장하고, 요청한 데이터를 제공하는 것

  • 개발자의 입장에서 특정 작업부하 유형에서 좋은 성능을 내게끔 저장소 엔진을 조정하려면 저장소 엔진이 내부에서 수행되는 작업에 대한 대략적인 개념을 이해할 필요가 있음

  • 이 장에선 RDBMS와 NoSQL의 저장소 엔진, 로그 구조(log-structured) 계열 저장소 엔진과 B-tree 기반의 페이지 지향(page-oriented) 계열 저장소 엔진을 검토해보자

• 간단한 데이터베이스

#!/bin/bash 
 db_set () {
 echo "$1,$2" >> database
 } 
 db_get () {
 grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
 }

• key-value 저장소를 함수 두 개로 구현될만큼 기본적인 저장소 형식은 매우 간단함

• 최신값을 찾기 위해서는 파일에서 키의 마지막 항목을 살펴봐야함

• append 작업은 매우 효율적이기 때문에 실제로 많은 데이터베이스는 내부적으로 append-only 데이터 파일인 log를 사용함

• 실제 데이터베이스는 다뤄야 할 많은 문제가 존재(동시성 제어, 로그가 영원히 커지지 않게끔 디스크 공간을 회수, 오류 처리, 부분적으로 기록된 레코드 처리)가 있지만, 기본 원리는 동일함

• 여기서 log는 포괄적인 의미로 연속된 추가 전용 레코드라고 이해할 수 있음

• 하지만, 이러한 데이터베이스는 많은 레코드가 있으면 성능하락이 발생. 매번 키를 찾을 때마다 모든 데이터베이스 파일을 처음부터 끝까지 스캔해야하기 때문 O(N)

• 이러한 문제를 해결하기 위한 해결책이 바로 색인임

색인(Index)

• 색인의 일반적인 개념은 어떤 부가적인 메타데이터를 유지하는 것(기본 데이터에서 파생된 추가적인 구조)

• 이는 데이터베이스의 내용에는 영향을 미치지 않으며, 단지 질의 성능에만 영향을 줌

• 하지만 색인 구조의 유지보수를 위해 쓰기 과정에서 오버헤드가 발생 왜냐하면 append-only방식을 버리고 데이터를 쓸 때마다 매번 색인도 갱신해야 하기 때문

• 색인 사용으로 인한 쓰기 오버헤드 및 질의 성능 향상 트레이드 오프가 존재하기 때문에 개발자는 애플리케이션의 전형적인 질의 패턴에 대한 지식을 활용해 수동으로 색인을 선택해야 함

• 해시(Hash) 색인

  • key-value 저장소는 일반적인 사전 타입(dictionary type)과 유사하며, 보통 해시 맵(hash map)으로 구현함

  • 가장 간단한 해시 색인 전략은 키를 데이터 파일의 바이트 오프셋에 매핑하고 인메모리 해시 맵을 유지하는 전략

  • 이를 위해서는 새로운 데이터를 삽입할 때마다 해시 맵도 갱신해야 함. 값을 조회하려면 해시 맵을 사용해 데이터 파일에서 오프셋을 찾아 해당 위치를 구하고 값을 읽음

• 실제로 비트캐스크(Bitcask)가 사용하는 방식이며 해시 맵을 전부 메모리에 유지하기 때문에 고성능의 읽기 및 쓰기를 보장

• 이러한 저장소는 각 키의 값이 자주 갱신되는 상황에 적합

  • 예를 들어 키는 고양이 동영상의 url이고 값은 비디오가 재생된 횟수인 경우라면, 작업부하에서는 쓰기가 아주 많지만 고유 키는 많지 않다. 즉, 키당 쓰기 수가 많지만 메모리에 모든 키를 보관할 수 있음을 의미

  • 항상 데이터를 추가한다면 결국 디스크 공간이 부족해지는 현상이 발생할 수 있음. 이는 특정 크기의 세그먼트(segment)로 로그를 나누는 방식으로 해결함. 특정 크기에 도달하면 세그먼트 파일을 닫고 새로운 세그먼트 파일에 이후 쓰기를 수행. 세그먼트 파일들에 대해 컴팬션(compaction)을 수행할 수도 있음. 컴팩션은 로그에서 중복된 키를 버리고 각 키의 최신 갱신 값만 유지하는 것을 의미

• 한 가지 유의점은 인메모리 기반의 해시 맵 저장을 사용하므로 데이터베이스가 재시작될 때 해시맵이 손실된다는 것. 세그먼트 파일이 크면 클수록 해시 맵 복원 작업은 오래 걸림. 비트캐스크는 각 세그먼트 해시 맵을 메모리로 빠르게 로딩할 수 있도록 스냅샷을 디스크에 저장해 복구 속도를 높이는 방법을 사용함

• 추가하는 방식이 아니라, 새로운 값이 들어오면 이전 값을 덮어쓰면 되지 않을까?

  • 추가와 세그먼트 병합은 순차 쓰기 방식이기 때문에 무작위 쓰기보다 훨씬 빠름

  • 특히 HDD에서 더욱 속도 차이가 남

  • 추가 방식은 동시성과 고장 복구에 있어 훨씬 간단함. 예를 들어 값을 덮어 쓰는 동안 데이터베이스가 죽는 경우에 대해 걱정할 필요가 없음. 이전 값 부분과 새로운 값 부분을 포함한 파일을 나누어 함께 남겨두기 때문임

• 하지만 단점도 존재

  • 해시 테이블은 메모리에 저장하므로 키가 너무 많으면 안됨. 원칙적으로 디스크에 해시 맵을 유지할 수는 있지만 좋은 성능을 기대하기 어려움. 무작위 접근 I/O가 많이 필요하며 디스크가 가득 찼을 때 확장하는 비용 및 해시 충돌 해소를 위한 복잡한 로직이 필요하게 됨

  • 또한, 범위 질의에 효율적이지 않음. 예를 들어 00000과 99999 사이의 모든 키를 쉽게 스캔할 수 없음. 해시 맵에서 모든 개별 키를 조회해야 함

SS 테이블과 LSM 트리

• SS 테이블에서의 변경 사항은 key-value를 key로 정렬하는 것

• 이처럼 키로 정렬된 형식을 정렬된 문자열 테이블(Sorted String Table)이라 함

• 각 키는 각 병합된 세그먼트 파일 내에 한 번만 나타남

• 장점

  • 세그먼트 병합은 파일이 사용 가능한 메모리보다 크더라도 간단하고 효율적임. 이 접근은 병합정렬 알고리즘과 유사함(위 그림 참조)

  

  • 파일에서 특정 키를 찾기 위해 메모리에 모든 키의 색인을 유지할 필요가 없음(희소 색인). 위 그림에서 handiwork 키를 찾으려 하면, handbag과 handsome 키의 오프셋을 알고 있고, 정렬되어 있으므로 handiwork는 두 키 사이에 있다는 사실을 알 수 있음 즉, handbag 오프셋으로 이동해 handiwork가 나올 때까지 스캔하면 됨

• 데이터를 키로 정렬하기

  • 데이터가 유입되는 쓰기는 임의 순서로 발생

  • 따라서, 레드블랙트리나 AVL 트리 같은 데이터 구조를 이용해 임의 순서로 키를 삽입하고 정렬된 순서를 유지함

• 저장소 작동 원리

  • 쓰기가 들어오면 인메모리 균현 트리(예를 들어 레드 블랙 트리)에 추가. 이 트리를 멤테이블(memtable)이라고 함

  • 멤테이블이 보통 수 메가바이트 정도의 임곗값보다 커지면 SS테이블 파일로 디스크에 기록. 새로운 SS테이블 파일은 데이터베이스의 가장 최신 세그먼트가 됨

  • 읽기 요청이 들어오면 먼저 멤테이블에서 키를 찾고, 그 다음 디스크 상의 최신 세그먼트를 찾고, 그 다음 두 번째 오래된 세그먼드 등으로 순차 접근

  • 가끔 세그먼트 파일을 합치고 덮어 쓰여지거나 삭제된 값을 버리는 병합과 컴팩션 과정을 수행(백그라운드)

  • 이때, 데이터베이스가 고장나서 아직 디스크로 옮겨지지 않은 멤테이블이 손실될 수 있음. 따라서 매번 쓰기를 즉시 추가할 수 있게 분리된 로그를 디스크 상에 유지해야 함

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

  • 로그 구조화 병합 트리(Log-Structured Merge-Tree)(LSM Tree)

  • 정렬된 파일 병합과 컴팩션 원리를 기반으로 하는 저장소 엔진은 LSM 저장소 엔진이라고 함

  • 루씬은 엘라스틱서치나 솔라에서 사용하는 검색 색인 엔진. 루씬은 용어 사전을 저장하기 위해 유사한 방법을 사용. 키를 단어(용어)로, 값을 단어를 포함한 모든 문서의 ID(포스팅 목록)으로 하는 키-값 구조로 구현

• 성능 최적화

  • LSM는 데이터 베이스에 존재하지 않는 키를 찾는 경우 느릴 수 있음

  • 이는 멤테이블을 거쳐 가장 오래된 세그먼트까지 키를 찾기 위해 거슬러 올라가야 하기 때문

  • 이런 종류의 접근을 최적화하기 위해 저장소 엔진은 보통 블룸 필터(Bloom filter)을 추가적으로 사용(집합 내용을 근사한(approximating) 메모리 효율적 데이터 구조로, 키가 데이터베이스에 존재하지 않음을 알려줌)

  • 병합전략

    • 크기 계층(size-tiered) : Hbase에서 사용. 상대적으로 좀 더 새롭고 작은 SS테이블을 오래되고 큰 SS테이블에 병합

    • 레벨 컴팩션(leveled compaction) : 레벨DB, 록스DB 사용. 키 범위를 더 작은 SS테이블로 나누고 오래된 데이터는 개별 레벨로 이동. 즉, 컴팩션을 점진적으로 진행해 디스크 공간을 덜 사용

B-Tree

• 거의 대부분의 RDBMS에서 사용하는 색인 구조

• LSM은 일반적으로 수 메가바이트 이상의 가변 크기를 가진 세그먼트로 나누고 순차적으로 기록

• 반면, B 트리는 4KB 크기(때로는 더 큰)의 고정 크기 블록이나 페이지로 나누고 한 번에 하나의 페이지에 읽기 또는 쓰기를 함

• 각 페이지는 주소나 위치를 이용해 식별하고, 하나의 페이지가 다른 페이지를 참조할 수 있음
  

• 색인 과정

  • 한 페이지는 B 트리의 루트로 지정되며 색인은 루트에서 시작함(위 그림 참조), 최종적으로는 개별 키(leaf page)를 포함한 페이지에 도달

  • B트리의 한 페이지에서 하위 페이지를 참조하는 분기 수를 분기 계수(branching factor)라고 함. 위 그림의 분기 계수는 6. 보통 수백 개까지 늘어남

  • 갱신 과정
    

    • B트리에 존재하는 키값을 갱신하려면 키를 포함한 리프 페이지를 검색하고 값을 바꾼 후, 다음 페이지를 디스크에 다시 기록

    • 새로운 키를 추가하려면 새로운 키를 포함하는 범위의 페이지를 찾아 해당 페이지에 키와 값을 추가. 만일 새로운 키를 수용한 페이지에 충분한 여유 공간이 없다면 페이지 하나를 반쯤 채워진 페이지 둘로 나누고 상위 페이지가 새로운 키 범위의 하위 부분들을 알 수 있게 갱신

    • 이 알고리즘은 트리가 계속 균형을 유지하는 것을 유지하며 n개의 키를 가진 B 트리를 깊이가 항상 O(log n)임을 보장

    • 분기 계수 500의 4KB 페이지의 4단계 트리는 256TB까지 저장이 가능(500^4*4096B)

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

  • B 트리의 기본적인 쓰기 동작인 새로운 데이터를 디스크 상의 페이지에 덮어 쓰는 것이, LSM 트리는 파일에 추가하는 형식으로 이루어짐(쓸모 없는 파일은 삭제)

  • 이 때 일부 페이지만 기록하고 데이터베이스가 고장난다면 결국 색인이 훼손되는 현상이 발생(예를 들어 고아 페이지 : 어떤 페이지와도 부모 관계가 없는 페이지)

  • 데이터베이스가 고장 상황에서 스스로 복구할 수 있도록 하려면 디스크에 쓰기 전 로그(write-ahead log. WAL)(재실행 로그(redo log))라고 하는 데이터 구조를 추가해야 함. 이는 변경된 내용을 적용하기 전에 모든 B 트리의 변경사항을 기록하는 추가 전용 파일임

  • 동시성 제어(다중 스레드가 동시에 B 트리에 접근)를 위해서는 보통 래치(latch)(가벼운 잠금(lock))으로 트리의 데이터 구조를 보호. 이런 측면에서 LSM 트리는 훨씬 간단하다. 백그라운드에서 모든 병합을 수행하고 새로운 세그먼트를 이전 세그먼트로 바꾸기 때문

• B 트리 최적화

  • 몇 가지 최적화 기법을 간단하게 살펴본다.(뒷 장에서 자세히 다룬다)

    • 고장 복구를 위한 WAL대신 쓰기시 복사 방지(copy-on-write scheme)를 사용. 변경된 페이지는 다른 위치에 기록하고 트리에 상위 페이지의 새로운 버전을 만들어 새로운 위치를 가리키는 방식

    • 페이지에 전체 키를 저장하는 게 아니라 키를 축약해 공간 절약

    • 리프 페이지를 디스크 상에 연속된 순서로 배치(질의가 정렬된 순서로 키 범위의 상당 부분을 스캔할 때의 성능 향상을 위해)

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

• B 트리와 LSM 트리의 비교

  • B 트리는 보통 읽기에서 빠르며 LSM 트리는 보통 쓰기에서 빠르다. LSM 트리에서의 읽기는 각 컴팩션 단계에 있는 여러 데이터 구조와 SS테이블을 확인하기 때문

  • B 트리는 모든 데이터를 최소한 두 번 기록한다. 쓰기전 로그(WAL)과 트리 페이지에 기록하기 때문. 또한 해당 페이지에서 몇 바이트만 바뀌어도 전체 페이지를 기록해야 하는 오버헤드도 존재

  • LSM 트리 역시 여러 번 데이터를 다시 씀. SS테이블의 반복된 컴팩션과 병합 때문. 하지만 LSM 트리는 여러 페이지를 덮어 쓰는 방식이 아닌 순차적으로 컴팩션된 SS테이블 파일을 쓰는 점에서 구분됨

  • 특히 하드드라이브에서 순차 쓰기가 임의 쓰기 보다 훨씬 빠름

  • LSM 트리는 압축률이 좋음. 보통 B 트리보다 디스크에 더 적은 파일을 생성. 또한, B 트리는 파편화로 인해 디스크 공간 일부가 남음(페이지를 나눌 때 일부 공간을 사용하지 않는 것을 떠올려보자). LSM 트리는 주기적으로 파편화를 없애기 위해 SS테이블을 다시 기록하기 때문에 저장소 오버헤드가 낮음

  • LSM 트리의 단점은 컴팩션 과정 중일 때 읽기와 쓰기 성능에 영향을 줄 수 있다는 것. 디스크가 비싼 컴팩션 연산을 하는 동안 병목현상이 발생할 수 있음

  • 즉, 컴팩션이 데이터 유입속도를 따라가지 못한다면, 디스크 상에 병합되지 않은 세그먼트 수가 디스크 공간이 부족할 때까지 증가할 수 있음(모니터링이 필요)

  • B 트리의 장점은 각 키가 색인의 한 곳에 정확히 존재한다는 점. 반면 LSM 트리는 다른 세그먼트에 같은 키의 다중 복사본이 존재할 수 있음. 이 때문에 강력한 트랜잭션 시맨틱을 제공하는 데이터베이스에는 B 트리가 훨씬 매력적임

• 기타 색인

  • 색인 안에 값 저장

    • 색인에서 키는 질의가 검색하는 대상이며, 값은 실제 로우를 가리키거나 다른 곳에 저장된 로우를 가리키는 참조 형태로 존재

    • 후자의 경우 로우가 저장된 곳을 힙 파일(heap file)이라 하며, 특정 순서 없이 데이터를 저장

    • 힙 파일은 키를 변경하지 않고 값을 갱신할 때 효율적임

    • 색인에서 힙 파일로 이동하는 것은 읽기 성능에 불이익을 주기 때문에 색인 안에 로우를 저장하는 방식이 클러스터드 색인임(ex. MySQL의 InnoDB는 테이블의 기본키가 언제나 클러스터드 색인임)

  • 다중 칼럼 색인

    • 가장 흔한 유형은 여러 필드를 결합한 결합색인(concatenated index)

    • 이러한 것은 지리 공간 데이터에서 중요하게 사용됨(네모난 공간 안애 모든 레스토랑을 찾아야 한다면? : 보통은 R 트리를 사용하는 것이 일반적임)

    • 다중 칼럼 색인은 1차원 색인에서 여러 레코드를 하나씩 필터링해나가는 방식에서 다차원으로 한번에 필터링이 가능해지는 장점이 존재

  • 전문 검색과 퍼지 색인

    • 철자가 틀린 단어와 같이 유사한 키에대한 검색을 허용. 애매모호한(fuzzy) 질의에 대응

    • 전문 검색 엔진은 일반적으로 특정 단어를 검색할 때 해당 단어의 동의어로 질의를 확장

    • 문서나 질의의 오타에 대처하기도 함

    • 최근에는 문서 분류 및 머신러닝의 방향으로 진행되는 중

  • 모든 것을 메모리에 보관

    • 메모리 가격이 하락하며 급부상

    • 인메모리 데이터베이스라고 함

    • 맴캐시드 같은 일부 인메모리 키-값 저장소는 캐시용도로만 사용하지만, 데이터베이스의 지속성을 목표로 하는 인메모리 데이터베이스도 존재(디스크에 변경 사항의 로그를 기록하거나 주기적으로 스냅샷을 생성하여 다른 장비에 복제하는 방법으로)

    • 레디스와 카우치베이스 같은 경우는 비동기로 디스크에 기록하기 때문에 약한 지속성을 제공.

    • 인메모리 데이터베이스의 성능 장점은 디스크에서 읽지 않아도 된다는 사실 때문만은 아님. 디스크 저장소 엔진도 운영체제가 최근에 사용한 디스크 블록을 메모리에 캐시하기 때문에 충분한 메모리를 가진 경우에는 디스크에서 읽을 필요가 없음

    • 성능 외에도 인메모리 데이터 베이스는 디스크 기반 색인으로는 구현하기 어려운 데이터 모델을 제공. 예를 들어 레디스는 우선순위 큐와 셋(set) 같은 다양한 데이터 구조를 데이터베이스와 같은 인터페이스로 제공함