Cheat sheet · Data & storage
Storage engines: B-tree and LSM
The problem
A sensor fleet sends 50 000 readings a second, and a B-tree table cannot keep up. We follow a write through an LSM-tree engine: WAL, memtable, SSTables and compaction, and see what it costs on reads.
What you learn
- Why a B-tree rewrites whole pages and turns small writes into random disk IO
- How an LSM-tree turns writes into appends: WAL, memtable, flush to SSTables
- Read amplification, Bloom filters and why compaction can stall writes
- When a B-tree wins and when an LSM-tree wins
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_sensors(["Sensors"])
n_ingest["Ingest service"]
n_wal[["WAL"]]
n_memtable{{"Memtable"}}
n_l0[("SSTables L0")]
n_dash["Dashboard API"]
n_compact("Compaction")
n_l1[("SSTables L1")]
n_sensors --> n_ingest
n_ingest --> n_wal
n_ingest --> n_memtable
n_memtable --> n_l0
n_dash --> n_memtable
n_dash --> n_l0
n_l0 --> n_compact
n_compact --> n_l1
n_dash --> n_l1Mermaid: request sequence
sequenceDiagram
participant n_ingest as Ingest service
participant n_table as B-tree table
participant n_wal as WAL
participant n_memtable as Memtable
participant n_l0 as SSTables L0
participant n_dash as Dashboard API
participant n_compact as Compaction
participant n_l1 as SSTables L1
Note over n_ingest,n_table: A write lands in a B-tree page
n_ingest->>n_table: INSERT INTO readings (sensor_id, ts, value)
n_table-->>n_ingest: INSERT 0 1
Note over n_ingest,n_table: At 50 000 writes a second the disk gives up
n_ingest->>n_table: LOG: checkpoint complete
Note over n_ingest,n_wal: LSM-tree: append to a log, sort in memory
n_ingest->>n_wal: APPEND 000412.log offset=88123904 len=64
n_wal-->>n_ingest: fsync: 0.4 ms
Note over n_memtable,n_l0: A full memtable becomes an SSTable
n_memtable->>n_l0: flush memtable #35;57
Note over n_dash,n_l0: One read checks 31 places
n_dash->>n_l0: GET s_1093/latest
n_l0-->>n_dash: memtable: miss
Note over n_dash,n_l0: A Bloom filter skips the wrong files
n_dash->>n_l0: GET s_1093/latest
n_l0-->>n_dash: memtable: miss
Note over n_compact,n_l1: Compaction merges files into level 1
n_compact->>n_l1: compact L0 -#62; L1
Note over n_ingest,n_memtable: Compaction falls behind and writes stall
n_ingest->>n_memtable: WARN write stall
Note over n_l0,n_compact: Give compaction room and cap the input
n_l0->>n_compact: compaction threads: 6 (was 2)
Note over n_dash,n_l1: A range read: where the B-tree wins
n_dash->>n_l1: SCAN s_1093 from 09:00 to 10:00
n_l1-->>n_dash: merge iterators: memtable, 3 x L0, L1D2
direction: right
n_sensors: "Sensors" {
shape: rectangle
}
n_ingest: "Ingest service" {
shape: rectangle
}
n_wal: "WAL" {
shape: queue
}
n_memtable: "Memtable" {
shape: hexagon
}
n_l0: "SSTables L0" {
shape: stored_data
}
n_dash: "Dashboard API" {
shape: rectangle
}
n_compact: "Compaction" {
shape: rectangle
style.multiple: true
}
n_l1: "SSTables L1" {
shape: stored_data
}
n_sensors -> n_ingest
n_ingest -> n_wal
n_ingest -> n_memtable
n_memtable -> n_l0
n_dash -> n_memtable
n_dash -> n_l0
n_l0 -> n_compact
n_compact -> n_l1
n_dash -> n_l1PlantUML: request sequence
@startuml
participant "Ingest service" as n_ingest
database "B-tree table" as n_table
queue "WAL" as n_wal
collections "Memtable" as n_memtable
database "SSTables L0" as n_l0
participant "Dashboard API" as n_dash
participant "Compaction" as n_compact
database "SSTables L1" as n_l1
note over n_ingest, n_table : A write lands in a B-tree page
n_ingest -> n_table : INSERT INTO readings (sensor_id, ts, value)
n_table --> n_ingest : INSERT 0 1
note over n_ingest, n_table : At 50 000 writes a second the disk gives up
n_ingest -> n_table : LOG: checkpoint complete
note over n_ingest, n_wal : LSM-tree: append to a log, sort in memory
n_ingest -> n_wal : APPEND 000412.log offset=88123904 len=64
n_wal --> n_ingest : fsync: 0.4 ms
note over n_memtable, n_l0 : A full memtable becomes an SSTable
n_memtable -> n_l0 : flush memtable #57
note over n_dash, n_l0 : One read checks 31 places
n_dash -> n_l0 : GET s_1093/latest
n_l0 --> n_dash : memtable: miss
note over n_dash, n_l0 : A Bloom filter skips the wrong files
n_dash -> n_l0 : GET s_1093/latest
n_l0 --> n_dash : memtable: miss
note over n_compact, n_l1 : Compaction merges files into level 1
n_compact -> n_l1 : compact L0 -> L1
note over n_ingest, n_memtable : Compaction falls behind and writes stall
n_ingest -> n_memtable : WARN write stall
note over n_l0, n_compact : Give compaction room and cap the input
n_l0 -> n_compact : compaction threads: 6 (was 2)
note over n_dash, n_l1 : A range read: where the B-tree wins
n_dash -> n_l1 : SCAN s_1093 from 09:00 to 10:00
n_l1 --> n_dash : merge iterators: memtable, 3 x L0, L1
@endumlPlantUML: components
@startuml
left to right direction
agent "Sensors" as n_sensors
component "Ingest service" as n_ingest
queue "WAL" as n_wal
stack "Memtable" as n_memtable
storage "SSTables L0" as n_l0
component "Dashboard API" as n_dash
collections "Compaction" as n_compact
storage "SSTables L1" as n_l1
n_sensors --> n_ingest
n_ingest --> n_wal
n_ingest --> n_memtable
n_memtable --> n_l0
n_dash --> n_memtable
n_dash --> n_l0
n_l0 --> n_compact
n_compact --> n_l1
n_dash --> n_l1
@endumlRecap
A B-tree updates data in place: fast, predictable reads and range scans, but every small write rewrites a page at a random spot. An LSM-tree appends and sorts later: very fast writes, paid for with read amplification and compaction.
Pick a B-tree for read-heavy, transactional data with many range queries. Pick an LSM-tree for write-heavy streams: events, metrics, logs. With an LSM, watch three numbers: L0 file count, pending compaction and write stalls.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| Accepted writes | 8 000/s | 50 000/s |
| Write amplification | 10 x | 12 x |
| Places checked per read | 1 | 5 |
| Read p99 | 3 ms | 45 ms |
Steps
- Case A write lands in a B-tree page
Every sensor sends a reading every few seconds.
- Problem At 50 000 writes a second the disk gives up
The fleet grows to 50 000 writes a second.
- Fix LSM-tree: append to a log, sort in memory
We move to an LSM-tree engine.
- Case A full memtable becomes an SSTable
When the memtable reaches 64 MB it is frozen, a new empty one takes writes, and the frozen one is written to disk as an SSTable: a sorted file that is never changed again.
- Problem One read checks 31 places
The dashboard asks for the latest reading of sensor
s_1093. - Fix A Bloom filter skips the wrong files
Each SSTable gets a Bloom filter, a few bits per key kept in memory.
- Fix Compaction merges files into level 1
L0 keeps growing with a new file every few seconds.
- Problem Compaction falls behind and writes stall
A storm hits, every sensor reports at once, and writes jump to 80 000 a second.
- Fix Give compaction room and cap the input
Compaction gets six threads instead of two.
- Case A range read: where the B-tree wins
The dashboard asks for one sensor's last hour.
- Recap Recap
A B-tree updates data in place: fast, predictable reads and range scans, but every small write rewrites a page at a random spot.
Terms
- B-tree
- A structure that keeps data in sorted pages and updates them in place. Reads and range scans are fast, but every small write rewrites a whole page at a random spot.
- LSM-tree
- A store that appends each write to the WAL, sorts it in an in-memory memtable and later flushes it to disk as an SSTable file. Writes are very fast; the price is read amplification and compaction.
- WAL (write-ahead log)
- Every change is first appended to a log file that only grows at the end, then applied to the main structure. If the server crashes, data is recovered from this log.