Module B2 — Databases at Scale

Structure: Balanced binary search tree of key → row_pointer pairs
Best for:  Equality (=), range queries (<, >, BETWEEN), ORDER BY, JOIN

Example:
  SELECT * FROM users WHERE email = 'a@b.com'
  Without index: scan all 10M rows
  With B-tree index on email: binary search → ~24 comparisons (log₂ 10M)

Structure: Hash map of key → row_pointer
Best for:  Equality queries only (=)
Worst for: Range queries (not supported — hash loses ordering)

Example: Memcached, Redis hash maps, MySQL MEMORY engine

CREATE INDEX idx_user_date ON orders(user_id, created_at);

Left-most prefix rule:
  ✅ WHERE user_id = 5                        (uses index)
  ✅ WHERE user_id = 5 AND created_at > X     (uses index)
  ❌ WHERE created_at > X                     (does NOT use index — skips user_id)

Most selective column should be first.

An index that contains all columns needed by a query:
  SELECT user_id, created_at FROM orders WHERE user_id = 5

If index includes (user_id, created_at), the DB reads only the index,
never touches the row data. Drastically reduces I/O.

✅ Speeds up SELECT dramatically
❌ Slows down INSERT, UPDATE, DELETE (must update the index too)
❌ Consumes disk space (can be 10–30% of table size)
❌ Can lead to index bloat over time (periodic REINDEX needed)

Rule: Index columns that appear in WHERE, JOIN ON, ORDER BY.
      Don't index every column — low-cardinality columns (boolean, status enum)
      give poor selectivity; the optimizer may prefer a full scan.

A — Atomicity:    Transaction is all-or-nothing. No partial writes.
C — Consistency:  DB transitions from one valid state to another.
                  Constraints (FK, NOT NULL, UNIQUE) always satisfied.
I — Isolation:    Concurrent transactions don't see each other's in-progress writes.
D — Durability:   Committed transactions survive crashes (WAL / fsync).

Phenomena (problems):
  Dirty Read:      Transaction A reads uncommitted data from B.
  Non-repeatable:  Transaction A reads same row twice; B commits between → different value.
  Phantom Read:    Transaction A runs same query twice; B inserts matching row → different count.

Isolation levels (weakest → strongest):
  READ UNCOMMITTED:  Allows dirty reads (rarely used)
  READ COMMITTED:    No dirty reads; non-repeatable reads possible (PostgreSQL default)
  REPEATABLE READ:   No dirty/non-repeatable reads; phantoms possible (MySQL default)
  SERIALIZABLE:      Fully isolated; no concurrency anomalies (slowest)

Trade-off: Higher isolation = fewer anomalies = more locking = lower throughput

BA — Basically Available:  System always responds (may be stale/partial)
S  — Soft State:           State can change over time even without input (replication)
E  — Eventually Consistent: Given no new updates, replicas will converge

BASE is not "ACID without guarantees" — it's a deliberate design choice for
availability and performance over strict consistency.

✅ Complex queries with JOINs across multiple tables
✅ ACID transactions required (financial, booking, inventory)
✅ Schema is well-defined and stable
✅ Rich query patterns (GROUP BY, aggregations, window functions)
✅ Data integrity constraints critical (FK, UNIQUE, CHECK)
✅ Team knows SQL deeply

Examples: PostgreSQL, MySQL, Aurora, SQLite

✅ Access pattern is simple and known (key lookup, range scan)
✅ Need horizontal scale beyond what vertical + sharding SQL can give
✅ Schema is flexible / evolving rapidly
✅ Extremely high write throughput required
✅ Data is naturally document-shaped (nested JSON), graph, or time-series

Examples: DynamoDB (key-value/document), Cassandra (wide-column),
          MongoDB (document), Neo4j (graph), InfluxDB (time-series)

Key-Value:
  Structure: Key → Value (blob, string, JSON, binary)
  Access:    Get(key), Put(key, value), Delete(key)
  Best for:  Session storage, caching, shopping carts, user preferences
  Examples:  Redis, DynamoDB, Riak

Document:
  Structure: Nested JSON/BSON documents; flexible schema per document
  Access:    Query on any field within document; partial updates
  Best for:  Content management, catalogs, user profiles, event logging
  Examples:  MongoDB, CouchDB, Firestore

Wide-Column (Column Family):
  Structure: Row key → sorted map of column families
  Access:    Efficient range scans on row key; sparse columns
  Best for:  Time-series, IoT telemetry, write-heavy analytics
  Examples:  Cassandra, HBase, Bigtable

Graph:
  Structure: Nodes (entities) + Edges (relationships) + properties on both
  Access:    Traverse relationships; shortest path; neighbor queries
  Best for:  Social networks, recommendation engines, fraud detection
  Examples:  Neo4j, Amazon Neptune, Dgraph

Time-Series:
  Structure: Timestamp + measurement; optimised for time-range queries
  Access:    Last N values, aggregations over time ranges, downsampling
  Best for:  Metrics, monitoring, IoT, financial tick data
  Examples:  InfluxDB, TimescaleDB, Prometheus

Architecture:
  Primary: accepts writes
  Replica(s): receive changes asynchronously from primary; serve reads

                     WRITE
[Client W] ──→ [Primary DB] ──async──→ [Replica 1]
                                  ──async──→ [Replica 2]
[Client R] ──→ [Replica 1]  (read traffic distributed)

