Leader Election using Dynamo DB Lock Client
--
A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable. — Leslie Lamport
Hey Folks!! It’s time for some fragments from the work life of AD. Today, we will discuss how to solve complex problems like leader election using Dynamo db.
Leader election is a very complex and widespread problem which is encountered in every distributed application. We need a leader to manage different tasks in an application. The application builder has the autonomy of outsourcing the type of tasks to the master, but the application needs an elected leader. As we elect the leaders via consensus, we can rely on the leader to make all the decisions which need a consensus. Leader can then inform all the nodes in the application about the decision and also act as a single source of truth for the entire system. We can also outsource actions, such as modifying data in the database to the leader as it provides consistency guarantees. We can also gain performance guarantees in the system, as we can avoid all the logic needed to add coordination.
Some added benefits on top of all the above mentioned benefits are frugality in terms of a single layer of cache or maybe autonomy in terms of implementation for the other parts of the system. Since the leader can act as the face of the application, it adds dependency in the leader's implementation to be consistent with the clients for the system.
So now that we agree on the benefits of the leader. Let's see the choices for electing theses leaders. Some of the most commonly used algorithms are Raft and Paxos. These algorithms are highly complex and require extensive deep dive in the algorithm before the implementation begins. This is because the consistency protocol in these algorithms has subtle details which are easily missed. The buggy implementation of these algorithms can easily cause the entire system to collapse, as most of the tasks depend on the leader and if the leader doesn’t come up for a certain amount of time, it will lead to downtime. I will save the details of Raft and Paxos for another post.
Let’s talk about how we can solve this problem using dynamo Db. DDB is a No-SQL based key value and document database. The benefits provided by DDB range from out of the box support for Conditional Updates, Data Replication and also, of course, Point in Time Recovery. We can break the leader election problem down into a distributed locking problem. Essentially, we need to provide a distributed lock to the machine and call it a leader. This client library contains the required logic to implement the distributed lock in your application.
Now let's talk about how to implement this distributed lock using DDB so that the leader can perform all the required tasks and can also ensure fault tolerant leader for the system. A simple distributed locking system has 2 basic ingredients: a lock manager and the entities(hosts) trying to acquire a lock. As we are solving this problem using DDB, we will use DDB as the lock manager and the entities trying to acquire the lock will be the pool of hosts staking their claim to be the leader. The support for conditional updates on DDB proves to be a key benefit for the hosts to work in harmony. The table we will create will have the following imperative attributes:
- Key — This is the partition key for the table. A single DDB table can support multiple locks and, for every lock supported, we would need an independent item in the table. As per the schema supported by DDB, we would need the partition keys to be unique in themselves.
- Lease Period — This represents the amount of duration we grant a host, the lock. We can customize this while creating the table.
- Additional Wait Period — This is an extra support in the library provided on top of the lease period. The client code on each of the host will poll the table for duration equal to “additional wait period” besides the lease duration.
- Flag for Lock Released — As the name itself suggests, this flag depicts if any of the host machines have the lock currently.
- Record Version Number — This is a unique UUID which is updated on every heartbeat. We have outsourced the responsibility of updating the RVN to the host, which has the lock currently.
- Owner Name — We left the choice of picking up a name for easily identifying the host machine to the builder of the application.
- Heartbeat Period — The responsibility of heart-beating within the required period lies with the host machine. This is customizable as well.
- Refresh Period — This period defines the time after which every host machine will try to acquire the lock. If the lock is present in the DDB, the caller will get the response, consisting of lease duration, and if the lock is not present, the library will grant the lock to the caller.
For exact implementation, checkout this library. We have all the above mentioned attributes in the client code of the library and can customize all of them according to the needs of the application.
Let's touch a bit on how to implement this in an application which runs in production. As we will have multiple machines waiting to complete the responsibilities of the leader, we need to make sure only one of them gets the opportunity. We can follow a task based model where we can define the application in terms of tasks. The application will have multiple tasks and one of them (leader election?) will be blocking in nature. This will ensure we execute all the other tasks after we have elected the leader. The leader election task will have all the required paraphernalia (client library) running and other tasks will keep on waiting till the leader election task completes and gives a green signal to the remaining tasks. We can have as many tasks as per the need for the application which needs execution on the leader. These tasks can range from a coordinating task which designates tasks to the other nodes or maybe from having other nodes perform a periodic function as per the requirements from the application.
Below, I summarize the above discussion in a few simple bullet points:
- We need a leader in any distributed application to outsource many responsibilities and ensure fault tolerancy.
- Raft and Paxos require intrinsic deep dive and are tough to implement, therefore rendering them unusable in production.
- DDB Lock Client is a simplistic yet fault tolerant way to ensure a simple leader election in a distributed system.
I'll end this post with the above splash of learnings. We will deep dive into Raft and Paxos another day. Signing off for now. Ciao! — AD
References:
