[250425] LevelDB SSTable

SSTable(Sorted String Table)은 LevelDB에서 디스크에 저장되는 기본 데이터 단위(파일 하나), MemTable의 키-값 쌍을 정렬된 상태로 저장함. SSTable은 불변(immutable) 파일로, 한 번 작성된 후에는 수정되지 않고, 새로운 데이터는 새로운 SSTable로 작성함. (LevelDB Table Format, 뭐 SSTable 의 일반적인 형식이라고 볼 수 있음)

주요 특징 정리:

• 키-값 쌍은 키 기준으로 정렬되어 저장함.
• 파일은 여러 블록으로 나뉘며, 데이터, 인덱스, 메타데이터를 포함함.
• Bloom 필터와 같은 메타데이터를 활용해 읽기 성능을 최적화함.
• 파일명은 고유한 6자리 숫자와 ".sst" 확장자로 구성됨.

SSTable은 LevelDB의 LSM Tree 구조에서 Level 0 이상의 데이터를 저장하며, 압축(compaction) 과정에서 상위 레벨로 이동하거나 병합됨. (구현체마다 다른 방식으로 최적화하는데 Level DB는 Leveling 이라는 방식을 쓰는듯?)

사실 공식문서만 봐도 쉽게 알 수 있음. 공식문서 맨 위에 있는 구조를 보자.

<beginning_of_file>
[data block 1]
[data block 2]
...
[data block N]
[meta block 1]
...
[meta block K]
[metaindex block]
[index block]
[Footer]        (fixed size; starts at file_size - sizeof(Footer))
<end_of_file>

SSTable은 여러 구성 요소로 나뉘어 있고, 각 요소는 특정 역할을 수행함. 아래 표는 SSTable의 구조를 요약한 것:

1. Memtable 순회
   • MemTable은 Skip List로 구현되어 키 기준으로 정렬된 상태임.
   • LevelDB는 MemTable을 순회하여 키-값 쌍을 순서대로 읽음.
2. 데이터 블록 생성
   • 키-값 쌍은 BlockBuilder를 통해 데이터 블록에 추가함.
   • 블록 크기가 4KB(기본값)에 도달하면, 블록은 체크섬과 압축 유형을 추가하여 SSTable 파일에 기록됨.
   • 새 블록이 시작되고, 이 과정은 모든 키-값 쌍이 기록될 때까지 반복됨.
3. 메타 블록 생성
   • 데이터 블록 생성 후, 메타 블록을 생성함.
   • 필터 블록과 통계 블록을 생성하여 메타 블록에 추가함.
4. 인덱스 블록 생성:
   • 각 데이터 블록에 대해 인덱스 블록에 항목이 추가됨.
   • 항목은 키 범위(이전 블록의 마지막 키와 다음 블록의 첫 키 사이)와 BlockHandle(오프셋, 크기)을 포함함.
5. 필터 블록 생성:
   • FilterPolicy가 지정된 경우, Bloom 필터가 생성되어 필터 메타 블록에 저장됨.
   • 필터는 2KB 단위로 키를 커버하며, 오프셋 배열과 함께 기록됨.
6. 메타인덱스 블록 생성:
   • 메타 블록(필터, 통계)의 이름과 BlockHandle이 메타인덱스 블록에 기록됨.
7. 푸터 작성:
   • 메타인덱스와 인덱스 블록의 BlockHandle, 패딩, 매직넘버가 푸터에 기록됨.
   • 푸터는 파일 끝에 고정 크기(40바이트)로 저장됨.
8. 파일명 지정:
   • SSTable 파일은 데이터베이스 디렉토리 내에 고유한 6자리 숫자와 ".sst" 확장자로 명명됨(예: 000001.sst).
   • 파일 번호는 TableFileName 함수에 의해 생성되며, 시퀀스 번호를 기반으로 증가함.

이 과정은 table_{builder.cc와} block_{builder.cc에서} 구현되고, SSTable은 Level 0에 저장됨.

• 형식: <six-digit-file-number>.sst
• 예시: 000001.sst, 000002.sst, 000003.sst
• 위치: 데이터베이스 디렉토리(예: /var/data/mydb/000001.sst)

파일 번호는 데이터베이스의 시퀀스 번호를 기반으로 증가하고, TableFileName 함수**에 의해 생성됨. 이 형식은 SSTable의 고유성을 보장하고, **MANIFEST 파일에서 각 SSTable의 레벨과 파일 번호를 추적함 (LevelDB Architecture).

