Extending Raft algorithm: Witnesses and Arbiters, Part 2

The previous post described how to add a Learner role to the Raft consensus algorithm. This post discusses how to add the Witness and Arbiter roles.

The Witness and Arbiter concepts are very similar, yet they differ in subtle ways. Both are a kind of voter. A regular voter can both initiate elections and participate in log replication: as a leader it serves both read and write workloads, and as a follower it can still serve read-only workloads. A Witness strips away the ability to serve reads and writes: it still participates in elections and log replication, but it does not apply the log to its state machine. Because it never applies log entries, it can be placed on cheaper, lower-performance hardware. An Arbiter goes one step further: it only votes and only synchronizes membership-change log entries, and does not replicate any other log entries at all, thereby reducing bandwidth usage.

Witness

In practice, there are two common approaches to implementing a Witness. The first stores the full dataset: a snapshot plus all log entries from that snapshot up to the leader’s latest append. This is identical to a regular Raft replica in every way except that it does not apply the log, so it saves on CPU and memory. Since it is essentially no different from a normal replica, it has no impact on the safety, durability, or liveness of the Raft algorithm. The second approach stores no snapshot at all, keeping only a recent tail of the log. Because it holds no snapshot, it also saves disk space.

How much log should it keep? We want to preserve liveness as much as possible: if the witness is elected as the new leader, the cluster should still be able to continue replicating and serving. Assume matched_log[V] is the maximum log that replica V has matched with the leader’s log. For any quorum that includes the witness, its log must overlap with at least one other node’s log in that quorum, i.e. matched_log[V] >= first_log[W]. Setting the witness aside, in the cluster formed by the remaining nodes, let matched_log[Q] be the minimum matched_log[V] within some quorum Q. Then max(matched_log[Q]) for all quorums is the maximum log the witness may delete.

Because it keeps only the recent log, its durability is weaker than the full-data version. Consider a three-node cluster A, B, C where C is the witness. If A fails and is lost before a replacement replica has caught up, and then B also fails and is lost, classic Raft would still hold a complete replica on C, so no data is lost. A log-only witness, by contrast, would lose that data permanently.

Although we derived an upper bound on log truncation that does not hurt liveness, in practice the truncation policy may be set more conservatively. For example, the bound can be lowered to the minimum matched_log across all replicas; this way, during recovery more replicas can re-apply the log quickly, shortening the time to become available.

One risk of the witness is that if one or more nodes in the cluster keep lagging for whatever reason, the witness will have to keep a fully overlapping history in order to preserve liveness and safety. The space taken by that history can be far larger than a full replica. So some implementations also allow the witness to be switched into a full replica: this turns the witness into a healthy replica and the unhealthy replica into the witness, which both prevents the cascading cost of continuously shipping snapshots to a replica that can never catch up and also achieves the goal of saving resources.

Figure 1: A witness and a lagging replica exchange roles — the witness becomes a full replica while the lagging replica becomes the witness. This bounds the witness’s growing history and also saves resources.

As you can see, no matter how the policy is tuned, the witness does not actually require any change to the Raft algorithm itself, so the necessary adjustments can be made entirely at the application layer.

Arbiter

A Witness reduces CPU, memory, and disk overhead, but the network overhead remains. This matters especially in a two-region, three-datacenter (2R-3DC) deployment, where two datacenters are co-located in the same city and the third is in a remote region; cross-region latency and bandwidth are both expensive. There is a requirement for the remote datacenter to replicate no log at all, serving only as an election arbiter. That is precisely the role of the Arbiter. For an arbiter to arbitrate elections, it must know the current membership — that is, it does not synchronize data log entries, but it must synchronize membership-change log entries.

Figure 2: A two-region, three-datacenter (2R-3DC) layout. The two co-located datacenters are connected by low-latency, high-bandwidth links, while the remote datacenter hosts only the arbiter, avoiding cross-region replication of data logs.

