mufassall

Cheat sheet · Data & storage

Storage engines: B-tree and LSM

15 min · Advanced · mufassall.dtwin.uz/en/l/storage-engines/

← Open the lesson

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
Final scene
30%60%25%40%45%20%75%

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_l1

Mermaid: 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, L1

D2

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_l1

PlantUML: 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
@enduml

PlantUML: 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
@enduml

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. 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

MetricStartEnd
Accepted writes8 000/s50 000/s
Write amplification10 x12 x
Places checked per read15
Read p993 ms45 ms

Steps

  1. Case A write lands in a B-tree page

    Every sensor sends a reading every few seconds.

  2. Problem At 50 000 writes a second the disk gives up

    The fleet grows to 50 000 writes a second.

  3. Fix LSM-tree: append to a log, sort in memory

    We move to an LSM-tree engine.

  4. 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.

  5. Problem One read checks 31 places

    The dashboard asks for the latest reading of sensor s_1093.

  6. Fix A Bloom filter skips the wrong files

    Each SSTable gets a Bloom filter, a few bits per key kept in memory.

  7. Fix Compaction merges files into level 1

    L0 keeps growing with a new file every few seconds.

  8. Problem Compaction falls behind and writes stall

    A storm hits, every sensor reports at once, and writes jump to 80 000 a second.

  9. Fix Give compaction room and cap the input

    Compaction gets six threads instead of two.

  10. Case A range read: where the B-tree wins

    The dashboard asks for one sensor's last hour.

  11. 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.