정렬을 제자리에 유지할 것인가, 메모리에서 하고 순차로 흘려보낼 것인가 — 디스크의 물리적 성질이 만든 두 갈래.
인덱스 자료구조를 논하기 전에, 그 밑에 깔린 물리 법칙 하나부터. append(순차 쓰기)는 싸고, random in-place(제자리 수정)는 비싸다. HDD든 SSD든.
SSD엔 물리적 헤드 이동(seek)이 없는데도 제자리 수정이 비싸다. 페이지(4~16KB)는 덮어쓰기 전에 블록을 통째로 지워야(erase) 하기 때문 — read-modify-write가 터진다. 이 부풀려진 실제 쓰기량을 쓰기 증폭(write amplification)이라 한다.
빠른 조회엔 정렬이 필요하다. B-Tree(실제로는 B+Tree)는 데이터를 디스크에 key 순 정렬 상태로 유지한다. 대가는 삽입 시의 random 쓰기.
한 페이지에 4개까지. 250을 넣어보자.
전체를 밀지 않는다. 꽉 찬 페이지를 둘로 쪼개 절반을 새 페이지로 옮기고, 부모에 포인터(구분키)를 꽂는다. 하지만 페이지 재작성 + 새 페이지 + 부모 수정 = 여러 곳 random 쓰기. 최악엔 부모로 위로 전파된다.
내부 노드는 데이터 없이 이정표(key+포인터)만 → 팬아웃 극대화 → 트리가 얕다(3~4단). 그래서 단건 조회 = 디스크 read 3~4번(상위는 캐시), 예측 가능한 낮은 지연. 리프끼리 링크드리스트로 이어져 범위 스캔은 "한 번 내려가 옆으로 훑기".
발상을 뒤집는다. "절대 제자리 수정 안 한다. append만." 쓰기는 폭발적으로 빨라지지만, 순서 없는 로그는 조회가 풀스캔이 된다. 해법: 정렬은 메모리에서, 디스크엔 순차로.
memtable = 정렬을 유지하는 인메모리 버퍼(스킵리스트/균형트리). 차면 얼려서 SSTable(정렬 파일)로 한 번에 순차 flush 후 비운다. 내구성은 WAL(commit log)이 보강 — 크래시 나도 WAL replay로 memtable 복원.
데이터가 여러 SSTable에 흩어지면 어떻게 풀스캔 없이 찾나? 파일마다 블룸필터(없는 파일 스킵)와 sparse index(블록당 첫 key)를 붙인다.
SSTable 1개 = [블룸필터] + [sparse index] + [정렬 블록]. 조회는 최신 파일부터: 블룸필터가 "없음"이면 디스크를 안 열고 스킵(FN 없으니 안전), "있을 수도"면 sparse index로 블록 1개 특정 → 이진탐색. 블룸필터의 false positive는 헛되이 여는 파일을 늘려 read amplification이 된다.
제자리 수정을 안 하니 갱신 = 새로 쌓기(최신 우선), 삭제 = 툼스톤(마커+타임스탬프). 죽은 데이터가 쌓이면 컴팩션(병합정렬)으로 정리한다.
옛 SSTable은 불변이라 지울 수 없다. 삭제는 최신 파일에 key → [삭제됨] 마커를 쌓는 것. 조회는 최신부터 보다 툼스톤을 먼저 만나면 "없음" 반환.
⚠️ 툼스톤은 옛 값과 병합되기 전엔 못 버린다(gc_grace_seconds). 일찍 버리면 삭제된 key가 부활(좀비).
정렬된 SSTable들을 병합정렬(순차 read+write)로 합쳐 key별 최신만 남기고 죽은 값·툼스톤을 물리적으로 버린다.
대가 = write amplification. 같은 데이터가 레벨을 타고 내려가며 여러 번 재기록된다.
| 축 | B-Tree | LSM-Tree |
|---|---|---|
| 쓰기 패턴 | random in-place (페이지 분할) | 순차 append (flush) |
| 쓰기 증폭 | 적음 | 많음 (컴팩션 재기록) |
| 단건 읽기 | 3~4홉, 예측가능·낮은 지연 | 여러 SSTable → read amp, p99 취약 |
| 강점 워크로드 | 읽기·point read, 쓰기 희박 | 쓰기 폭주(로그/잦은 갱신) |
| 대표 | MySQL InnoDB, PostgreSQL | RocksDB, Cassandra, HBase, ScyllaDB |
write / read / space amplification은 동시에 다 줄일 수 없다. 워크로드가 무엇을 희생해도 되는지가 선택 기준.
읽기:쓰기 = 50:1, 단건 조회, p99 50ms, 수천만 건. → 쓰기가 희박해 LSM의 유일한 강점을 안 쓰면서 read amp·p99 리스크만 떠안음. 게다가 RDB 몇 대면 될 걸 분산 운영복잡도로 감쌈.
✅ 판단: B-Tree RDB. 진짜 쓰기가 병목일 때 그 부분만 분리.
하루 수십만 row DELETE → 툼스톤 폭증. 읽히는 파티션에 툼스톤이 고이면 range read가 그걸 다 스캔 → tombstone_failure_threshold(10만) 초과 시 쿼리 실패. gc_grace 10일간 잔존.
✅ 판단: 삭제 단위를 파티션 키(member_id)로 모델링 → 파티션 툼스톤 몇 개 / 나이 만료는 TTL+TWCS로 SSTable 통째 drop. "누구를 지우나"와 "언제 만료하나"는 독립된 두 축.
잦은 갱신 + 잦은 읽기인데 컴팩션이 기본값(STCS). 옛 버전이 여러 tier에 흩어져 read amp↑·space amp↑. 노드 추가는 노드마다 같은 병증을 복제하는 헛발질.
✅ 판단: 엔진 교체 말고 LCS로 컴팩션 전략 전환(read/space amp 급감, 대가는 write amp). 단 순수 쓰기 파이어호스엔 오히려 STCS/TWCS.
memtable의 내구성 보강. 크래시 복구 = 체크포인트 + WAL replay.
Read·Update·Memory 오버헤드는 동시에 최적화 불가 — write/read/space amp의 이론적 배경.
B-Tree와 LSM 사이 절충 구조 (TokuDB 등).
memtable에 쓰는 인메모리 정렬 자료구조 선택.
툼스톤 부활 방지 유예기간. 분산 삭제의 정합성.
인덱스·검색엔진을 원본 DB와 동기화(change data capture).