A simple approach is to implement the Arbiter as a witness that frequently pauses log replication. Specifically, when a membership change or an election occurs, log synchronization to the witness is resumed and it goes through all of the witness’s existing flow. Once the cluster is stable and only data logs are being synchronized, log synchronization to the witness is paused. The benefit is that safety is easy to argue; the downside is that it still needs to synchronize a small amount of data log. If the user has no strict requirement about where data must be stored, this drawback is usually not a problem.

To be a true arbiter, its log is no longer continuous: it keeps only membership-change log entries and drops all data log entries. To guarantee liveness, it also needs to participate in elections, but it can only vote or request votes based on the latest known membership-change log entry. If it becomes the leader, it can neither commit any log nor provide service; it can only be responsible for replicating its own membership-change log out and transferring the leadership to any eligible replica.

If no data log is to be transmitted at all, then the membership used to commit data logs must be separated from the membership used to commit membership-change logs and elections. Consider a cluster with three nodes A, B, C, where C is the arbiter. Suppose A and B become partitioned, and we want to change the membership to A and C. Because C does not receive data logs, if A still uses {A, C} as the membership for committing data logs, it will be unable to commit any data log. On the other hand, if the election membership does not include C, then while B is partitioned, the cluster A, B, C cannot change to A and C at all. Therefore, the membership for committing data logs is the set of voters in the cluster excluding the arbiter; the membership for membership-change logs is the cluster’s full membership. The membership for elections is special: to guarantee that the members of the election quorum contain both the complete committed data log and the complete committed membership-change log, a new leader must obtain at least half of the votes from both membership lists, as well as a quorum of the full list. Since the membership-change membership is exactly the full membership, it needs at least half of the data-log membership and a quorum of the full list. For example, with m regular voters and n arbiters, a new leader needs ceil(m / 2) votes from the data-log membership and a quorum of floor((m + n) / 2) + 1 from the full membership. In a joint state, this requirement still has to be applied to each of the two lists separately.

Under the premise of a split membership list, a single membership-change log entry in the log, besides causing its own membership change, additionally triggers two membership-list switches: from a list that excludes the arbiter to one that includes it, and then back to one that excludes it. Because Raft’s log is linear, this implies that there must be a synchronization mechanism between log commits and membership-list switches. Otherwise, a successful commit under the post-switch list is not equivalent to a successful commit under the pre-switch list, and a fortiori does not guarantee that the log will not be lost.

Figure 3: Under a split membership list, a single membership change, besides its own change, triggers two additional list switches. The joint state holds both old and new versions of each list; data commits and membership-change commits each use a different list, while an election requires at least half of the votes from the data-log list and a quorum from the full membership list.

First consider the safety of data logs. To guarantee that a data log is not lost after the two membership-list switches, the leader’s data log must be present in some quorum of the post-switch membership. It is sufficient for the log to have been replicated to any quorum of either of the post-switch membership lists. For example, suppose we are changing the membership from {A, B, C} to {A, D, C}, where A is the leader and C is the arbiter. Assume the log entry that enters the joint state is (3, 10), where each entry is denoted as (term, index), and the data log entry just before it is (3, 9). We must ensure that (3, 9) has been replicated to {A, B} or {A, D} before the membership-change entry (3, 10) can take effect, i.e. before entering the joint state. The same logic applies to the entry that leaves the joint state: if the cluster exits the joint state at (3, 20), we must ensure that (3, 19) has been synchronized to A and D before the exit takes effect. Suppose that during any of this, a node fails; the newly elected leader must contain the new membership-change entry. If the arbiter becomes the leader, it can always synchronize the change entry to at least one node in the remaining quorum, and that node can then become the new leader and continue serving.

Next consider the safety of membership-change logs. For a membership-change log entry to survive the membership-list switch, either it must also form a quorum in the post-switch data-log membership, or the leader must wait for the arbiter to persist the membership before committing any subsequent data log. Either way, this means the leader must wait for the membership-change entry to be committed before it can commit any subsequent data log.

