# Replication and Consistency Decision: [Dataset or service]

> Building-block decision record for how a dataset is copied across
> machines, zones or regions, and which consistency guarantees clients get.
> It covers the replication topology (single leader, multi-leader,
> leaderless), synchronous and asynchronous replication, quorums, the
> consistency model offered per operation, failover and the PACELC
> trade-off. Concepts draw on PACELC (Abadi, IEEE Computer, February
> 2012), on the consistency model map published by Jepsen, on
> linearizability (Herlihy and Wing, 1990), on the formal CAP result
> (Gilbert and Lynch, 2002) and on the Dynamo paper (DeCandia et al.,
> 2007) for quorums. Replace every `[bracketed]` value and every row marked
> *Example*. Worked examples use Quillmere, an invented book-review and
> reading-list platform shared by the other building-block templates in
> this category.

<!--
Guidance: How to use this template
- Decide consistency per operation, not per database. "Read my own
  review after posting it" and "show the global review count" need
  different guarantees, and paying for the stronger one everywhere is
  expensive.
- Write the failure story first (section 6): what a client sees when a
  replica, a zone or a whole region is lost, and how much acknowledged
  data can be lost. Then pick the topology that tells that story.
- Name models precisely. "Strong consistency" means different things to
  different vendors; use the names in section 4 and say which operations
  get which model.
- Test the claim. A consistency model is a promise about histories; check
  it with fault-injection tests, not only by reading documentation.
-->

## Document control

<!-- Guidance: Consistency choices change product behaviour; include a product reviewer, not only engineers. -->

| Field | Value |
|---|---|
| Document ID | [REPL-REC-001] |
| Dataset | [*Example:* Book reviews and ratings] |
| Store | [*Example:* Leaderless replicated key-value store, 3 replicas per partition] |
| Deployment | [*Example:* One region, three availability zones; second region planned] |
| Version | [0.1] |
| Status | [Draft / In review / Approved / Implemented / Superseded] |
| Owner | [@reviews-lead] |
| Reviewers | [@data-platform-lead], [@sre], [@product-manager] |
| Last updated | YYYY-MM-DD |
| Classification | [Internal] |
| Related | Partitioning and Sharding Plan (`system-design/partitioning-sharding-guide`), Distributed Key-Value Store System Design (`system-design/design-distributed-kv-store`), Event Delivery Guarantees (`system-design/event-delivery-guarantees`) |

### Approvals

| Role | Name | Decision | Date |
|---|---|---|---|
| Data owner | [@name] | [Approved / Changes requested] | YYYY-MM-DD |
| Data platform | [@name] | [Decision] | YYYY-MM-DD |
| Product | [@name] | [Decision] | YYYY-MM-DD |

### Revision history

| Version | Date | Author | Change summary |
|---|---|---|---|
| 0.1 | YYYY-MM-DD | [@name] | First draft |
| 0.2 | YYYY-MM-DD | [@name] | *Example:* Review posting moved from W=1 to W=2 after lost-write incident |

## 1. Goals and constraints

<!-- Guidance: State the durability, availability and latency targets that the replication design must meet, and the recovery point objective (RPO) and recovery time objective (RTO) for losing a zone and a region. -->

| Target | *Example* value | Notes |
|---|---|---|
| Write availability | 99.95% monthly | Posting a review |
| Read latency p99 | 20 ms within a region | Review lists |
| RPO, zone loss | 0 (no acknowledged write lost) | Synchronous to 2 of 3 zones |
| RPO, region loss | At most 5 s of writes | Asynchronous cross-region copy |
| RTO, region loss | 15 minutes | Manual promotion runbook |
| [Target] | [Value] | [Notes] |

## 2. Replication topology

<!-- Guidance: Compare the three topologies for this dataset. Single leader is the easiest to reason about; multi-leader and leaderless trade simpler failover and local writes for conflict handling. -->

| Topology | How writes flow | Strengths | Weaknesses |
|---|---|---|---|
| Single leader | All writes to one leader per partition, followers copy its log | Simple ordering, easy to offer linearizable reads from the leader | Failover needed when the leader fails; cross-region writes pay round-trip latency |
| Multi-leader | Each region or site has a leader; leaders exchange changes | Local writes in every region, survives region partition | Write conflicts must be detected and resolved |
| Leaderless | Client or coordinator writes to several replicas and reads from several (quorums) | No failover step, tolerates slow replicas | Conflicts and read repair; ordering is per key at best |

Decision: [*Example:* Leaderless within the region for reviews (N = 3,
one replica per zone). Asynchronous copy to the second region when it
opens. User account data stays on a single-leader relational store.]

```mermaid
flowchart LR
  C["Client"] --> Co["Coordinator"]
  Co --> A["Replica zone A"]
  Co --> B["Replica zone B"]
  Co --> Cz["Replica zone C"]
  A -. "async copy" .-> R2["Region 2 replicas"]
```

## 3. Synchronous, asynchronous and quorums

