4 ms·

Raft itself - rather than any framework in which you would actually want to use it - is quite simple to implement. A few classmates of mine and I implemented a

Raft itself - rather than any framework in which you would actually want to use it - is quite simple to implement. A few classmates of mine and I implemented a barebones Raft instance in about a weekend.

james-mcelwain 6y ago
I feel like setting up the tests to validate that your Raft implementation is actually correct would take at least a weekend by itself.
- justicezyx 6y ago
  Just figure out what to test in a weekend probably would be worth some Lamport-level smartness...
  - hangonhn 6y ago
    Or Ousterhout level since we're talking about Raft. His career is amazing with contribution in many different areas of CS -- not to say Lamport's hasn't been.
    - justicezyx 6y ago
      The comments in this list seem from really smart people. I used to follow Jepsen https://jepsen.io/ https://jepsen.io/ closely. Those tests are quite comprehensive. But I think even those are not sufficient to quantify the quality of Paxos/Raft. Tools like TLA+ probably require a few months to learn and become proficient.
- inaseer 6y ago
  Writing tests to prove you've a correct implementation is indeed a very hard problem. I toyed with an interesting idea last year where I began to write a simple (but intentionally incorrect) Paxos implementation using P# (now known as Coyote) and wanted to see if P#/Coyote's systematic exploration of the state space will show me the various race conditions which violated the protocol's correctness. To my surprise, the technique was quite effective. P#/Coyote was able to point out to a number of bugs after I specified the safety and liveness properties which weren't too hard to do. In effect, after specifying the safety/liveness properties, I was able to use P#/Coyote's state-space exploration to ensure the implementation had solid test coverage. More details are at https://github.com/imnaseer/DiscoveringPaxos https://github.com/imnaseer/DiscoveringPaxos where the project starts out with a simple naive implementation, uses P#/Coyote to find bugs, makes incremental modifications till we finally have a working version faithfully following the Paxos description.
