Understanding linearizability

March 10, 2021 | minutes read

I’m preparing for my Distributing Systems midterm and I was struggling to understand the differences between serializability and linearizability (why are these two words so difficult to spell right). Apparently, these two concepts are very different. To gain some clarity, I searched online and found this awesome YouTube video posted by Martin Kleppmann ; in the video, he dives deep into linearizability and I wanted to share some of the key take aways

Key Takeaways

  • Happens before relationship (coined by Leslie Lamport) deals with causality and only applies to message sends and receives, related to logical clocks.
  • Linearizability focuses with not with logical clocks, but with real time
  • Linearzability states that an operation must take place sometime after it started but before it ended. That’s not entirely clear, so let’s let’s imagine a scenario with two clients: client 1 and client 2. Client 1 performs a write key=x value=0. And imagine client 2 performs a get key=x. And finally, suppose that the key value store current contains a key=x, value=100. With linearzability, it’s entirely possible that if both client 1 and client 2 overlap, that client 2 gets either value=0 or value=100.
  • Linearzability is not serializability. They are not the same. The latter is isolation between transactions; as if they are executed in some serial order. The former is multiple replicas behaving as if there is a single replica.

I’m Matt Chung. I’m a software engineer, seasoned technology leader, and father currently based in Seattle and London. I love to share what I know. I write about topic developing scalable & fail-safe software running in the AWS cloud, digital organization as a mechanism for unlocking your creativity, and maximizing our full potentials with personal development habits.

View all articles