3 ms·

A cool tiny bit of trivia about RAMCloud: that's from this project that the Raft consensus algorithm emerged! (https://raft.github.io/raft.pdf https://raft.gith

by erwan 8y ago

A cool tiny bit of trivia about RAMCloud: that's from this project that the Raft consensus algorithm emerged! (https://raft.github.io/raft.pdf https://raft.github.io/raft.pdf) Right now, I think that the algo is used in RAMCloud via LogCabin (https://github.com/logcabin/logcabin https://github.com/logcabin/logcabin). Raft is more practical (as in "well specified") than Paxos and closest to its lesser known cousin, VR (Viewstamped Replication). Beyond the academic genealogy of the project, what is interesting here is the fact that usability is a first-class concern. Clearly the fact that it was born out of a real/breathing project was a driving factor. It wasn't just an academic being creative. To pick a notorious example, have a quick look at Leslie Lamport's paper on Paxos: you are never quite sure whether what you are reading is a distributed systems paper or a vintage edition of the Holy Bible. So Raft had great timing too. It came after decades of clumsy (because novel!) systems research on consensus algos and from a laboratory of practitioners, hence its designers knew exactly how previous attempts were deficient with respect to their own needs. And it turns out these overlapped with a lot of people's. There is wisdom to be learnt from this. Also, on another note I think that's funny because this narrative reads exactly like a startup-story!

antics 8y ago
Raft is certainly easier to explain, but it's hard to argue that Raft is more practical. For one thing, implementing Raft in a performant way is incredibly difficult. Where paxos has very fine-grained units of consensus (e.g., ballots), in Raft, everything happens through leases, and is totally linear. This is one of the major reasons a bunch of (all?) major Raft implementations do unprincipled things like non-quorum reads. This sort of problem also makes it very difficult to get Raft to do anything on an unreliable network. Raft is also super noisy, so you have to do stuff like piggy back heartbeats in other RPC calls. One way of thinking about this is: in paxos much of the complexity is in the specification itself. Performant Raft pushes this complexity into external systems. Both of these are extremely hard problems. There is no free lunch. If the problem is really just verifying the model, then I think you are better off writing a simple modeling language, writing paxos in it, and then compiling that to c++ or something. This was the approach Google took in paxos made live[1] for example. [1]: http://www.read.seas.harvard.edu/~kohler/class/08w-dsi/chandra07paxos.pdf http://www.read.seas.harvard.edu/~kohler/class/08w-dsi/chand...
- makmanalp 8y ago
  To expand on this point, check out this talk by the CockroachDB VP of engineering[0]: they used raft but found out that it's approximately as complicated as paxos. They also do non-quorum reads, all through the leader replica) [0] https://atscaleconference.com/videos/scale-2018-run-your-database-like-a-cdn/ https://atscaleconference.com/videos/scale-2018-run-your-dat...

by erwan 8y ago

antics 8y ago

Raft is certainly easier to explain, but it's hard to argue that Raft is more practical. For one thing, implementing Raft in a performant way is incredibly difficult. Where paxos has very fine-grained units of consensus (e.g., ballots), in Raft, everything happens through leases, and is totally linear. This is one of the major reasons a bunch of (all?) major Raft implementations do unprincipled things like non-quorum reads. This sort of problem also makes it very difficult to get Raft to do anything on an unreliable network. Raft is also super noisy, so you have to do stuff like piggy back heartbeats in other RPC calls. One way of thinking about this is: in paxos much of the complexity is in the specification itself. Performant Raft pushes this complexity into external systems. Both of these are extremely hard problems. There is no free lunch. If the problem is really just verifying the model, then I think you are better off writing a simple modeling language, writing paxos in it, and then compiling that to c++ or something. This was the approach Google took in paxos made live[1] for example. [1]: http://www.read.seas.harvard.edu/~kohler/class/08w-dsi/chandra07paxos.pdf http://www.read.seas.harvard.edu/~kohler/class/08w-dsi/chand...

makmanalp 8y ago
To expand on this point, check out this talk by the CockroachDB VP of engineering[0]: they used raft but found out that it's approximately as complicated as paxos. They also do non-quorum reads, all through the leader replica) [0] https://atscaleconference.com/videos/scale-2018-run-your-database-like-a-cdn/ https://atscaleconference.com/videos/scale-2018-run-your-dat...