Hey Isaac! I did a three minute "one-slide" lightning talk [1] on Viewstamped Replication at the PaPoC '21 workshop at EuroSys organized by Heidi Howard, and h

Hey Isaac! I did a three minute "one-slide" lightning talk [1] on Viewstamped Replication at the PaPoC '21 workshop at EuroSys organized by Heidi Howard, and had a few seconds to spend on how Viewstamped Replication compares with Multi-Paxos (Paxos with leader election) and Raft (Paxos with leader election and some overly strong restrictions). Raft is at the extreme end of the spectrum with lowest availability and lowest performance, compared to Viewstamped Replication and Multi-Paxos further along the spectrum. The reason for this is that Raft suffers from the distributed equivalent of the classic RAID 5 problem, where if the leader fails, it requires the next leader to have a perfectly pristine log without even a single latent sector error, or else the whole Raft cluster can become unavailable. Raft has no mechanism to repair the new leader's log and so cannot fully utilize redundancy to maximize cluster availability, whereas Viewstamped Replication Revisited describes how to leverage Merkle Trees for leader repair, and also features a recovery protocol in case a replica loses its whole state. The Raft paper and thesis have no storage fault model. At first glance, Raft appears easy to implement, yet Raft's correctness (let alone availability) also depends entirely on "perfect" storage across the whole cluster, which I find surprising given how even RAID systems have long moved on from RAID 5. Here again, Viewstamped Replication Revisited has no such dependence on durable storage for correctness and can be run entirely in-memory much more simply. Raft also leans on randomized election timeouts to deal with its problem of split votes during leader election, which all (split votes and randomized timeouts) both add unnecessary latency to the leader election phase. Viewstamped Replication has no problem of split votes to begin with, so it can react much more quickly to leader failure, since replicas in Viewstamped Replication are surprisingly "not selfish" and don't vote for themselves but rather work together to have an advantage in insight on who the next leader should be (simple modulo function). This additional deterministic input to the protocol I find is a massive algorithmic gain. RAFT is popular, but as Heidi Howard said in another of her talks, it's worth surveying the literature before reaching for RAFT. Multi-Paxos is identical to Viewstamped Replication which preceded it, except that it tolerates "gaps" in the log. In other words operations can be committed out of order. However, with our hash chaining optimization on Viewstamped Replication that we created for TigerBeetle [2], we're able to achieve the same performance benefit of having the followers ack ops instantly back to the leader (even if a follower doesn't yet have the complete log, i.e. we've moved log backfill repairs out of the critical path), but without all the added complexity that Multi-Paxos has of resolving "gaps" that are never filled. The difference between Paxos and Multi-Paxos is something that people often get wrong. Paxos does not do leader election but requires two RTTs to commit an op, with the advantage that any replica can lead for the op. Multi-Paxos does do leader election for the leader to order the op, but with the advantage that it requires just one RTT to commit an op. The choice of Paxos ("active replication" = 2 RTT) or Multi-Paxos ("passive replication" = 1 RTT) depends on how close your users are to all your replicas, and how you layout your cluster in terms of geography and availability regions. Raft was published in 2013 and is very similar to the Viewstamped Replication Revisited paper published by Barbara Liskov and James Cowling a year before in 2012 (in fact, I find the latter more understandable than the former). Both Raft and Viewstamped Replication are all in the Multi-Paxos family. Of course, Viewstamped Replication pioneered consensus a year before Paxos in 1988 in Brian M. Oki's doctoral dissertation, it's just that the terms "Paxos" or "Multi-Paxos" are how we classify these categories of algorithms today. Multi-Paxos is what most people need for state machine replication, and I find it remarkable that Viewstamped Replication had all of this, batteries included, from the beginning. [1] https://www.youtube.com/watch?v=tlz0FbzGGGo https://www.youtube.com/watch?v=tlz0FbzGGGo [2] You can see TigerBeetle's VR implementation starting from here: https://github.com/coilhq/tigerbeetle/blob/main/src/main.zig#L47-L56 https://github.com/coilhq/tigerbeetle/blob/main/src/main.zig...