Paxos in 25 Lines
nil.csail.mit.edu
Paxos in 25 Lines
1–10 of 40 posts
Re: Paxos in 25 Lines
#2 1 proposer(v):
2 while not decided:
2 choose n, unique and higher than any n seen so far
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.
Re: Paxos in 25 Lines
#3Re: Paxos in 25 Lines
#4I 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.c...
Re: Paxos in 25 Lines
#5I miss numbed code, cba scrolling up to a line and doing: end, return, space space, delete, enter, mouse, space space, end.
just type 8.5: code here
(float to insert between lines)
also no nesting.
then run a processor like go-fmt that checks the format for you.
and use the directory structure for class and methods, directory is a class, and a filename is a method.
Re: Paxos in 25 Lines
#6Here'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
Re: Paxos in 25 Lines
#7This 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 what's written here is not safe on its own.
Re: Paxos in 25 Lines
#81 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.
Also, this is a resubmission from 3 days ago from the same user.
Re: Paxos in 25 Lines
#9everyone, please, read the following blog post before using any 'wow!'s in your next exclamation:
RAFT Explained – Part 1/3: Introduction to the Consensus Problem http://container-solutions.com/raft-explained-part-1-the-con...
"While Paxos can be described with a page of pseudo-code, our complete implementation contains several thousand lines of C++ code."
Re: Paxos in 25 Lines
#10Here's one in 1 line:
run_paxos()