Database
Design

Picking the right database is the first signal in any system design. Each type has a distinct data model, consistency profile, and performance envelope.

ACID vs BASE

Transaction Isolation Levels

-- Composite index: column order = selectivity order (most selective first)
CREATE INDEX idx_orders ON orders(user_id, status, created_at);
-- Supports: WHERE user_id=? | WHERE user_id=? AND status=?
-- Ignores:  WHERE status=? (leftmost prefix rule)

-- Covering index: avoids heap fetch entirely
CREATE INDEX idx_covering ON orders(user_id) INCLUDE (total, created_at);

-- Partial index: index only what you query
CREATE INDEX idx_pending ON orders(created_at) WHERE status = 'pending';

-- Expression index: on computed values
CREATE INDEX idx_email_lower ON users(LOWER(email));

-- EXPLAIN ANALYZE — always verify your index is used
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE user_id = 123;

Sharding splits data across multiple nodes when a single machine can't handle the volume. It's a last resort — exhaust vertical scaling, read replicas, and caching first.

Consistent Hashing — Virtual Nodes

Hotspot Problem & Solutions

-- Problem: celebrity/viral user gets millions of requests → single shard overloaded

-- Solution 1: Shard key salting — spread one user across sub-shards
shard_key = user_id + "_" + random(1, 100)    // write to 100 sub-shards
// Read: query all 100, merge results (scatter-gather)

-- Solution 2: Dedicated shard for known hot keys
IF user_id IN hot_users_list:
    route_to_dedicated_hot_shard(user_id)

-- Solution 3: Cache in front of shard
-- Absorb read spikes with Redis before hitting the shard

-- Solution 4: Time-based compound key for time-series
BAD:  shard_key = device_id          -- all writes go to same shard
GOOD: shard_key = (device_id, month) -- distributes over time

Cross-Shard Operations — The Hard Part

Replication Topologies

// Problem: User posts a tweet, reads feed, doesn't see their own tweet
// Cause: read served from replica lagging 200ms behind primary

// Solution 1: Route reads to primary for 1 second after write
function read(userId, lastWriteTime):
  if now() - lastWriteTime < 1000ms:
    return primary.read()   // strong consistency window
  return replica.read()     // eventual after window

// Solution 2: Replication tokens — read from replica that has seen the write
write_token = primary.write(data)           // returns LSN/position
replica.read(min_lsn=write_token)           // waits for replica to catch up

// Solution 3: Sticky sessions — same user always hits same replica

Cache Placement Strategies

Cache Eviction Policies

The Three Cache Failure Modes

// Hard problem: "There are only two hard things in CS..."

// 1. TTL-based (simplest) — accept brief staleness
cache.set(key, value, ttl=300)   // expires in 5 minutes regardless

// 2. Event-driven invalidation
on_db_write(user_id):
  cache.delete(f"user:{user_id}")    // invalidate on write
  // Next read will repopulate from DB

// 3. Write-through with version tag
version = db.increment("user_version:{id}")
cache.set(f"user:{id}:{version}", data, ttl=3600)

// 4. CDC (Change Data Capture) — Debezium reads WAL
// DB WAL → Kafka → cache invalidation consumer
// Most reliable for complex invalidation logic

// 5. Two-level cache (L1 local + L2 Redis)
L1 = process_memory_lru(max=1000, ttl=10s)   // ultra-fast, small
L2 = redis_cluster(ttl=300s)                // shared across instances

Locking Strategies

-- Pessimistic: lock the row immediately
BEGIN;
SELECT balance FROM accounts WHERE id = 42 FOR UPDATE;  -- row locked
UPDATE accounts SET balance = balance - 100 WHERE id = 42;
COMMIT;  -- lock released

-- Optimistic: version-based CAS
SELECT balance, version FROM accounts WHERE id = 42;
-- ... do processing ...
UPDATE accounts
  SET balance = balance - 100, version = version + 1
  WHERE id = 42 AND version = 7;  -- fails if version changed
-- If 0 rows affected → conflict, retry

Deadlocks — Detection & Prevention

-- Prevention rule: always acquire locks in the same global order
-- BAD: T1 locks user_A then account_B; T2 locks account_B then user_A → deadlock

-- GOOD: always lock by ascending ID
ids = sorted([user_id, account_id])
FOR id IN ids:
  SELECT * FROM resources WHERE id = id FOR UPDATE

-- Set lock timeout to avoid indefinite waits
SET lock_timeout = '2s';

-- Use SKIP LOCKED for queue-like workloads (no blocking)
SELECT * FROM jobs WHERE status = 'pending'
LIMIT 1 FOR UPDATE SKIP LOCKED;

MVCC — How Postgres Avoids Read-Write Contention

Multi-Version Concurrency Control stores multiple versions of each row. Readers see a consistent snapshot of the DB at their transaction start time — they never block writers, writers never block readers.

-- Each row has hidden system columns:
--   xmin: transaction ID that inserted this version
--   xmax: transaction ID that deleted/updated (0 = live)

-- Snapshot isolation: your transaction sees rows where
--   xmin <= your_txn_id AND (xmax = 0 OR xmax > your_txn_id)

-- Consequence: old versions accumulate → VACUUM reclaims them
-- VACUUM FREEZE prevents transaction ID wraparound (32-bit overflow)
-- autovacuum_freeze_max_age = 200M transactions (monitor this!)

Write Amplification & Hot Row Contention

-- Problem: global counter row gets thousands of updates/sec
-- BAD: single row counter — serialized writes, massive contention
UPDATE counters SET count = count + 1 WHERE key = 'page_views';

-- GOOD: Sharded counters — N rows, randomly pick one to increment
shard = random(0, 99)
UPDATE counters SET count = count + 1
  WHERE key = 'page_views' AND shard = shard;
-- Read: SELECT SUM(count) FROM counters WHERE key = 'page_views'

-- BETTER: Buffer increments in Redis INCR, flush to DB in batches
redis.incr("page_views")   // O(1), no DB contention
// Background job flushes Redis→DB every 10s

Distributed Locking

// For cross-service mutual exclusion — e.g. cron job should run once

// Simple single-node lock
acquired = redis.set(
  "lock:job_name",
  "owner_uuid",
  NX=True,          // only set if Not eXists
  PX=30000          // auto-expire in 30s (prevents deadlock on crash)
)

if acquired:
  try:
    do_work()
  finally:
    // Release ONLY if we still own it (Lua script for atomicity)
    redis.eval("""
      if redis.call('get', KEYS[1]) == ARGV[1] then
        return redis.call('del', KEYS[1])
      end
    """, ["lock:job_name"], [owner_uuid])

// Redlock: acquire on N/2+1 independent Redis nodes for safety
// Clock skew and GC pauses can still cause split-brain — use with care