mufassall

Cheat sheet · Data & storage

CAP: when the link breaks

14 min · Advanced · mufassall.dtwin.uz/en/l/cap/

← Open the lesson

The problem

A seat-booking service runs in two data centres that copy changes to each other. When the link between them breaks, each side must choose: refuse writes and stay correct, or accept them and sort out conflicts later. How quorums make that choice automatic.

What you learn

  • Why asynchronous replication means some reads are stale (eventual consistency)
  • What a network partition forces you to choose: consistency or availability
  • How an available system reconciles conflicting writes after the link heals
  • Why quorums with R + W > N give fresh reads and let only the majority write
Final scene

Diagram as code

The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.

Mermaid: flowchart

flowchart LR
  n_user_e(("User (east)"))
  n_api_e["API east"]
  n_db_e[("DB east")]
  n_user_w(("User (west)"))
  n_api_w["API west"]
  n_db_w[("DB west")]
  n_db_t[("DB third site")]
  n_user_e --x n_api_e
  n_api_e --> n_db_e
  n_user_w --> n_api_w
  n_api_w --> n_db_w
  n_db_e --x|"lost"| n_db_w
  n_api_e --x|"lost"| n_db_t
  n_api_w --> n_db_t
  classDef slow fill:#fff4d6,stroke:#b26a00,color:#3d2600
  class n_api_e slow

Mermaid: request sequence

sequenceDiagram
  participant n_db_e as DB east
  participant n_db_w as DB west
  actor n_user_w as User (west)
  participant n_api_w as API west
  participant n_fixer as Reconciler
  participant n_api_e as API east
  participant n_db_t as DB third site
  actor n_user_e as User (east)
  Note over n_db_e,n_db_w: Two data centres, one booking system
  n_db_e->>n_db_w: REPLICATE dc-east -#62; dc-west
  Note over n_user_w,n_api_w: For 30 ms the two sides disagree
  n_user_w->>n_api_w: GET /seats/14A HTTP/1.1
  n_api_w-->>n_user_w: HTTP/1.1 200 OK
  Note over n_db_e,n_db_w: The link between the sites breaks
  n_db_e-xn_db_w: ERROR replication to dc-west: connection timed out after 5000 ms
  Note over n_user_w,n_api_w: Choice 1: stay correct, refuse writes
  n_user_w->>n_api_w: POST /seats/14B/hold HTTP/1.1
  n_api_w-->>n_user_w: HTTP/1.1 503 Service Unavailable
  Note over n_api_w,n_db_w: Choice 2: stay available, accept writes on both sides
  n_api_w->>n_db_w: UPDATE seats SET holder = 'u_77',
  n_db_w-->>n_api_w: UPDATE 1
  Note over n_db_e,n_db_w: The link is back, so are the conflicts
  n_db_e->>n_db_w: REPLICATE dc-east -#62; dc-west
  Note over n_db_w,n_fixer: Reconcile with a business rule
  n_db_w->>n_fixer: RESOLVE seat:14B
  Note over n_api_e,n_db_t: Three replicas, write to two, read from two
  n_api_e->>n_db_t: PUT seat:14C holder=u_42 N=3 W=2
  Note over n_user_e,n_api_e: Now the partition decides itself
  n_user_e->>n_api_e: POST /seats/14D/hold HTTP/1.1
  n_api_e-->>n_user_e: HTTP/1.1 503 Service Unavailable

D2

direction: right

n_user_e: "User (east)" {
  shape: person
}
n_api_e: "API east" {
  shape: rectangle
  style.fill: "#fff4d6"
  style.stroke: "#b26a00"
}
n_db_e: "DB east" {
  shape: cylinder
}
n_user_w: "User (west)" {
  shape: person
}
n_api_w: "API west" {
  shape: rectangle
}
n_db_w: "DB west" {
  shape: cylinder
}
n_db_t: "DB third site" {
  shape: cylinder
}

n_user_e -> n_api_e {
  target-arrowhead.shape: cross
}
n_api_e -> n_db_e
n_user_w -> n_api_w
n_api_w -> n_db_w
n_db_e -> n_db_w: "lost" {
  target-arrowhead.shape: cross
}
n_api_e -> n_db_t: "lost" {
  target-arrowhead.shape: cross
}
n_api_w -> n_db_t

PlantUML: request sequence

