A beginner’s guide to Linearizability

(Last Updated On: May 18, 2018)

Introduction

Linearizability is a lesser-known, yet omnipresent property of a data registry in the context of read and write operations that might happen concurrently.

This article aims to explain what linearizability consists of, and why it’s more prevalent that you might have previously thought.

Instantaneous reads and writes

Now, assuming you have a database system with a single node like in the following diagram:

The first SELECT statement reads the value of 50, while the second SELECT reads the value of 10 since in between the two read operations a write operation was executed.

Linearizability means that modifications happen instantaneously, and once a registry value is written, any subsequent read operation will find the very same value as long as the registry will not undergo any modification.

Linearizability is what the CAP Theorem calls Consistency.

Non-linearizability

To demonstrate what it means for a system to be non-lineraizable, consider the following diagram:

This time, we don’t have a single registry or a single source of truth. Our system uses asynchronous database replication, and we have a Primary node that takes both reads and writes and a Follower node used for read operations only.

Because replication happens asynchronously, there’s a lag between the Primary node row modification and the time when the Follower applies the same change.

One database connection changes the account balance from 50 to 10 and commits the transaction. Right after, a second transaction reads from the Follower node, but since replication did not apply the balance modification, the value of 50 is read.

Therefore, this system is not linearizable since changes don’t appear to happen instantaneously. In order to make this system linearizable, we need to use synchronous replication, and the Primary node UPDATE operation will not complete until the Follower node also applies the same modification.

However, if the number of nodes increases, synchronous replication will not be feasible for two reasons. First, updating multiple nodes synchronously increases response time which can impact application responsiveness. Second, if one node does not respond anymore, all writes will have to stall until that node becomes responsive or if the system is reconfigured to exclude that particular node.

For this reason, in a distributed system, a consensus protocol like Paxos or Raft is a much better alternative to provide linearizability.

Java Memory Model

Linearizability is not limited to distributed systems and databases. When using Java, reads and writes are not guaranteed to be linearizable unless the modifying variable is volatile or if both the write and the read are executed from within a synchronized block.

Because most computer systems use multiple CPU cores, and each core has its own cache, a write operation might only change the variable in the CPU cache. For the change to propagate to the main memory, the write-behind CPU cache needs to be flushed, and that’s exactly what the volatile keyword actually does.

If you enjoyed this article, I bet you are going to love my Book and Video Courses as well.

Conclusion

In a single-threaded enthronement, every read and write operation is automatically linearizable, which makes it very easy to reason about state, as well as guaranteeing correctness when it comes to implementing a certain algorithm.

In a multi-threaded environment, if the system is not linearizable, it’s going to be much more challenging to guarantee correctness since reads and writes appear to happen at different times than their actual wall-clock time.

To conclude, a linearizable system guarantees a strict time ordering of read and writes operations matching the wall-clock time flow.

Subscribe to our Newsletter

* indicates required
10 000 readers have found this blog worth following!

If you subscribe to my newsletter, you'll get:
  • A free sample of my Video Course about running Integration tests at warp-speed using Docker and tmpfs
  • 3 chapters from my book, High-Performance Java Persistence, 
  • a 10% discount coupon for my book. 
Get the most out of your persistence layer!

Advertisements

2 thoughts on “A beginner’s guide to Linearizability

  1. Recently I need to add a custom classloader to Hibernate (I am using 5.2).
    I tried to extend org.hibernate.boot.registry.classloading.internal.ClassLoaderServiceImpl but not getting any way to register my classloader so that it can be looked by Hibernate .

    I tried to use the following:

    BootstrapServiceRegistryBuilder bootstrapRegistryBuilder =
    new BootstrapServiceRegistryBuilder();
    // add a custom ClassLoader
    bootstrapRegistryBuilder.applyClassLoader( customClassLoader );

    but it doesn’t work.

    I although am able to use an integrator just by packaging META-INF/services/org.hibernate.integrator.spi.Integrator, is there anyway to do the same for org.hibernate.boot.registry.classloading.spi.ClassLoaderService

Leave a Reply

Your email address will not be published. Required fields are marked *