Data & storage / 3 / 11
Storage engines: B-tree and LSM
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.
- 15 min
- Advanced
- 11 steps
- Accepted writes
- 8 000 /s
- Write amplification
- 10 x
- Places checked per read
- 1
- Read p99
- 3 ms
- request
- reply
- redelivery
- duplicate
- lost
Numbers are a model scenario, not measurements
The real request
Ingest service → B-tree tableRequest
INSERT INTO readings (sensor_id, ts, value)1
VALUES ('s_1093', 1795392843, 21.4);
Response
INSERT 0 1
wal: +96 bytes2
page 81233: dirty, 8192 bytes to flush3
sensor_id— The first key column. Readings from 10 000 sensors land on 10 000 different pages.wal— The write-ahead log entry: small and sequential. This part is cheap.dirty— The page changed in memory. Sooner or later all 8 KB are written back.
Course: 42 lessons
01 Foundations
02 Scaling
03 Data & storage
04 Communication
05 Reliability
06 Architecture
07 Security
08 Shipping
09 Whole systems
10 Business processes