Consensus algorithms at scale: Part 5

If you’re still catching up, you can find links to each article in the series at the bottom of this article.

In this post, we will look at how to make revocation and establishment of leadership work if there are race conditions. We will also cover forward progress requirements.

Recap of parts 1-4

Durability is the main reason we want to use a consensus system.
Since durability is use-case dependent, we made it an abstract requirement that the consensus algorithms assume nothing about the durability requirements.
We started off with the original properties of a consensus system as defined by Paxos and modified it to make it usable in practical scenarios. Instead of converging on a value, we changed the system to accept a series of requests.
We narrowed our scope down to single leader systems.
We came up with a new set of rules that are agnostic of durability. The essential claim is that a system that follows these rules will be able to satisfy the requirements of a consensus system. Specifically, we excluded some requirements like majority quorum that have previously been used as core building blocks in consensus algorithms.
We looked at a number of practical scenarios where it is difficult to make a simplistic majority quorum approach work well. A flexible consensus system would accommodate those use cases more comfortably.
We conceptualized the leadership change process into two distinct concerns: Revoke and Establish. This opens up more implementation options that previous traditional algorithms did not accommodate.

Two approaches to resolving race conditions

If we had only one agent that performed leadership changes, there would be no reason to worry about races. But this is not practical because a network partition could isolate that agent and prevent it from performing the necessary actions.

Introducing more than one agent to perform leadership changes requires us to handle race conditions. There are two approaches to resolving races: either the first agent wins, or the last one wins. The determination of who is first or last can vary depending on the approach used. We will drill down on this as we analyze each option.

An approach that makes the first agent win essentially prevents later agents from succeeding. This is equivalent to obtaining a lock. We will therefore call this approach lock-based. The other one will be called the lock-free approach.

We will analyze these approaches separately. As we will see below, this difference is quite fundamental, and it is surprising that it has not been called out explicitly for consensus algorithms.

The elector

Let us make a quick detour to introduce a new term.

At YouTube, each shard had fifteen eligible primaries. Having all of them scan for failures and perform active failovers was not practical. Instead, we had one agent in each region that scanned for failures and also performed leadership elections.

In other words, it is not necessary for a candidate to elect itself as leader. A separate agent can perform all the necessary steps to promote a candidate as leader. We will call this the elector. In many situations, like in the case of YouTube, this separation may be necessary. Unsurprisingly, Vitess has also inherited this separation: VTorc is a Vitess component that acts as the elector.

It is beneficial to conceptualize the role of an elector as being distinct from that of a candidate. This does not preclude a candidate from taking on such a role. This terminology will be useful for the sections below.

Lock-based approach

Obtaining a lock simplifies the problem of changing leadership. It guarantees that the elector that succeeds at getting the lock is the only one capable of making changes to the system.

However, the lock-based approach introduces a problem with forward progress. For example, an elector may successfully obtain a lock and then crash or become partitioned out of the rest of the system. This will prevent all other electors from ever being able to repair this situation. To resolve this, lock-based systems must introduce a time component: any elector that obtains a lock must complete its task within a certain period of time, after which the lock is automatically released.

A lock-based approach generally converges faster than approaches that are lock-free. This is because the first node that attempts a leadership change is likely to have made the most progress towards completing the task. Under most circumstances, giving the first elector the chance to succeed will complete the leadership change with the least disruption.

The act of obtaining a lock requires the participation of multiple nodes. This ensures that forward progress is possible if some nodes fail or if there is a network partition. Coincidentally, this problem shares some properties of distributed consensus. For this reason, the existing nodes that are participating in the quorum could be reused to obtain the lock. In fact, this is exactly what Raft does, but it is implicit.

Locking as a separate concern

One may argue that a system like Raft does not obtain a lock even though it makes the first elector win. This is because the act of obtaining a lock is shadowed by other actions it takes. If you subtract out the other actions (revoke, establish, and propagate) in the code that performs an election, it will be evident that what is left is the act of obtaining a distributed lock.

An algorithm has the option of implementing the locking function as an explicit and separate step. Choosing to do this gives us more flexibility because we can fine-tune this step without conflicting with the concerns of revocation or establishment.

How to obtain a lock

