SSTable

SSTable 은 고쳐 쓰지 않는 저장 파일입니다. 값을 바꾸려면 새 파일을 하나 더 씁니다. 키 하나로 값을 찾는 일과 키 범위를 훑는 일을 합니다. 파일 끝에는 어느 블록에 무엇이 있는지 적어 둔 인덱스가 붙습니다.

상세

SSTable 은 줄임말입니다. 무엇을 줄인 것인지는 하나로 정해져 있지 않습니다. 이 이름이 실린 원 논문은 풀어 적지 않고, 뒤따른 구현들이 각자 다르게 풉니다. Cassandra 문서는 Sorted String Table(정렬된 문자열 테이블)로 적습니다. RocksDB 용어집은 앞의 세 글자를 Sorted Sequence Table(정렬된 시퀀스 테이블)로 적습니다. 어느 쪽으로 읽든 이 파일이 키 순서로 정렬돼 있다는 뜻은 같습니다.

SSTable 은 지속적이고 정렬되어 있으며 변경되지 않는 맵입니다. 키에서 값으로 가는 맵이고, 키와 값 둘 다 임의의 바이트 문자열입니다. 제공하는 연산은 둘입니다. 지정한 키에 딸린 값을 찾는 연산, 그리고 지정한 키 범위 안의 키·값 쌍을 전부 순회하는 연산입니다.

이름순으로 찍어 낸 종이 명부를 떠올리면 가깝습니다. 한 사람을 짚어 찾는 것도, ㄱ 부터 ㄷ 까지를 죽 훑는 것도 됩니다. 대신 한 줄을 고치려면 명부를 통째로 새로 찍어야 합니다.

파일 안쪽은 블록의 나열입니다. 블록 하나는 보통 64KB 이고 이 크기는 설정할 수 있습니다. 어느 블록으로 가야 하는지는 블록 인덱스가 알려줍니다. 이 인덱스는 SSTable 의 끝에 저장됩니다. 그리고 SSTable 을 열 때 메모리로 올라옵니다. 그래서 조회 한 번이 디스크 탐색 한 번으로 끝납니다. 메모리에 있는 인덱스에서 이진 탐색으로 알맞은 블록을 고르고, 그 블록만 디스크에서 읽습니다. SSTable 을 통째로 메모리에 올려 두는 선택지도 있습니다. 그러면 조회와 스캔이 디스크를 건드리지 않습니다.

변경되지 않는다는 조건이 이 자료구조의 중심입니다. 값을 고치거나 지우는 일이 이미 쓰인 파일을 다시 쓰지 않습니다. 대신 새 SSTable 이 쌓입니다. 읽기는 그래서 여러 SSTable 을 겹쳐 본 병합 뷰에서 이뤄집니다. 메모리 안의 정렬된 버퍼인 memtable 과 SSTable 들이 모두 사전순으로 정렬된 자료구조라, 병합 뷰를 만드는 일이 순서대로 훑기로 끝납니다.

쌓이는 파일 수는 컴팩션이 되돌립니다. 컴팩션은 쌓인 SSTable 을 읽어 새 SSTable 로 합치고 입력이 된 것들은 버리는 백그라운드 작업입니다. 종류가 셋으로 갈립니다.

메모리 버퍼가 임계치에 닿으면 그 버퍼를 얼리고 새 버퍼를 하나 만듭니다. 얼린 버퍼는 SSTable 하나로 바뀌어 디스크에 쓰입니다. 이것이 마이너 컴팩션입니다. 이 일이 노리는 것은 둘입니다. 서버가 쓰는 메모리를 줄이는 것, 그리고 이 서버가 죽었을 때 되살리느라 커밋 로그에서 읽어야 하는 데이터의 양을 줄이는 것입니다. 커밋 로그는 갱신을 다시 적용할 수 있게 순서대로 적어 두는 기록입니다. 컴팩션이 도는 동안에도 들어오는 읽기와 쓰기는 계속 처리됩니다.

마이너 컴팩션은 돌 때마다 새 SSTable 을 만듭니다. 이대로 두면 읽기가 몇 개인지 정해지지 않은 SSTable 에서 갱신을 병합해야 할 수 있습니다. 그래서 백그라운드에서 머징 컴팩션을 주기적으로 돌려 파일 수에 상한을 둡니다. 머징 컴팩션은 SSTable 몇 개와 메모리 버퍼를 읽어 새 SSTable 하나를 쓰고, 입력이 된 것들은 일이 끝나는 대로 버립니다.

