Who needs linearizability?

Question

I've been reading about the differences between serializability and linearizability, which are both consistency criteria for replicated systems such as replicated databases. However, I don't know in which cases linearizability would be needed, even though it's stronger than serializability.

Could you come up with scenarios where such strong property would actually be necessary?

Answer 1

Consider the design of concurrent, wait-free (or lock-free, which is weaker) data structures. In this scenario, linearizability is generally required, even though in some cases, performance and scalability can be improved by satisfying a weaker correctness condition. Whether an implementation satisfying such a weak condition is useful is usually application-dependent. In contrast, a linearizable implementation is always usable, because designers can view it as atomic.

Moreover, linearizability is a non-blocking property: a total operation (defined for all object states) is never required to block. Instead, Serializability is not a non-blocking property. Therefore, in order to increase the degree of concurrency, designers of concurrent data structures always rely on linearizability.

Answer 2

I've reread Herlihy and Wing many times over the past 15 years. It is a very difficult read. And that is unfortunate, because while there are some subtleties around the edges the basic idea is actually quite reasonable.

In short: linearizability is like serializability, but with the additional requirement that the serialization respect additional ordering constraints between the transactions. The goal is to allow you to reason rigorously about an individual atomic data structure rather than having to reason about the entire system all at once.

Linearizability is also easy to achieve: just associate a mutex with the object you want to linearize. Every transaction on that object starts by locking the mutex and finishes by unlocking the mutex.

Here are the definitions I'll use:

A system is serializabile if given a set of transactions over a set of data, any result of executing the transactions is the same as if the transactions were executed in some sequential order, and the operations within each transaction are contained within their transaction in the order specified by the transaction's code.

Serializability disallows the appearance of interleaving of operations between different transactions, and requires that the chosen ordering of transactions satisfies causality (if transaction A writes the value x, and transaction B reads the value x that A wrote, then transaction A must precede transaction B in the chosen serial order.) But it says nothing about any other constraints on the ordering of transactions (in particular, it says nothing about processes and the order in which processes perceive events.)

