Raft Vs Viewstamped Replication

[Heidi Howard]

I was re-reading this paper[1] today and it struck me how similar these two protocols are. Putting aside the minor optimisations by Raft such as Raft using <term,index> in test for log consistency instead of including the whole log like VR and Raft using AppendEntries to update behind nodes, instead of these nodes explicitly asking other nodes for upto date log entries. 

The only major difference is the how a node chooses who to give a vote too. In Raft, a node grants a vote to the first node who askes (plus the extra conditions on commitment) whereas in VR, a node grants its vote to a node as a deterministic function of the term number (Round robin style). 

Any know of any performance evaluation between these two protocols? or have any thoughts on the differences between them.

[1]  Liskov, Barbara, and James Cowling. "Viewstamped replication revisited." (2012). http://pmg.csail.mit.edu/papers/vr-revisited.pdf

-- 

Regards
Heidi Howard

PhD Student

University of Cambridge

www.cl.cam.ac.uk/~hh360

[Diego Ongaro]

Hi Heidi,

With apologies to Barbara, James, and Brian. VR introduced some great
ideas, and VRR was a huge improvement in clarity. I think the industry
would be in a better place now with respect to consensus if it had
paid less attention to Paxos and more to VR.

You're right, Heidi, that Raft and VR/VRR are similar, and we
acknowledge this in the first page of the paper.

At a high level, you could argue they're exactly the same. Lamport
would probably call them both Paxos. Their messaging pattern is
similar. Why they work is similar, and their proofs of correctness
could be similar.

At a low level, you could argue they're very different. Raft's
mechanism is compact (VRR uses 10 message types where Raft uses 4 to
accomplish the same tasks). Raft spells out how to do leader election
with randomized timeouts and how to avoid transferring entire logs.

And of course membership changes are entirely different.

Now (2015), there's a huge difference in completeness. Raft has
several implementations including membership changes and log
compaction, some evaluation, a proof or two, my dissertation (a lot of
discussion about design choices), and many online resources to help
people learn. I don't think VR/VRR is competitive with any of that
currently. For example, I just searched GitHub for "Viewstamped
Replication" and found only one project; searching "VRR" yields noise.

Paper-wise, I'm biased, but I think the Raft paper is more accessible
to beginners. That's because the Raft paper explains the why, and the
VRR paper just tells you the what.

I also think the leader election algorithm in the original VR is
better than in VRR. I discuss this in the related work in my
dissertation. The original VR has the view manager tell the new leader
to start, yes, but it doesn't have to transmit any log entries. And I
still don't feel great about the leader being a function of the view
(term) number. It feels misleading, since of course different servers
might be in different views, especially during leader changes. But I
haven't implemented or evaluated that approach.

We (John and I) actually didn't know about the VRR paper until after
we had started Raft. I think the earliest time someone mentioned it to
us was three days before our first paper submission on Raft, in
September 2012, buried in an email with a bunch of other pointers.
Would we have used VRR instead of creating Raft if we knew abut it in
time? I'm not sure, but it definitely would have been a better
starting point for us.

Know of any performance evaluation between these two protocols? Nope.
Normal-case operation would be the same, so you'd probably have to
compare leader changes. And I feel like that depends on the details of
how you "optimize" VRR, so I don't know if it'd be apples-to-apples.

Hope I haven't offended anyone, and hope this helps,
Diego

> --
> You received this message because you are subscribed to the Google Groups
> "raft-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to raft-dev+u...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Heidi Howard]

Wow, thanks for such a comprehensive response diego :)

Of course I don't meet to offend anyone, I'm just interested in how different algorithms design decisions lead to their relative strengths and weaknesses. My particular interest is in how we can apply algorithms such as VRR, Multi-Paxos and Raft to internet-scale systems.

reponses in-lined below

On 6 April 2015 at 01:46, Diego Ongaro <onga...@gmail.com> wrote:

Hi Heidi,