메이저가 아닌 컴팩션이 낸 SSTable 에는 삭제 항목이 들어 있을 수 있습니다. 이 항목은 아직 살아 있는 옛 SSTable 안의 지워진 데이터를 가리는 표식입니다. 모든 SSTable 을 정확히 하나로 다시 쓰는 머징 컴팩션은 메이저 컴팩션이라고 부릅니다. 그 결과물에는 삭제 정보도, 지워진 데이터도 남지 않습니다.

셋이 이어지는 경로는 이렇습니다.

flowchart TD
    A["메모리 버퍼가 임계치에 닿음"] -->|마이너 컴팩션| B["버퍼를 얼려 SSTable 하나로 내려씀"]
    B --> C["SSTable 이 쌓임"]
    C -->|머징 컴팩션| D["SSTable 몇 개와 메모리 버퍼를 읽어 새 SSTable 하나로"]
    D --> E["입력이 된 SSTable 과 버퍼를 버림"]
    E --> C
    C -->|메이저 컴팩션| F["모든 SSTable 을 정확히 하나로 다시 씀"]
    F --> G["삭제 정보도 지워진 데이터도 남지 않음"]

복잡도

이 자료구조의 비용은 디스크를 몇 번 건드리는지가 지배합니다. 조회는 파일을 연 뒤라면 디스크 읽기 한 번으로 끝나고, 쓰기는 파일을 앞에서 뒤로 한 번 적어 내려가는 것으로 끝납니다. 메모리 안의 비교 몇십 번과 디스크 읽기 한 번은 값의 자릿수가 다릅니다. 그래서 아래 표는 O 표기보다 디스크 읽기 횟수를 먼저 읽어야 합니다.

세는 단위는 둘입니다. 조회와 순회와 공간은 파일이 담은 키의 수가 아니라 블록의 수로 셉니다. 아래에서는 그 수를 B 라고 적습니다. 인덱스에서 하는 이진 탐색의 대상이 블록이고, 디스크에서 읽어 오는 단위도 블록이기 때문입니다. 쓰기만 파일이 담은 항목의 수로 셉니다. 그 수는 N 이라고 적습니다. 쓰기는 블록을 고르는 일이 아니라 들어온 항목을 처음부터 끝까지 한 번씩 적어 내려가는 일이기 때문입니다.

조회 값은 인덱스를 몇 겹으로 두느냐에 따라 갈립니다. 그래서 아래 표는 두 경로를 따로 셉니다.

인덱스를 두 겹으로 두는 방식은 이렇습니다. 인덱스 항목을 일정 간격으로 다시 뽑아 표본을 만들어 둡니다. 메모리에 상주시키는 것은 인덱스 전체가 아니라 그 표본입니다. 상주시킬 메모리는 줄어듭니다. 대신 평상시의 디스크 읽기가 한 계단 늘어납니다. 두 겹 경로의 평균이 한 겹 경로의 최악과 같은 2회인 것이 그래서입니다. 표본을 몇 개마다 뽑을지는 구현이 정합니다. 실제 값 하나는 아래 예시에 있습니다.

최악이 오는 조건은 두 경로에서 같습니다. 상주해야 할 것이 아직 메모리에 없을 때입니다. 한 겹이면 인덱스가, 두 겹이면 표본이 그것입니다. 읽어 들이는 시점은 SSTable 을 여는 때라, 방금 열린 파일을 처음 조회하는 순간이 그 자리입니다. 한 번 올라온 뒤로는 같은 파일의 조회가 모두 평균 쪽 값을 씁니다.

블록 크기가 이 값들을 흔듭니다. 블록을 작게 잡으면 한 번에 읽어 오는 양이 줄고, 대신 블록 수가 늘어 인덱스 항목도 늘어납니다. 블록을 크게 잡으면 반대입니다. 압축도 같은 자리에 있습니다. 블록마다 따로 압축하면 공간을 조금 잃습니다. 그 대신 파일 전체를 풀지 않고 SSTable 의 작은 조각만 읽을 수 있습니다.

여러 SSTable 이 쌓였을 때 그것들을 병합하는 비용은 이 표의 값이 아닙니다. 그것은 SSTable 을 쌓아 쓰는 저장 구조인 LSM(Log Structured Merge) 트리 쪽의 값입니다. 한 번 쓴 데이터를 컴팩션이 여러 번 다시 쓰는 쓰기 증폭도 그 자리에서 셉니다.

형태

파일은 앞에서부터 데이터 블록, 메타 블록, 메타인덱스 블록, 인덱스 블록, 풋터 순으로 놓입니다. 풋터는 파일 맨 끝에 고정 길이로 앉아 있어서, 파일 크기에서 풋터 길이를 뺀 자리부터 읽으면 바로 잡힙니다. 위가 파일 앞, 아래가 파일 끝입니다.

