Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

In search of a simple consensus algorithm

rystsov.info

Post reply on HN
Print view View original

71–80 of 87 posts

Re: In search of a simple consensus algorithm

#71

Post by throwaway91111 »

ReidZB wrote: post #60
jerf wrote: post #57

Earlier quoted context omitted.

I would suggest just dropping Kolmogorov in general, and just referencing the human idea that shorter is generally going to be simpler. I wouldn't have a problem sticking with you through that. Sure, I can feed that to my pedant mill as with anything else, but since it's not really the core idea I'll roll with you on it.

Agreed. The section basically boils down to "despite maybe looking simpler, Single-Decree Paxos is still tricky." I don't think something particular and formal like Kolmogorov complexity even fits the tone there.

Right. There's no strict value to higher or lower complexity in the Kolmogorov sense, so you might as well assign the value to something more tangible (like pseudocode terseness or something)

Re: In search of a simple consensus algorithm

#72

Post by rystsov »

freels wrote: post #70
rystsov wrote: post #69

Earlier quoted context omitted.

> cannot start a paxos instance for a new log entry until all prior instances have been resolved It's wrong. In Grydka (Single-decree Paxos) all the keys are independent so it's possible to update them at the same time without blocking. Grydka's throughput is comparable to Etcd on the same type of machines (4720 vs 5227 rps) and I never optimized for it (my goal was to fit 500 lines) so it's also wrong that it's "non…

This is true, but comes at the cost of not being able to preserve linearity across arbitrary keys, and you are still limited by the throughput on updates to a single key.

Assuming linearity is atomic multi-key updates:

1. There are tasks which don't require atomic multi-key updates

2. Atomic multi-key updates can be implemented on the client side (see RAMP, Percolator transactions or the Saga pattern)

3. Once the data overgrow the size of one machine you need to shard the log and at this time you're in the same situation

Re: In search of a simple consensus algorithm

#73

Post by freels »

rystsov wrote: post #72
freels wrote: post #70

Earlier quoted context omitted.

This is true, but comes at the cost of not being able to preserve linearity across arbitrary keys, and you are still limited by the throughput on updates to a single key.

Assuming linearity is atomic multi-key updates: 1. There are tasks which don't require atomic multi-key updates 2. Atomic multi-key updates can be implemented on the client side (see RAMP, Percolator transactions or the Saga pattern) 3. Once the data overgrow the size of one machine you need to shard the log and at this time you're in the same situation

Fair enough, though at that point, you're layering on additional complexity and getting further away from the goal of simplicity. (And to point 3, while this is true, using a log means this problem can be dealt with a lot later, and there are solutions that don't involve giving up linearizability, such as a dedicated set of log replicas apart from data partitions, or implementing something like Calvin.)

My main point was that the deficiencies of strong-leader-based consensus protocols are overstated, and despite a (minor IMO) level of additional starting complexity, a raft-like protocol is going to be quite a bit simpler than a paxos-based protocol of equivalent capability.

Re: In search of a simple consensus algorithm

#74

Post by moyix »

eutectic wrote: post #56
ReidZB wrote: post #45

The article abuses Kolmogorov complexity... > 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…

Kolmogorov complexity is not computable in general , but it is decidable for a substantial subset of programs.

Really? Do you have an example of a substantial set of programs where that holds? I don't see a priori how it could work unless you can do exhaustive search over the space of all programs and determine if they halt and return the right answer.

Re: In search of a simple consensus algorithm

#75

Post by strictfp »

When looking for a per-key strongly consistent but still highly available datastore I found Hibari, which uses chain replication. Really interesting rech which tries to solve the same problem: http://www.snookles.com/scott/publications/erlang2010-slf.pd...

Hibari does have a master orchestrator, similar to GFS master server. But it's only needed in reconfiguration events.

Re: In search of a simple consensus algorithm

#76

Post by pizza »

ReidZB wrote: post #45

The article abuses Kolmogorov complexity... > 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…

related: "Program-Size Complexity Computes the Halting Problem", https://www.cs.auckland.ac.nz/research/groups/CDMTCS/researc...

Re: In search of a simple consensus algorithm

#77

Post by rdtsc »

> For example, instead of using a distributed log as an Event Sourcing backend for building a key/value storage as an interpretation of an ordered stream of updates we can run a distributed log instance per key.

That is a key insight. I often wonder if people who implemented Raft and discarded Paxos right off the bat knew this? Also I think "Paxos Made Live" scared everyone away from Paxos for a long time.

But what is often missing is that Google implemented a distributed log system. Paxos doesn't do a distributed log by default and just deals with reaching consensus on a value. In practice there is often a need for a log, but not always. If a distributed log is not need Paxos becomes less scary.

Re: In search of a simple consensus algorithm

#78

Post by yorwba »

moyix wrote: post #74
eutectic wrote: post #56

Earlier quoted context omitted.

Kolmogorov complexity is not computable in general , but it is decidable for a substantial subset of programs.

Really? Do you have an example of a substantial set of programs where that holds? I don't see a priori how it could work unless you can do exhaustive search over the space of all programs and determine if they halt and return the right answer.

The hard part here is not finding a set of programs that always halt (primitive recursive functions can compute anything you'd ever want to run on large inputs), but proving that they are correct (I'm pretty sure equivalence of primitive recursive functions is undecidable).

Edit: but if someone gives you the primitive recursive Kolmogorov complexity of a program, you can check it by running all shorter programs on all inputs until you found a counterexample for each of them. So it is semi-decidable.

Edit to edit: This would even work for the general Turing-machine definition of Kolmogorov complexity.

Re: In search of a simple consensus algorithm

#79

Post by grogers »

It's strange that I can't find anything on implementing a CAS register this way. It seems like a relatively straightforward combination of single-decree paxos and the ABD algorithm. Of course, reasoning about distributed algorithms is never simple, and this still isn't...

Re: In search of a simple consensus algorithm

#80

Post by rystsov »

grogers wrote: post #79

It's strange that I can't find anything on implementing a CAS register this way. It seems like a relatively straightforward combination of single-decree paxos and the ABD algorithm. Of course, reasoning about distributed algorithms is never simple, and this still isn't...

I described it in this post http://rystsov.info/2015/09/16/how-paxos-works.html

With single-decree Paxos you can write a storage which provides the following API:

function changeQuery(key, change, query) {

var value=this.db.get(key); value = change(value);

this.db.commit(key, value);

return query(value);

}

By providing different implementations of change & query you can achieve different beviour including CAS.

Post reply on HN