SSTable 기반 저장 엔진 구현 및 원리 설명

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 분석

대상자

• 데이터베이스 내부 구조 이해를 원하는 개발자
• LSM-Tree, SSTable, Bloom Filter 등 고급 저장 엔진 기술을 학습하고자 하는 중급 이상 개발자
• Python 기반 저장 엔진 구현에 관심 있는 학습자

핵심 요약

• SSTable는 정렬된 키-값 쌍을 디스크에 저장하는 불변 파일 형식으로, 범위 쿼리와 빠른 읽기를 가능하게 함.
• LSM-Tree의 핵심 구성 요소로, 메모리에 있는 memtable과 디스크에 저장된 SSTable을 조합하여 고성능 저장 엔진 구현 가능.
• Bloom Filter와 희소 인덱스를 통해 불필요한 디스크 접근 최소화 및 읽기 최적화 가능.

섹션별 세부 요약

1. SSTable 및 LSM-Tree 개요

• SSTable는 정렬된 키-값 쌍을 저장하는 불변 파일 형식으로, 대규모 데이터 처리에 최적화됨.
• LSM-Tree는 메모리에 있는 memtable과 디스크에 저장된 SSTable을 결합하여 빠른 쓰기와 효율적인 읽기를 지원.
• SSTable은 LevelDB, RocksDB, Cassandra 등 현대 데이터베이스의 핵심 구성 요소.

2. 메모리 구조 (Memtable)

• Memtable은 정렬된 리스트로, bisect 모듈을 활용하여 빠른 삽입 및 조회 가능.
• Memtable이 너무 커지면 디스크에 새로운 SSTable로 플러시됨.
• Python에서 Memtable 클래스를 통해 메모리 기반 키-값 저장 구현.

3. SSTable 작성 및 인덱싱

• SSTableWriter는 정렬된 키-값 쌍을 디스크에 저장하며, 희소 인덱스와 Bloom Filter를 생성.
• 희소 인덱스는 N번째 키와 파일 오프셋을 저장하여 빠른 위치 이동 가능.
• Bloom Filter는 키가 확실히 존재하지 않을 때 디스크 읽기를 스킵 가능.

4. SSTable 읽기 및 검색

• SSTableReader는 메모리의 memtable을 먼저 체크한 후, Bloom Filter로 SSTable 검색.
• 희소 인덱스를 활용하여 SSTable 파일 내 해당 위치로 이동 후 스캔.
• SSTable 클래스는 memtable과 SSTable 파일을 통합 관리.

5. 서버 및 테스트 환경

• UNIX 소켓 서버(sstable_server.py)를 통해 set/get 연산 제공.
• CLI 클라이언트(main.py)로 서버와 상호작용 가능.
• stress_test.py 스크립트로 1000개의 랜덤 키-값 쌍 삽입 및 읽기 테스트 수행.

6. 성능 및 확장성 고려사항

• LSM-Tree는 시퀀셜 쓰기 최적화로 높은 쓰기 성능 제공.
• 희소 인덱스와 Bloom Filter로 데이터 확장 시 읽기 성능 유지 가능.
• Compaction, 범위 쿼리, 압축 등 추가 기능 확장 가능.

결론

• SSTable 기반 저장 엔진 구현은 현대 데이터베이스의 내부 구조 이해에 유용.
• Bloom Filter와 희소 인덱스를 활용한 읽기 최적화가 핵심.
• Python으로 구현한 예제를 기반으로 자체 저장 엔진 개발 가능.