Part 4 of 8 · week 4 of the learning path
When data volume, speed or complexity is the main challenge, the design comes down to four choices: how data is stored, copied, split and kept consistent.
Learning objectives
- Choose a storage engine and data model for a workload.
- Reason about replication, partitioning and the anomalies they create.
- Pick transaction and consistency levels, and decide between batch and stream processing.
Storage
| Choice | Strength | Used by |
|---|---|---|
| B-tree | Updates in place, fast reads, mature indexing | Most relational databases |
| LSM-tree | Fast writes through sequential appends and background compaction | Cassandra, RocksDB and similar |
| Row store | Whole-record reads and writes (OLTP) | Application databases |
| Column store | Scanning a few columns over many rows (OLAP) | Warehouses and analytics |
Replication
- Leader and followers: writes go to the leader and copy to followers, synchronously or asynchronously; simple and common.
- Multi-leader: several leaders accept writes, useful across regions, but conflicts must be resolved.
- Leaderless with quorums: with N replicas, a write needs W acknowledgements and a read asks R; when R plus W is greater than N, a read overlaps the latest write.
- Replication lag causes anomalies: reading your own write from a lagging follower, or seeing data go backwards. Route a user's reads to the leader after a write, or track versions.
Partitioning
- By key range: keeps related keys together and supports range scans, but sequential keys such as timestamps create hot spots.
- By hash: spreads load evenly, but loses range scans.
- Rebalancing: use many more partitions than nodes, or consistent hashing, so adding a node moves little data.
- Identifiers: avoid a single auto-increment counter at scale; use IDs that combine a timestamp, a shard or machine part and a sequence so they are unique and roughly sortable.
Transactions and consistency
- ACID transactions protect against partial failure; isolation levels trade safety for speed: read committed, snapshot isolation and serializable.
- Know the anomalies: dirty reads, lost updates and write skew, where two transactions each read the same data and write different rows so that together they break a rule.
- Distributed transactions with two-phase commit are slow and fragile; prefer sagas where the business allows.
- Consistency ranges from linearizable (acts like one copy) to eventual. Choose the weakest level a feature can tolerate, and the strongest for money and inventory.
Batch and stream: batch jobs (Spark, MapReduce) process bounded data cheaply and accurately; stream processors (Flink, Kafka Streams) handle unbounded data with low latency and must deal with windows and late events. Design stream jobs to be idempotent so replays give the same result.
Worked numbers: 1 billion users at 1 KB each is about 1 TB. With three replicas that is 3 TB; at 500 GB per node you need about six nodes before growth and headroom. With N=3, W=2 and R=2 a read always overlaps the latest acknowledged write.
Real-world examples
- Amazon Dynamo (2007): a published design for a highly available key-value store using leaderless replication and quorums; it inspired many later databases.
- Google Spanner (2012): a globally distributed database that offers strong consistency by using tightly synchronized clocks, showing that the trade-off can be pushed with specialized hardware.
- Instagram IDs: the team documented generating sortable IDs from a timestamp, a shard ID and a sequence, so each shard creates unique IDs with no central counter.
Design exercise: design the storage for a chat history store holding 100 billion messages. Choose the engine, the partition key, the replication setting and the consistency level, and explain how you would serve the latest 50 messages of a conversation.
Quiz 4 (5 questions, pass mark 4)
- Why are LSM-trees good for write-heavy workloads?
- A) They give faster random reads than B-trees in every case
- B) Writes are sequential appends merged later by compaction
- C) They need no disk
- D) They give transactions across nodes
- With N=3 replicas, which setting makes a read overlap the latest acknowledged write?
- A) W=1, R=1
- B) W=1, R=2
- C) W=2, R=2
- D) W=0, R=3
- What causes the read-your-writes anomaly?
- A) Too many indexes
- B) Clock skew in browsers
- C) Encrypted disks
- D) Reading from a follower that has not yet received your recent write
- Why hash-partition a table keyed by timestamp instead of using key ranges?
- A) All current writes hit one range partition, a hot spot, while hashing spreads them
- B) Timestamps are sensitive data
- C) Range queries become faster
- D) It removes the need for replicas
- Two on-call doctors each see the other on call and both go off call. What is this and what prevents it?
- A) A dirty read, fixed by a cache
- B) Write skew, fixed by serializable isolation or explicit locking
- C) A network partition, fixed by retries
- D) A deadlock, fixed by more replicas
Quiz 4 answers
Sources and further reading
- Designing Data-Intensive Applications by Martin Kleppmann, the main reference for this module.
- Dynamo: Amazon's highly available key-value store, the 2007 paper (hosted copy).
- Spanner: Google's globally distributed database, the OSDI 2012 paper.
- Sharding and IDs at Instagram, on time-sortable 64-bit IDs per shard.
Part 4 of 8 in the System Design Learning Path series. Next: part 5.
Top comments (0)