Consistency Models and Distributed Databases Questions

Direct answer

Dynamo-style databases commonly expose three consistency levels an application can choose per operation: strong (contact every replica / ALL), quorum (majority, R + W > N), and eventual (contact one replica / ONE). Strong consistency contacts every replica and always returns the latest committed write, at the cost of the highest latency and the lowest availability during a partition; eventual consistency returns whatever a nearby replica has, fastest and most available, but possibly stale; quorum consistency sits between the two, requiring only a majority of replicas to agree (R + W > N), which gives a strong practical guarantee (every read quorum is guaranteed to overlap every write quorum in at least one replica) without paying the cost of contacting every single replica on every operation.

Structured elaboration

• Strong (ALL) reads: the read is guaranteed to reflect the most recent successful write, as if there were only one copy of the data. Implemented by requiring every replica (R = N or W = N) to participate, or by always routing to the current write leader in systems that have one.
• Eventual (ONE) reads: the read may return an older value if it lands on a replica that has not yet received the latest write. Implemented by reading from whichever single replica is closest or least loaded, no quorum coordination required.
• Quorum (majority) reads: a read or write is acknowledged only after a majority of replicas respond (for N=3, a quorum is 2; for N=5, a quorum is 3). Choosing R and W so that R + W > N guarantees every read quorum overlaps every write quorum by at least one replica, so a quorum read is guaranteed to see the most recent quorum-acknowledged write, without the latency and availability cost of waiting on every single replica the way ALL does.

Worked example

• Strong (ALL) reads: a user checks their own account balance immediately after a transfer. They must see the transfer reflected, so the read pays the latency cost of confirming with every replica (or the leader).
• Eventual (ONE) reads: a public-facing "total likes on this post" counter. A read that is a few seconds behind is invisible to the user experience and the read stays cheap and highly available.
• Quorum reads: an inventory count during checkout, where ALL would be too slow and too fragile (any single slow replica blocks the read), but ONE risks showing stale stock and overselling the last unit. QUORUM (for N=3, R=2, W=2, so R+W=4 > N=3) gives a strong, majority-backed answer while still tolerating one replica being slow or down, which is the practical default most production Dynamo-style deployments reach for when they need "correct and fast" rather than either extreme.

Trade-offs and pitfalls

The three levels are a latency/availability-versus-freshness dial, not a correctness hierarchy where "stronger is always better." Choosing ALL for every read on a high-traffic, low-stakes field (like a like-counter) needlessly funnels all that traffic through every replica and makes the system less available during a partition, for a guarantee the product never needed. The common mistake is picking the strongest level available "to be safe" instead of matching the level to what a stale read would actually cost.

Direct answer

The core idea is that consistency becomes a parameter on each request rather than a fixed property of the whole database: the service stores each key with N replicas, and a client picks linearizable, causal, or eventual per key (or even per call) by choosing how many replicas the coordinator must contact and what ordering metadata it must check before returning. Linearizable calls pay a quorum round-trip and a version check; causal calls pay a smaller round-trip to confirm the client's own prior writes are visible; eventual calls pay almost nothing, a single nearby replica answers immediately.

Structured elaboration

