Database Internals and Storage Engines Questions

Approach summary:

• Goal: strong consistency (serializability) for multi-shard transactions with minimal latency. Two common architectures: centralized 2PC coordinator vs per-transaction distributed consensus (Paxos/Raft). I'll compare both, enumerate failure modes, and give SRE-focused optimizations to reduce latency and avoid deadlocks/long-tail commits.

1. Two-Phase Commit (central coordinator)

• How: Transaction coordinator collects Prepare from involved shard leaders, issues Commit/Abort after all prepared.
• Pros: Simple, smaller consensus surface (only coordinator needs durability), predictable flow, lower steady-state message count.
• Cons: Coordinator is single point of blocking; if coordinator fails after participants prepare, participants block until coordinator recovery or timeout; requires participants to hold locks during prepare→commit window.

Failure modes:

• Coordinator crash after participants prepared → participants block (resource lock) → potential distributed deadlock and availability loss.
• Network partition isolating coordinator → participants either block or time out and abort depending on policy → risk of violating atomicity if misconfigured.
• Participant crash during prepare/commit → coordinator retries; long recovery extends lock hold.

Optimizations (SRE-minded):

• Use coordinator replication (leader-elected via Raft) to remove single-process SPOF while keeping 2PC protocol semantics.
• Short prepared-states: push durable participant prepare to local WAL and release non-essential resources; keep only minimal metadata/locks.
• Deadline/timed aborts + exponential backoff and client-visible retry guidance; surface metrics/alerts on prepared-count and prepared-duration.
• Parallelize remote prepares; piggyback heartbeats; batch small transactions.

2. Distributed consensus per transaction (Paxos/Raft)

• How: Treat transaction commit as a consensus instance across all participants (or a superquorum, or use per-shard Raft with a global coordinator elected via consensus).
• Pros: Survivable — no coordinator single point; consensus ensures liveness under leader changes; participants don't hold prepared locks indefinitely because commit is agreed via replicated log.
• Cons: Much higher latency and message complexity (O(n) consensus per transaction across shards); increased load on quorum leaders and network; complexity implementing multi-shard linearizability.

Failure modes:

• Leader election latency for involved quorums increases commit tail latency.
• Cross-shard consensus requires intersecting quorums; if quorums overlap badly due to failures, progress stalls.
• Network partitions can force repeated elections and long commit tails.

Optimizations:

• Use hierarchical consensus: per-shard Raft + lightweight global coordinator that only sequences transaction ids (not payload) via a small consensus group — reduces data movement.
• Fast-path: if all participants agree and are on same epoch/leader, use a 1 RTT commit (coordinator asks leaders, they respond, coordinator commits in log).
• Use leader locality: prefer shard leaders colocated or route transaction to a node that is leader for most involved shards to reduce cross-datacenter RTTs.
• Use consensus batching (group commits) and speculative execution with safe rollback: execute optimistically and validate commit via short consensus, falling back if validation fails.

Avoiding distributed deadlocks & long-tail commits

• Avoid holding application locks during coordinator/consensus delay; separate logical locks from durable prepare state; use optimistic concurrency control (timestamp ordering / MVCC) so conflicts abort quickly instead of blocking.
• Deadlock detection: maintain wait-for graph per transaction coordinator with timeouts and use transaction timestamps to break cycles deterministically (e.g., wound-wait).
• Bound prepared duration: enforced TTLs with automatic abort and clear observability; surface alerts if prepared-count > threshold.
• Fast failover: replicate coordinators via Raft, keep leadership stable, and use fast leader transfer on overload.
• Client-side: allow idempotent retries and expose clear transient vs permanent error signals.

Operational guidance (SRE)

• SLOs: separate latency SLOs for single-shard vs cross-shard commits; monitor prepared-count, leader-election rate, commit tail percentiles.
• Chaos testing: simulate coordinator and leader crashes, partitions, and long GC pauses; verify automatic cleanup of prepared states.
• Capacity planning: provision network and CPU headroom for consensus leader nodes; prioritize low-latency inter-shard links or colocate hot-shard leaders.
• Observability: trace end-to-end transaction path, track per-transaction RTT across shards, alert on long-tail percentiles (p99.9).

Trade-offs summary:

• 2PC (with replicated/coordinator leaders) is lower steady-state latency but needs careful handling to avoid blocked prepared states.
• Per-transaction consensus gives stronger liveness guarantees at higher latency and complexity; use hybrid designs (local Raft + lightweight global coordinator, fast-path/optimistic commits) to get the best of both worlds.

Brief definitions:

• Read uncommitted: transactions may see uncommitted writes from others (lowest isolation).
• Read committed: each statement sees a snapshot of committed data at statement start; no dirty reads.
• Repeatable read: transaction sees a consistent snapshot from its start for all statements (snapshot isolation).
• Serializable: transactions behave as if executed in some serial order (strongest).

