Cheat Sheet
Key takeaway
Replication gives you copies (availability); partitioning gives you capacity (scalability). They solve different problems, they are used together, and almost every database decision reduces to what the access pattern needs and what guarantee you are willing to give up.
Key terms
| Term | One line |
|---|---|
| Relation / tuple / attribute | Table / row / column |
| Impedance mismatch | Nested objects vs flat tables; needs a translation layer |
| Normalization | Each fact stored once, linked by foreign key |
| Replication | Multiple copies of the same data |
| Partitioning / sharding | Different data on different nodes |
| Replication lag | Delay between primary and secondaries |
| Hotspot | One partition taking disproportionate data or traffic |
| Quorum | Minimum nodes that must respond: r + w > n |
| LWW | Last-write-wins conflict resolution |
| Scatter-gather | Query every partition, merge results |
| CDC | Change data capture — stream row changes to another system |
SQL vs NoSQL
| Relational if... | Non-relational if... |
|---|---|
| Data is structured | Data is unstructured |
| ACID required | Need to serialize/deserialize |
| Fits on one node | Data is large |
ACID: Atomicity (all or none) · Consistency (invariants hold) · Isolation (concurrent = sequential) · Durability (survives failure). Prevents dirty reads, lost updates, phantom reads. ACID's C is not CAP's C.
The four NoSQL families
| Family | Model | Use for | Examples |
|---|---|---|---|
| Key-value | Hash table | Sessions, carts — lookup by identity | DynamoDB, Redis, Memcached |
| Document | JSON/XML/BSON trees | Catalogs, CMS — varied self-contained records | MongoDB, Firestore |
| Graph | Nodes + edges | Social graphs, fraud, recommendations — traversal | Neo4j, OrientDB |
| Columnar | Stored by column | Analytics, warehousing — scans over few columns | Redshift, BigQuery |
Columnar ≠ wide-column. Columnar = OLAP scans. Wide-column (Cassandra, HBase) = high-throughput writes via column families.
NoSQL drawbacks: no standard query language (hard to port) · weaker consistency and no foreign-key constraints — referential integrity becomes your code.
NewSQL (Spanner) = horizontal scale plus ACID, paid for in write-path coordination latency.
Replication
Synchronous -> replicas current, higher latency, blocks on a slow replica Asynchronous -> fast writes, replicas lag, UNREPLICATED WRITES ARE LOST Semi-sync -> wait for ONE replica; bounded loss, fastest-peer latency
Leader-based replication defaults to async — durability is not guaranteed.
| Model | Writes | Failover | Conflicts | Consistency |
|---|---|---|---|---|
| Single-leader | One node (bottleneck) | Election + fencing | None — leader serializes | Strong on leader |
| Multi-leader | Several nodes | Moderate | Yes — must resolve | Eventual |
| Leaderless | Every node | None to lose | Yes — versioning | Tunable via r/w |
Single-leader propagation methods
| Method | Ships | Weakness | Used by |
|---|---|---|---|
| Statement-based | SQL statements | NOW() and other nondeterminism diverges | Older MySQL |
| WAL shipping | Low-level bytes | Coupled to engine internals; hard version upgrades | PostgreSQL, Oracle |
| Logical (row-based) | Row changes | More verbose | PostgreSQL, MySQL — enables CDC |
Replication lag causes: data loss on primary failure · inconsistent reads. Fix: read-your-writes — read own data from leader, or better, a version watermark any caught-up follower can satisfy.
Conflict resolution (multi-leader)
| Strategy | How | Risk |
|---|---|---|
| Conflict avoidance | Pin a record's writes to one leader | Breaks on failover/relocation |
| Last-write-wins | Highest timestamp survives | Silent data loss from clock skew |
| Custom logic | Merge, or prompt the user | Low — nothing discarded blindly |
Topologies: circular · star · all-to-all (most robust) — one node failure breaks the other two.
Quorums
r + w > n guarantees read and write sets overlap
| n/r/w | Legal? | Character |
|---|---|---|
| 3/2/1 | ✗ (2+1 not > 3) | Read can miss the write |
| 3/2/2 | ✓ | Balanced default |
| 3/1/3 | ✓ | Fast reads, slow writes |
| 3/3/1 | ✓ | Fast writes, slow reads |
Latency = slowest node in the quorum, not the average.
Partitioning
Vertical = move tables/columns (split blobs off) — manual, static. Horizontal = split rows into shards — automatable, dynamic.
| Strategy | Advantage | Disadvantage |
|---|---|---|
| Key-range | Range queries easy; data sorted | Hotspots if keys skew |
| Hash-based | Uniform distribution | Range queries hit every partition |
| Consistent hashing | Scales with minimal data movement | Non-uniform without virtual nodes |
Number of shards = Database size / Size per shard
= 10 TB / 50 GB = 200 shards
Rebalancing
Never hash mod n — changing n remaps nearly every key.
| Strategy | Partition count | Used by |
|---|---|---|
| Fixed number | Constant; move whole partitions | Elasticsearch, Riak |
| Dynamic | Splits/merges by size | HBase, MongoDB |
| Proportional to nodes | Fixed count per node | Cassandra, Ketama |
Throttle rebalancing — unthrottled moves under load cascade into outages.
Secondary indexes
| By document (local) | By term (global) | |
|---|---|---|
| Write | Cheap — one shard | Expensive — several index nodes |
| Read | Scatter-gather all shards | Targets specific nodes |
| Use for | Write-heavy | Read-heavy |
Request routing
Any node (forwards) · Routing tier · Client-aware (partition map). All three need a fresh map → ZooKeeper or equivalent (HBase, Kafka, SolrCloud). Small, strongly consistent control plane separate from the data plane.
Centralized vs distributed
| Centralized | Distributed | |
|---|---|---|
| Pro | Simple maintenance, strong ACID, simple programming model | Nearest-shard access, parallel subqueries |
| Con | Latency at node limits, single point of failure | Cross-site latency, expensive joins, consistency complexity |
Query optimization — move computation to the data
T = a + v / b a = access delay, b = data rate, v = data volume Move Product (100,000 tuples) to A -> 0.1 + 0.4 = 0.5 s Move Store + Sales (1,010,000) to B -> 0.2 + 4.04 = 4.24 s Filter Brand='Wolf' at B, move 10 rows -> 0.1 + ~0 = ~0.1 s <- 42x faster
Push predicates down. When transfer dominates, cut volume; when access delay dominates, cut round trips.
Quick decision cues
- Multi-record transactions needed → relational, and stay there
- Lookup by single identifier at huge rate → key-value
- Records with varying shapes → document
- The relationships are the query → graph
- Aggregate scans over few columns → columnar
- Read-heavy → replicas + cache; write-heavy → shard
- Acked write must never vanish → semi-sync at minimum
- Data is derived and rebuildable → async replication is fine
- Offline writes required → multi-leader
- No leader to fail over → leaderless + quorums
- Adding nodes often → consistent hashing / fixed partitions
- Query by non-partition key, read-heavy → global index by term
Work the Interview Walkthrough for the full design and the Concept Drills for rapid-fire practice.