block-beta
columns 1
  d1["데이터 블록 1"]
  d2["데이터 블록 2"]
  dn["데이터 블록 N"]
  m1["메타 블록 1"]
  mk["메타 블록 K"]
  mi["메타인덱스 블록"]
  ix["인덱스 블록"]
  ft["풋터 · 고정 길이"]

키·값 쌍은 정렬된 순서로 저장되어 데이터 블록들로 나뉩니다. 그 블록들이 파일 앞쪽에 하나씩 이어 붙습니다. 각 데이터 블록은 따로 압축할 수 있습니다.

파일 안의 위치는 BlockHandle 이라는 내부 포인터가 가리킵니다. 담는 것은 둘입니다.

offset:   varint64
size:     varint64

인덱스 블록에는 데이터 블록마다 항목이 하나씩 들어갑니다. 항목의 키는 그 데이터 블록의 마지막 키보다 크거나 같고 다음 데이터 블록의 첫 키보다는 앞서는 문자열입니다. 값은 그 데이터 블록의 BlockHandle 입니다. 이 인덱스가 파일 끝에 있고, SSTable 을 열 때 메모리로 올라옵니다.

파일 맨 끝의 풋터는 길이가 고정입니다. 담는 것은 메타인덱스 블록의 핸들, 인덱스 블록의 핸들, 길이를 맞추기 위한 0 바이트 패딩, 그리고 매직 넘버입니다. 패딩까지 합해 핸들 두 개의 자리가 40 바이트로 고정됩니다.

metaindex_handle: char[p];      // 메타인덱스 블록의 핸들
index_handle:     char[q];      // 인덱스 블록의 핸들
padding:          char[40-p-q]; // 길이를 고정하려고 채우는 0 바이트
magic:            fixed64;      // 이 파일이 무엇인지 알리는 값

메타 블록은 고르는 자리입니다. 필터 정책을 주고 데이터베이스를 열면 필터 블록이 테이블마다 저장됩니다. 그 위치는 메타인덱스 블록의 항목이 알려줍니다. 항목의 키는 filter. 뒤에 필터 정책의 이름을 붙인 문자열이고, 값은 필터 블록의 BlockHandle 입니다. RocksDB 의 같은 자리에는 필터 블록·인덱스 블록·압축 사전 블록·범위 삭제 블록·속성 블록이 이름을 달고 들어갑니다.

한 SSTable 이 언제나 파일 하나인 것은 아닙니다. Cassandra 는 데이터·인덱스·필터를 각각 다른 컴포넌트 파일로 나눠 담습니다. Data.db 안에서 행은 파티션 단위로 묶입니다. 파티션은 파티션 키가 같은 행을 한데 모은 무리입니다. 파티션끼리는 토큰 순서로 놓입니다. 토큰 순서는 기본 설정에서 파티션 키를 해시한 값의 순서입니다. 파티션 안의 행은 클러스터링 키 순서로 놓입니다. 클러스터링 키는 파티션 안에서 행의 순서를 정하는 키입니다.

예시

LevelDB

블록 크기 기본값은 소스의 옵션 정의에 이렇게 박혀 있습니다.

size_t block_size = 4 * 1024;

블록 하나에 담는 사용자 데이터의 대략적인 크기입니다. 여기 적는 크기는 압축하기 전 데이터 기준입니다. 압축을 켜면 디스크에서 실제로 읽는 단위는 이보다 작을 수 있습니다. 이 값은 도는 중에도 바꿀 수 있습니다. 같은 자리의 값이 Bigtable 논문에서는 보통 64KB 였습니다.

풋터 끝에는 이 파일이 무엇인지 알리는 고정 값이 박힙니다.

magic: fixed64;   // == 0xdb4775248b80fb57 (little-endian)

정렬된 테이블 파일의 확장자는 .ldb 입니다. 로그 파일은 최근 갱신을 순서대로 덧붙여 적는 파일입니다. 이 파일이 정해진 크기에 닿으면 그 내용이 정렬된 테이블로 바뀌어 레벨 0 에 놓입니다. 정렬된 테이블은 여러 레벨로 조직되고, 레벨 0 은 로그 파일에서 갓 바뀐 테이블이 놓이는 가장 젊은 레벨입니다. 로그 파일 크기의 기본값은 대략 4MB 입니다.

RocksDB

BlockBasedTable 이 기본 SST(Sorted Sequence Table) 테이블 포맷입니다. 이 포맷 문서는 LevelDB 의 테이블 포맷 문서에서 갈라져 나왔습니다. 풋터의 자리 배치는 같고, 매직 넘버만 다릅니다.

