mufassall

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
Open in Lab
20%30%
  • request
  • reply
  • redelivery
  • duplicate
  • lost

Numbers are a model scenario, not measurements

The real request

Ingest service → B-tree table

Request

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
  1. sensor_id — The first key column. Readings from 10 000 sensors land on 10 000 different pages.
  2. wal — The write-ahead log entry: small and sequential. This part is cheap.
  3. dirty — The page changed in memory. Sooner or later all 8 KB are written back.
Course: 42 lessons
  1. 01 Foundations

    1. The life of a request
    2. Latency and throughput
    3. Napkin math
  2. 02 Scaling

    1. Scaling up vs scaling out
    2. Load balancing
    3. Stateless servers
    4. Caching
    5. CDN and edge caching
  3. 03 Data & storage

    1. SQL and NoSQL
    2. Database indexes
    3. Storage engines: B-tree and LSM
    4. Database replication
    5. Sharding
    6. Consistent hashing
    7. Unique IDs
    8. CAP: when the link breaks
    9. Consensus and leader election
    10. Transactions
    11. File uploads
  4. 04 Communication

    1. API styles
    2. Message queues
    3. Pub/sub and event logs
    4. Real-time updates
    5. Reliable callbacks
  5. 05 Reliability

    1. Redundancy and failover
    2. Rate limiting
    3. Timeouts and retries
    4. Observability
  6. 06 Architecture

    1. Microservices
    2. Service discovery
    3. Sagas and the outbox
    4. Batch vs stream
  7. 07 Security

    1. Authentication
    2. Authorization
    3. Encryption and secrets
  8. 08 Shipping

    1. Testing
    2. CI/CD: from commit to production
  9. 09 Whole systems

    1. From requirements to design
    2. Design a URL shortener
    3. Design a news feed
    4. Design a chat
  10. 10 Business processes

    1. Payment gateway