다른 파일 유형도 데이터베이스 디렉토리에 존재하지만, SSTable은 ".sst" 확장자로 구분됨:

• MANIFEST: 데이터베이스 구조 변경 로그(예: MANIFEST-000001).
• CURRENT: 현재 MANIFEST 파일의 이름.
• LOG: Write-Ahead Log(예: 000001.log).

LevelDB에서 "복원(restore)"은 데이터베이스를 열 때 디스크에 저장된 상태를 재구성하는 과정을 의미함. LevelDB 는 데이터가 로그로 순차저장되어있음. 이 로그를 통해 데이터를 다시 복원해야 조회가 가능함.

이는 SSTable, MANIFEST, WAL을 활용하여 수행됨. 복원 과정은 다음과 같음:

1. CURRENT 파일 읽기
2. CURRENT 파일은 현재 MANIFEST 파일의 이름을 저장함. (예: MANIFEST-000001)
3. MANIFEST 파일 읽기
4. MANIFEST 파일은 데이터베이스 구조 변경 로그임.
5. 각 레벨에 속한 SSTable 목록, 파일 번호, 시퀀스 번호 등을 포함함.
6. LevelDB는 MANIFEST를 파싱하여 현재 버전(Version)을 재구성함. 이는 각 레벨(0~6)의 SSTable 목록을 포함함.
7. WAL 재생
8. Write-Ahead Log(WAL)이 존재하면, LevelDB는 이를 재생하여 MemTable(Skip List)을 재구성함.
9. WAL은 플러시되지 않은 쓰기 작업을 기록하며, log_reader.cc를 통해 읽힘.
10. 재생 후, MemTable은 최신 키-값 쌍을 포함하며, 이후 플러시될 수 있음.
11. SSTable 메타데이터 로드
12. LevelDB는 각 SSTable의 푸터를 읽어 메타인덱스와 인덱스 블록의 위치를 확인함.
13. 인덱스 블록과 필터 블록(Bloom 필터)은 메모리에 로드되거나 캐싱되어 빠른 접근을 지원함.
14. 데이터 블록은 디스크에 남아 있고, 필요 시 table_reader.cc를 통해 읽힘.
15. 캐싱 및 최적화
16. LevelDB는 TableCache를 사용해 자주 접근하는 SSTable의 메타데이터를 캐싱함.
17. ShardedLRUCache(16개 샤드, LRU 알고리즘)를 활용해 캐시 효율성을 높임.
18. 읽기 작업 준비:
19. 복원 후, LevelDB는 MemTable, 불변 MemTable, 그리고 SSTable을 순차적으로 확인하여 읽기 요청을 처리함.
20. Bloom 필터는 키가 SSTable에 없는 경우 디스크 읽기를 건너뛰어 성능을 향상시킴.

이 과정은 db_impl.cc와 version_set.cc에서 구현되고, 데이터베이스 상태를 빠르게 복원하여 읽기/쓰기 작업을 지원함.

복원을 완료하면 SSTable 파일을 읽어 데이터를 조회함.

1. 푸터 읽기:
   • 파일 끝에서 40바이트 푸터를 읽어 메타인덱스와 인덱스 블록의 BlockHandle을 확인함.
2. 인덱스 블록 로드:
   • 인덱스 블록을 읽어 이진 탐색으로 목표 키가 포함될 가능성이 있는 데이터 블록을 식별함.
3. 필터 블록 확인:
   • Bloom 필터를 통해 키가 SSTable에 존재할 가능성을 확인함.
4. 데이터 블록 읽기:
   • 식별된 데이터 블록을 읽어 목표 키-값 쌍을 검색함.
   • 블록이 압축된 경우, block.cc를 통해 압축 해제됨.
   • 키가 없으면 디스크 읽기를 건너뜀.

데이터 블록 읽기: 식별된 데이터 블록을 읽어 목표 키-값 쌍을 검색함. 블록이 압축된 경우, block.cc를 통해 압축 해제됨.

이 과정은 table_reader.cc와 block.cc에서 구현되고, 캐싱과 Bloom 필터를 활용해 효율성을 극대화함.

• https://github.com/google/leveldb/blob/main/doc/table_format.md
• https://chenju2k6.github.io/blog/2018/11/leveldb