Data Replication & Consistency

Difficulty: Advanced

Question

Explain the CAP theorem. How do different replication strategies handle consistency and availability trade-offs?

Answer

CAP Theorem states that a distributed system can guarantee at most two of three properties: - Consistency (C): Every read receives the most recent write - Availability (A): Every request receives a response (may not be latest) - Partition Tolerance (P): System operates despite network partitions

Since network partitions are inevitable in distributed systems, you must choose between CP (consistent but may be unavailable during partitions) or AP (available but may return stale data).

Replication strategies: 1. Single-Leader: One primary handles writes, replicas handle reads. Strong consistency for writes, eventual for reads. 2. Multi-Leader: Multiple primaries accept writes. Better availability but conflict resolution needed. 3. Leaderless: Any node accepts reads and writes. Uses quorum (W + R > N) for consistency.

Consistency levels: Strong (linearizable), Sequential, Causal, Eventual.

Code examples

Single-Leader Replication

// Single-leader (master-slave) replication
// Write to primary -> replicate to secondaries

// PostgreSQL replication setup
// Primary: postgresql.conf
// wal_level = replica
// max_wal_senders = 5
// synchronous_standby_names = 'replica1'

// Application-level read/write splitting
class DatabaseRouter {
  constructor() {
    this.primary = new Pool({ host: 'primary-db', port: 5432 });
    this.replicas = [
      new Pool({ host: 'replica-1', port: 5432 }),
      new Pool({ host: 'replica-2', port: 5432 })
    ];
    this.currentReplica = 0;
  }

  // Writes always go to primary
  async write(sql, params) {
    return this.primary.query(sql, params);
  }

  // Reads go to replicas (round-robin)
  async read(sql, params) {
    const replica = this.replicas[this.currentReplica % this.replicas.length];
    this.currentReplica++;
    return replica.query(sql, params);
  }

  // Read-your-writes consistency:
  // After a write, read from primary briefly
  async readAfterWrite(sql, params, userId) {
    const lastWrite = await redis.get(`last_write:${userId}`);
    if (lastWrite && Date.now() - parseInt(lastWrite) < 5000) {
      return this.primary.query(sql, params); // Read from primary
    }
    return this.read(sql, params); // Read from replica
  }
}

// Usage
const db = new DatabaseRouter();
await db.write('UPDATE users SET name = $1 WHERE id = $2', ['Alice', 1]);
await redis.set('last_write:1', Date.now(), 'EX', 10);
const user = await db.readAfterWrite('SELECT * FROM users WHERE id = $1', [1], 1);

Read/write splitting directs writes to the primary and reads to replicas. Read-your-writes consistency ensures a user sees their own recent changes by temporarily routing their reads to the primary.

Quorum-Based Consistency

// Leaderless replication with quorum
// N = total replicas, W = write quorum, R = read quorum
// Rule: W + R > N ensures consistency

class QuorumStore {
  constructor(nodes, writeQuorum, readQuorum) {
    this.nodes = nodes;           // e.g., 3 nodes
    this.W = writeQuorum;         // e.g., 2 (write to 2 of 3)
    this.R = readQuorum;          // e.g., 2 (read from 2 of 3)
    // W + R = 4 > N = 3 -> guaranteed consistency
  }

  async write(key, value) {
    const version = Date.now();
    const writePromises = this.nodes.map(node =>
      node.set(key, { value, version }).catch(() => null)
    );

    const results = await Promise.allSettled(writePromises);
    const successes = results.filter(r => r.status === 'fulfilled' && r.value).length;

    if (successes < this.W) {
      throw new Error(`Write quorum not met: ${successes}/${this.W}`);
    }

    return { success: true, version };
  }

  async read(key) {
    const readPromises = this.nodes.map(node =>
      node.get(key).catch(() => null)
    );

    const results = (await Promise.allSettled(readPromises))
      .filter(r => r.status === 'fulfilled' && r.value)
      .map(r => r.value);

    if (results.length < this.R) {
      throw new Error(`Read quorum not met: ${results.length}/${this.R}`);
    }

    // Return the value with the highest version (most recent write)
    const latest = results.sort((a, b) => b.version - a.version)[0];

    // Read repair: update stale nodes
    for (const node of this.nodes) {
      node.set(key, latest).catch(() => {});
    }

    return latest.value;
  }
}

// Quorum configurations:
// N=3, W=2, R=2: Strong consistency, tolerates 1 failure
// N=3, W=1, R=3: Fast writes, slow reads, strong consistency
// N=3, W=3, R=1: Slow writes, fast reads, strong consistency
// N=3, W=1, R=1: Eventual consistency (W+R=2 < N=3)

Quorum ensures that any read overlaps with at least one node that has the latest write. Read repair fixes stale nodes during reads. The W and R values let you tune the consistency vs performance trade-off.

Conflict Resolution in Multi-Leader

// Multi-leader: two primaries accept writes concurrently
// Conflict: both update the same key at the same time

// Strategy 1: Last Write Wins (LWW)
function resolveByTimestamp(conflictA, conflictB) {
  return conflictA.timestamp > conflictB.timestamp ? conflictA : conflictB;
  // Simple but can lose data!
}

// Strategy 2: Merge values (CRDTs)
// Conflict-free Replicated Data Types
class GCounter {
  // Grow-only counter that merges without conflicts
  constructor(nodeId, counts = {}) {
    this.nodeId = nodeId;
    this.counts = counts; // { nodeA: 5, nodeB: 3 }
  }

  increment() {
    this.counts[this.nodeId] = (this.counts[this.nodeId] || 0) + 1;
  }

  value() {
    return Object.values(this.counts).reduce((sum, v) => sum + v, 0);
  }

  // Merge: take max of each node's count
  merge(other) {
    const merged = { ...this.counts };
    for (const [node, count] of Object.entries(other.counts)) {
      merged[node] = Math.max(merged[node] || 0, count);
    }
    return new GCounter(this.nodeId, merged);
  }
}

// Strategy 3: Application-level resolution
async function resolveConflict(key, versions) {
  // Present both versions to the user
  // (like Git merge conflicts)
  // Or use domain-specific rules:
  if (key.startsWith('cart:')) {
    // Shopping cart: union of items
    return mergeCartItems(versions);
  }
  if (key.startsWith('profile:')) {
    // Profile: most recent wins
    return versions.sort((a, b) => b.timestamp - a.timestamp)[0];
  }
}

// DynamoDB approach: vector clocks
// Each write includes a version vector
// [nodeA:3, nodeB:2] vs [nodeA:2, nodeB:3]
// Neither dominates -> conflict detected -> app resolves

Multi-leader replication requires conflict resolution. LWW is simple but lossy. CRDTs merge automatically without conflicts for certain data types. Application-level resolution gives the most control but adds complexity.

Key points

Concepts covered

CAP Theorem, Replication, Eventual Consistency, Strong Consistency, Quorum