데이터 중심의 애플리케이션 설계 - SSTable과 LSM-Tree

키-값 쌍이 연속적으로 저장된 로그 구조의 스토리지 세그먼트를 키-값 쌍의 순서가 키별로 정렬되도록 해보자. 이러한 형식을 정렬된 Sorted String Table 또는 줄여서 SSTable이라고 부른다.
SSTable의 각 키는 병합된 각 세그먼트 파일 내에서 한 번만 나타나야 한다(압축 프로세스에서 이미 이를 보장한다).

SSTable가 로그 세그먼트와 비교하여 갖는 장점

1. 파일이 사용 가능한 메모리보다 큰 경우에도 세그먼트를 병합하는 것이 간단하고 효율적이다.
   입력 파일을 나란히 읽기 시작하고 각 파일의 첫 번째 키를 살펴보고 정렬 순서에 따라 가장 낮은 키를 출력 파일로 복사한 후 반복한다. 이렇게 하면 키별로 정렬된 새로운 병합 세그먼트 파일이 생성된다.

2. 파일에서 특정 키를 찾기 위해 모든 키의 인덱스를 메모리에 보관할 필요가 없다.
   일부 키에 대한 오프셋을 알려주려면 여전히 메모리 내 인덱스가 필요하지만, 몇 킬로바이트는 매우 빠르게 스캔할 수 있으므로 몇 킬로바이트의 세그먼트 파일당 하나의 키만 있으면 충분할 수 있다.

3. 읽기 요청은 요청된 범위의 여러 키-값 쌍을 스캔해야 하므로, 디스크에 쓰기 전에 이러한 레코드를 블록으로 그룹화하여 압축할 수 있다. 그러면 희소한 인메모리 인덱스의 각 항목은 압축된 블록의 시작을 가리킨다. 압축은 디스크 공간을 절약할 뿐만 아니라 I/O 대역폭 사용량도 줄여준다.

SSTable 구축과 유지 관리

처음부터 데이터를 키별로 정렬하려면 어떻게 해야 할까? 쓰기 요청은 어떤 순서로든 발생할 수 있다. 디스크에서 정렬된 구조를 유지하는 것보다 메모리에서 유지하는 것이 훨씬 쉽다.
레드-블랙 트리 또는 AVL 트리와 같은 데이터 구조를 사용하면 어떤 순서로든 키를 삽입하고 정렬된 순서대로 다시 읽을 수 있다.

이제 스토리지 엔진이 다음과 같이 작동하도록 만들 수 있다:

• 쓰기가 들어오면 인메모리 균형 트리(AVL) 데이터 구조에 추가한다. 이 인메모리 트리를 memtable이라고 부르기도 한다.

• memtable이 특정 임계값(일반적으로 몇 메가바이트)보다 커지면 이를 SSTable 파일로 디스크에 기록한다.
  트리는 키별로 정렬된 키-값 쌍을 이미 유지하고 있기 때문에 이 작업을 효율적으로 수행할 수 있다.
  새 SSTable 파일은 데이터베이스의 가장 최근 세그먼트가 된다.
  SSTable이 디스크에 기록되는 동안에도 새로운 memtable 인스턴스에 대한 쓰기가 계속될 수 있다.

• 읽기 요청을 처리하려면 먼저 멤테이블에서 키를 찾은 다음 가장 최근 디스크에 있는 세그먼트, 그 다음 오래된 세그먼트 등에서 키를 찾아야 한다.

• 가끔씩 백그라운드에서 병합 및 압축 프로세스를 실행하여 세그먼트 파일을 결합하고 덮어쓰거나 삭제된 값을 버린다.

이 방식은 단 한 가지 문제가 있다. 데이터베이스가 충돌하면 가장 최근의 쓰기(멤테이블에 있지만 아직 디스크에 기록되지 않은)가 손실된다는 것이다. 이 문제를 피하기 위해 이전 섹션에서와 같이 모든 쓰기가 즉시 추가되는 별도의 로그를 디스크에 보관할 수 있다. 이 로그는 정렬된 순서가 아니지만, 크래시 발생 후 멤테이블을 복원하는 것이 유일한 목적이므로 중요하지 않다. memtable이 SSTable에 기록될 때마다 해당 로그는 삭제될 수 있습니다.

SSTables로 LSM 트리 만들기

SSTable의 알고리즘은 한 애플리케이션에 내장되도록 설계된 키-값 스토리지 엔진 라이브러리인 LevelDB 및 RocksDB 에서 사용되는 알고리즘이다. 유사한 스토리지 엔진이 Cassandra와 HBase에서 사용되며, 이 두 엔진은 모두 Google의 Bigtable 논문에서 영감을 얻었다. 또한 이 논문에서 SSTable과 memtable이라는 용어를 도입했다.

원래 SSTable 인덱싱 구조는 패트릭 오닐 등이 로그 구조 파일 시스템에 대한 이전 작업을 기반으로 하여 로그 구조 병합 트리(또는 LSM-Tree)라는 이름으로 불렀다.
정렬된 파일을 병합하고 압축하는 이 원리를 기반으로 하는 스토리지 엔진을 보통 LSM 스토리지 엔진이라고 일컫는다.

Elasticsearch와 Solr에서 사용하는 전체 텍스트 검색용 인덱싱 엔진인 Lucene도 용어 사전을 저장하는 데 비슷한 방법을 사용한다.
전체 텍스트 인덱스는 키-값 인덱스보다 훨씬 더 복잡하지만, 검색 쿼리에 단어가 주어지면 그 단어를 언급하는 모든 문서(웹 페이지, 제품 설명 등)를 찾는다는 비슷한 아이디어를 기반으로 한다.
이것은 키-값 구조로 구현되는데, 키는 단어(용어)이고 값은 해당 단어가 포함된 모든 문서의 ID 목록(게시 목록)이다. Lucene은 용어에서 게시글 목록으로의 매핑이 SSTable과 같은 정렬된 파일에 보관되며, 필요에 따라 백그라운드에서 병합된다.

성능 최적화

스토리지 엔진이 실제로 잘 작동하도록 하기 위해서는 많은 세부 사항이 필요하다. 예를 들어,
LSM 트리 알고리즘은 데이터베이스에 존재하지 않는 키를 조회할 때 속도가 느려질 수 있다.
멤테이블을 확인한 다음 세그먼트를 가장 오래된 것까지 거슬러 올라가야 키가 존재하지 않는지 확인할 수 있기 때문이다.

이러한 종류의 액세스를 어떻게 최적화할까?
이 경우, 스토리지 엔진은 종종 추가 블룸 필터를 사용한다.
블룸 필터는 집합의 내용을 근사화하기 위한 메모리 효율적인 데이터 구조이다.
키가 데이터베이스에 나타나지 않는지 여부를 알려주므로 존재하지 않는 키에 대한 불필요한 디스크 읽기를 줄일 수 있다.

또한, SSTable을 압축하고 병합하는 순서와 타이밍을 결정하는 다양한 전략이 있다.
가장 일반적인 옵션은 크기 계층 압축과 레벨 압축이다.
LevelDB와 RocksDB는 레벨 압축을 사용하고, HBase는 크기 계층을 사용하며, Cassandra는 이 두 가지를 모두 지원한다.

• 크기 계층 압축에서는 더 작고 새로운 SSTable이 더 오래되고 더 큰 SSTable에 연속적으로 병합된다
• 레벨 압축에서는 키 범위가 더 작은 SSTable로 분할되고 오래된 데이터는 별도의 “레벨”로 이동되므로 압축이 더 점진적으로 진행되고 디스크 공간을 덜 사용할 수 있다.