11–20 of 40 posts
1 proposer(v): 2 while not decided: 2 choose n, unique and higher than any n seen so far 26 lines. It's pseudocode, so not really only 26 lines as it needs some more supporting functions to "choose n, unique and..." and other stuff to make setting variable states atomic. Good way to explain the algo though.
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…
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.
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…
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 i…
> 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.
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…
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 i…
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.
Here's a version I wrote in C++ for ScalienDB about 5-6 years ago, this startup has since folded so it's dead code: https://github.com/scalien/scaliendb/tree/master/src/Framewo... Paxos: for replicating data PaxosLease: for negotiating a lease, eg. leader Quorum: pluggable "majority" rules, not that important ReplicatedLog: use Paxos for each append, initiated by leader
This is missing what to me is the most important part of the algorithm: a quorum of acceptors must propagate writes to the learners. With just what's shown here, you're not tolerant to network partitions that cause a subset of the "accept" messages to be lost. That process can of course be optimized in a number of ways that drastically cut down on the network overhead as compared to the naive MxN write pattern, but w…
Here's one in 1 line: run_paxos()
I have used something similar to defuse endless arguments about which language is more expressive, or better, and turn it into a more productive discourse. I simply make a tentative assertion that there is a perfect language for every problem, one where only one line of code is needed to solve the problem, it reads as follows: doit
Then I follow up with stating that the language is probably rather useless for anything else.
I don't know why it usually works to open up the discussion, it seems to me as such a trivial and obvious observation, but apparently the perspective is something many rarely come to observe without prompting.
I'm well aware that 'doit' can't really be considered to be a language, except in a very limited sense, it can also simply be a function call, which maybe helps to bring into focus the intersection between language, libraries and their relative applicability to the task that needs solving, and the environment it must be solved in.
Trivial, obvious but somehow deeply at the heart of writing the correct code to solve a particular problem, because everything is a tradeoff somewhere between extremes.
This is missing what to me is the most important part of the algorithm: a quorum of acceptors must propagate writes to the learners. With just what's shown here, you're not tolerant to network partitions that cause a subset of the "accept" messages to be lost. That process can of course be optimized in a number of ways that drastically cut down on the network overhead as compared to the naive MxN write pattern, but w…
In my layman understanding: Given a set, a quorum is some method to choosing a sub set, such that any two such sub sets will always have at least one overlapping member.
Majority is one quorum algorithm - given a set [A,B,C], the majorities are: [A,B,C], [A,B], [A,C] and [B,C]. Any two of those sets will have at least one member overlapping.
However, majority is somewhat wasteful, because the latency of these quorum-based algorithms are almost always bound by the slowest member of the quorum - the more machines you need to wait for, the more likely one of them will be outlier-slow.
You'd potentially be better off choosing a quorum algorithm that requires less than a majority - because that'd mean, in the best case, fewer responses to wait for, lowering the probability that one of those members will be very slow. There are drawbacks to this - it makes fault tolerance and provisioning harder to calculate - but it's got some cool potential benefits.
Some cool ones to explore here: https://pdfs.semanticscholar.org/a243/7f18205414f6398b29c4f8...