jzhao.xyz

Search IconIcon to open search

 .
  \_.
  /

Consistency

Last updated June 27, 2022

# Definitions

# ACID Consistency

The state satisfies application-specific invariants (e.g. every course with students enrolled must have at least one lecturer) at any given point in time

# Replication Consistency

Many models to choose from! Most common being read-after-write consistency

Imagine a scenario where

Clearly, client is getting inconsistent results. We can fix this via a quorum read.

# Atomic Commitment Problem

Big problem with distributed transactions: atomic commitment problem

Usually done through two-phase commit (2PC)

But what if the coordinator crashes? The algorithm is blocked until coordinator recovers. We can use a fault-tolerant two-phase commit (uses total order broadcast)

# Linearizability

Defined as consistency in the face of concurrent reads/writes.

Informally: every operation takes effect atomically sometime after it started and before it finished. All operations behave as if executed on a single copy of the data

Not to be confused with serializability: transactions having the same effect as if they were run in some serial order. Also contrasting with causal relationships, linearizability is defined in terms of real-time whereas causal is defined in terms of message sending and receiving.

The consequence/desired property of linearizability is that every operation returns an “up-to-date” value, sometimes called “strong consistency”

We can guarantee linearizability of get (quorum read + read repair) and set (blind write to quorum). If events overlap, either order could happen and is ok.

Not without downsides

# Eventual Consistency

Alternative to linearizability is eventual consistency.

If there are no more updates, eventually all replicas will be in the same state.

But how do we know when there are no more updates? This can be an indefinite amount of time. An upgraded version of this is strong eventual consistency which has a few additional rules:

Properties

# Summary

Summary of minimum system model requirements for various forms of consistency

Problem Must wait for communication Requires synchrony
atomic commit all participating nodes partially synchronous
consensus, total order broadcast quorum partially synchronous
linearizable get/set quorum asynchronous
eventual consistency, causal broadcast, FIFO broadcast local replica only asynchronous

Interactive Graph