Replication, consistency and fault tolerance notes — Unit 4

Replication is the process of maintaining multiple copies of data across different nodes in a distributed system.

⇒1.1 Key Motivations

• Reliability / Fault Tolerance: If one node holding data crashes, the system can simply switch to another node holding a replica. Data is not lost.
• Performance: If users in Tokyo and New York both need a file, placing a replica in both cities drastically reduces read latency. It also load-balances requests across multiple servers.

Replication introduces a massive problem: Keeping the copies synchronized. If a user updates Replica A, Replicas B and C are immediately out of date. If another user reads from Replica B before the update propagates, they see stale (inconsistent) data.

⇒2.1 The Trade-off

To keep data perfectly consistent, you must lock all replicas, update all of them over the network, and then unlock them. This makes write operations incredibly slow and ruins performance.

A consistency model is a contract between the processes and the data store. If processes obey certain rules, the store promises to work correctly.

⇒3.1 Strict Consistency

Any read on a data item `x` returns a value corresponding to the result of the most recent write on `x`. This requires an absolute global clock, making it impossible to implement in real distributed systems.

A slightly weaker, but implementable model. The result of any execution is the same as if the (read and write) operations by all processes on the data store were executed in some sequential order.

⇒4.1 The Rule

It does not matter what the absolute 'real time' order of operations was. What matters is that ALL processes see the EXACT SAME order of events.

If P1 writes A, then P2 writes B, it is perfectly fine if everyone sees B written before A. But it is a violation if P3 sees A then B, while P4 sees B then A.

Weaker than sequential. It differentiates between events that are causally related and those that are concurrent.

⇒5.1 The Rule

Writes that are potentially causally related must be seen by all processes in the same order. Concurrent writes may be seen in a different order on different machines.

For example, if I post a comment (Write 1), and you reply to it (Write 2), everyone MUST see Write 1 before Write 2. But if two unrelated users post different comments at the same time, some nodes can see user A's comment first, and other nodes can see user B's first.

The weakest model, but the most common in modern web architectures (like DNS or social media profiles).

⇒6.1 The Guarantee

If no new updates are made to a given data item, eventually all accesses to that item will return the last updated value. There are no ordering guarantees while updates are actively happening.

This provides maximum performance and availability. If you change your Twitter bio, it's fine if users in Europe see the old bio for another 5 minutes, as long as it eventually updates.

Focuses on the perspective of a single client moving between replicas.

⇒7.1 Models

• Monotonic Reads: If a client reads data `x`, any successive read by that client will always return that same value or a more recent value (never an older one).
• Monotonic Writes: A write by a client on `x` is completed before any successive write on `x` by the same client.
• Read Your Writes: The effect of a write by a client will always be seen by a successive read by the same client.

Where, when, and by whom should replicas be placed?

• Permanent Replicas: The core static set of replicas (e.g., three main database servers in a cluster).
• Server-Initiated Replicas: A web server notices a file is highly requested, so it dynamically creates a local copy (like a CDN).
• Client-Initiated Replicas: Client caches (like your web browser caching images to load pages faster).

When a replica is updated, how is that change propagated?

• Primary-Based Protocols: All write operations must be sent to a single designated 'Primary' server. It orders the writes and pushes them to the backups. Safe, but the primary is a bottleneck.
• Replicated-Write Protocols: Any replica can accept a write. Write conflicts are resolved using timestamps or voting (Quorum). Highly available but complex conflict resolution.

Used in Replicated-Write systems (like Cassandra) to guarantee consistency without requiring every single node to be online.

⇒10.1 Read and Write Quorums

Let `N` be total replicas, `W` be Write Quorum, `R` be Read Quorum.

To safely read/write, you must follow the rule: `W + R > N`.

If `N=5`, and you require writes to reach `W=3` nodes to be 'successful', then reading requires `R=3` nodes. Because `3 + 3 = 6 > 5`, the read group and write group are mathematically guaranteed to overlap by at least one node, meaning the read will always pull the latest data.

A system is fault-tolerant if it can continue to function in the presence of faults.

⇒11.1 Concepts

• Fault: The mechanical or algorithmic cause (e.g., a cosmic ray flipping a bit in RAM).
• Error: The manifestation of the fault (the program calculates 2+2=5).
• Failure: The system stops meeting its specifications (the server crashes and drops user connections).

Fault tolerance aims to catch Errors before they result in a system Failure.

The primary technique for hiding failures is redundancy.

• Information Redundancy: Adding extra bits (like parity bits or Hamming codes) to data to allow error detection and correction.
• Time Redundancy: If an action fails, simply try it again. Highly effective for transient network drops.
• Physical Redundancy: Having backup hardware. (e.g., Triple Modular Redundancy (TMR) where three chips calculate the same equation and vote on the answer).

Proposed by Eric Brewer, this is the most famous theorem in distributed systems.

⇒13.1 The Three Guarantees

• Consistency: Every read receives the most recent write.
• Availability: Every request receives a (non-error) response, without the guarantee that it contains the most recent write.
• Partition Tolerance: The system continues to operate despite an arbitrary number of network messages being dropped or delayed.

The theorem states that a distributed data store can simultaneously provide at most two of these three guarantees.

• Replication: Crucial for reliability and scaling, but breaks consistency.
• Consistency Models: Range from Strict (impossible) to Eventual (highly performant but allows stale reads).
• Quorums: Allow safe reading/writing across replicas without needing all replicas to be online.
• CAP Theorem: You must choose between Consistency and Availability during a network Partition.