- closeparen 6y ago
  This is a Distributed Systems homework project at several universities. In mine, a Jepsen-style test harness was part of the autograder. This happens every once in a while on HN: some mentions having done one of these assignments, and immediately gets tackled for it. Maybe professors aren’t doing a good job conveying the limitations. But also this community is gratuitously hostile to people who have no reason to doubt that the code they wrote from the Raft paper, which passed the test suite, was Raft.
  - kelnos 6y ago
    I don't sense any hostility here, just healthy skepticism. At the risk of sounding condescending, building something for a class assignment is very different from building something that you'd feel comfortable rolling out in production. Hell, one of the commenters upthread worked on the implementation of raft in Apache Kudu. To be perfectly frank, I would take their word on something before that of someone talking about their homework assignment. It's an incredibly useful learning tool, but it takes a lot more work to make it robust. I really hope you read this gently. (As the HN guidelines say, "Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith.") I'm not trying to talk down to you or treat you with hostility (and I know that it's really hard to convey that via text). I would just ask that when someone who has professional, real-world experience in something says it is difficult and time-consuming to do it right, you'd avoid assuming they just don't know what they're doing, and that perhaps there are aspects that you haven't considered. And hey, maybe you or some of the other commenters are just ridiculously smart and focused and can write it in a weekend. But if that's the case, it's pretty uncharitable to push a narrative that it's trivial. Not saying that's what's happening here, but that could be how it's coming off.
    - james-mcelwain 6y ago
      Right, my point was just that there's no such thing as a "mostly works" consensus algorithm. By definition these algorithms are intended for systems that can't tolerate failure. If you feel confident you've built a complex algorithm like this correctly on the first try you probably haven't. Hubris and distributed systems just don't mix. Verifying correctness to back up our empirical claims is often the hardest and most overlooked part of software engineering.
ccleve 6y ago
I doubt very much that you implemented a proper command log with truncation and rollback for leaders and followers, a state machine, leader election with voting, epochs, timeouts with smart backoffs, pipelining, async transport servers and clients with object serialization, quorums, initialization and discovery, persistent state, graceful shutdown, adding and removing members, a proper event queue, snapshots, and proper distributed testing. You can build a toy implementation in a weekend if you have a cookbook. A production-ready implementation takes a bit more.
- dnautics 6y ago
  I believe ucsc has (or had?) a distributed systems class in erlang, and correctly implementing each of those features would be about 3-4 days for a skilled erlang programmer and maybe a week for an undergrad, so that's doable for a team of 2 or 3 undergrads in a term. Maybe out of scope for an undergrad are things like testing high latency/unreliable/jittery connections.

james-mcelwain 6y ago

I feel like setting up the tests to validate that your Raft implementation is actually correct would take at least a weekend by itself.

justicezyx 6y ago
Just figure out what to test in a weekend probably would be worth some Lamport-level smartness...
- hangonhn 6y ago
  Or Ousterhout level since we're talking about Raft. His career is amazing with contribution in many different areas of CS -- not to say Lamport's hasn't been.
  - justicezyx 6y ago
    The comments in this list seem from really smart people. I used to follow Jepsen https://jepsen.io/ https://jepsen.io/ closely. Those tests are quite comprehensive. But I think even those are not sufficient to quantify the quality of Paxos/Raft. Tools like TLA+ probably require a few months to learn and become proficient.
inaseer 6y ago
Writing tests to prove you've a correct implementation is indeed a very hard problem. I toyed with an interesting idea last year where I began to write a simple (but intentionally incorrect) Paxos implementation using P# (now known as Coyote) and wanted to see if P#/Coyote's systematic exploration of the state space will show me the various race conditions which violated the protocol's correctness. To my surprise, the technique was quite effective. P#/Coyote was able to point out to a number of bugs after I specified the safety and liveness properties which weren't too hard to do. In effect, after specifying the safety/liveness properties, I was able to use P#/Coyote's state-space exploration to ensure the implementation had solid test coverage. More details are at https://github.com/imnaseer/DiscoveringPaxos https://github.com/imnaseer/DiscoveringPaxos where the project starts out with a simple naive implementation, uses P#/Coyote to find bugs, makes incremental modifications till we finally have a working version faithfully following the Paxos description.
closeparen 6y ago
This is a Distributed Systems homework project at several universities. In mine, a Jepsen-style test harness was part of the autograder. This happens every once in a while on HN: some mentions having done one of these assignments, and immediately gets tackled for it. Maybe professors aren’t doing a good job conveying the limitations. But also this community is gratuitously hostile to people who have no reason to doubt that the code they wrote from the Raft paper, which passed the test suite, was Raft.
- kelnos 6y ago
  I don't sense any hostility here, just healthy skepticism. At the risk of sounding condescending, building something for a class assignment is very different from building something that you'd feel comfortable rolling out in production. Hell, one of the commenters upthread worked on the implementation of raft in Apache Kudu. To be perfectly frank, I would take their word on something before that of someone talking about their homework assignment. It's an incredibly useful learning tool, but it takes a lot more work to make it robust. I really hope you read this gently. (As the HN guidelines say, "Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith.") I'm not trying to talk down to you or treat you with hostility (and I know that it's really hard to convey that via text). I would just ask that when someone who has professional, real-world experience in something says it is difficult and time-consuming to do it right, you'd avoid assuming they just don't know what they're doing, and that perhaps there are aspects that you haven't considered. And hey, maybe you or some of the other commenters are just ridiculously smart and focused and can write it in a weekend. But if that's the case, it's pretty uncharitable to push a narrative that it's trivial. Not saying that's what's happening here, but that could be how it's coming off.
  - james-mcelwain 6y ago
    Right, my point was just that there's no such thing as a "mostly works" consensus algorithm. By definition these algorithms are intended for systems that can't tolerate failure. If you feel confident you've built a complex algorithm like this correctly on the first try you probably haven't. Hubris and distributed systems just don't mix. Verifying correctness to back up our empirical claims is often the hardest and most overlooked part of software engineering.

ccleve 6y ago

I doubt very much that you implemented a proper command log with truncation and rollback for leaders and followers, a state machine, leader election with voting, epochs, timeouts with smart backoffs, pipelining, async transport servers and clients with object serialization, quorums, initialization and discovery, persistent state, graceful shutdown, adding and removing members, a proper event queue, snapshots, and proper distributed testing. You can build a toy implementation in a weekend if you have a cookbook. A production-ready implementation takes a bit more.

dnautics 6y ago
I believe ucsc has (or had?) a distributed systems class in erlang, and correctly implementing each of those features would be about 3-4 days for a skilled erlang programmer and maybe a week for an undergrad, so that's doable for a team of 2 or 3 undergrads in a term. Maybe out of scope for an undergrad are things like testing high latency/unreliable/jittery connections.