SSTable (Sorted String Table)

SSTable (Sorted String Table)

키-값 쌍이 키 순서대로 정렬되어 저장된 불변(Immutable) 디스크 파일로, LSM-Tree의 디스크 계층을 구성하는 핵심 자료구조

특징: 정렬된 불변 파일, 순차 읽기/쓰기 최적화, 병합(Merge) 효율적, 한 번 쓰면 수정 불가

구성요소

• •Data Block: 정렬된 키-값 쌍 저장, 압축 가능(Snappy, LZ4, Zstd)
• •Index Block: 각 Data Block의 첫 키와 오프셋 매핑, 이진 탐색으로 블록 위치 결정
• •Bloom Filter Block: 각 SSTable에 포함된 키의 멤버십 테스트, 불필요한 디스크 읽기 방지
• •Meta Block: 통계, 압축 정보, 필터 정보 등 메타데이터
• •Footer: Index Block과 Meta Block의 오프셋 저장

불변성(Immutability): 생성 후 수정/삭제 불가 → 동시 읽기 안전(락 불필요), 캐싱 용이, 스냅샷 지원

병합(Compaction)

• •여러 SSTable을 병합하여 중복 키 제거, 삭제 마커(Tombstone) 적용, 새 SSTable 생성
• •정렬된 파일 간 머지소트: O(N) 순차 읽기/쓰기 → I/O 효율적
• •Compaction 전략: Leveled(레벨별 크기 제한, 읽기 최적화), Size-Tiered(크기별 병합, 쓰기 최적화)

Bloom Filter 연계: 읽기 시 SSTable에 키가 존재하는지 Bloom Filter로 사전 확인 → 없으면 디스크 접근 생략 → 읽기 증폭 감소

읽기 과정: MemTable 검색 → L0 SSTable(최신) → L1 → L2 → ... 순서, 각 SSTable에서 Bloom Filter 확인 → Index Block 이진 탐색 → Data Block 접근

비교

적용사례: LevelDB, RocksDB, Cassandra, HBase, Google Bigtable

연관: LSM-Tree, Compaction, Bloom Filter, MemTable, WAL