Forge Learn/Algorithms Behind Distributed Systems

Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Quorum Reads & Writes

6 min read

You'll learn to

-State the R + W > N rule and explain why it guarantees read/write overlap
-Reason about the availability and consistency tradeoff as R and W change
-Implement a basic quorum check for reads and writes

Vector clocks let you detect when two writes conflict. Quorum reads and writes are a strategy for making conflicts rarer in the first place, by controlling exactly how many replicas must participate in every read and every write. The Quorum Reads & Writes level asks you to implement the rule that governs that: R + W > N.

N, W, and R

Say a piece of data is replicated across N nodes. A write is considered successful once it has been acknowledged by W of those nodes, not necessarily all N, waiting for every single replica would make the system unavailable the moment any one node is slow or down. A read is considered successful once it has collected responses from R nodes and returned the most recent value among them. N, W, and R are all configurable per system, and the relationship between them determines the system's consistency guarantees.

Why R + W > N Guarantees Freshness

If R + W > N, then any set of W nodes that accepted a write and any set of R nodes consulted on a subsequent read must share at least one node in common. You cannot pick W nodes and R nodes out of a pool of N that are entirely disjoint once their sizes add up to more than N. That overlapping node is guaranteed to have seen the latest write, so a quorum read is guaranteed to observe it, once the client compares the versions returned by the R nodes and picks the newest. This is a pigeonhole argument: you cannot split N nodes into two groups of size W and R with no shared member if W + R exceeds N.

The R + W > N check is one line, but it is the line that determines whether the whole system can silently serve stale data.

def has_read_your_write_guarantee(n: int, w: int, r: int) -> bool:
    """R + W > N guarantees every read overlaps at least one node
    from the most recent successful write."""
    return r + w > n


def quorum_write(replica_acks: int, w: int) -> bool:
    """A write succeeds once w replicas have acknowledged it."""
    return replica_acks >= w


def quorum_read(responses: list, r: int):
    """A read succeeds once r replicas have responded; return the
    value with the highest version among those that responded."""
    if len(responses) < r:
        return None  # not enough replicas responded, read fails
    return max(responses, key=lambda entry: entry["version"])["value"]


# Example: N=5 replicas. W=3, R=3 -> 3+3=6 > 5, so every quorum
# read is guaranteed to overlap the most recent quorum write.
assert has_read_your_write_guarantee(n=5, w=3, r=3) is True
# W=2, R=2 -> 2+2=4, not > 5: reads can miss the latest write entirely.
assert has_read_your_write_guarantee(n=5, w=2, r=2) is False

def has_read_your_write_guarantee(n: int, w: int, r: int) -> bool:
    """R + W > N guarantees every read overlaps at least one node
    from the most recent successful write."""
    return r + w > n

def quorum_write(replica_acks: int, w: int) -> bool:
    """A write succeeds once w replicas have acknowledged it."""
    return replica_acks >= w

def quorum_read(responses: list, r: int):
    """A read succeeds once r replicas have responded; return the
    value with the highest version among those that responded."""
    if len(responses) < r:
        return None  # not enough replicas responded, read fails
    return max(responses, key=lambda entry: entry["version"])["value"]

# Example: N=5 replicas. W=3, R=3 -> 3+3=6 > 5, so every quorum
# read is guaranteed to overlap the most recent quorum write.
assert has_read_your_write_guarantee(n=5, w=3, r=3) is True
# W=2, R=2 -> 2+2=4, not > 5: reads can miss the latest write entirely.
assert has_read_your_write_guarantee(n=5, w=2, r=2) is False

The Tradeoff: Consistency vs Availability

Raising W and R closer to N strengthens consistency guarantees but weakens availability. A write or read now needs more nodes to be up and responsive, so any given request is more likely to fail during a partial outage. Lowering W and R, for example W=1, R=1, write to any one node and read from any one node, maximizes availability at the cost of consistency, since R + W will not exceed even a small N, so reads can easily miss the latest write. This is the same tension the CAP theorem describes at a higher level. Quorum's N, W, R knobs are how a real system tunes exactly where on that spectrum it wants to sit, and different data in the same system often pick different tradeoffs.

A useful sanity check for an interview: with N=3, W=2, R=2 (a very common default in Cassandra/DynamoDB-style stores), R+W=4 > N=3, so you get the freshness guarantee while tolerating one node being down for either a read or a write.

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Ready to Build This?

The Quorum Reads & Writes level has you implement the W-acknowledgment and R-response logic and enforce R + W > N, the rule that lets a replicated store balance consistency against availability instead of choosing an all-or-nothing extreme.

Vector Clocks: Ordering Events Without a Shared Clock Simple Sorts: Bubble, Insertion & Selection

Discussion0

Join the Discussion

No comments yet. Be the first to start the thread!