Consistency Patterns

Three levels of consistency

When the same data lives on several machines, a write lands on one of them first. Consistency models describe what readers may see while the write spreads.

Eventual consistency in action

The most common source of stale reads is replication lag: the leader has the write, a follower does not yet. If a user writes to the leader and then reads from a follower, their own change seems to vanish.

Guarantees users notice

Full strong consistency is expensive, but a few weaker guarantees fix most of what users actually see:

Quorums: strong reads from replicas

Many replicated stores use quorums. With N replicas, a write succeeds once W replicas have it, and a read asks R replicas and takes the newest value. If R + W > N, every read set overlaps every write set in at least one replica, so the read sees the latest write.

• W = N, R = 1: fast reads, but a write fails if any replica is down.
• W = 1, R = N: fast writes, slow reads.
• W = R = majority (2 of 3, 3 of 5): a common balance that survives a minority of failures.
• R + W ≤ N: faster and more available, but reads can miss the latest write (eventual consistency).

import java.util.*;

class Quorum {
    record Versioned(long version, String value) {}

    // True when every read set must overlap every write set.
    static boolean isStrong(int n, int r, int w) {
        return r + w > n;
    }

    // The newest value among the replicas that answered.
    static Versioned read(List<Versioned> answers, int r) {
        if (answers.size() < r) {
            throw new IllegalStateException("only " + answers.size() + " of " + r + " replicas answered");
        }
        return answers.stream()
            .max(Comparator.comparingLong(Versioned::version))
            .orElseThrow();
    }
}

def is_strong(n, r, w):
    """True when every read set must overlap every write set."""
    return r + w > n

def quorum_read(answers, r):
    """answers: (version, value) pairs from the replicas that replied."""
    if len(answers) < r:
        raise RuntimeError(f"only {len(answers)} of {r} replicas answered")
    return max(answers, key=lambda a: a[0])

Common mistakes

• Making everything strongly consistent "to be safe" and paying for it in latency and outages.
• Spreading reads across followers without handling read-your-writes, so users think their saves failed.
• Assuming eventual means "within a second". Without monitoring replication lag, "eventually" can be minutes during an incident.
• Using R + W ≤ N and expecting reads to always be current.

Interview questions

Try answering out loud before you open each one.

Check yourself

Related topics

• CAP TheoremAvailability and Consistency
• Availability Patterns: Fail-over and ReplicationAvailability and Consistency

Further reading

• Eventually Consistent Werner Vogels, 2008
• Designing Data-Intensive Applications (chapter 5, Replication) Martin Kleppmann, O'Reilly