Tuesday, July 5, 2016

Martin Kleppmann on “Sequential Consistency versus Linearizability”

Did you ever wonder what is Sequential Consistency or Linearizability or what are the differences between the two?
If the answer is yes, then you should watch this presentation by Martin Kleppmann:

This proof is interesting, and you have to take into account that this is for a single register. If you're using a reader-writer lock (or the Left-Right technique) and you're only doing reads, then the overhead is that of reading/writing to a couple of variables, which amortized over the entire critical section can become a very low overhead, and therefore make linearizability profitable.
Now you can say, that you can use the same argument for seq-cst, but the problem with such an argument is that there are no seq-cst locks or rw-locks, for the simple reason that seq-cst is not (generically) composable.  Therefore, I would argue that, depending on what you're doing, you can have more performance for a linearizable object that you get for a seq-cst object, simply because you can not compose regular reads and writes with seq-cst reads and writes and still expect the result to be seq-cst, but you can for a linearizable object like a mutex, or a rw-lock or a left-right.

No comments:

Post a Comment