3 ms·

I realize this is pseudocode, but I still feel like the bigger challenge is not in implementing a theoretically correct Paxos, but a production-ready one. It's

I realize this is pseudocode, but I still feel like the bigger challenge is not in implementing a theoretically correct Paxos, but a production-ready one. It's probably pretty well-known the Chubby[1] team's experiences dealing with unexpected complexity from using Paxos in production. A choice quote: "While Paxos can be described with a page of pseudo-code, our complete implementation contains several thousand lines of C++ code." 1: https://static.googleusercontent.com/media/research.google.com/en//archive/paxos_made_live.pdf https://static.googleusercontent.com/media/research.google.c...

bastawhiz 10y ago
When I hear about these algorithms taking many thousands of lines of code in a "low-level" language like C or C++, I wonder how much of that could be simplified away if you didn't need to manually manage memory. Performance aside, how much of those "several thousand lines" would be unnecessary in a higher-level language? I implemented Raft in a couple hundred lines of succinct JavaScript a few years ago. I can only imagine someone smarter than me could write a production-ready Paxos implementation in less than a thousand well-commented lines of JavaScript or Python.
- tines 10y ago
  The paper linked anticipates your question in the sentences after grandparent's quote: > The blow-up is not due simply to the fact that we used C++ instead of pseudo notation, nor because our code style may have been verbose. Converting the algorithm into a practical, production-ready system involved implementing many features and optimizations – some published in the literature and some not.
- elvinyung 10y ago
  > I implemented Raft in a couple hundred lines of succinct JavaScript But is it production-ready? :) None of the extra complications described in the paper were inherent to C/C++. It covered things like leader leases, log compaction, handling disk corruption, and group membership changes -- optimizations that weren't intrinsic to Paxos itself, but still crucial for running it in production. Another choice quote from the paper: "There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions." Also, a random data point: etcd's Raft implementation stands at about 4000 lines of Go right now, not including tests.
  - bastawhiz 10y ago
    > But is it production-ready? :) Production-ready enough for my use case ;) I also didn't mention Go in my post because--despite having managed memory--it's syntactically very long. Not a complaint, but all of the Go code I've seen and written tends to be "taller and skinnier" (less dense?) than the code I've seen and written in other languages like Scala or Python.

bastawhiz 10y ago

When I hear about these algorithms taking many thousands of lines of code in a "low-level" language like C or C++, I wonder how much of that could be simplified away if you didn't need to manually manage memory. Performance aside, how much of those "several thousand lines" would be unnecessary in a higher-level language? I implemented Raft in a couple hundred lines of succinct JavaScript a few years ago. I can only imagine someone smarter than me could write a production-ready Paxos implementation in less than a thousand well-commented lines of JavaScript or Python.

tines 10y ago
The paper linked anticipates your question in the sentences after grandparent's quote: > The blow-up is not due simply to the fact that we used C++ instead of pseudo notation, nor because our code style may have been verbose. Converting the algorithm into a practical, production-ready system involved implementing many features and optimizations – some published in the literature and some not.
elvinyung 10y ago
> I implemented Raft in a couple hundred lines of succinct JavaScript But is it production-ready? :) None of the extra complications described in the paper were inherent to C/C++. It covered things like leader leases, log compaction, handling disk corruption, and group membership changes -- optimizations that weren't intrinsic to Paxos itself, but still crucial for running it in production. Another choice quote from the paper: "There are significant gaps between the description of the Paxos algorithm and the needs of a real-world system. In order to build a real-world system, an expert needs to use numerous ideas scattered in the literature and make several relatively small protocol extensions." Also, a random data point: etcd's Raft implementation stands at about 4000 lines of Go right now, not including tests.
- bastawhiz 10y ago
  > But is it production-ready? :) Production-ready enough for my use case ;) I also didn't mention Go in my post because--despite having managed memory--it's syntactically very long. Not a complaint, but all of the Go code I've seen and written tends to be "taller and skinnier" (less dense?) than the code I've seen and written in other languages like Scala or Python.