3 ms·

As an example of this in distributed systems: There's a classic metastability issue in probably most implementations of state machine replication protocols suc

As an example of this in distributed systems: There's a classic metastability issue in probably most implementations of state machine replication protocols such as Raft, where a lagging follower, if it sees an op that's newer than what it's expecting, must first repair and catch up its state (FIFO repair) before it can ACK back to the leader. Apart from introducing latency in the critical path, this can lead to really bad queueing behavior where the lagging follower queues the latest request from the leader while it first catches up, but because this catch up can take seconds or minutes, in that time the pending request queue has also overflowed, and now we're back to state transfer catch up all over again, a vicious cycle. However, there is a new approach (LIFO repair) that we developed for TigerBeetle [1] to eliminate this bimodality, maintain (and even reinforce) safety and achieve constant ACK latencies from all followers, no matter their state. If you're curious as to how this works, we'll be talking about this LIFO repair as part of Viewstamped Replication Made Famous [2], a $20,000 consensus challenge launching in September. [1] https://www.tigerbeetle.com https://www.tigerbeetle.com [2] https://github.com/coilhq/viewstamped-replication-made-famous https://github.com/coilhq/viewstamped-replication-made-famou...

MatteoFrigo 5y ago
I am looking forward to learning about the LIFO repair when you guys decide to talk about it. However, the fact that Raft is goofy and conflates safety, liveness, and dynamics, doesn't mean that the metastability problem has not been solved in a more traditional FIFO setup. The basic issue is that things like Raft (but most other descriptions in the literature as well) describe replication in terms of RPC: request arrives at the leader, the leader sends three RPCs to followers, waits for two acks, etc. If you actually implement things this way (and many people do) then you end up with the problem that you describe. However, you can organize the system in a different way. A request arrives to the leader and is appended to the leader's proposer log. A separate asynchronous protocol reconciles the proposer log with the follower acceptor logs. This protocol looks like TCP, with some caveats to account for log divergence, so it is pretty well-understood technology. By dimensioning log sizes and timeouts correctly, you can deamortize the whole catchup procedure and bound the latency of every operation as seen from the client (assuming that a quorum of acceptors is available).
- jorangreef 5y ago
  Yes, and in fact one of the things I like about Viewstamped Replication is that it does not describe replication in terms of RPC, but rather in terms of message passing, which I believe maps better to the domain of consensus, and which nudges people in the right direction when they start to think about their messaging protocol. Thanks, hope to see you at the live launch event in September! All the details are in the repo linked above. Beyond some of these new techniques, what I'm really most excited about for the live launch event in September is the back-to-back interviews with Brian Oki (Viewstamped Replication 1988) and James Cowling (Viewstamped Replication Revisited 2012). It's going to be a special moment, celebrating the pioneering consensus and replication protocol and the people behind it.

MatteoFrigo 5y ago

I am looking forward to learning about the LIFO repair when you guys decide to talk about it. However, the fact that Raft is goofy and conflates safety, liveness, and dynamics, doesn't mean that the metastability problem has not been solved in a more traditional FIFO setup. The basic issue is that things like Raft (but most other descriptions in the literature as well) describe replication in terms of RPC: request arrives at the leader, the leader sends three RPCs to followers, waits for two acks, etc. If you actually implement things this way (and many people do) then you end up with the problem that you describe. However, you can organize the system in a different way. A request arrives to the leader and is appended to the leader's proposer log. A separate asynchronous protocol reconciles the proposer log with the follower acceptor logs. This protocol looks like TCP, with some caveats to account for log divergence, so it is pretty well-understood technology. By dimensioning log sizes and timeouts correctly, you can deamortize the whole catchup procedure and bound the latency of every operation as seen from the client (assuming that a quorum of acceptors is available).

jorangreef 5y ago
Yes, and in fact one of the things I like about Viewstamped Replication is that it does not describe replication in terms of RPC, but rather in terms of message passing, which I believe maps better to the domain of consensus, and which nudges people in the right direction when they start to think about their messaging protocol. Thanks, hope to see you at the live launch event in September! All the details are in the repo linked above. Beyond some of these new techniques, what I'm really most excited about for the live launch event in September is the back-to-back interviews with Brian Oki (Viewstamped Replication 1988) and James Cowling (Viewstamped Replication Revisited 2012). It's going to be a special moment, celebrating the pioneering consensus and replication protocol and the people behind it.