• Components: a stateless coordinator layer that receives requests and fans them out to the replica set for a key; a replica store (each replica holds the key's value plus version metadata); a client library that lets the caller specify the desired consistency level per request and hides the fan-out/quorum logic behind a simple get(key, consistency) / put(key, value, consistency) API.
• Client behavior per tier:
  • Linearizable: the coordinator contacts a write quorum on put and a read quorum on get, sized so that R + W > N, guaranteeing every linearizable read sees the latest linearizable write.
  • Causal: the client library attaches a small causal-context token (a version vector covering the keys that client has previously read or written) to each request; the coordinator ensures the read reflects at least that context before returning, without requiring a full quorum.
  • Eventual: the coordinator returns whatever the nearest reachable replica has, no version check, no quorum.
• Failure handling: if a linearizable request cannot reach a quorum (say, during a partition), it must fail loudly rather than silently downgrading to a weaker guarantee the caller did not ask for; a causal or eventual request degrades more gracefully, since a caller who already accepted weaker guarantees can tolerate serving from fewer replicas.
• Routing and replication: replicate asynchronously to all N regions for eventual/causal reads to stay fast everywhere; for linearizable operations, route the quorum check to whichever replicas are needed to satisfy R or W, which usually means at least one round trip leaves the client's local region if the quorum cannot be satisfied locally.
• Meeting the 10,000-requests-per-second-per-region target: the coordinator layer is stateless, so it scales horizontally behind a load balancer, independent of the consistency tier a given request uses. The eventual and causal tiers carry almost none of the quorum-coordination cost, so most of the traffic (whichever tiers the workload's key mix favors) never becomes a bottleneck; the linearizable tier is the one that needs headroom planning, since every linearizable call consumes capacity on W replicas at once, so the replica set's write capacity, not the coordinator, becomes the limiting factor if a large share of traffic requests the strongest tier.

Worked example (executed quorum arithmetic for the linearizable tier)

For N=5 replicas and a fixed read quorum R=2, what is the minimum write quorum W that still guarantees linearizable reads, and what happens to that guarantee if W is set one lower?

def strongly_consistent(N, R, W):
    return (R + W) > N
min_W = N - R + 1  # = 5 - 2 + 1 = 4

Running this: with N=5, R=2, the minimum W is 4 (executed; confirmed). At W=4, strongly_consistent(5, 2, 4) returns True; at W=3 (one less), it returns False (executed; both confirmed). That single-replica difference is the entire gap between a linearizable guarantee and none: at W=4 the read quorum (2) and write quorum (4) are guaranteed to overlap in at least one replica, so any read is guaranteed to see the latest write; at W=3, R+W=5 equals N rather than exceeding it, so a read quorum and a write quorum can land on entirely disjoint sets of replicas and a client can read a stale value. Under a single node failure, this linearizable configuration (W=4 of 5) can still accept writes (4 of the remaining 4 healthy replicas can still form the quorum only if exactly one has failed; a second simultaneous failure would block writes entirely), which is the concrete availability cost of choosing the strongest tier.

Trade-offs and pitfalls

The main pitfall is letting a caller request "linearizable" and silently getting something weaker during a partition, which is worse than an honest failure, because the caller has no way to know their guarantee was violated. The API must make that distinction explicit (an error, not a downgraded success) for the linearizable tier specifically, while causal and eventual tiers can be designed to degrade gracefully since the caller already accepted a weaker guarantee going in. A second pitfall is ergonomics: if choosing the wrong tier for a given field is easy to do by accident (say, a default that quietly falls back to eventual), the client library should make the strongest-needed tier the explicit default for anything touching money or safety, and require an opt-in to relax it, rather than the reverse.

Direct answer

Once you already know two replicas disagree (read-repair and anti-entropy are how you detect that in the first place), the resolution toolkit has three pieces, and each answers a different question about what to do next. Vector clocks tell you whether two writes are genuinely concurrent or one causally follows the other, but do not by themselves pick a winner; last-write-wins (LWW) picks a winner by timestamp and silently discards the loser; CRDTs (Conflict-free Replicated Data Types) are data structures designed so that any two divergent replicas merge back into the same value automatically, with no discarded data and no coordination required.

Structured elaboration

• Vector clocks: each replica keeps a per-node counter, incremented on every local write. Comparing two vector clocks tells you if one is causally "before" the other (safe to just keep the later one) or "concurrent" (a true conflict). Vector clocks are a detection mechanism, not a resolution policy: they tell you a conflict exists, not what to do about it. A common resolution policy layered on top (the one Amazon's original Dynamo system uses) is to keep both concurrent versions as sibling values, return them together on the next read, and let the client or an application-level merge function decide; the shopping-cart use case merges siblings by unioning their items rather than picking one and discarding the other. The trade-off: if a client instead applies a naive "just pick one" policy (an implicit last-write-wins on top of vector-clock-detected concurrency), the discarded sibling's write is lost with no record it ever existed, which is exactly the failure the sibling-return approach is designed to avoid, at the cost of pushing the merge decision onto every client that reads a multi-valued key. Use case: detecting when a client's write was based on stale data. Pitfall at scale: the clock grows with the number of nodes/clients that have ever written the key, and for use cases with many writers (like collaborative editing) this metadata can grow faster than the data itself.
• Last-write-wins (LWW): on a detected conflict, keep whichever write has the later timestamp and discard the other. Use case: high-volume, low-stakes fields where an occasional lost update is acceptable (a "last seen" timestamp, a UI preference). Pitfall: it silently drops a genuinely concurrent write with no record it ever existed, which is unacceptable for anything where losing an update has real cost (an inventory decrement, a cart item).
• CRDTs: data structures (counters, sets, sequences) with a merge operation mathematically guaranteed to converge to the same result regardless of the order replicas merge in, with no coordination and no lost updates. Use case: counters, collaborative documents, presence/membership sets. Pitfall: not every data type has a natural CRDT formulation (a bank balance with a hard floor of zero is much harder to express as a CRDT than a simple counter), and CRDT metadata (tombstones for removed set elements, per-node counters) accumulates over time and needs periodic garbage collection or it silently grows the storage footprint.

Worked example (executed)

A grow-only counter (G-Counter) CRDT, where each node tracks its own increments and merge takes the max per node:

class GCounter:
    def __init__(self, node_id, node_ids):
        self.node_id = node_id
        self.counts = {n: 0 for n in node_ids}

    def increment(self, amount=1):
        self.counts[self.node_id] += amount

    def merge(self, other):
        merged = GCounter(self.node_id, self.counts.keys())
        for n in self.counts:
            merged.counts[n] = max(self.counts[n], other.counts[n])
        return merged

    def value(self):
        return sum(self.counts.values())

nodes = ["A", "B", "C"]
a = GCounter("A", nodes); a.increment(5)
b = GCounter("B", nodes); b.increment(3)
c = GCounter("C", nodes); c.increment(2)

print(a.merge(b).merge(c).value())  # A-then-B-then-C
print(c.merge(b).merge(a).value())  # C-then-B-then-A

Three replicas increment concurrently with no coordination (A does 5, B does 3, C does 2). Merging in order A-then-B-then-C gives value 10; merging in the reverse order C-then-B-then-A also gives value 10 (executed; both orders confirmed to converge to the same result). Extending to a PN-Counter (adds a second counter for decrements) lets the same technique represent both increments and decrements:

class PNCounter:
    def __init__(self, node_id, node_ids):
        self.node_id = node_id
        self.p = {n: 0 for n in node_ids}
        self.n = {n: 0 for n in node_ids}

    def increment(self, amount=1):
        self.p[self.node_id] += amount

    def decrement(self, amount=1):
        self.n[self.node_id] += amount

    def merge(self, other):
        merged = PNCounter(self.node_id, self.p.keys())
        for k in self.p:
            merged.p[k] = max(self.p[k], other.p[k])
            merged.n[k] = max(self.n[k], other.n[k])
        return merged

    def value(self):
        return sum(self.p.values()) - sum(self.n.values())

x = PNCounter("X", ["X", "Y"]); x.increment(10)
y = PNCounter("Y", ["X", "Y"]); y.decrement(4)
print(x.merge(y).value())

A concurrent +10 on one replica and -4 on another merges to 6 (executed; confirmed), with neither operation lost.

Contrast that with LWW on the same kind of concurrent update: two replicas write qty=8 and qty=3 a millisecond apart, with neither replica having seen the other's write. LWW keeps only the later timestamp and discards the earlier one with no record a conflicting write ever existed, which is exactly the failure mode a CRDT (or the sibling-return vector-clock policy above) is designed to avoid, at the cost of needing a merge-friendly data structure in the first place.

Trade-offs and pitfalls

For a reporting database that must maintain referential integrity across regions (a foreign-key-style reference from one table to another), none of these three techniques resolve the problem by themselves: LWW and CRDTs converge each row independently, but a reference can still point at a row that a concurrent delete removed on the other side. That needs an explicit dangling-reference detection pass layered on top of whichever base reconciliation technique you use, plus a policy for what to do with an orphaned reference (restore it, tombstone the referencing row too, or flag it for manual cleanup), and the reconciliation process needs to tolerate a temporarily-incompatible schema if one region has rolled forward a schema change the other has not yet applied. The common mistake is picking one technique (usually LWW, because it is the simplest to implement) for everything, rather than matching the technique to what a lost or merged update actually costs for that specific field.

Direct answer

Leaderless (Dynamo-style) replication lets any replica accept a write, coordinating only via a quorum, so write availability survives the failure of any single node; leader-based replication routes all writes through one elected leader, which makes conflict handling trivial (there is only ever one order of writes) at the cost of write availability collapsing if that leader is unreachable. Leaderless designs shine on write-heavy, globally-distributed, availability-critical workloads; leader-based designs are preferable when writes need a strict, unambiguous order and conflicts are expensive to resolve after the fact.

Structured elaboration

• Write availability: leaderless systems keep accepting writes as long as a quorum of replicas is reachable, from any region, with no single point of failure. Leader-based systems stop accepting writes entirely if the leader is unreachable, until a new leader is elected (which itself takes time and, done wrong, risks a split-brain where two nodes both believe they are the leader).
• Conflict detection and handling: leaderless systems can accept concurrent, conflicting writes to the same key on different replicas, and must detect and resolve that after the fact (vector clocks to detect the conflict, then last-write-wins, CRDTs, or application-level merge logic to resolve it). Leader-based systems avoid the conflict entirely, because the leader serializes all writes into one order; there is nothing to reconcile.
• Operational complexity: leaderless systems push complexity into conflict resolution and tuning (which quorum sizes, which merge strategy). Leader-based systems push complexity into leader election, failover, and replication lag monitoring (how far behind are the followers, and what happens if the leader fails before a follower has caught up).

Worked example

A shopping cart across multiple devices (Dynamo's original use case) fits leaderless replication well: a customer can add an item from their phone while offline and from their laptop moments later, and the system should accept both writes and merge them (union the cart contents) rather than reject one because a leader was briefly unreachable. A bank account ledger fits leader-based replication far better: two concurrent, conflicting writes to the same balance cannot simply be "merged," so having a single authoritative order for writes to a given account is worth the availability cost of occasionally waiting on a leader election. Google Spanner is a real-world example of this choice taken to its logical extreme rather than an exception to it: it partitions data into ranges, and each range is backed by its own Paxos group with a single elected leader that serializes every write to that range, trading a leaderless design's availability for the guarantee that two conflicting writes to the same key can never both succeed in the first place.

Trade-offs and pitfalls

The common mistake is picking leaderless because "high availability sounds strictly better," without budgeting for the conflict-resolution work it creates. A leaderless design that never gets real conflicting writes (say, because every key is only ever written by one client) gets the availability benefit for free; a leaderless design applied to data with frequent genuine multi-writer conflicts (like a shared inventory count) needs real investment in merge logic, or it silently produces wrong answers that look like a working system.

Direct answer

Read-repair and anti-entropy are the two standard ways a replicated store fixes replicas that have drifted apart: read-repair is reactive, fixing divergence the moment a read happens to touch it, and anti-entropy is proactive, a background process that scans and reconciles replicas continuously, regardless of whether anyone reads that data. You tune read-repair up when correctness of frequently-read keys matters most and you can afford slightly higher read latency; you tune anti-entropy up (or its scheduling more aggressive) when data is rarely read but must still converge, or when you need a floor on staleness independent of read traffic.

Structured elaboration

• Read-repair: on a read, the coordinator queries multiple replicas, compares their values, returns the most recent one to the client, and asynchronously (or synchronously, in "read-repair-blocking" mode) writes the corrected value back to the stale replicas. Its coverage is limited to keys that actually get read; a key nobody reads never gets repaired this way.
• Anti-entropy: a background process (commonly using Merkle trees or version-vector comparisons) periodically compares whole replicas or partitions of them, independent of read traffic, and repairs whatever divergence it finds. It guarantees eventual convergence even for cold keys, at the cost of continuous background I/O and bandwidth.

Operationally, running anti-entropy well at scale requires: scheduling and staggering (so a full sweep does not hit every node's disk and network at once), prioritization (hot or business-critical keys first, so the highest-impact divergence is fixed soonest), bandwidth control (throttling so the repair traffic does not starve foreground reads and writes), verification via checksums or Merkle trees (comparing hashes of subtrees rather than every raw key, so divergence detection is cheap), and resuming cleanly after a node crash mid-sweep rather than restarting the whole comparison from scratch.

To know anti-entropy is actually working, monitor: the divergence rate found per sweep (how many keys or subtrees needed repair, which tells you how fast replicas are drifting relative to how fast you are fixing them), the age of the oldest unrepaired divergence you have detected (the real staleness bound the system is delivering in practice, not the theoretical one), sweep completion time versus the sweep interval (a sweep that takes longer to finish than the gap between sweeps means the system is falling behind, not keeping up), and the bandwidth/CPU the repair process is consuming against its throttle budget. A widening trend in any of these, more divergence found per sweep than last time, or sweeps that no longer complete inside their scheduled window, is the signal that anti-entropy is losing ground to write volume rather than keeping pace with it.

Worked example

A Merkle tree turns an O(n) "compare every key" scan into an O(log n) divergence check. With two replicas holding 3 keys, where only user:42 has diverged:

import hashlib

def h(x):
    return hashlib.sha256(x.encode()).hexdigest()[:8]

replica_A = {"user:1": "v1", "user:2": "v1", "user:42": "vA-stale"}
replica_B = {"user:1": "v1", "user:2": "v1", "user:42": "vB-fresh"}

def merkle_root(replica):
    keys = sorted(replica.keys())
    leaves = [h(k + ":" + replica[k]) for k in keys]
    level = leaves
    while len(level) > 1:
        nxt = []
        for i in range(0, len(level), 2):
            if i + 1 < len(level):
                nxt.append(h(level[i] + level[i + 1]))
            else:
                nxt.append(h(level[i] + level[i]))  # odd node: duplicate
        level = nxt
    return level[0]

print(merkle_root(replica_A))
print(merkle_root(replica_B))

Running this (executed; confirmed): merkle_root(replica_A) is 56c6f93d, merkle_root(replica_B) is 36243be6. Since the roots differ, the process knows immediately that something diverged without comparing all 3 keys directly. Walking down from the root to find which branch's hash differs then pinpoints exactly user:42 as the diverged key; the other two keys never need to be compared. At production scale (millions of keys per node) this is the difference between an O(log n) check most sweeps can complete cheaply and an O(n) full scan that would saturate the network.

Trade-offs and pitfalls

Read-repair alone leaves cold data permanently stale if it is never read again, which is why production systems run both together, not one instead of the other. Anti-entropy alone, run too aggressively, competes with foreground traffic for disk and network bandwidth, which is why prioritization (hot keys first) and throttling matter as much as the comparison algorithm itself. A repair sweep that dies mid-run and restarts from scratch every time is a common operational trap: track progress (a cursor or checkpoint over the key range) so a crash costs minutes of re-work, not a full re-scan.