Pros:
  ✅ Scales reads horizontally (add more replicas)
  ✅ Replicas can be promoted to primary if primary fails
  ✅ Replicas can serve analytics queries (separate read pool)

Cons:
  ❌ Replication lag — reads from replica may be stale
  ❌ Primary is still single write point (vertical scale only for writes)
  ❌ Failover takes time; potential for data loss (async window)

Scenario:
  1. User updates their profile photo (write → primary)
  2. User immediately views their profile (read → replica)
  3. Replica hasn't received update yet → user sees old photo

Solutions:
  a) Read-your-own-writes: route user's reads to primary for their own data
  b) Monotonic reads: always route same user to same replica
  c) Sync replication: write waits for replica acknowledgement (slower)
  d) Synchronous replication for critical paths only

All nodes accept writes. Must handle write conflicts.

Conflict resolution strategies:
  Last-write-wins (LWW): Timestamp-based; risk of data loss
  CRDTs:                 Conflict-free Replicated Data Types (mathematical guarantee)
  Application merge:     Business logic resolves conflicts
  Avoid conflicts:       Partition writes by user/tenant (each user has one home node)

Use case: Multi-datacenter active-active (geo-distributed writes)
Examples: Cassandra, CockroachDB (with consensus), MySQL Group Replication

Synchronous:
  Primary waits for replica ACK before confirming write to client
  ✅ No data loss on primary failure
  ❌ Write latency increases by one network RTT
  ❌ If replica is slow, primary is slowed

Semi-synchronous:
  Primary waits for ACK from at least ONE replica (not all)
  Balance between durability and latency

Asynchronous (default for most systems):
  Primary confirms write immediately; replication happens in background
  ✅ Lowest write latency
  ❌ Recent writes may be lost if primary crashes before replica catches up

Without sharding: All 10B rows on one DB node → single point of scale limit
With sharding:    2.5B rows on Shard 0, 1, 2, 3 each → 4× write throughput

Partition by range of shard key value.

Shard 0: user_id 1 – 25,000,000
Shard 1: user_id 25,000,001 – 50,000,000
Shard 2: user_id 50,000,001 – 75,000,000
Shard 3: user_id 75,000,001 – 100,000,000

✅ Range queries efficient (all results on one or few shards)
✅ Easy to add new shards at end of range
❌ Hot spots: if recent users are most active, highest user_id shard is hot
❌ Uneven distribution if data is skewed

shard = hash(shard_key) % num_shards

User 12345 → hash(12345) % 4 = 2 → Shard 2

✅ Even distribution (hash distributes randomly)
✅ No hot spots
❌ Range queries require scatter-gather (must ask all shards)
❌ Resharding is painful: changing num_shards remaps all keys

Map servers and keys to same hash ring (0 to 2³² positions).
Each key belongs to the nearest server clockwise on the ring.

Adding/removing a server only remaps K/N keys.
(K = total keys, N = total servers → ~1/N fraction remapped)

Virtual nodes: Each physical server → multiple virtual positions on ring.
               Ensures even distribution even with few servers.

Used by: DynamoDB, Cassandra, Memcached clusters

Problem: A single shard key is accessed overwhelmingly more than others.
  Example: Taylor Swift's user_id during a concert ticket release
           A viral post's post_id with millions of concurrent reads

Solutions:
  1. Key suffixing: post_id_0, post_id_1, ..., post_id_9 → distribute across shards
  2. Caching: Put a Redis cache in front; DB shard only for cache misses
  3. Read replicas per shard: multiple replicas for the hot shard
  4. Application-level fan-out: pre-compute and distribute to many buckets

Problem: JOINs across shards are expensive (scatter-gather + merge)

Solutions:
  1. Denormalise: embed related data in the same document/row (NoSQL pattern)
  2. Design sharding key to co-locate related data:
       Shard all of a user's orders by user_id → queries for "my orders" stay on one shard
  3. Use a separate analytics DB (data warehouse) for cross-shard aggregations
  4. Accept scatter-gather for rare complex queries; cache results aggressively

Architecture for read-heavy systems (e.g., 95% reads, 5% writes):

[Writes] → [Primary]
                ├──→ [Replica 1] ←── [Read LB]
                ├──→ [Replica 2] ←── /
                └──→ [Replica 3] ←── /
                        ↑
                [Read traffic distributed by read LB]

Scaling further:
  - Add more replicas (reads scale linearly)
  - Use connection pooling (PgBouncer/ProxySQL) to reduce connection overhead
  - Cache hot reads in Redis → avoid DB altogether for most reads
  - Cross-region replicas for geo-distributed read latency reduction

┌─────────────────────────────────────────────────────────────────┐
│                    DECISION FRAMEWORK                            │
│                                                                 │
│  Need ACID + complex queries?           → PostgreSQL / MySQL    │
│  Need massive write throughput?         → Cassandra / DynamoDB  │
│  Need flexible document schema?         → MongoDB               │
│  Need graph traversals?                 → Neo4j                 │
│  Need time-series + metrics?            → InfluxDB / TimescaleDB│
│  Need full-text search?                 → Elasticsearch         │
│  Need distributed SQL (global)?         → CockroachDB / Spanner │
│  Need in-memory cache?                  → Redis / Memcached     │
│  Need object/file storage?              → S3 / GCS              │
└─────────────────────────────────────────────────────────────────┘