With apologies to Barbara, James, and Brian. VR introduced some great
ideas, and VRR was a huge improvement in clarity. I think the industry
would be in a better place now with respect to consensus if it had
paid less attention to Paxos and more to VR.

 

I cannot agree more :)

 

You're right, Heidi, that Raft and VR/VRR are similar, and we
acknowledge this in the first page of the paper.

 

Yep, and your thesis has a nice comparison of them

 

At a high level, you could argue they're exactly the same. Lamport
would probably call them both Paxos. Their messaging pattern is
similar. Why they work is similar, and their proofs of correctness
could be similar.

I agree with this, though I suppose that most consensus algorithms which use state machine replication approach will look similar in this regard. 

 

At a low level, you could argue they're very different.  Raft's
mechanism is compact (VRR uses 10 message types where Raft uses 4 to
accomplish the same tasks). Raft spells out how to do leader election
with randomized timeouts and how to avoid transferring entire logs.

I make it 12 for VRR and 8 for Raft, not that it matters

Raft's AppendEntries encapsulates VRR's Prepare, StartView, PrepareOK, Commit, GetState and NewState messages.

Raft's RequestVotes encapsulates VRR's StartViewChange and DoViewChange.

Raft's ClientRequest encapsulates VRR's Request and Reply.

Raft's RegisterClient encapsulate VRR's unnamed message and response for the same purpose.

I've not include VRR's Recovery/RecoveryOK message since im assuming access to persistent storage and I've also not counted dynamic membership and separate messages for readonly support, for fair comparison between raft and VRR.

 

And of course membership changes are entirely different.

yep!

 

Now (2015), there's a huge difference in completeness. Raft has
several implementations including membership changes and log
compaction, some evaluation, a proof or two, my dissertation (a lot of
discussion about design choices), and many online resources to help
people learn. I don't think VR/VRR is competitive with any of that
currently. For example, I just searched GitHub for "Viewstamped
Replication" and found only one project; searching "VRR" yields noise.

There is no doubt you've done a great job, I'm a shame there hasn't been more interest in VR/VRR though.

 

Paper-wise, I'm biased, but I think the Raft paper is more accessible
to beginners. That's because the Raft paper explains the why, and the
VRR paper just tells you the what.

I agreed, hence why raft has proven so popular.

 

I also think the leader election algorithm in the original VR is
better than in VRR. I discuss this in the related work in my
dissertation. The original VR has the view manager tell the new leader
to start, yes, but it doesn't have to transmit any log entries. And I
still don't feel great about the leader being a function of the view
(term) number. It feels misleading, since of course different servers
might be in different views, especially during leader changes. But I
haven't implemented or evaluated that approach.

It is this core difference that interests me. I wonder in which cases VRR round robin (RR) might elect a leader faster than Raft first come first vote (with log consistency checks) (RCFV). Raft used non-determinism to minimise the probability of candidates competing for votes, with RCFV this isn't an issue so our timeouts can be fixed e.g. 150mm instead of 150mm-300mm. We tradeoff reduce risk of split votes with the risk that a new elected leader might be down

 

We (John and I) actually didn't know about the VRR paper until after
we had started Raft. I think the earliest time someone mentioned it to
us was three days before our first paper submission on Raft, in
September 2012, buried in an email with a bunch of other pointers.
Would we have used VRR instead of creating Raft if we knew abut it in
time? I'm not sure, but it definitely would have been a better
starting point for us.

Know of any performance evaluation between these two protocols? Nope.
Normal-case operation would be the same, so you'd probably have to
compare leader changes. And I feel like that depends on the details of
how you "optimize" VRR, so I don't know if it'd be apples-to-apples.

Hope I haven't offended anyone, and hope this helps,
Diego

Thanks, It did help :)

--

Regards
Heidi

[Diego Ongaro]

Ah, I was counting dynamic membership (+StartEpoch and EpochStarted
for VRR) but wasn't counting client stuff (which is similar in both).

It's a good question. I think you'd also want to include the time for
VRR to identify and transfer log entries to the new leader, though.