<!-- Guidance: For leader-based systems, say how many followers must confirm before a write is acknowledged. For leaderless systems, give N, W and R per operation. R + W > N makes read and write sets overlap, but on its own does not give linearizability (sloppy quorums, concurrent writes and failed partial writes can still return older values). -->

Quorum options for N = 3, *Example*:

| W | R | R + W > N? | Writes survive replica failures | Reads survive replica failures | Typical use |
|---|---|---|---|---|---|
| 2 | 2 | Yes | 1 | 1 | Balanced default |
| 1 | 1 | No | 2 | 2 | Fast, may read stale |
| 3 | 1 | Yes | 0 | 2 | Read-heavy, write blocked by any slow replica |
| 1 | 3 | Yes | 2 | 0 | Write-heavy, reads blocked by any slow replica |

Latency effect, *Example:* replicas answer in 2 ms, 5 ms and 80 ms (one
zone is degraded). A write with W = 2 completes at the second reply,
5 ms; with W = 3 it waits for the 80 ms replica.

Availability effect, *Example:* if each replica is independently
available 99.9% of the time, the chance that at least 2 of 3 are
available is 3p^2(1 - p) + p^3 = 99.9997%, and at least 1 of 3 is
1 - (1 - p)^3 = 99.9999999%. Failures in the same zone or caused by the
same deployment are not independent; treat these figures as an upper
bound.

Asynchronous copy, *Example:* with 4,000 writes per second and a
cross-region lag of 300 ms, an unplanned region failover can lose about
4,000 x 0.3 = 1,200 acknowledged writes. State that number to the product
owner in section 6.

Decision per operation: [*Example:* post review W = 2, R = 2; read review
list R = 1 with read repair; update rating counter W = 1 with
merge on read.]

## 4. Consistency models offered

<!-- Guidance: Use the names from the literature. The Jepsen consistency map (adapted from Bailis et al. and Viotti and Vukolic) arranges models by strength and by availability: models at or above sequential consistency, snapshot isolation or cursor stability cannot be totally available in an asynchronous network, and models at or above read-your-writes can be at most sticky available (the client must keep talking to the same servers). -->

| Model | Promise in plain words | Availability under partition (Jepsen map) |
|---|---|---|
| Strict serializable | Transactions appear to run one at a time, in real-time order | Not totally available |
| Serializable | Transactions appear to run one at a time, in some order | Not totally available |
| Snapshot isolation | Each transaction reads a consistent snapshot; write-write conflicts abort | Not totally available |
| Linearizable | Each single-object operation appears to take effect at one instant between call and return | Not totally available |
| Sequential | All clients see operations in one order consistent with each client's own order | Not totally available |
| Causal | Operations that are causally related are seen in that order by everyone | Sticky available |
| Read your writes | A client sees its own earlier writes | Sticky available |
| Monotonic reads | A client never sees older data after seeing newer data | Totally available |
| Read committed | No reads of uncommitted data | Totally available |
| Eventual | Replicas converge if writes stop (not on the Jepsen map; a liveness property) | Totally available |

Mapping for this dataset:

| ID | Operation | Model required | How provided | *Example* reason |
|---|---|---|---|---|
| CM-01 | *Example:* Author sees own review right after posting | Read your writes | Session pinned to coordinator plus R = 2 | Users report "lost" reviews otherwise |
| CM-02 | *Example:* Review list for a book | Monotonic reads, eventual | R = 1, sticky replica per session | Order may lag by seconds |
| CM-03 | *Example:* Rating average | Eventual | Counter merged on read | Small errors acceptable |
| CM-04 | *Example:* Username change | Linearizable | Single-leader store, conditional write | Two users must not get the same name |
| [CM-NN] | [Operation] | [Model] | [Mechanism] | [Reason] |

## 5. Conflict handling

<!-- Guidance: Any topology that accepts concurrent writes to the same key on different replicas needs a conflict rule. Last-writer-wins by timestamp silently drops one write; say if that is acceptable. -->

| Data | Conflict rule | Loss possible? | *Example* decision |
|---|---|---|---|
| Review text | Version vector per review; keep both versions and let the author choose | No | Concurrent edits from two devices shown as a choice |
| Like counter | Per-replica counters summed on read (a counter CRDT) | No | Totals converge |
| Profile settings | Last writer wins on server timestamp | Yes, the earlier write | Accepted by product |
| [Data] | [Rule] | [Yes/No] | [Decision] |

## 6. Failover and failure story

<!-- Guidance: Describe what clients see in each failure. Include the split-brain guard for leader-based systems (fencing tokens, leases, or a consensus service). Pitfall: automatic failover that promotes a follower that is behind, losing writes nobody counted. -->

