Skip to content
Putting It All Together
step 1/5

Reading — step 1 of 5

Read

~1 min readTransactions & MVCC

Putting It All Together

A full LSM-tree KV with transactions:

LayerLesson
In-memory KV1
Ordered iteration2
TTL3
Write-ahead log4
Memtable + flush5
SSTable format6
LSM read path7
Compaction8
Bloom filters9
Transactions10
MVCC11

What we glossed over:

  • Replication: leader-follower, Raft consensus, Paxos.
  • Sharding: partition keys across nodes.
  • Distributed transactions: 2-phase commit, percolator, FoundationDB's transaction protocol.
  • Snapshots / backups: consistent points for restore.
  • Encryption: at-rest and in-transit.
  • Online schema changes: DDL operations without downtime.
  • Time-series optimizations: time as part of the key; older data compacted differently.

Real systems you should look at:

  • LevelDB: Google, ~50k LoC. The reference LSM-tree implementation.
  • RocksDB: Facebook fork; many production tweaks.
  • Cassandra: distributed LSM with size-tiered compaction.
  • etcd: BoltDB-backed, MVCC, strongly consistent, used by Kubernetes.
  • FoundationDB: distributed ACID, stunning architecture (Apple uses it everywhere).
  • TiKV: distributed RocksDB + Raft.
  • CockroachDB: distributed SQL on top of TiKV-like storage.

You've now built a meaningful subset of all of these.

Discussion

Ask a question, share an insight, or help someone who’s stuck.

Sign in to post a comment or reply.

Loading…