Discussion for a better understanding of Derecho.

[Steamgjk]

After reading the TOCS paper, I feel Derecho is fantastic, but I still have a few questions I am not sure of, so I would like to discuss them with you staff, in order to make a better understanding.

1. I am trying to make a head-to-head comparison between Multi-Paxos/Raft and Derecho from the design perspective.The first comparison point is the commit condition. Suppose we have 3 nodes, denoted as P, Q, R. In Multi-Paxos, it has the concept of quorum, which is f+1=2. So if the request is accepted and replicated to 2 nodes (1 leader + 1 follower), then it is committed (i.e. can be recovered after crash). Derecho, on the other hand, describes the commit condition as "when enough copies are safely logged, Derecho can consider the update to have committed (green versions), and read-only queries can be permitted to access the updated values. " Here I am not sure whether "enough copies" means 2 or 3.

   Suppose P receives a client request, P ordered_multicasts it, and receives 'true' from P and Q, but not from R. In this case, can P reply "committed" to the client?

   I tend to believe "enough copies" is 3. In the above case, the update information has not been propogated to R. But then another request comes to R querying the system state (Since there is no strong leadership in Derecho, the client just takes an arbitrary node from P,Q,R to query, and it picks R). R can only return its latest commit version, which does not include the change caused by the previous request. In that way, it breaks linearizability.

2. "Derecho uses a simple round-robin delivery order: Each active sender can provide one multicast per delivery cycle, and the messages are delivered in round-robin order. "

   In my understanding, a node becomes active when it receives the request from external clients. But what if some node, say, R, does not receive any external request for a long time? Does R still need to issue multicast in every delivery cycle (just like no-op)? What is the definition of "delivery cycle"? How does these 3 nodes coordinate this? I feel there must be a centralized role to coordinate them. If all the 3 nodes are active senders, then P:1, Q:1, and then R fails or its request is delayed, but P and Q are still multicasting P:2, Q:2, in this way, should P:2 and Q:2 wait until R:1 appear, or can P:2 and Q:2 be appended directly after Q:1?

3. Based on para 2-3 in Sec 3.6, If any active node fails, then a new view will be triggered. Does that cause a degradation of liveness, compared with Multi-Paxos? For Multi-Paxos, if one node fails, the other 2 can still form the quorum and continue to work without being affected by that failure. But based on the description here, so long as one node fails in Derecho subgroup, the remaining can only come back to normal after the new view and removing the failed one.