Applying these two rules, let’s walk through replacing an arbiter node and see how safety and liveness are preserved. Assume the cluster switches from {A, B, C} to {A, B, D}, where A is the leader and both C and D are arbiters. Suppose the joint-state entry is (2, 10). By the data-log safety rule, (2, 9) must already have been replicated to A and B, so the cluster enters the joint state. At this point, the cluster can still complete an election no matter which node fails. For example, suppose (2, 10) was replicated only to D, and then A fails. D becomes the new leader, replicates (2, 10) to B and C, and finally transfers leadership to B. After B becomes the leader, it may append other data log entries before choosing to exit the joint state. By the data-log safety rule, before A returns, B cannot replicate those data logs to A, so it cannot guarantee that the data logs remain present in at least one quorum after exiting the joint state. Therefore B cannot exit the joint state, nor can it perform any other membership change, and the cluster becomes unavailable.

Figure 4: The arbiter-replacement example. After A fails, D takes over and then transfers leadership to B, but the data logs appended during the joint state prevent B from exiting the joint state.

This exposes a tension between joint consensus as a linear two-phase algorithm and membership-list switching. Because joint consensus requires that a membership-change entry be committed before the next membership-change entry can be appended, and because the safety of a membership-list switch requires that the data log still hold a majority in the new membership, if new data logs are written while in the joint state, a membership change under an arbiter cannot exit the joint state after a node fails — that is, liveness is lost.

There are three ways to resolve this. The first is to abandon joint consensus and use only single-replica changes. This handles the datacenter-partition problem faced by a 2R-3DC deployment, but it introduces a brief risk window of unavailability when you want to replace a node. The second is to keep joint consensus but reject inserting data log entries during a change. The benefit is that it avoids the unavailability risk of the first approach; the drawback is that a membership change will introduce latency jitter.

The third approach is to adjust the joint consensus algorithm. Clearly, once the cluster enters the joint state, the only two things that can happen next are: the log is overwritten and the joint state rolls back, or the joint state is committed and can only be exited by a new log entry. Therefore, consecutive joint consensus steps can be chained by combining the previous step’s exit-joint with the next step’s enter-joint into a single log entry. For example, consider changing from configuration 1 to configuration 2 and then to configuration 3. The classic joint consensus algorithm first enters joint(1, 2); after it is committed, it switches to 2. After that switch is committed, it enters joint(2, 3), and finally reaches 3. The modified version instead goes to joint(1, 2); after it is committed, it switches directly to joint(2, 3), and finally reaches 3.

Here, joint(1, 2) and joint(2, 3) both contain membership list 2. The election quorum of each of these two joint states necessarily contains a quorum of configuration 2, and any two quorums of configuration 2 necessarily share at least one common member. Therefore, any election quorum of joint(1, 2) and any election quorum of joint(2, 3) must intersect. By the safety of elections, during the membership-change process, at most one leader can be elected within a term. The chained change algorithm is therefore safe. Let’s call this algorithm Chained Joint Consensus.

Figure 5: A comparison of classic joint consensus and Chained Joint Consensus. For two consecutive changes, the Chained version combines the previous step’s exit-joint with the next enter-joint, saving one state.

Apply Chained Joint Consensus to the example above. B appends data log entries during this time, and then notices that A never returns, so it decides to downgrade the cluster. It switches from ({A, B, C}, {A, B, D}) to ({A, B, D}, {B, D}). Because B’s own log already forms a quorum in the post-switch data-log membership (namely {B}), this change entry can be proposed. The change entry is committed by {B, D}, so the switch succeeds. It then proposes a new membership-change entry to switch to {B, D}, which also succeeds, and the cluster becomes available again. If B had appended data logs and then failed before the downgrade, and A returned, it could still follow a similar flow and ultimately switch to {A, D}.