The primary requirement of using the existing nodes to obtain a lock is that the set of nodes each elector reaches has to intersect with those of the others. A majority-based system automatically ensures this intersection. This allows for algorithms like Raft to piggy-back the locking as a side-effect of performing revocation and establishment.

For systems that do not use the majority approach, the fact that revocation has to complement establishment ensures that the electors will have to reach an intersecting set of nodes. So, this property also allows us to perform locking as a side-effect of revocation and establishment.

But this is not our only option. Any mechanism that ensures that only one elector can act will work equally well. Here are some alternatives:

Use a simple majority for the purpose of obtaining a lock, while using a more sophisticated approach for revocation and establishment.
In Vitess, we use an external system like etcd to obtain such a lock. The decision to rely on another consensus system to implement our own may seem odd. But the difference is that Vitess itself can complete a massive number of requests per second. Its usage of etcd is only for changing leadership, which is in the order of once per day or week.
Humans could decide to manually authorize an elector to perform a leadership change, essentially giving it a “lock”.

Proposal numbers

If you are using a lock-based approach, there is no need to use proposal numbers or leadership terms for the purpose of electing a leader. But we may still need to assign such a number to facilitate the propagation of requests. We will discuss this in a subsequent blog.

Graceful leadership changes

Once a lock is obtained, the elector is guaranteed that no one else will be changing the system while they hold the lock. A big advantage of this situation is that the current leader can be discovered, which allows us to use the graceful method of changing leadership described in the previous blog.

The clock

In lock-based systems, we have to rely on accurate clocks. The system also has to make sure that sufficient tolerances are built into timeouts to account for normal clock skews, which are typically in the milliseconds. In general, it is advisable to use “many seconds” of granularity to sequence events.

Consistent reads

Relying on locks lets us exploit the time component to give leaders a lease, thereby guaranteeing no leader change during the lease period. This lets the users perform efficient, consistent reads by accessing the leader without the need for a quorum read. The existing leader could continue to renew the lease as it completes more requests, which leads to prolonged stability.

Lock-free approach

In the case of a lock-free approach, the newest elector must win over an older one. This requires the algorithm to assign a time-based order to the electors that are racing with each other. In Paxos, these are referred to as proposal numbers. In Raft, these are known as term numbers. To facilitate reasoning, we can view these numbers as timestamps.

How does this work?

The core of the lock-free approach is that the followers that accept an establishment or revocation request must remember the timestamp of the elector that issued the request and should reject requests with older timestamps.

There are two possible ways a lock-free approach would converge:

The elector with the older timestamp completes its election before the one with the newer timestamp. Following this, the one with the newer timestamp will end up revoking that leadership and establishing its own.
The elector with the newer timestamps completes first. Then the one with the older timestamp will fail at its attempt, and the leadership established by the newer timestamp will prevail.

To cover the above scenarios, every elector must assume that there may be another elector with an older timestamp attempting a leadership change. It must therefore attempt to revoke leadership from all potential candidates, not just the current known leader. The completion of this process ensures that all possible leaderships (present and future) with an older timestamp are invalidated. This addresses the case where an old elector is slow at performing its actions. This also adds safety against clock skews: a new leader with an incorrect older timestamp will just fail at completing a leadership change, as if it was an older leader.

Pros and Cons

The main advantage of a lock-free approach is that it naturally supports forward progress. If an existing elector fails, a different elector can initiate a new round without knowledge of the state or age of an older elector. For this reason, there is no need to depend on timeouts.

The disadvantage of a lock-free approach is that there is no certainty of a stable leader. This is because it is possible for a leadership to end between the time you discover it and give it a request.

Consistent Reads

The absence of a stable leader makes consistent reads complicated. We essentially have to resort to quorum reads.

Recommendations

The elegance of a lock-free approach may seem tempting, but the lack of a stable leader complicates everything else. Having to reach a quorum for consistent reads is a major drawback for scaling systems.

Weighing these options, a lock-based system should be preferred for large scale consensus systems. Having a stable leader simplifies many other operational parts of the system.

In Vitess, the current leader for each cluster is published through its topology, and a large number of workflows rely on this information to perform various tasks. Any operation that does not want the leader to change just has to obtain a lock before doing its work.

Consensus algorithms at scale: Part 5 - Handling races