| Failure | Client effect | Data loss | Detection and action |
|---|---|---|---|
| *Example:* One replica down | None for W = 2, R = 2 | None | Hinted handoff, replace node |
| *Example:* One zone down | None for reviews; latency rise | None | Alert, capacity check on remaining zones |
| *Example:* Region down | Reviews read-only from region 2 after promotion | Up to about 1,200 writes (section 3) | Manual promotion within 15 minutes |
| *Example:* Network partition between zones | Minority side rejects W = 2 writes | None | Clients retry on majority side |
| [Failure] | [Effect] | [Loss] | [Action] |

## 7. PACELC summary

<!-- Guidance: PACELC (Abadi 2012) extends CAP: if there is a Partition, choose Availability or Consistency; Else, in normal operation, choose Latency or Consistency. The "else" half matters every day, because synchronous replication across distance always costs latency. -->

| Operation | During partition (PA or PC) | Normal operation (EL or EC) | Reason |
|---|---|---|---|
| *Example:* Post review | PC within region (reject on minority side) | EC (wait for W = 2) | No acknowledged review may be lost |
| *Example:* Read review list | PA (serve from any replica) | EL (R = 1) | Freshness of seconds is fine |
| *Example:* Cross-region copy | PA | EL (asynchronous) | Region round trip too slow for writes |
| [Operation] | [Choice] | [Choice] | [Reason] |

The 2012 paper uses Dynamo-style systems in their default configuration as
its main example of PA/EL and fully transactional systems as PC/EC; many
real systems are tunable per operation, which is why this table is per
operation.

## 8. Verification

<!-- Guidance: Plan tests that can catch a violation of the claimed models: concurrent clients, injected partitions, clock skew and process pauses, with a checker over the recorded history. -->

- [ ] Fault-injection test with partitions between zones, recorded
      history checked for the models in section 4.
- [ ] Clock skew test for any last-writer-wins data.
- [ ] Failover drill measures actual RPO and RTO against section 1.
- [ ] Replication lag dashboard with alert at [*Example:* 2 s] p99.
- [ ] Read-your-writes probe: write and immediately read through a new
      session and the same session, measure the stale-read rate.

## 9. Decisions and open items

<!-- Guidance: Record each decision with its reason; link larger ones to an ADR (`architecture/adr-full`). -->

| ID | Decision or open item | Reason | Owner | Status |
|---|---|---|---|---|
| RC-01 | *Example:* Leaderless N = 3 across zones, W = 2, R = 2 for review posts | Zone loss without data loss or failover step | @reviews-lead | Decided |
| RC-02 | *Example:* Username changes stay on single-leader store | Need linearizable uniqueness | @accounts-lead | Decided |
| RC-03 | *Example:* Product accepts up to about 1,200 lost writes on region loss | Asynchronous cross-region copy | @product-manager | Open |
| [RC-NN] | [Item] | [Reason] | [@owner] | [Status] |

## Glossary and references

<!-- Guidance: Keep definitions consistent with section 4. -->

| Term | Meaning |
|---|---|
| N, W, R | Replicas per item, acknowledgements required for a write, replies required for a read |
| Quorum | A set of replicas large enough that any two such sets overlap |
| Replication lag | Delay between a write on one replica and its arrival on another |
| Split brain | Two nodes both acting as leader for the same data |
| Sticky available | Available to clients that keep talking to the same servers |
| RPO and RTO | Maximum data loss and maximum recovery time accepted for a failure |

References:

- Abadi D., "Consistency Tradeoffs in Modern Distributed Database System
  Design: CAP is Only Part of the Story", Computer 45(2), IEEE, February
  2012, pages 37 to 42, https://doi.org/10.1109/MC.2012.33.
- Jepsen, Consistency Models (map and definitions),
  https://jepsen.io/consistency (checked 2026-10-30).
- Herlihy M., Wing J., "Linearizability: a correctness condition for
  concurrent objects", ACM Transactions on Programming Languages and
  Systems 12(3), 1990, pages 463 to 492,
  https://doi.org/10.1145/78969.78972.
- Gilbert S., Lynch N., "Brewer's conjecture and the feasibility of
  consistent, available, partition-tolerant web services", ACM SIGACT
  News 33(2), 2002, pages 51 to 59, https://doi.org/10.1145/564585.564601.
- DeCandia G. et al., "Dynamo: Amazon's highly available key-value store",
  SOSP 2007, pages 205 to 220, https://doi.org/10.1145/1294261.1294281.
- Related templates: Partitioning and Sharding Plan
  (`system-design/partitioning-sharding-guide`), Data Store Selection
  (`system-design/data-store-selection`), Distributed Key-Value Store
  System Design (`system-design/design-distributed-kv-store`), Distributed
  Lock and Coordination System Design
  (`system-design/design-distributed-lock-coordination`), Event Delivery
  Guarantees (`system-design/event-delivery-guarantees`).

## Standard and licence note

Based on the publicly available papers and the Jepsen consistency map
cited above; no standard governs replication design. Model names follow
the literature; the explanations, tables, numbers and examples are
original to this collection, and Quillmere is an invented organisation.
Check the current documentation and published test results of the store
you adopt before relying on a claimed model. Template licence: MIT.