4. Related to 2, the consistency of SSTs on each node is implemented by using RDMA to poll each other's SST all the time, so that each node's SST can be continuously updated, and the execution order of the requests issued by every node is determined by the round-robin order, e.g. P:1, Q:1,R:1, P:2, Q:2, R:2... It is high-performance due to RDMA. But when we are using TCP, I think its latency should also be at least 4 message delays: Suppose a client submit a request to R (This is R's first request, R:1) and gets the reply from R.Then the message flow is client->R->P,Q->R->client. More than that, if P and Q do not recieive any external requests, I guess there are 2 possible options: (1) P, Q also need to multicast a no-op request, otherwise, R cannot execute the client request, because P:1 and Q:1 must be executed ahead of it (2) there is some timeout mechanism, R waits for some time and then it is sure that P:1 and Q:1 will not come, so that it can execute R:1. Which option is true, or are there any other options?

5. Regarding Figure 6, client is allowed to query the state with timestamp. Does derecho assume clocks among clients and replicas are synchronized or not? I am considering, if clients' clocks are not synced, Client-A has a faster clock than Client-B, and they both use their current timestamp to query and they both beleive they will get the fresh value. Then, even if they submit query simulatenously (or even further, Client-B queres after Client-A gets its query result), Client-B will get an older version of result than Client-A, right? In that way, it also violates linearizability.

[KenBirman]

This is kind of a complicated posting because you are asking a mixture of good questions with kind of basic ones, giving me the sense that maybe you didn't read the TOCS paper sections that covered some of these topics. I would have a look at the video we used in 2019 when we taught a 3-hour introduction to Derecho at SOSP in a tutorial session there. It is available here or from http://www.cs.cornell.edu/ken/slides

1. You don't seem to have internalized the way that virtual synchrony works. This is very important to understand and can lead to HUGE confusion otherwise. In virtual synchrony, we always start with membership management. Membership is automatically managed and tracked and reported, and everything is build on this membership layer -- and it uses a standard quorum based Paxos protocol very much like if we used RaFT for membership, or some other Paxos (the relevant paper and protocol would be vertical Paxos, and specifically, protocol II). You could also look at the video of lecture 11, at https://www.cs.cornell.edu/courses/cs5412/2022sp/Syllabus.html.

   Now the reason this matters is because with membership managed for the protocols, we can run a Paxos with the update quorum equal to N_k, but now N_k is the size of the current view for the current epoch: the number of members listed in view k. Stop here, make sure you fully understand this point. Don't read onwards until this is totally obvious for you... it is so important to everything else that by skipping past this, you've confused yourself in a major way.

   Good, so now we are on the same page! I hope you suddenly have a horrifying insight: Derecho is waiting for replies from all the N_k members. It isn't waiting for a subset. It wants every single one of them to reply. Every single member of the group will have exactly the identical data -- this is a model called state machine replication, but not using quorums for the logs. It works like atomic multicast and in fact Derecho is an atomic multicast solution, when used in volatile mode.

   So what if some process doesn't respond? Well, eventually, the view manager kicks it out, a new view k+1 will be formed, and that process won't be included. The "termination" code runs for the prior epoch (this is fully explained in the TOCS paper). Then a state transfer might occur if someone joined the group. And then we resume with a new view and hence a new N_k+1.

   You can see now that all of question 1 was based on a very basic misunderstanding and that maybe it would be a good idea to reread the TOCS paper. Good thought... you should!

2. This is (mostly) a good question. We discuss it in much more detail in the Spindle paper, which is available from http://www.cs.cornell.edu/ken (click publications). But in a nutshell: the null sending scheme is adaptive and automatically sends a null if the process has nothing else to send and we need something from it for the round-robin rule to be applied, but won't do stupid things like sending a stream of nulls for no good reason.

   To the extent that this is NOT a good question, we get back to your very big misunderstanding about membership. Let me ask you: given managed membership, why does this answer the second half of your question 2? You should be able to easily see this now. If not, go back and do that homework! There aren't any shortcuts... if you don't understand virtual synchrony you won't understand Derecho.

   (Neither will the professor you are doing this for! Keep that in mind too because you may have to educate them -- famously, professors often learn from their students...)

3. No, not at all. In fact they are really using the identical quorum policy, except that in Derecho it "kicks in" only when new views are defined. In multiPaxos it gets applied on every update even if membership has been stable for an hour (which is probably conservative: membership in most replicated services would be stable for many hours at a time). Why do extra work on every update if you can just save it up and only do that work when updating membership? But the liveness rule is actually the identical one. It has a fancy name called <>W and without adding strange network assumptions, <>W is the usual requirement (or something stronger that has <>W plus extra stuff built in).

4. No, there isn't any special reason TCP would be different. Actually datacenter TCP performs pretty close to RDMA and we think that with DPDK the gap may even vanish -- we are doing experiments to investigate this now. Anyhow, TCP is faster than you knew, and in any case your scenario doesn't pose any particularly problematic delays. Reading the Spindle paper will help. Have a look at it. (I explained how to find it in 2).

5. This is quite a good question. You can read more about the exact way the snapshot isolation scheme is working by looking at the old Freeze Frame File System paper, FFFS. But in fact Derecho isn't tracking causal order and in the HLC timestamps the causal field is always 0. The point you make is valid: when we switch to using real-time (1) we do assume a delta, and (2) we will respect sender-order if the sender uses increasing timestamps, but the bottom line is that we are switching to a real-time ordering, and NOT using the request arrival ordering except in the "same sender FIFO" case. I don't think this violates linearizability in any situation at all, but it could lead to apparent causal reordering because when we trust the timestamps to be valid, we obviously are potentially sorting the data into timestamp order, and once we've done this, causality across multiple clients could easily be lost. But because we are still doing an atomic multicast -- totally ordered!!! -- and because we do respect sender FIFO order, we actually are still a linearizable system. In fact we are doing more than just linearizability: the snapshot isolation behavior is a strongly serializable snapshot isolation. Quite nifty, in my opinion....

[Steamgjk]

Thanks for the explanation and pointers. I think I need some effort to digest them,
But one quick question related to 4, here "datacenter TCP performs pretty close to RDMA" is talking about the setting in bare-metal machine cluster, rather than public cloud VM, right?

Because according to my measurement, inter-VM latency can goes to 50-80us per message delay, even with UDP. It is far longer than RDMA (I remember it can be very fast to only multiple us).

[KenBirman]

As the Spindle paper explains, we are actually surprisingly latency-tolerant. We already saw this when creating RDMC but Spindle takes the whole opportunistic batching thing much further, plus adds an adaptive null-send layer to the multicast infrastructure, and the system ends up easily able to handle delays that seem large enough that you would expect them to be an issue. This has us keen to experiment with cellular 5G and 5G WiFI over DPDK, because we think we might do unexpectedly well in such settings.

[Steamgjk]

I totally agree with your point. I think Spindle is awesome. I am not challenging Spindle or Derecho.

Let me put it in this way:
If I use VMs for both external clients and derecho nodes, and the inter-VM latency is 80us, then
If there is only 1 external client, and this external client wants to commit a request, it needs to take at least 80*4=320us from its submission to getting the commit acknowledgement, is that right?

Here "at least" means I only count the message delay (4 message delay), without considering the processing delay (e.g. quorum check) at derecho nodes, or batching delay, or any straggler effect.

[KenBirman]

Close. It takes roughly 80*3 us in that case: the data must be sent to a member of the shard, hence 80us, then multicast, hence 80us more, and then there will be an exchange of status requiring a further delay of 80us. So you would not expect to see better than 240us in this case, compared to something more like 1.8-2.5us for RDMA-accelerated clusters with 0.6us-0.7us one-way latencies. But with DPDK, which puts the TCP stack in user space, the latencies may be better than 80us in a cluster with a fast optical interconnect.

[KenBirman]

PS: Also, there is no quorum check. This is not the RaFT protocol and the update itself doesn't need a quorum check.

[KenBirman]

One more observation: I’m assuming that even if the group has n members, the tcp layer is pretty concurrent and doesn’t bottleneck. So the multicast outputs are all sent concurrently, and the SST all to all status exchanges also are concurrent.