magic: fixed64;   // 0x88e241b785f4cff7 (little-endian)

Cassandra

여기서는 SSTable 하나가 파일 하나가 아닙니다. 컴포넌트 파일 여러 개가 한 벌을 이룹니다.

Data.db  Index.db  Summary.db  Filter.db  CompressionInfo.db  Statistics.db  TOC.txt

Data.db 가 실제 행의 내용입니다. Index.db 는 파티션 키에서 Data.db 안의 위치로 가는 인덱스입니다. 넓은 파티션이면 파티션 안의 행까지 가는 인덱스도 함께 들어갑니다. Summary.db 는 Index.db 항목을 기본값으로 128 개마다 하나씩 뽑아 둔 표본입니다. Filter.db 는 이 SSTable 이 담은 파티션 키의 블룸필터입니다. CompressionInfo.db 는 Data.db 안 압축 청크의 오프셋과 길이를 적어 둔 메타데이터입니다. Statistics.db 는 타임스탬프, 지웠다는 표식인 톰스톤, 클러스터링 키, 컴팩션·복구·압축·TTL(Time To Live) 같은 이 SSTable 에 관한 메타데이터를 담습니다. TOC.txt 는 이 한 벌에 어떤 컴포넌트 파일이 있는지 적은 평문 목록입니다.

사용처

Bigtable — 구글이 내부에서 Bigtable 의 데이터를 저장하는 데 SSTable 파일 형식을 씁니다. 데이터는 타블릿 단위로 나뉘어 서비스됩니다. 타블릿은 SSTable 여러 개로 이뤄지고 서버 한 대가 맡아 읽고 쓰는 데이터 덩어리입니다. 타블릿의 지속 상태가 SSTable 의 시퀀스로 저장되고, 최근에 커밋된 갱신만 메모리의 정렬된 버퍼에 남습니다. 읽기는 그 버퍼와 SSTable 시퀀스의 병합 뷰에서 수행됩니다. 둘 다 사전순으로 정렬된 자료구조라 병합 뷰를 만드는 값이 싸다는 것이 이 구조를 고른 이유입니다. 컬럼을 묶은 단위인 컬럼 패밀리 여럿을 다시 묶은 것이 로컬리티 그룹인데, 로컬리티 그룹마다 SSTable 이 따로 만들어져서 같이 안 읽는 컬럼 패밀리를 갈라 두면 읽을 때 건드리는 파일이 줄어듭니다.

LevelDB — 로그 파일이 정해진 크기를 넘으면 그 내용을 정렬된 테이블로 바꿔 레벨 0 에 놓습니다. 확장자는 .ldb 입니다. 항목 하나는 그 키의 값이거나 그 키의 삭제 표식입니다. 삭제 표식을 남기는 이유는 더 오래된 정렬된 테이블에 남아 있는 낡은 값을 가리기 위해서입니다.

RocksDB — 기본 SST 테이블 포맷이 BlockBasedTable 입니다. 이 프로젝트의 용어집은 SST 를 Sorted Sequence Table 의 줄임말로 적습니다. 키가 대체로 정렬된 순서로 놓여서 키 하나나 순회 위치를 이진 탐색으로 짚을 수 있다는 것이 이 파일의 성질입니다. 컴팩션은 SST 파일 몇 개를 다른 SST 파일들로 병합하는 백그라운드 작업입니다.

Cassandra — 저장 엔진이 메모리의 memtable 과 디스크의 변경되지 않는 SSTable 로 이뤄집니다. 이 프로젝트의 문서는 SSTable 을 Sorted String Table 의 줄임말로 적습니다. 데이터를 정렬해 저장하는 이유로 컴팩션 때의 병합 정렬을 듭니다. SSTable 은 테이블마다 유지되고, memtable 이 디스크로 내려간 뒤로는 다시 쓰이지 않습니다. 그래서 파티션 하나가 보통 여러 SSTable 파일에 걸쳐 저장됩니다.

관련 항목

SSTable 을 이루는 구성 요소

인덱스 · 이진 탐색 · 블룸 필터

SSTable 이 거치는 처리 단계

memtable · 커밋 로그 · 컴팩션

SSTable 이 담아 나르는 메타데이터

TTL · 톰스톤 · 타임스탬프 · 클러스터링 키

SSTable 이 속하는 상위 구조

LSM 트리 · 타블릿 · 로컬리티 그룹 · GFS(Google File System, 구글 파일 시스템)

SSTable 을 실제로 구현·채택한 제품

Bigtable · LevelDB · RocksDB · Cassandra · HBase