Keyboard shortcuts

/ or ⌘/Ctrl K
Find a note
j / k
Next / previous section or linked note
h / l
Collapse or go to parent / expand or enter
e or Alt-click
Read a linked note here
o
Open focused note on its own
g g / G
First / last section or linked note
g h / g a
Home / all notes
g b / g t
Backlinks / table of contents
t
Cycle System, Light, Dark
? / Esc
Show / close this reference

Search: ↑/↓ or Ctrl N/P, Enter to open. Shortcuts pause while typing.

cap theorm (brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services [e5637e25]

Tags: distributed systems, papers

Main takeaways:

  • Most systems in early distributed relational design did not take into account partition tolerance (aka mostly CA)
  • network partition puts pressure on strong consistency and high availability
  • strong consistency and performance have tension during normal operation
  • how consistent does your data actually need to be - if availability is necessary, then we need to explore whether consistency models other than strong consistency are workable

  • consistency and availability are not binary choices unless you limit yourself to strong consistency - www.infoq.com/articles/cap-twelve-years-later-how-the-rules-have-changed/

    • not really "2 out of 3" more like "2.5 out of 3"
    • ACID != CAP

1. Details

  • 3 properties

    • consistency: all nodes see the same data at the same time
    • availability: node failures to not prevent survivors from continuing to operate
    • partition tolerance: system continues to operate during message loss
  • only two can be satisfied

  • CA: strict quorum protocols like two phase commit

    • Does not distinguish between node failures and network failures

      • stops accepting writes to avoid introducing divergence
      • two phase commit and common in relational db's

  • CP: majority quorum protocols like Paxos

    • prevents divergence by forcing asymmetric behavior on two sides of the partition
    • drops the minority partition
    • incorporate network partitions into their failure model
    • Paxos, Raft, viewstamp replication, etc
  • AP: conflict resolution protocols like Dynamo

2. Strong Consistency vs Other Consistency

  • Strong

    • linearizable consistency - all operations execute atomically in a globally real-time ordering

    • sequential consistency - all operations execute atomically in a order consistent with the order seen at individual nodes that is equal at all nodes

      • not composable!

  • Weak

    • client-centric - client id or session id may guarentee that the client never sees old data (aka some kind of caching on the client end so they never read from old replicas)
    • causal

    • eventual - if values stop changing, then at some undefined point in time all nodes guarenteed to share the same value

      • usually defined in a more strict manner like "eventually last writer wins"
  • arxiv.org/abs/0909.1788