46. LSM 트리 (Log-Structured Merge-Tree)

⚠️ 이 문서는 초당 수십만 건의 데이터가 쏟아지는 빅데이터/NoSQL 환경(Cassandra, RocksDB, HBase 등)에서, 디스크의 물리적 한계인 '랜덤 쓰기(Random Write)' 병목을 우회하여 극강의 쓰기 속도를 달성하기 위한 스토리지 엔진 자료구조인 **LSM 트리(Log-Structured Merge-Tree)**를 다룹니다.

핵심 인사이트 (3줄 요약)

  1. 본질: 기존 B-Tree가 디스크 상의 데이터 위치를 찾아가 조금씩 덮어쓰는(Random Write) 방식이라면, LSM 트리는 모든 새 데이터를 일단 메모리에 모아두었다가 디스크에 로그 파일처럼 일렬로 쭉 이어 쓰는(Sequential Write) 방식이다.
  2. 가치: 디스크 헤드가 데이터를 저장할 위치를 찾느라 윙윙거리며 움직이는 시간(Seek Time)을 완전히 제거하여, 하드디스크나 SSD 환경에서 기존 RDBMS 대비 쓰기 성능을 수십 배 이상 극대화한다.
  3. 기술 체계: 메모리에 임시 저장하는 멤테이블(MemTable), 디스크에 순차 저장되는 불변 파일인 SS테이블(SSTable), 그리고 오래된 디스크 파일들을 주기적으로 합쳐서 정리하는 컴팩션(Compaction)이라는 3단계 구조로 작동한다.

Ⅰ. 쓰기 병목의 근원: B-Tree와 랜덤 쓰기의 한계

수십 년간 RDBMS를 지배해 온 B-Tree는 '읽기'에는 좋지만, 엄청난 속도로 쏟아지는 '쓰기'에는 쥐약이다.

  1. B-Tree의 랜덤 쓰기 (In-place Update):
    • B-Tree에서 데이터 '50번'을 새로 저장하거나 수정하려면, 디스크에 있는 트리의 루트부터 나뭇가지를 따라 내려가 정확한 블록 위치를 찾아 덮어써야 한다. (디스크 헤드가 이리저리 튀어 다님)
    • 데이터가 쌓이고 트리가 커지면, 노드 분할(Split)까지 일어나 디스크 쓰기 부하가 기하급수적으로 증가한다.
  2. 디스크의 물리적 특성:
    • 하드디스크(HDD)는 물론이고 SSD조차도 '여기저기 찔끔찔끔 쓰는 것(랜덤 쓰기)'보다 '한 군데에 모아서 쭉 이어서 쓰는 것(순차 쓰기)'이 수백 배 이상 빠르다. LSM 트리는 이 특성에 착안했다.

📢 섹션 요약 비유: B-Tree가 도서관 사서가 책이 반납될 때마다 서가(디스크)를 이리저리 돌아다니며 '원래 있던 분류 위치'에 정확히 꽂아 넣는 방식이라면, 너무 바빠서 책이 수북이 쏟아질 때 쓰기엔 너무 느린 방식입니다.

Ⅱ. LSM 트리의 3단계 구조: MemTable과 SSTable

LSM 트리는 모든 쓰기를 일단 '메모리'와 '순차 로그'로 받아낸다.

  1. Write-Ahead Log (WAL)와 멤테이블 (MemTable):
    • 데이터가 들어오면 만약을 대비해 디스크에 순차적(Append-only)으로 간단한 로그(WAL)만 남기고, 실제 데이터는 메모리에 있는 멤테이블(주로 Red-Black Tree 등)에 정렬된 상태로 차곡차곡 쌓아둔다. (디스크 탐색 없음, 초고속)
  2. 플러시 (Flush)와 SS테이블 (SSTable):
    • 멤테이블이 꽉 차면(예: 64MB), 이 정렬된 데이터 덩어리를 디스크로 한 번에 쭉 밀어낸다(순차 쓰기). 이렇게 저장된 디스크 파일을 **SS테이블(Sorted String Table)**이라고 부른다.
    • ┌─────────────────────────────────────────────────────────┐ │ [초고속 유입] ---> [메모리: 멤테이블 (정렬)] │ │ ↓ (꽉 차면 디스크로 순차 쓰기) │ │ [디스크: SS테이블 1 (불변)] [SS테이블 2] [SS테이블 3] ... │ └─────────────────────────────────────────────────────────┘
  3. 불변성 (Immutability):
    • 디스크에 쓰인 SS테이블은 절대 수정되지 않는다(불변). 만약 데이터를 '수정'하거나 '삭제'하더라도, 해당 내용을 지우는 게 아니라 "A 데이터는 지워짐(Tombstone)"이라는 새 기록을 또 멤테이블에 쓸 뿐이다.

📢 섹션 요약 비유: 반납된 책(데이터)을 일일이 서가에 꽂지 않고, 일단 데스크 옆 빈 책상(멤테이블)에 번호순으로 쌓아둡니다. 책상이 꽉 차면 그걸 그대로 상자에 담아 창고(디스크의 SS테이블)에 차곡차곡 쌓아 올리기만 하므로 접수 속도가 엄청나게 빠릅니다.

Ⅲ. 트레이드오프: 읽기 속도의 하락과 컴팩션(Compaction)

쓰기를 최적화한 대가로, 읽기 과정은 조금 피곤해졌다.

  1. 읽기 패널티 (Read Amplification):
    • 데이터를 찾으려면 가장 최신인 메모리(멤테이블)부터 뒤지고, 없으면 디스크에 있는 여러 개의 SS테이블들을 가장 최근 파일부터 과거 파일까지 순서대로 다 뒤져봐야 한다.
  2. 블룸 필터 (Bloom Filter)의 구원:
    • 이 읽기 패널티를 줄이기 위해, "이 SS테이블 안에 해당 데이터가 절대 없다"는 것을 메모리 상에서 즉시 판별해 주는 블룸 필터(Bloom Filter) 자료구조를 필수적으로 사용한다.
  3. 컴팩션 (Compaction) 백그라운드 정리:
    • 시간이 지나면 SS테이블이 수천 개로 늘어나고, 지워진 데이터(Tombstone) 쓰레기가 공간을 낭비한다.
    • 따라서 백그라운드 스레드가 주기적으로 여러 개의 SS테이블을 읽어와 중복된 것과 지워진 것을 버리고, 최신 데이터만 모아 크고 깨끗한 1개의 새로운 SS테이블로 병합(Merge)해 주는 작업(Compaction)을 수행한다.

📢 섹션 요약 비유: 책을 상자에 담아 창고에 무작정 쌓아두었으니 찾을 때(Read) 여러 상자를 열어봐야 해서 귀찮습니다. 그래서 밤마다 직원(컴팩션)이 상자들을 열어 낡은 책은 버리고 상자를 합쳐서 깔끔하게 재정리해 두어야 다음날 책을 찾기 수월해집니다.