JEPSEN

Linearizability

Linearizability is one of the strongest single-object consistency models, and implies that every operation appears to take place atomically, in some order, consistent with the real-time ordering of those operations: e.g., if operation A completes before operation B begins, then B should logically take effect after A.

This model cannot be totally or sticky available; in the event of a network partition, some or all nodes will be unable to make progress.

Linearizability is a single-object model, but the scope of “an object” varies. Some systems provide linearizability on individual keys in a key-value store; others might provide linearizable operations on multiple keys in a table, or multiple tables in a database—but not between different tables or databases, respectively.

When you need linearizability across multiple objects, try strict serializability. When real-time constraints are not important, but you still want every process to observe the same total order, try sequential consistency

Formally

Herlihy & Wing introduced linearizability in their 1990 paper Linearizability: A Correctness Condition for Concurrent Objects. Ignoring some bookeeping necessary to fill in the possible results of incomplete operations, a history H is one in which there is an equivalent sequential (e.g. non-concurrent) history S, and the partial real-time order of operations in H is consistent with the total order of S, and which preserves the objects’s single-threaded semantics.

Viotti and Vukolić rephrase this definition in terms of three set-theoretic constraints on histories:

  • SingleOrder (there exists some total order of operations)
  • RealTime (consistent with the real time bound
  • RVal (obeying the single-threaded laws of the associated object’s datatype)