Anomalies allowed (yes = permitted):

• Read uncommitted: dirty read (yes), non-repeatable read (yes), phantom reads (yes), write skew (yes).
• Read committed: dirty read (no), non-repeatable read (yes), phantom reads (yes), write skew (yes).
• Repeatable read (snapshot isolation): dirty read (no), non-repeatable read (no), phantom reads (no for the snapshot), write skew (yes — possible under SI).
• Serializable: dirty read (no), non-repeatable read (no), phantom reads (no), write skew (no).

Notes on PostgreSQL:

• Default level: Read Committed.
• Practical guarantees: PostgreSQL uses MVCC so readers generally don’t block writers and writers don’t block readers. Read Committed gives statement-level consistency: each statement sees only committed rows as of its start (so you won’t see dirty reads, but successive statements in a transaction can see different data). PostgreSQL’s Repeatable Read implements true snapshot isolation (so a transaction sees a stable snapshot), and Serializable (implemented with Serializable Snapshot Isolation / SSI) detects and aborts dangerous patterns (including write skew) to provide full serializability.

Situation: We need to add a populated column to a 50 TB partitioned table distributed across hundreds of nodes with zero/minimal user impact, controlled backfill resource usage, safe rollback, and preserved replica consistency.

Plan (high-level):

1. Add column metadata-only (nullable, no default) to avoid full-table rewrite.
2. Backfill data incrementally, per-partition, with throttled, idempotent workers.
3. Verify per-partition checksums and replication lag; promote column constraints only after verification.
4. Provide rollback by stopping workers and leaving schema in safe state; final destructive changes only after confirmation.

Tools & orchestration:

• Schema change: use the DB’s metadata-only ALTER (e.g., MySQL/InnoDB: ADD COLUMN NULL with no default), or tools like gh-ost/pt-online-schema-change only if metadata change not supported.
• Backfill orchestration: a controller service (Kubernetes / Airflow / Celery) that schedules per-partition backfill jobs across nodes.
• Backfill worker: small binary (Go/Python) reading primary key ranges for a partition, computing column value, writing via batched UPSERTs using transactions where possible.
• Coordination: service stores job state in distributed store (etcd/Zookeeper/DB table) to resume/rollback.

Throttling & resource control:

• Per-worker rate limits (QPS, rows/sec) and batch-size tuning.
• CPU/memory cgroups or Kubernetes resource limits to bound IO/CPU.
• Backoff based on real-time signals: replica lag, disk I/O, CPU, application latency SLOs. Controller polls metrics (Prometheus) and dynamically adjusts concurrency.
• Staged ramp-up: sample partitions -> small percentage -> full rollout with canary partitions.

Replica consistency:

• Preserve replication by performing writes through same write path; monitor replica lag and throttle to keep lag under threshold.
• Ensure idempotency so retries don’t corrupt replicas (use PK-based upserts).
• If using async replication, verify using per-partition checksums (e.g., pt-table-checksum or custom row-hash) before marking complete.

Verification:

• Per-partition row counts and hash checks after backfill; compare primary vs replica.
• Application smoke tests hitting canary partitions to ensure no errors.
• Monitor error rates, latencies, and replica lag metrics; alarms for thresholds.

Rollback and safety:

• Workers are cancellable; controller can pause/stop rollout quickly.
• Because column was added NULL-safe, rollback simply stops backfill and optional DROP COLUMN later after confirming unused.
• If partial writes happened, backfill is idempotent so re-running reconciles state; for destructive rollback, run compensating jobs to set values back to NULL or remove column only after quiescing application.
• Keep slow path in app: read new column, if NULL compute on read until backfill complete to avoid inconsistencies during rollout.

Edge cases & finalization:

• After full verification, add NOT NULL + default in a controlled metadata-only operation (or copy-validate-swap pattern) during low-traffic window.
• Document and run post-mortem and provide runbook for abort/cleanup.

Why this works:

• Metadata-only ADD avoids immediate heavy IO.
• Per-partition, throttled, idempotent backfills minimize impact and allow rapid rollback.
• Active monitoring of replication and application SLOs ensures safety and consistency.

Synchronous vs asynchronous replication — short definitions

• Synchronous replication: master waits until one or more replicas acknowledge the write has been durably persisted before returning success to the client.
• Asynchronous replication: master returns success immediately after local commit; replication to followers happens in the background.

Implications (compare per area)

• Write latency:
  • Synchronous: higher, because each write incurs network + disk latency to replica(s).
  • Asynchronous: lower, single-node commit latency only.
