Tuning LSM Trees — Compaction, Write Amplification, and Read Amplification TODO
Concept
An LSM tree buffers writes into an in-memory memtable, flushes it as a sorted, immutable file (an SSTable), and periodically merges the files piled up across levels via compaction — turning random writes into sequential ones to gain write throughput. The tradeoff is three kinds of amplification. Write amplification is the multiple by which one logical write ends up being rewritten to disk repeatedly across compactions. Read amplification is the cost of a single lookup having to check multiple levels and files. Space amplification is the ratio by which stored data exceeds the actual live data, because old versions and delete markers haven't been cleaned up yet. Leveled compaction keeps key ranges non-overlapping within each level, which keeps read and space amplification low at the cost of high write amplification; tiered (size-tiered) compaction does the opposite — low write amplification, but many overlapping files driving up read and space amplification. In other words, the three amplifications can't all be minimized simultaneously — tuning knobs like Bloom filters, block cache, file size, and level fan-out are all ways of choosing which corner of that triangle to sacrifice.
A chain node's state database or an indexer's backend is typically LSM-based, so when you hit a disk-write blowup or a read-latency spike from lagging compaction, you can't diagnose the cause without this three-way-amplification lens.
Code & Formula
# LSM 트리 튜닝 — 컴팩션·쓰기 증폭·읽기 증폭 — 레벨을 쌓고 병합할 때마다 같은 데이터가 몇 번씩 다시 쓰이는지 측정한다.
# memtable → SSTable flush → 레벨 컴팩션 과정에서 논리적 쓰기량 대비 실제 디스크 기록량(쓰기 증폭)을 계산한다.
class LSMTree:
def __init__(self, level_multiplier=4, level0_size=4):
self.levels = [] # levels[i] = 그 레벨에 쌓인 바이트 수
self.level_multiplier = level_multiplier
self.level0_size = level0_size
self.logical_bytes_written = 0
self.actual_bytes_written = 0
def flush_memtable(self, size):
self.logical_bytes_written += size
self.actual_bytes_written += size # memtable → L0 flush (1회 기록)
if not self.levels:
self.levels.append(0)
self.levels[0] += size
self._maybe_compact(0)
def _maybe_compact(self, i):
capacity = self.level0_size * (self.level_multiplier ** i)
if self.levels[i] <= capacity:
return
moved = self.levels[i]
self.levels[i] = 0
if i + 1 >= len(self.levels):
self.levels.append(0)
self.levels[i + 1] += moved
self.actual_bytes_written += moved # 컴팩션도 디스크에 다시 쓰는 비용이다
self._maybe_compact(i + 1)
tree = LSMTree()
for _ in range(50):
tree.flush_memtable(size=1)
write_amp = tree.actual_bytes_written / tree.logical_bytes_written
print("레벨별 현재 크기:", tree.levels)
print(f"논리 쓰기량={tree.logical_bytes_written}, 실제 디스크 기록량={tree.actual_bytes_written}")
print(f"쓰기 증폭(write amplification) = {write_amp:.2f}x")
# 읽기 증폭: 하나의 키를 찾으려면 최악의 경우 각 레벨을 다 확인해야 한다
levels_to_check = len([lv for lv in tree.levels if lv > 0])
print(f"읽기 증폭(최악의 경우 확인해야 할 레벨 수) ≈ {levels_to_check}")
docs/code/algorithms/algorithms-71.py
Exercise
Load a random-key write workload onto RocksDB or a similar engine, vary the compaction style and level fan-out, and table out actual disk bytes written against logical bytes written (write amplification) alongside lookup p99 latency.
Practical Connection
If Verex's event indexer writes logs mostly as time-ordered appends and queries them per-market by range, key design and compaction policy alone can shift query latency and disk lifetime substantially on the same hardware.
Where it lands in Jayverse
- Verex: pick leveled compaction for the event indexer, not tiered. Per-market range queries need low read and space amplification more than raw write throughput, so leveled compaction fits Verex's time-ordered, per-market query pattern better.
- gitboard: track write amplification and lookup p99 as indexer dashboard metrics. Per this PoC's exercise, keep the actual-disk-bytes-vs-logical-bytes ratio and p99 latency visible, so a compaction-lag spike is diagnosed against real numbers instead of guessed at.
- Devnet: run the write-amplification benchmark against Verex's real key schema, not a synthetic one. Vary compaction style and level fan-out on the actual per-market, time-ordered key design before picking defaults.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| write amplification | 쓰기 증폭 · 논리적으로 한 번 쓴 데이터가 디스크에 여러 번 다시 쓰이는 정도를 가리키는 스토리지 용어. "Write amplification is the multiple by which one logical write" |
| read amplification | 읽기 증폭 · 조회 한 번에 여러 레벨·파일을 확인해야 하는 비용을 가리킬 때. "Read amplification is the cost of a single lookup" |
| space amplification | 공간 증폭 · 실제 데이터보다 저장 공간을 얼마나 더 차지하는지 나타내는 비율. "Space amplification is the ratio by which stored data exceeds" |
| fan-out | 팬아웃, 한 레벨이 갖는 파일 개수 비율 · 컴팩션 설정을 튜닝할 때 쓰는 용어. "vary the compaction style and level fan-out" |
| at the cost of | ~을 대가로, ~을 희생하고 · 한쪽 장점을 얻는 대신 다른 쪽이 나빠질 때. "at the cost of high write amplification" |
| table out | 표로 정리해서 나타내다 · 실험 결과를 비교 가능한 표로 만들 때 쓰는 구동사. "table out actual disk bytes written against logical bytes" |
| piled up | 쌓이다, 누적되다 · 파일이나 작업이 정리되지 않고 계속 쌓일 때. "the files piled up across levels via compaction" |
| LSM (tree) | 로그구조병합트리(Log-Structured Merge tree) · 쓰기를 버퍼링 후 정렬된 파일로 플러시·병합하는 스토리지 엔진 구조, 이 카드의 주제. "An LSM tree buffers writes into an in-memory memtable" |
| SSTable | 정렬된 불변 파일(Sorted String Table) · 메모리의 memtable이 디스크로 flush될 때 만들어지는 파일 포맷. "flushes it as a sorted, immutable file (an SSTable)" |
| RocksDB | 페이스북이 만든 LSM 기반 임베디드 키밸류 스토어 · 실습에서 쓰기 증폭을 측정할 실제 엔진으로 언급. "Load a random-key write workload onto RocksDB or a similar engine" |
| Bloom filter | 블룸 필터(확률적 멤버십 검사 자료구조) · 읽기 증폭을 줄이는 튜닝 손잡이 중 하나로 언급. "tuning knobs like Bloom filters, block cache, file size" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.