Chapter 8: Replication

Introduction

The chapter introduces redundancy as a way to preserve durable promises when components can fail.

• Durability as a lasting promise: Explain that durability means a committed transaction’s effects remain permanent, and describe why a business may rely on that promise before taking another action.
  Why it matters: A system’s acknowledgment is useful only if others can safely act on it.
• Failures and the need for redundancy: Distinguish the failure-free theoretical model from a practical model where components can fail, and explain why redundancy is added to avoid a single point of failure that could break a promise to users.
  Why it matters: Replication begins with the problem that one failing component may leave a system unable to honor its commitments.

Key terms: durability, committed transaction, ACID guarantees, theoretical system model, practical system model, Crash-Stop, Crash-Recovery, single point of failure, redundancy

8.1 Redundancy

The section defines redundancy as duplication plus coordination, then uses a replicated logic gate to show how it improves reliability while explaining its less straightforward effect on scalability.

• Duplication and coordination: Explain that redundancy duplicates subsystems and coordinates them so the copies act as one coherent system; replication is a common way to duplicate something.
  Why it matters: Copies alone do not make a working system; the way they work together matters.
• Static and dynamic redundancy: Distinguish static redundancy, whose components and interactions remain fixed during the system's lifetime, from dynamic redundancy, whose components and interactions can change.
  Why it matters: The distinction clarifies what can change in a redundant system while it runs.
• Redundant logic gate example: Trace how three copies of a logic gate and majority voting replace a single point of failure: one failed gate can be outvoted, and the majority gate is itself replicated to avoid becoming a single point of failure.
  Why it matters: The example makes the need for both duplication and coordination concrete.
• Redundancy and scalability relationship: Explain that redundancy can improve reliability and may aid scalability by distributing data across nodes and load across replicas, but it can sometimes decrease scalability instead.
  Why it matters: More copies do not automatically mean a system can handle more load.

Key terms: redundancy, duplication, coordination, replication, static redundancy, dynamic redundancy, logic gate, majority gate, majority vote, single point of failure

8.2 Thinking about replication and consistency

The section uses a library’s copies and editions of one book to show why replication and consistency depend on how we define an item and decide which copies count as equivalent.

• Logical books and physical copies: Distinguish the author’s book as a logical item from the physical copies held by a library, and explain why counting copies alone does not settle what counts as a replica of that item.
  Why it matters: Replication requires a clear idea of what the copies are supposed to represent.
• Edition equivalence and inventory counts: Explain how different judgments about whether SICP editions count as the same book yield different inventory counts: ten if any edition qualifies, eight if only the Scheme editions qualify, or two if only the JavaScript edition qualifies. Relate those judgments to the section’s questions of identity and equivalence—“oneness” and “sameness.”
  Why it matters: Whether replicas count as the same item depends on the equivalence standard being applied.

Key terms: logical item, physical item, replication, edition, identity, equivalence, oneness, sameness

8.3 Replication

This section defines replication and explains how replication transparency balances the illusion of one object against consistency, availability, and latency.

• Replicas and reliability: Explain that replication represents one logical object with multiple identical physical objects, called replicas, to improve reliability beyond the limits of a single object.
  Why it matters: This distinction between one logical object and multiple physical replicas underpins the chapter’s discussion of replication.
• Replication transparency tradeoffs: Describe replication transparency as hiding multiple replicas behind the illusion of one object, while deciding which replication details to conceal or reveal in light of consistency, availability, and latency.
  Why it matters: The single-object illusion shapes the tradeoffs users experience when a system uses replicas.

Key terms: replication, logical object, physical objects, replicas, replication transparency, consistency, availability, latency

8.4 The mechanics of replication

This section introduces why replicating changing state is harder than replicating static or stateless components, and uses a counter to explain monotonicity.

• Stateless and stateful replication: Distinguish redundant deployment of stateless services from replication of stateful components, and explain why the section focuses on the latter.
  Why it matters: Recognizing stateless redundancy as replication makes clear where the harder problems begin.
• Changing state and propagation: Explain why replicating an unchanging object is straightforward but replicating a changing one requires its changes to propagate properly. Describe the section’s simplified key-value-store example, in which the whole dataset fits on one node and partitioning is ignored.
  Why it matters: Propagation of changes is the source of the replication complexity examined next.
• Monotonicity of counter changes: Explain monotonicity as the property that a new change does not contradict current knowledge, using the counter threshold example to contrast increment-only changes with a possible reset.
  Why it matters: The counter shows that different kinds of change have different consequences for what a replica can safely conclude.

Key terms: stateless components, stateful components, load-balance, key-value store, partitioning, propagate, monotonicity, increment, reset