• Durability guarantees / RPO:
  • Synchronous: near-zero RPO for the acknowledged replicas (durability guaranteed up to the acknowledged set).
  • Asynchronous: non-zero RPO — any writes not yet replicated can be lost if master fails.
• Failover complexity:
  • Synchronous: simpler to reason about if quorum/primary selection is well-defined (but requires careful split-brain prevention and quorum management).
  • Asynchronous: simpler runtime but harder during failover — need to detect which replica has the latest state and reconcile divergent logs.
• Risk of data loss on master failover:
  • Synchronous: low (if you require acknowledgement from N replicas, data present on those N nodes).
  • Asynchronous: higher — unreplicated recent commits can be lost.

Operational trade-offs and mitigations

• Synchronous needs reliable, low-latency network and careful capacity planning. Use quorum-based write acknowledgement (e.g., majority) to avoid split-brain.
• Asynchronous often pairs with WAL shipping, ack-level tuning, and point-in-time recovery strategies.

Real-world scenarios where synchronous replication is appropriate despite increased write latency

• Financial systems (payments, ledger): legal/regulatory need zero-loss guarantees for committed transactions.
• Inventory control for high-value items where oversell is unacceptable.
• Billing systems or settlements where each write represents money movement and must be durable before confirming to user.
• Cross-datacenter active-passive setups when compliance demands that write is persisted in both locations before success (with the caveat this increases latency — often acceptable for strong correctness needs).

As an SRE, choose synchronous when business correctness and RPO requirements outweigh increased write latency; choose asynchronous where latency and throughput are paramount and small, bounded RPO is acceptable.

Recommended index strategy (goal: optimize the three query patterns while keeping insert cost reasonable):

1. Frequent read: recent orders per customer sorted by created_at

• Create a composite btree: (customer_id, created_at DESC)
  • Rationale: satisfies WHERE customer_id = ? ORDER BY created_at DESC LIMIT N without additional sort.
  • Example: CREATE INDEX idx_orders_customer_createdat ON orders (customer_id, created_at DESC);

2. Daily aggregation for analytics (GROUP BY date(created_at))

• If table is very large and queries scan long time ranges, use a BRIN index on created_at:
  • CREATE INDEX brin_orders_createdat ON orders USING BRIN (created_at);
  • Rationale: BRIN is small and cheap to maintain for append-mostly timestamp data and speeds range scans for large time windows.
• Optionally, provide a covering index if analytics query filters by customer_id too: (created_at, total_amount) is not typical; instead rely on BRIN + sequential scan of relevant pages.

3. Search by status and amount range

• Use a partial composite index for common statuses to reduce index size:
  • CREATE INDEX idx_orders_status_amount_active ON orders (total_amount) WHERE status = 'confirmed';
  • Or a multicolumn btree if status is low-cardinality and often combined: CREATE INDEX idx_orders_status_amount ON orders (status, total_amount);
  • Rationale: partial index reduces disk & maintenance if queries mostly target a subset of statuses.

Trade-offs

• Each additional btree index increases insert/commit latency (random I/O, WAL) and disk usage roughly proportional to index size. At 10k inserts/sec this can become significant.
• BRIN has minimal maintenance cost and tiny disk footprint but less selective—best for time-range scans on naturally clustered timestamps.
• Partial indexes reduce size and maintenance but only help queries matching the predicate.
• If you need very low insert latency, prefer BRIN + fewer btree indexes, or offload heavy analytics to a replica/warehouse.

Monitoring & validation under 10k inserts/sec

• Track index usage & effectiveness:
  • pg_stat_user_indexes: idx_scan to see if index is used.
  • pg_stat_all_indexes or pg_stat_user_tables: idx_tup_fetch / seq_scan ratios.
  • pg_stat_statements: observe query latency and frequency; compare EXPLAIN ANALYZE before/after.
• Monitor insert pipeline health:
  • WAL generation, wal_bytes, and replication_lag (if replicas used).
  • Insert latency/commit time (application metrics).
  • IO metrics: disk throughput, iops, avg latency.
• Monitor index health and bloat:
  • pgstattuple, pg_repack estimates, or pg_catalog.pg_index_size.
  • autovacuum activity and vacuum pause/queue metrics.
• Alerting:
  • Significant rise in avg insert latency, sustained high wal_bytes/sec, increased seq_scan for targeted queries (indicates index not used), growth in index bloat or IO saturation.
• Validation process:
  • Baseline with no new indexes: capture typical p95/p99 latencies, explain plans.
  • Add index in staging/replica, run representative workload, measure p99 insert latency, idx_scan increases, total query CPU/IO.
  • Iterate: drop or convert indexes (btree -> partial or BRIN) if insert cost too high.

Practical tip: deploy analytics-heavy indexes on a read replica or ETL into a columnar store when 10k/sec inserts plus complex analytics create conflicting demands.