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 non-data log entries, and does not replicate data 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 highest log through which the witness may compact.

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. There is no need to resume from the last replication progress; instead, it can quickly jump to a recent replication point by installing only the corresponding snapshot metadata, and then resume log replication from there. 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 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 partial log. If it becomes the leader, it can neither commit any log nor provide service; it can only be responsible for replicating its own partial log out and transferring the leadership to any eligible replica.

Membership list switch

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 non-data 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 non-data 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 non-data 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 non-data log 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 non-data log entry in the log 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 triggers two additional list switches. The joint state holds both old and new versions of each list; data-log commits and non-data-log 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.

Log Safety

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 non-data logs. For a non-data 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 entry before committing any subsequent data log. Either way, this means the leader must wait for the non-data log 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: Replacing the arbiter. After A fails, D forwards the old enter-joint to B; B then appends its own term-4 empty log, but exit-joint fails because it cannot form a quorum on {A, B}.

Membership Change

This exposes a tension between joint consensus as a linear two-phase algorithm and membership-list switching. Joint consensus requires that a membership-change entry be committed before the next membership-change entry can be appended; otherwise it cannot be guaranteed that the membership lists before and after the change intersect. And the safety of a list switch requires that the data log still hold a majority in the new membership. So 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. During this process there are not only data logs, but possibly also the empty log entry that a new leader must append upon taking office. To ensure that the new leader can commit the old membership-change log and still propose a new change entry to exit the intermediate unavailable state, we must guarantee:

1. No data logs may be added during the joint process, otherwise the joint state cannot be exited;
2. The empty log entry appended after the leader takes office must be treated as a non-data log, committed using the non-data log membership list; otherwise the new leader cannot commit a log entry of its own term, and therefore cannot commit the predecessor leader’s possibly-remaining membership-change log.

Apply this to the example above. After B takes office, it synchronizes its appended empty log entry through {B, C} and {B, D}, thereby committing the predecessor leader’s enter-joint entry. Then it wants to exit the joint state. Because of the data-log safety, we can be sure that all data logs before the enter-joint have already been replicated by B, so it only needs to replicate the data logs to any quorum after exiting the joint state. We know A definitely also has the data logs, so B can safely propose the exit-joint entry, completing the change and being able to start accepting data logs again. If A still does not come back, a new membership change can be initiated to kick A out of the cluster.

Now consider another case: suppose {A, B, C} is changed to {D, B, C}, where A is the leader and C is the arbiter. Assume A had not yet sent the data logs to D when it failed at the same time as D (for example, the same datacenter lost power). By the reasoning above, B can definitely become the leader. But B cannot determine whether D has the complete data logs, so it still cannot exit the joint state. It is therefore visible that liveness needs a stricter constraint: the leader’s data log must be present in some quorum of the final post-switch membership list. By this constraint, when B finds itself in the joint state, it can be sure that the data logs before the joint entry have definitely already existed in a majority of the members of the exit-joint data membership list, so it can confidently propose the exit-joint entry, completing the change.

Figure 5: The stricter liveness rule — the gate sits at enter-joint. If D holds no log the change is blocked; if D holds the log, enter and exit both succeed. The membership change never gets stuck in the joint state.

If the business is very latency-sensitive, a single-server membership change can be used instead. This approach does not split the change into two phases, so it naturally avoids the blocking problem introduced by joint consensus. The latency waiting introduced by the membership-list switch still remains, and it also brings its own availability risk inherent to a single-server change. Treating the empty log entry as a non-data log is, however, still mandatory; otherwise the new leader would likewise be unable to commit the single-server change left behind by its predecessor, and the cluster would ultimately get stuck.

Summary

This post introduced two cost-saving replica types — the Witness and the Arbiter — along with the algorithmic adjustments needed to integrate them into Raft. The Witness is less invasive and mechanically simpler; used appropriately, it can achieve cost savings comparable to the Arbiter. The Arbiter’s mechanism is more complex: membership changes require additional coordination of the replication and commit order between data logs and membership-change logs, and in extreme cases can introduce latency jitter, but it yields the most extreme cost savings. If cross-region bandwidth is the main bottleneck and you can tolerate latency jitter, the Arbiter is a good choice; otherwise the Witness is already sufficient.