8.4.1 System model

This section sets out the component, network, and failure assumptions used to reason about replication and network partitions.

• Component and link model: Describe a distributed system as concurrent components exchanging messages, with one component or the network taking a step at a time. Explain the shift from a central network component to point-to-point links and how it makes partitions easier to visualize.
  Why it matters: The link model makes it possible to reason about which replicas can communicate during a partition.
• Failures and partition assumptions: State that the system is partially synchronous, its components may suffer Crash-Stop, Omission, or Crash-Recovery failures, and its network is unreliable. Describe message loss in this replication context as a partition caused by failure of one or more communication links.
  Why it matters: These assumptions define the failures that replication must contend with.

Key terms: concurrent components, messages, point-to-point communication links, network partitions, partially synchronous, Crash-Stop failure, Omission failure, Crash-Recovery failure, unreliable network, network partition

8.4.2 Replication lag

This section explains why replicas inevitably lag behind changes, why that lag matters, and how failures can add to it.

• Inherent replication lag: Explain why a change cannot appear on every replica instantaneously and how the resulting lag can threaten replication transparency.
  Why it matters: Even without failures, replicas can temporarily reflect different states.
• Sources of additional lag: Distinguish unavoidable inherent replication lag from imposed replication lag caused by network partitions or component failures.
  Why it matters: The distinction separates the delay replication always has from delay caused by disruptions.

Key terms: replication lag, inherent replication lag, replication transparency, imposed replication lag, network partitions, component failures

8.4.3 Synchronous vs. asynchronous replication

This section contrasts when operations complete under synchronous and asynchronous replication and explains a hybrid approach that waits for a quorum.

• Replication completion timing: Distinguish synchronous replication, which completes an operation only after every other node has replicated the change and acknowledged it, from asynchronous replication, which completes it once the initial node has processed it without waiting for other nodes.
  Why it matters: The point at which an operation is called complete determines what a client can assume about the replicas.
• Synchronous replication tradeoff: Explain that waiting for every node gives synchronous replication immediate consistency across nodes, but can affect latency and availability because completion depends on every node responding in time.
  Why it matters: This tradeoff explains why a system might avoid waiting for every replica.
• Quorum hybrid replication: Describe the hybrid strategy in which a majority of replicas, called a quorum, must acknowledge an operation in the foreground, while replication to replicas outside the quorum can proceed asynchronously in the background.
  Why it matters: A quorum shows how systems can require some acknowledgments without waiting for every replica.

Key terms: synchronous replication, asynchronous replication, acknowledgments, foreground, background, immediate consistency, latency, availability, hybrid strategy, quorum

8.4.4 State-based vs. log-based replication

This section contrasts replicating a system’s current state with replicating the operations that produce it, under a deterministic state-machine assumption.

• State and operation replication: Distinguish state-based replication, which sends the current state or a diff, from log-based replication, which sends the sequence of operations. Apply both approaches to the counter example: increment-by(2) followed by increment-by(3).
  Why it matters: The distinction clarifies whether replicas receive a result or the operations that produce it.
• Deterministic state machine premise: Explain why the discussion assumes a deterministic state machine: replicas starting in the same state and applying the same operations in the same order arrive at the same state.
  Why it matters: Without that premise, sending identical operations would not guarantee identical resulting states.

Key terms: state-based replication, log-based replication, current state, sequence of operations, deterministic state machine, start state, same operations, same order

8.4.5 Single-leader, multileader, and leaderless systems

This section compares replication configurations by who can accept operations, the conflicts they create, and how replication lag affects reads from followers.

• Replication leadership configurations: Distinguish single-leader, multileader, and leaderless replication by which nodes can accept operations and how changes reach followers where applicable.
  Why it matters: Who can accept an operation determines how a replicated system handles requests and coordinates changes.
• Leadership and conflict tradeoffs: Explain why a single leader can become a single point of failure, while multileader and leaderless systems can face conflicts from concurrent operations. Describe why conflict resolution needs care, using last write wins as an example.
  Why it matters: Removing reliance on one leader does not remove the need to handle competing updates correctly.
• Follower reads and freshness: Explain why the shorthand 'leaders handle writes, followers handle reads' is incomplete: follower reads can improve performance but may be stale because updates take time to propagate, so reads requiring the newest data must go to the leader.
  Why it matters: A read-serving choice can change whether a client sees the most recent update.

Key terms: single-leader, multileader, leaderless, leader, follower, single point of failure, conflict resolution, last write wins, conflict-free replicated data types (CRDTs), replication lag

8.5 Summary

This summary connects redundancy and replication to reliability, then recaps the consistency tradeoffs and two ways to propagate replicas.