[_vvhw]

I am implementing a Multi-Paxos variant called Viewstamped Replication (http://pmg.csail.mit.edu/papers/vr-revisited.pdf) for TigerBeetle (https://github.com/coilhq/tigerbeetle) and keeping notes along the way to help other implementors down the line.

Some things I'm finding so far:

* As developers, we're used to thinking of services in terms of streaming TCP connections and RPCs. You send a request on a connection and get a response back on the same connection. However, distributed consensus algorithms (or at least their authors) like to think and write in terms of messages and message passing and the classic Actor pattern. For example, it's not uncommon for a consensus client to send a message to a leader but then get the ACK back from another server, a subsequently elected leader. That's at odds with the networking protocol we're used to. It's not always easy to shoehorn a consensus protocol onto a system that already has a TCP oriented design. Embrace message passing and multi-path routing.

* We're familiar with Jepsen. The network fault model is front of mind (dropped/delayed/replayed/corrupted messages, partitions, asymmetrical network topologies and performance). We're far less wary of the storage fault model: latent sector errors (EIO), silent bit rot, misdirected writes (writes written by firmware to the wrong sector), corrupt file system metadata (wrong journal file size, disappearing critical files), kernel page cache coherency issues (marking dirty pages clean after an fsync EIO), confusing journal corruption for a torn write after power failure.

* We underestimate the sheer bulk of the code we need to write to implement all the components of a practical consensus protocol correctly (a consensus replica to run the protocol at each node, a write ahead journal for storage, a message bus for in-process or remote messaging, a state machine for service up calls). The consensus protocol invariants are tough but limited, but the amount of code required to be written for all these components is brutal and there are so many pitfalls along the way. For example, when you read from your write ahead journal at startup and you find a checksum mismatch, do you assume this is because of a torn write after power failure as ZooKeeper and LogCabin do? What if it was actually just bit rot halfway through your log? How would you change your write ahead journal to disentangle these?

* We tend to think of the correctness of any given consensus function as binary, and fail to appreciate the broad spectrum of safety requirements required for specific components of the consensus algorithm. In other words, we don't always take fully to heart that some consensus messages are more critical than others. For example, we might resend an ACK to the leader if we detect (via op number) that we've already logged the prepare for that op number. However, most implementations I've seen neglect to assert and double-check that we really do have exactly what the leader is asking us to persist before we ACK. It's a simple verification check to compare checksums before skipping the journal write and acking the duplicate prepare and yet we don't.

* Another example, when we count messages from peers to establish quorum during leader election, we might count these messages without applying all the assertions we can think of on them. For example, are we asserting that all the messages we're counting are actually for the same leader election term? Or did we simply assume that we reset the array of messages being counted during the appropriate state transition sometime back in the past? The former is a much stronger guarantee, because it keeps you from double-counting stale leader election messages from past election phases, especially if these were successive (e.g. multiple rounds of elections because of split votes with no successful outcome). We should rather assume that the array we store these messages in, and that we're counting, could contain anything, and then assert that it contains exactly what we expect.

* Our intuition around fault tolerance might suggest that local storage faults cannot propagate to destroy global consensus. Yet they do (https://www.youtube.com/watch?v=fDY6Wi0GcPs). We need to be really careful how we repair local faults so that we do so correctly in the context of the global consensus protocol.

* Finally, I think what also really helps is to have a completely deterministic consensus protocol Replica abstraction that you initialize with an abstract Message Bus, Journal and State Machine instance. This Replica instance can send messages to in-process or remote Replica instances, and has on_message() handlers for the various protocol messages that either change state and/or send messages but can never fail (i.e. no error union return type) because that amplifies the dimensionality of the code paths. For timeouts, don't use the system clock because it's not deterministic. Instead, use a Timeout abstraction that you step through by calling tick() on the Replica. With these components in place, you can build an automated random fuzzing test to simulate your distributed network and local storage fault models and test invariants along the way, outputting a deterministic seed to reproduce any random failures easily.

[eternalban]

> I am implementing a Multi-Paxos variant called Viewstamped Replication

VR is -not- a variation of Paxos much less the later multi-paxos.

Viewstamped Replication was developed independently from Paxos and is distinct from Paxos. (And it came out a year before Paxos):

From the author of this OP:

https://brooker.co.za/blog/2014/05/19/vr.html

"Introduced in May 1988 in Brian Oki's PhD thesis, Viewstamped Replication predates the first publication of Paxos by about a year. If you're looking for intrigue you may be disappointed: both Lamport and Liskov claim the inventions were independent."

[_vvhw]

VR was of course developed independently by Barbara Liskov and Brian Oki and then revisited by Barbara Liskov with James Cowling.

However, it is common practice and perfectly acceptable to refer to VR as a variant of "Multi-Paxos" because that's actually EXACTLY what it is in theory, the protocol maps one-to-one, cf. Dan Ports (he explains it nicely here, see slide 46 if you want his bumper sticker version): https://courses.cs.washington.edu/courses/csep552/16wi/slide...

The more you understand VR and Multi-Paxos the more you will see that this is true.

In fact, and you may be surprised/disappointed at this, but Raft is also a variant of Multi-Paxos very similar to VR (cf. Heidi Howard https://groups.google.com/g/raft-dev/c/cBNLTZT2q8o), except with tighter restrictions on leader election that make it less efficient than VR, which is why we chose VR over Raft coincidentally.

By the way, that's a fantastic post by Marc Brooker and was part (along with references by Martin Thompson and Heidi Howard) of what made us pay more attention to VR in the first place.

[eternalban]

Not surprised or disappointed, really. My take on RAFT is that it's basically Paxos for elections and a more relaxed regime in between.

But Brooker's post (in my OP) actually addresses VR vs Paxos distiction:

It's easy to believe that these two protocols are, in fact, the same. That doesn't appear to be the case. A new paper by van Renesse et. al., titled Vive La Difference: Paxos vs. Viewstamped Replication vs. Zab, looks at Paxos and VR through the lenses of refinement and abstraction, and finds they are not exactly equivalent due to design decisions in the way they refine a model the paper calls Multi-Consensus. One of the key differences is active (Paxos) vs. passive (VR) replication: "Passive vs. Active Replication: In active replication, at least f + 1 replicas each must execute operations. In passive replication, only the sequencer executes operations, but it has to propagate state updates to the backups."

Which reminds of ZAB (of Zookeepr fame), another protocol languishing in relative obscurity.

Anyway, thanks for your input. I have this thing for underdogs and this VR vs Paxos thing is a very minor cause, and I guess you triggered me there. /g

[_vvhw]

"My take on RAFT is that it's basically Paxos"

You're right that Raft is Paxos for the leader election phase, in the same way that VR is Paxos for the view change phase, or that Paxos is basically VR's view change but for deciding a value.

But a better way of saying this would be that Raft is Multi-Paxos (https://news.ycombinator.com/item?id=23123701), because Raft is much more than Paxos (in the same way that VR is more than Paxos because it not only decides on a value/leader but is also a protocol for replication). I think this is where our misunderstanding came in.

Yes, I've read the linked "Vive La Difference" paper. As the excerpt makes clear, one of the key differences is active replication (Paxos: with multiple concurrent processes that want to decide on a value) vs passive replication (Multi-Paxos variants: VR and Raft and ZAB all protocols with a single leader elected for a given term/view during which multiple rounds of replication take place).

The name Multi-Paxos just means that the first round of Paxos for leader election is reused for multiple rounds of replication, driven by a single leader instead of competing processes always using the minimum two-phase Paxos.

"I have this thing for underdogs"

Yes, me too, and that's why I tried to show that VR is no less than Multi-Paxos in my original comment, and that Raft is not newer than Multi-Paxos in my follow-up. It would be great for VR to receive the recognition it deserves.

[eternalban]

Well, in that case we mildly disagree. My take is this:

That functionally M-Paxos and Raft are equivalent does not make them the equivalent. RAFT uses a protocol that looks awfully like Paxos for election of a single leader - so it has nothing to do with multi-Paxos (as I understand it). But that L.E. phase + the interim regime gives you functional equivalence to Multi-Paxos.

[_vvhw]

Happy to mildly disagree!

"RAFT uses a protocol that looks awfully like Paxos for election of a single leader"

Agreed.

"so it has nothing to do with multi-Paxos (as I understand it)"

Except that Raft is not only a protocol for single leader election, it's also a replication protocol (see the "AppendEntries" message), and that's why it is Multi-Paxos. Multi-Paxos is just the category or classification for a family of consensus protocols that use the strategy of single leader election and replication with terms/views/epochs (the "interim regime" you refer to) for strict serializability. This is the passive replication leader/follower primary/backup strategy.

Outside of Multi-Paxos, there are also consensus protocols that achieve strict serializability with Paxos but without electing a single stable leader, e.g. FastPaxos. These exploit low latency between the client and all replicas, but this is not always available, or may suffer from tail latency issues, hence implementations such as Raft use the MultiPaxos strategy of a stable leader, which may be better connected to the rest of the cluster than the client.

As an implementation, depending on how you zoom, Raft is very different to VR and ZAB, but it's still in the same Multi-Paxos class since it reuses a single stable leader derived from one instance of Paxos for "multiple" rounds or instances of replication, hence "Multi-" "Paxos".

At least this is how I understand it from Heidi Howard and others who seem to share this "view".