3 ms·

Paxos's complexity is often overstated. I made a simple implementation of Paxos for a key-value store as a proof of concept to demonstrate how you can simplify

• rystsov 10y ago
  Gryadka is less than 500 but supports membership change :) yet 3 hours on it is quite impressive
  • rescrv 10y ago
    JS vs sparse C++? Cut comments and change coding style and you can easily get close to 500 lines. One thing I think is worth touching on is the pipelining ability of multi-paxos that is missing when you have a single register with the Synod protocol. For key-value operations, it's not a problem. For a true replicated state machine, this can hinder performance. In Replicant[1] I added pipelining to ensure Paxos was unlikely to be a bottleneck to replicated state machines. For complex state machines, the state machine becomes CPU bound. [1] https://github.com/rescrv/replicant https://github.com/rescrv/replicant
    • rystsov 10y ago
      It would still lack "Consistent get operations", "Paxos group changes", be "bound to localhost" and do more than 1 round trip to commit. What do you mean by pipelining?
• cube2222 10y ago
  I think that this is cause mainly by the fact, that Leslie Lamport had first written "The one time parliment", which was said to be complex because of the language he used there. I think this is the main cause, as now there are a lot of materials available to understand Paxos.
  • rescrv 10y ago
    If you mean, "The Part-time Parliament," it's indeed a little complex. It's worth reading his description of the paper to understand why: http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxos http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxo... In short, not everyone has the same sense of humor.
    • cube2222 10y ago
      I now it was for fun, but it did make the algorithm substantially more complex to understand. Paxos made simple is much easier in comparison.
• iainmerrick 10y ago
  How heavily have you tested it? I haven't tried implementing Paxos myself, but anecdotally, it's very hard to get it completely right. And when it's being used as key low-level infrastructure, it has to be completely right. This blog post we're discussing agrees: "I planned to finish it in a couple of days, but the whole endeavor lasted a couple of months, the first version has consistency issues, so I had to mock the network and to introduce fault injections to catch the bugs. [...] Single Decree Paxos seems simpler than Raft and Multi-Paxos but remains complex enough to spend months of weekends in chasing consistency." Your approach of using many small Paxos instances is very interesting, though! I'd love to see some real world performance comparisons.
  • rescrv 10y ago
    Indeed pocdb is not intended to be a fully "ready" implementation. There are likely liveness bugs (that can be mitigated by periodically calling work_state_machine on every write outstanding), but it is unlikely to have safety bugs stemming from protocol misunderstandings (any safety bug is likely a small typo). My main projects using Paxos are Replicant[1] and Consus[2], both of which have consumed significantly more time to get Paxos correct. [1] https://github.com/rescrv/replicant https://github.com/rescrv/replicant [2] http://consus.io/ http://consus.io/