There is another related idea that does add in the constraints about the order in which processes executed operations (but doesn't talk about transactions only individual read/write operations):

A system is sequentially consistent if the result of any execution is the same as if the operations of all the processes were executed in some sequential order, and the operations of each individual process appear in this sequence in the order specified by its program. (Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE T Comp 28:9(690-691), 1979).

Implicit in the definition of sequential consistency is that we only accept sequential orders where for each memory location (object) the induced sequential order of operations obeys the rule that the value returned by each read operation to location x must be the same value that was written by the immediately preceding write operation to location x in the sequential order.

Linearizability has the good intentions of (a) combining together the notion of transactions (from serialization) with the notion that processes expect the operations they issue to complete in order (from sequential consistency) and (b) narrowing the correctness criteria to talk about each object in isolation, rather than forcing you to reason about the system as a whole. (I would like to be able to say that my object's implementation is correct even in a system where there are other objects that are not linearizable.) I believe Herlihy and Wing may have been trying to rigorously define a monitor.

Part (a) is "easy": A sequential consistency-like requirement would be that the transactions on the object issued by each process appear in the resulting sequence in the order specified by the program. A serialization-like requirement would be that the transactions on the object are all mutually exclusive (can be serialized).

The complexity comes from objective (b) (being able to talk about each object independently of all the others).

In a system with multiple objects it is possible that operations on object B place constraints on the order in which we believe operations were invoked on object A. If we are looking at the entire system history then we will be constrained to certain sequential orders, and will need to reject others. But we wanted a correctness criteria that we could use in isolation (reasoning just about what happens to object A without appealing to the global system history).

For example: suppose I am trying to argue about the correctness of object A, which is a queue, suppose object B is a memory location, and suppose I have the following execution histories: Thread 1: A.enqueue(x), A.dequeue() (returns y). Thread 2: A.enqueue(y), A.dequeue() (returns x). Is there an interleaving of events that would allow this implementation of the queue to be correct? Yes:

Thread 1                           Thread 2
A.enqueue(x)                       ...
...                                A.enqueue(y)
...                                A.dequeue() (returns x)
A.dequeue(y) (returns y)           ...

But now what if the history (including object B) is: B starts with value 0. Thread 1: A.enqueue(x), A.dequeue() (returns y), B.write(1). Thread 2: B.read() (returns 1) A.enqueue(y), A.dequeue() (returns x).

Thread 1                           Thread 2
A.enqueue(x)                       ...
A.dequeue() (returns y)            ...                       (uh oh!)
B.write(1)                         ...
...                                B.read() (returns 1)
...                                A.enqueue(y)
...                                A.dequeue() (returns x)

Now we'd like our definition of "correctness" to say that this history indicates that either our implementation of A is buggy or our implementation of B is buggy, because there is no serialization that "makes sense" (either Thread 2 needs to read a value from B that hasn't been written yet, or Thread 1 needs to dequeue a value from A that hasn't been enqueued yet.) So while our original serialization of the transactions on A seemed like a reasonable one, if our implementation allows a history like the second one, then it is clearly incorrect.

So the constraints that linearization adds are quite reasonable (and necessary even for simple data structures like FIFO queues.) They are things like: "your implementation should disallow dequeue() a value that won't be enqueued() until some time in the future." Linearizability is quite easy (and natural) to achieve: just associate a mutex with your object, and each transaction starts by locking and ends by unlocking. Reasoning about linearizability starts to get tricky when you are trying to implement your atomicity with non-blocking or lock-free or wait-free techniques instead of simple mutexes.

If you are interested in some pointers to the literature, I found the following (although I think the discussion about "real-time" is one of the red-herrings that make linearizabilty more difficult than it needs to be.) https://stackoverflow.com/questions/4179587/difference-between-linearizability-and-serializability

Answer 3

First, linearizability and serializability are not directly comparable. As the table below shows, the main difference is that on the left hand side, all individual operations are atomic (like having a java synchronized around each op. On the right side, the unit of atomicity is a transaction; an individual operation is not atomic. Which is why Serializability has always been a part of the database literature, while the left-hand side has been the subject of processor-memory literature (read/write op is atomic). The original Key-Value stores (such as dbm and memcached) started off on the left hand side (get/put is atomic), but newer ones are increasingly supporting transactions (such as Google's spanner).

obj. operations are atomic      |  Transactions are atomic
--------------------------------+---------------------------------
Linearizability                 |
Sequential Consistency          |    Serializability
Causal Consistency              |
Cache Consistency               |

Linearizability requires that a system of objects in a concurrent setting must behave identical to a sequential system that handles one operation (a request/response pair) at a time -- in a parallel universe -- in such a way that (a) the clients in both universes see exactly the same responses (b) temporal order is preserved (more on this below).

The definition of Serializability, like Sequential Consistency, only requires the first criterion.

Temporal order preservation means this: if A:x.op1() (A is a client, x is an object, and op1 is an operation) finished before another operation B:y.op2() started, then in the sequential universe the requests are handled in the same order. This isn't required in Sequential Consistency (SC); the object is allowed to queue up a client's request, respond to the client, then evaluate it later. Further, the object may handle a later request from some other client out of turn, evaluating it before getting to the first one.

Non-preservation of temporal order is a problem. After A:x.op1(), suppose A picked up the phone and told B about it, then B called x.op2() call. There is no way for the system to know about this causal chain of events, since the second step involved a message not tracked by the system. In many real cases, it is not unreasonable for A to assume that once x had responded to it, B's invocation can rely on the updated state. If temporal order was not preserved, A and B are in for a surprise. This wouldn't happen in a linearizable system.

The second nice property of temporal order preservation is locality and compositionality, that a system built of linearizable objects is itself linearizable. So, instead of having one monolithic key-value store, you can shard it into many separate partitions each managed by its own KV-store server; if each of them is linearizable, the whole database functions as one linearizable monolithic KV store, with no extra effort.