DB

LSM Tree 란?

peanutwalnut 2025. 1. 20. 21:48

Log-Structured Merge Tree 의 줄임말이다.

대규모 쓰기 작업을 효율적으로 처리하기 위해 고안된 데이터 구조로, 주로 NoSQL DB(예: Cassandra, HBase, LevelDB, RocksDB 등)나 검색 엔진(예: Lucene)에서 스토리지 엔진으로 활용됩니다.

 

일반적인 B-Tree 기반 스토리지 엔진과 달리, 쓰기 작업을 메모리에 먼저 로그 구조 형태로 누적(버퍼링)한 뒤, 주기적으로 디스크에 순차적으로 반영(머지)함으로써 랜덤 쓰기를 순차 쓰기로 전환하는 것이 핵심 아이디어입니다.

 

1. LSM Tree의 기본 개념

  1. 쓰기(Write) 최적화
    • 전통적인 B-Tree는 노드 안에서 데이터를 삽입/삭제할 때 랜덤 접근이 자주 발생하며, 특히 디스크 기반 환경에서 성능 저하가 발생하기 쉽습니다.
    • LSM Tree는 쓰기 작업을 디스크에 직접 반영하지 않고, 메모리(Write Buffer)에 로그 구조로 쌓은 뒤, 일정 조건(버퍼가 가득 차거나 일정 시간이 지났을 때 등)이 되면 배경 작업(Compaction, Flush)을 통해 디스크로 내리는 구조입니다.
  2. 메모리에 유지되는 구조(MemTable, C0)
    • 쓰기는 먼저 메모리에 있는 **MemTable(또는 C0 컴포넌트)**에 기록됩니다.
    • MemTable이 가득 차면(또는 조건 충족 시) 해당 데이터를 정렬한 뒤 SSTable(또는 C1, C2 컴포넌트) 형태로 디스크에 순차 기록합니다.
  3. 디스크에 쌓이는 SSTable(또는 Sorted Files)
    • 디스크에는 이미 정렬된 파일(예: SSTable)이 여러 개 쌓이게 되는데, 새로운 SSTable이 생길 때마다 **오래된 SSTable들과 병합(Compaction)**하여, 중복 데이터나 이미 삭제된 데이터를 제거하며 더 큰 SSTable로 재구성할 수 있습니다.
  4. 읽기(Read) 처리
    • 데이터를 조회할 때는, 최신 데이터를 보유하고 있을 가능성이 높은 **메모리(MemTable)**를 먼저 확인하고,
    • 메모리에 없으면, 디스크에 있는 여러 SSTable을 순서대로(또는 효율적인 인덱스 구조를 통해) 조회합니다.
    • Compaction이 이루어지지 않아 중복된 키가 여러 SSTable에 걸쳐 있을 수도 있으므로, 최신 버전을 찾기 위해 합치는 과정이 필요할 수 있습니다.
  5. Compaction(병합) 작업
    • 여러 SSTable을 주기적으로 병합하여, 중복 데이터 정리, 삭제 처리된 키 제거, 파일 수 감소 등을 수행합니다.
    • Compaction은 시스템 리소스를 많이 소모하기 때문에, 적절한 스케줄링/알고리즘 설계가 중요합니다.

 

 

2. LSM Tree의 장단점

장점

  1. 높은 쓰기 성능
    • 쓰기를 주로 메모리 버퍼에 기록하고, 디스크에는 순차 쓰기를 하므로, 랜덤 쓰기가 많은 워크로드에 유리합니다.
  2. 압축/합치기(Compaction) 과정에서 최적화 가능
    • 오래된 데이터, 삭제된 키 등을 정리함으로써 스토리지 사용량을 효율화할 수 있습니다.
  3. 확장성(Scalability)
    • 대규모 분산 DB에서 수평 확장 시에도, 각 노드가 LSM Tree 기반으로 쓰기를 처리하기 때문에 쓰기 병목이 비교적 적습니다.

단점

  1. 읽기 지연 가능성
    • 최신 데이터를 찾기 위해 여러 SSTable을 순회할 수도 있으므로, 읽기 성능이 B-Tree 구조보다 떨어질 수 있습니다.
    • 이를 보완하기 위해 Bloom Filter 등으로 “해당 SSTable에 특정 키가 있는지”를 빠르게 확인하거나, 인덱스를 활용하는 방식을 많이 씁니다.
  2. Compaction 부담
    • 데이터 양이 많아질수록 Compaction 작업 비용이 커져서, 쓰기 성능에 영향을 미칠 수 있습니다.
    • 시스템 리소스를 계획적으로 배분하고, Compaction 스케줄과 정책을 최적화해야 합니다.
  3. 메모리 사용량
    • 메모리에 MemTable 버퍼를 유지해야 하므로, 충분한 메모리가 필요합니다.

 

3. 대표적인 LSM Tree 기반 스토리지/DB 예시

  1. Apache Cassandra
    • LSM Tree 구조를 사용하는 대표적인 NoSQL DB.
    • 멀티 리전, 멀티 노드 분산 환경에서의 높은 쓰기 성능을 위해 채택.
  2. Apache HBase
    • Hadoop 생태계의 컬럼 지향 분산 DB.
    • 구글 Bigtable 논문 기반으로 LSM Tree에 해당하는 MemStore + HFile 구조를 사용.
  3. LevelDB, RocksDB
    • 구글 LevelDB, 페이스북 RocksDB 등은 단일 노드 스토리지 엔진으로 LSM Tree 기반.
    • MySQL 등 전통적인 DB에서도 RocksDB를 플러그인 스토리지 엔진으로 사용 가능(예: MyRocks).
  4. Lucene/Solr/Elasticsearch
    • 검색 엔진 내부도 비슷한 원리(인덱스 세그먼트 생성 후 병합)로 동작하므로, LSM Tree와 유사한 구조를 갖습니다.