Atomically Updating Multi-Node Cache

In this blog post, we will go over an approach on how to atomically update a hashmap which has been distributed across multiple nodes. There are obviously some approaches which you might find out there on the internet but the purpose of this blog is to have a very simplistic approach and not solve the problem by 2-phase commit or 3-phase commit.

Understanding the Problem

Let’s say we have a hashmap which has been partitioned across 3 nodes. Some keys of the hashmap are distributed on Node 1 , some on Node 2 and some on Node 3. Now we want to atomically update multiple keys of the map simultaneously.

For simplicity, let’s assume that we want to update the following keys in the cache atomically

• Key K1 to V1′
• Key K2 to V2′
• Key K3 to V3′

Obviously there are ways in which you can easily achieve the atomic updates by using 2 phase commit protocol. To know more about 2-phase commit protocol, go to this link. However 2-phase commit protocol has it’s own limitations in terms of system throughput as it is blocking in nature.

Understanding the Solution

To solve this, we will use an intermediate hashmap on one of the nodes which will maintain all these atomic operations. So when an atomic operation is made, we do the following

• We add this atomic operation entry in the hashmap on the designated node.
• After adding the entry, we carry all of these individual operations within this atomic operation. These individual operations are applied on each of the nodes.
• When all of these individual operations have been completed , then we remove the entry of the atomic operation from the intermediate table.

Lifecycle of an Atomic Write

• Whenever any atomic operation comes, we will store the atomic operation on one of the designated nodes. DO NOT WORRY, storing these atomic operations is done only for a time being until all the individual operations have been applied.

• After the atomic operation is stored on any of the designated node ( like in the above case we are storing the atomic operation within Node 1 ), we break down the atomic operation into different individual operations and start applying them onto all the different nodes.

• After all the individual operations have been applied on all the nodes, atomic operation entry is removed from the designated node.

Lifecycle of a Read Operation

• Whenever any read operation is made, we will make the cache request to the corresponding node storing the entry for the key. However along with that node, we will also make another request to the designated node on which all the atomic operations are being stored ( like in the above case, we will make request to Node 1 )
• Now we will get the following results on the client side
  • Result of the Value of the Key K2 from the map
  • All the Atomic Operations which involve the Key K2
• Now on getting these results back from the , the client can reconcile the value of K1 by applying all the subsequent values in the order of the timestamp.

Client will make 2 API call
- One API call to the designated node storing all the Intermediate Atomic Operations. If there is any entry for the key K2, return that , otherwise return null.
- One API call to the node on which we have the value for the Key K2. In this , we will return the value for the Key K2

So if there is a value coming from the designated node, if there is a value for Key K2 coming from the designated node with the Atomic Operations then use that value otherwise use the value coming from the partitioned node with the key K2.

References

• https://en.wikipedia.org/wiki/Two-phase_commit_protocol
• https://martinfowler.com/articles/patterns-of-distributed-systems/two-phase-commit.html