Michael's Notes & Blog

Consistency and Consensus

Consistency Guarantees

Eventual consistency (convergence)

Linearizability (make a system appear as if there were only one copy of the data, and all operations on it are atomic)

example - alice has seen the result of a game, while later bob sees that they are still playing, because they are reading from 2 different replicas

What Makes a System Linearizable

  • If a read request is concurrent with a write request, it may return either the old or the new value.
  • After any one read has returned the new value, all following reads (on the same or other clients) must also return the new value.
  • The requirement of linearizability is that the lines joining up the operation markers always move forward in time (from left to right), never backward.

Linearizability Versus Serializability

  • Serializability is an isolation nproperty of transacitons, where every transaction may read and write multiple objects
  • Linearizability is a recency guarantee on reads and writes of a register (an individual object).
  • A database may provide both serializability and linearizability, and this combination is known as strict serializability or strong one-copy serializability.
  • Implementations of serializability based on two-phase locking or actual serial execution are typically linearizable.

Relying on Linearizability

Locking and leader election

Constraints and uniqueness guarantees

Cross-channel timing dependencies

Implementing Linearizable Systems

  • Single-leader replication (potentially linerizable)
  • Consensus algorithms (linearizable)
  • Multi-leader replication (not linearizable)
  • Leaderless replication (probably not linearizable)

The Cost of Linearizability

  • CAP theorem
  • Linearizability is slow (even memory of multi-core cpu is not linearizable)