Raft-style Elections: Dynamic Membership

I'm not usually one for sitting down and reading a PhD thesis. Usually.

The Raft consensus algorithm solves a common problem in computer science in a reasonably elegant, simple way. Let's say you have the following situation:

You have several systems tasked with (and capable of) running the same job periodically. You need to ensure the following:

You may assume this could be done with locks, but the final point of "picking up where the first left off in case of failure" complicates that solution due to the need for state management. This is a scenario that Raft would shine in, among many others.

Perhaps somewhat surprisingly, the official Raft homepage contains a really, really good interactive explanation. The Secret Lives of Data is another page which does an excellent job of showcasing the major points of the algorithm in a nice powerpoint-like presentation. I would generally recommend the powerpoint first since it tells you what you're seeing in the interactive exhibit.

I really do recommend checking those out. They do a better job of explaining how it works than I could in a single blog post. It'll be required reading for understanding the modifications made later in this post.

Let's take a look at our previous scenario of running jobs on a schedule and add one more constraint to it:

One of the biggest issues with implementations of the Raft protocol is that their expectation is that all members are pre-defined. Before you even start the quorum you need to know where and how many Raft members you have. This is a problem for systems that dynamically add or remove systems based on factors such as load. You'd have to re-create the entire consensus every time you add or remove a member - at best. At worst, you're just stuck.

A project I did a few years ago required such a system. I created a Raft-adjacent implementation which only handled leadership election, but did so with the added parameter that a member could be added or removed at any time. Without further ado, here's how I did it.

With dynamic membership, you're guaranteed to run into a situation in which there's an even number of members in your quorum. Raft handles this by requiring N / 2 + 1 members to elect a leader in the event of an even number of members, which is simple enough, but we need to re-calculate this when systems are added.

For an odd number of nodes, we use ceil(N / 2) instead. Both of these can be simplified to a single floor(N / 2) + 1 calculation.

For example, let's say we have a leader elected with three nodes. We then add three more nodes which know nothing about the current leadership election. In this instance, we want to set our current leader to a candidate and have it re-issue a new election cycle. This will mean that, for a short time, there will be no leader, but performing a full election starting with the current leader will virtually guarantee that member is re-elected and that all of the new members are up to speed.

At some point, you will likely have enough nodes that adding a few won't affect an election at all. There's also no need to re-calculate on membership removal because a current election cycle is as stable as the leader node. If the leader is lost, a new election cycle will only use the remaining members anyway.

The implementation I needed to write had no real use-case or need for a replication log. Raft is actually a story of two parts:

Not requiring this meant that heartbeats were smaller and on-disk persistence wasn't required. Vote tallies were simply stored in-memory on each member because they could easily be removed and re-added if needed anyway.

When a new member joined an existing cluster, it assumed no current state. It would do the normal thing of waiting until a timeout to perform a membership election, etc. If any member received a heartbeat of a higher election cycle than it already had, it would immediately set the current election cycle and leader. Heartbeats from leaders below our current election cycle can be safely ignored.

Similarly, if an existing leader or member node got a vote request from a (often new) member with an election cycle lower than it already had, the existing member would deny the vote and send back information on the current cycle and leader.

And, finally, if a new member joins during an election we can assume everyone is voting for the same leader (as is most often the case) and cast our vote accordingly. If this new member can see current votes being cast it can also set itself up accordingly and assume it is to follow a new leader.

These ensured that new members joining the quorum would quickly and reasonably safely get up to speed on the current state of things.

There's one final issue that can come up with dynamic membership: When a new quorum first starts, it will likely only have one member to start with but may very quickly get a second.

The temptation is to have each node set itself as the leader on initial startup but this will mean that, if the current election cycle is 1, we'll end up in a split-brain where each node simply assumed it was the leader and we'll have to wait for one of them to time out before a "real" election takes place.

We found that, sometimes, it was nice to be able to force a leader in a few relatively rare cases such as removing an existing leader (and knowing we were going to do it) without wanting to wait for a new election cycle.

In these cases, "proposing" a new leader is as simple as setting a new election cycle and proposing one of the members as the new leader for that cycle (and then becoming a candidate or follower on the node that set the new cycle). Assuming everything is reasonably stable already, no new election cycles would be going on anyway so that would effectively be guaranteed leadership for the chosen member.

That's really about it. Raft is a robust and simple algorithm and adding to it is equally simple, with a few "gotchas" here and there and some optimizations that can be done while sacrificing a tiny bit of reliability.

While there weren't any fun pictures in this one, I hope you enjoyed a somewhat-technical write-up regardless.