@startuml
database "DB east" as n_db_e
database "DB west" as n_db_w
actor "User (west)" as n_user_w
participant "API west" as n_api_w
participant "Reconciler" as n_fixer
participant "API east" as n_api_e
database "DB third site" as n_db_t
actor "User (east)" as n_user_e
note over n_db_e, n_db_w : Two data centres, one booking system
n_db_e -> n_db_w : REPLICATE dc-east -> dc-west
note over n_user_w, n_api_w : For 30 ms the two sides disagree
n_user_w -> n_api_w : GET /seats/14A HTTP/1.1
n_api_w --> n_user_w : HTTP/1.1 200 OK
note over n_db_e, n_db_w : The link between the sites breaks
n_db_e ->x n_db_w : [lost] ERROR replication to dc-west: connection timed out after 5000 ms
note over n_user_w, n_api_w : Choice 1: stay correct, refuse writes
n_user_w -> n_api_w : POST /seats/14B/hold HTTP/1.1
n_api_w --> n_user_w : HTTP/1.1 503 Service Unavailable
note over n_api_w, n_db_w : Choice 2: stay available, accept writes on both sides
n_api_w -> n_db_w : UPDATE seats SET holder = 'u_77',
n_db_w --> n_api_w : UPDATE 1
note over n_db_e, n_db_w : The link is back, so are the conflicts
n_db_e -> n_db_w : [duplicate] REPLICATE dc-east -> dc-west
note over n_db_w, n_fixer : Reconcile with a business rule
n_db_w -> n_fixer : RESOLVE seat:14B
note over n_api_e, n_db_t : Three replicas, write to two, read from two
n_api_e -> n_db_t : PUT seat:14C holder=u_42 N=3 W=2
note over n_user_e, n_api_e : Now the partition decides itself
n_user_e -> n_api_e : POST /seats/14D/hold HTTP/1.1
n_api_e --> n_user_e : HTTP/1.1 503 Service Unavailable
@enduml

PlantUML: components

@startuml
left to right direction
actor "User (east)" as n_user_e
component "API east" as n_api_e #fff4d6;line:b26a00
database "DB east" as n_db_e
actor "User (west)" as n_user_w
component "API west" as n_api_w
database "DB west" as n_db_w
database "DB third site" as n_db_t
n_user_e -[#c62828]-> n_api_e
n_api_e --> n_db_e
n_user_w --> n_api_w
n_api_w --> n_db_w
n_db_e -[#c62828,dashed]-> n_db_w : lost
n_api_e -[#c62828,dashed]-> n_db_t : lost
n_api_w --> n_db_t
@enduml

Recap

Links between sites do break, and then you choose: be correct or be available. You cannot have both during the cut.

1) Async replication means stale reads for a short time, even on a good day. 2) Consistent (CP): the cut-off side refuses writes. 3) Available (AP): both sides accept, then a business rule reconciles conflicts. 4) Quorums with R + W > N give fresh reads and let only the majority side write.

Numbers: at the start and at the end

MetricStartEnd
Writes accepted100%50%
Stale reads0%0%
Unresolved conflicts0/h0/h
Replication lag30 ms30 ms

Steps

  1. Case Two data centres, one booking system

    Users near the east site book seats through the east API, users near the west site through the west API.

  2. Problem For 30 ms the two sides disagree

    User u_42 books seat 14A in the east.

  3. Problem The link between the sites breaks

    A fibre between the data centres is cut.

  4. Fix Choice 1: stay correct, refuse writes

    East is the primary for bookings.

  5. Case Choice 2: stay available, accept writes on both sides

    The other option: the west keeps taking bookings during the cut.

  6. Problem The link is back, so are the conflicts

    The fibre is repaired and replication resumes.

  7. Fix Reconcile with a business rule

    A reconciler reads every conflict and applies a rule chosen by the business: for seats, the earlier hold wins.

  8. Fix Three replicas, write to two, read from two

    A small third site is added.

  9. Case Now the partition decides itself

    The east site is cut off from both others.

  10. Recap Recap

    Links between sites do break, and then you choose: be correct or be available.

Terms

CAP
When the network splits, a system must choose: stay consistent (CP) and refuse writes on the cut-off side, or stay available (AP) and accept writes on both sides. During the cut you cannot have both.
Network partition
A broken link between parts of a system so they can no longer see each other. Both sides keep running but cannot agree.
Eventual consistency
If writes stop, all copies end up the same, but not at every instant. With asynchronous replication some reads are briefly stale.
Quorum (R + W > N)
A write counts once W of N replicas confirm it, and a read asks R replicas. If R + W > N, every read overlaps the latest write on at least one replica, and only the majority side can write.