[컴퓨터시스템응용기술사 제140회 2교시 2번]

답안 구조

1. 개요
2. LSM-Tree의 개념 및 구조
3. LSM-Tree의 동작 원리 및 특징
4. Bloom Filter의 개념 및 동작 원리
5. Bloom Filter의 특징 및 한계
6. LSM-Tree와 Bloom Filter의 연동
7. 결론

용어 정의

LSM-Tree

디스크 쓰기 성능 최적화를 위한 데이터 구조로, 메모리 컴포넌트와 디스크 컴포넌트를 계층적으로 관리하며 병합 연산을 통해 일관성을 유지한다.

Bloom Filter

특정 요소의 집합 포함 여부를 확률적으로 고속 검사하는 공간 효율적인 자료구조. 거짓 긍정(False Positive)은 발생 가능하나 거짓 부정(False Negative)은 없다.

False Positive (거짓 긍정)

Bloom Filter에서 실제 존재하지 않는 데이터를 존재한다고 판단하는 오류로, 확률적 특성상 발생 가능하나 허용 가능한 수준으로 제어된다.

SSTable (Sorted String Table)

LSM-Tree의 디스크 컴포넌트에서 데이터를 정렬된 형태로 저장하는 불변(immutable) 파일. 읽기 효율성을 높인다.

핵심 내용