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.
<aside> 💡 real time ordering: 指最终生效的操作顺序，和真实的执行顺序一致。
在 Consistency in Non-Transactional Distributed Storage Systems.pdf 中，定义了 linerability 的三种特性：
<aside> 💡 single-order: 就是 total-order 的 single-object 版，指对一个 data 的操作可以被排序。
</aside>
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
Herlihy & Wing introduced linearizability in their 1990 paper Linearizability: A Correctness Condition for Concurrent Objects. Ignoring some bookkeeping necessary to fill in the possible results of incomplete operations, a linearizable 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: