41–50 of 87 posts
I have the feeling like this article is just bashing strong master consensus protocols. But the truth is, yes, they incur a penalty for electing a master. However, this really gets amortized in most workloads if the leader changes only rarely. Additionally, in an environment with a good network connection between nodes (a few ms), you can set the timeout to be much less than a few seconds (could be less than a second…
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 Paxos by removing leader election, multi-master management, and log garbage collection. Here's my blog post on the issue: http://hack.systems/2017/03/13/pocdb/ The entire implementation is 1100 lines of code including comments.
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 Paxos by removing leader election, multi-master management, and log garbage collection. Here's my blog post on the issue: http://hack.systems/2017/03/13/pocdb/ The entire implementation is 1100 lines of code including comments.
I have the feeling like this article is just bashing strong master consensus protocols. But the truth is, yes, they incur a penalty for electing a master. However, this really gets amortized in most workloads if the leader changes only rarely. Additionally, in an environment with a good network connection between nodes (a few ms), you can set the timeout to be much less than a few seconds (could be less than a second…
Just fyi, you were presumably thinking of incur rather than infer.
> When it is applied to the algorithms, it means that an algorithm with the shortest implementation is simpler.
That is misleading. Kolmogorov complexity is the length of the shortest program (in a pre-defined language) that produces a given object. So, if the shortest program that produces Algorithm A is smaller than the shortest program that produces Algorithm B, then the Algorithm A is less Kolmogorov-complex ("simpler") than Algorithm A.
This does not mean you can take two existing implementations (in C, say) and compare the implementation length and declare one is "simpler," unless you are claiming that both implementations are as short as possible. Since Kolmogorov complexity is not computable, that seems like a tall order.
Maybe they are right that Single-Decree Paxos is simpler (either in the sense of Kolmogorov complexity or in some other sense, who knows), but invoking Kolmogorov complexity here seems totally unwarranted -- it doesn't add anything substantive.
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 Paxos by removing leader election, multi-master management, and log garbage collection. Here's my blog post on the issue: http://hack.systems/2017/03/13/pocdb/ The entire implementation is 1100 lines of code including comments.
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.
It's worth reading his description of the paper to understand why: http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxo...
In short, not everyone has the same sense of humor.
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 Paxos by removing leader election, multi-master management, and log garbage collection. Here's my blog post on the issue: http://hack.systems/2017/03/13/pocdb/ The entire implementation is 1100 lines of code including comments.
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.
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 Paxos by removing leader election, multi-master management, and log garbage collection. Here's my blog post on the issue: http://hack.systems/2017/03/13/pocdb/ The entire implementation is 1100 lines of code including comments.
Gryadka is less than 500 but supports membership change :) yet 3 hours on it is quite impressive
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.
Earlier quoted context omitted.
Etcd used this scheme to provide fast reads but Aphyr demonstrated that it may lead to stale reads https://github.com/coreos/etcd/issues/741 . If you can't afford stale reads then you should ask Etcd to wait for confirmation from the majority of followers before acknowledging a read with ?quorum=true. It makes Etcd do 1 round trip for reads (just like Gryadka). The same is applicable to other products (you can't rela…
etcd didn't implement leases; it just assumed that the last Raft election was still good. You can elect a leader for a set period of time (say, 10 seconds) and serve strong reads for a lesser period of time (5 seconds) if you have reasonable assumptions of how good your local oscillators work and avoid jumps. If you don't trust your local clock to any level of accuracy, why do you trust your local CPU? Cockroach DB d…
An instance may be running in virtual environment where time freezes are possible. A human may make an error and rollback time to 1970.
It's impossible to eliminate all these factors so yes I don't trust time but I trust CPU.
Maybe CockroachDB is doing it correctly but the terrible default settings make this optimisation negligible because when the leader dies the system hangs for 12 seconds.
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 Paxos by removing leader election, multi-master management, and log garbage collection. Here's my blog post on the issue: http://hack.systems/2017/03/13/pocdb/ The entire implementation is 1100 lines of code including comments.
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 th…
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 [2] http://consus.io/