Monotonic Reads

Asynchronous replication leads to a fascinating situation where it feels like we are going through a wormhole traveling back and forth in time. In this essay, we understand why this happens and the consequences and devise a quick solution to address it.

Through the wormhole

As per Wikipedia, a wormhole can be visualized as a tunnel with two ends at different points in spacetime (i.e., different locations, different points in time, or both), allowing us to traverse back and forth in time again and again. So, where exactly is a wormhole in the context of a distributed datastore?

Say, we have a distributed KV store having one Master and 2 Replica nodes, and we make three updates on a key X, the first update U1 sets X as 1, the second update U2 sets it to 2, while the third update U3 sets X to 3. Like in a typical Master Replica setup, the writes go to the Master, and they are propagated to Replicas through an Asynchronous replication. The reads are typically sent to any one of the Replicas at random.

The writes are propagated to the Replicas asynchronously, which means both the Replicas will have slight replication lags and say this lag on Replica 1 is of 2 seconds, and on Replica 2 is 1 second. As of current time instant, all the three updates U1, U2, and U3 have happened on the Master, while only update U1 has reached Replica 1, and it is lagging behind Replica 2 that saw updates U1 and U2.

time traveling database - monotonic reads

Say, after making the update U3 at instant t, the User initiates a read that hits Replica 2. Since the update U3 is yet to reach the Replica 2, it returned 2, an old value of X. This breaks Read your write consistency and make the user feel that the recent write is lost. Say the user makes another read after this one, which now reaches Replica 1, and since the Replica 1 has just seen the update U1, it returns the value 1, which is even older than the last returned value.

Here we see that after the latest write U3, the two successive reads yielded historical values depending on which Replica it hit, giving a feel of traveling back in time. The situation becomes even more interesting when the Replica starts to catch up. Depending on which Replica the read request went to, the User would be oscilating between the old and new values of X, giving it a feel of going through the wormhole.

Monotonic Reads

Monotonic read guarantees users to see value always moving forward in time, no matter how many or how quickly it tries to read the data. It is a weaker guarantee than strong consistency but a stronger one than eventual consistency.

Achieving Monotonic Reads

The root cause of this seemingly random fetch lies in allowing the read request to hit Replicas with different Replication Lags. For a particular Replica, the writes are always applied in order, moving forward in time. So, a niche solution for this problem is to make the read request of a user sticky to a replica.

monotonic reads

Once it is ensured that a particular user's request only goes to a specific replica, that User will see updates always moving forward in time as the Replica continues to catch up with the Master.

To implement stickiness, the server can pick the Replica using the hash of the User ID instead of picking it randomly. This way, the stickiness between a user and a Replica helping us achieve Monotonic Reads.

Arpit Bhayani

Arpit's Newsletter

CS newsletter for the curious engineers

❤️ by 38000+ readers

If you like what you read subscribe you can always subscribe to my newsletter and get the post delivered straight to your inbox. I write essays on various engineering topics and share it through my weekly newsletter.

Other essays that you might like

Indexing on Partitioned Data

380 reads 2022-02-07

In this essay, we will take a detailed look into how we could index the partitioned data, allowing us to query the data ...

Conflict Resolution

275 reads 2022-01-09

In this essay, go in-depth to understand ways to resolve and avoid conflicts in a multi-master setup....

Conflict Detection

709 reads 2021-11-28

In this essay, we talk about conflicts and understand what they are, how to detect them in a multi-master setup....

Architectures in Distributed Systems

563 reads 2021-06-22

While designing a Distributed System, it is essential to pick the right kind of architecture. Usually, architectures are...

Be a better engineer

A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.

Paid Courses

System Design for Beginners

A masterclass that helps early engineers and product managers become great at designing scalable systems.

132+ learners

Details →

System Design Masterclass

A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.

1000+ learners

Details →

Redis Internals

Learn internals of Redis by re-implementing some of the core features in Golang.

98+ learners

Details →

Free Courses

Designing Microservices

A free playlist to help you understand Microservices and their high-level patterns in depth.

823+ learners

Details →

GitHub Outage Dissections

A free playlist to help you learn core engineering from outages that happened at GitHub.

651+ learners

Details →

Hash Table Internals

A free playlist to help you understand the internal workings and construction of Hash Tables.

1027+ learners

Details →

BitTorrent Internals

A free playlist to help you understand the algorithms and strategies that power P2P networks and BitTorrent.

692+ learners

Details →