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

Paxos in 25 Lines

nil.csail.mit.edu

Post reply on HN
Print view View original

21–30 of 40 posts

Re: Paxos in 25 Lines

#21

Post by d0vs »

cortesoft wrote: post #11
bfung wrote: post #2

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.

Number of lines is the most ridiculous metric anyway. Most languages have no line length limit, just replace all newlines with semicolons, and you have a one line program!

> Most languages have no line length limit

Some languages do?

Re: Paxos in 25 Lines

#22

Post by elvinyung »

jakewins wrote: post #20
GeneralMayhem wrote: post #7

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…

Mostly unrelated, but a fun fact about quorums that I enjoy noting whenever I can because it still seems under-explored: A quorum != a majority. Currently most (all?) production implementations I've seen of RAFT and the various Paxoses use "majority" as the quorum algorithm, so the two get mostly conflated. In my layman understanding: Given a set, a quorum is some method to choosing a sub set, such that any two such…

I would argue that by the time you've chosen Paxos or some other majority quorum commit protocol, you're already well aware that you're building a CP system, and that availability and latency aren't your main concern. A majority quorum is basically the most obvious (and somewhat brute force) way of providing serializable consistency in the system.

The one non-majority quorum commit protocol that most people are probably already familiar with is the "sloppy quorum" replication in Dynamo systems[1] (e.g. Cassandra, Riak, Voldemort, etc.). Basically, since the quorum is configurable on a per-cluster basis instead of being inherent to the protocol, and usually isn't a majority of the cluster, the system can still make progress when half of the nodes are unreachable. (But of course, as the paper notes, this means that you need to resolve conflicts some other way, which adds a whole bunch of complexity.)

1: http://www.allthingsdistributed.com/files/amazon-dynamo-sosp...

Re: Paxos in 25 Lines

#23

Post by porges »

d0vs wrote: post #21
cortesoft wrote: post #11

Earlier quoted context omitted.

Number of lines is the most ridiculous metric anyway. Most languages have no line length limit, just replace all newlines with semicolons, and you have a one line program!

> Most languages have no line length limit Some languages do?

("Free-format") Fortran has a max line length of 132 chars, up from ("fixed-format") 72 chars on punch cards.

Re: Paxos in 25 Lines

#26

Post by jasonwatkinspdx »

jakewins wrote: post #20
GeneralMayhem wrote: post #7

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…

Mostly unrelated, but a fun fact about quorums that I enjoy noting whenever I can because it still seems under-explored: A quorum != a majority. Currently most (all?) production implementations I've seen of RAFT and the various Paxoses use "majority" as the quorum algorithm, so the two get mostly conflated. In my layman understanding: Given a set, a quorum is some method to choosing a sub set, such that any two such…

I think you'd be interested in Flexible Paxos[1] if you haven't run into it.

[1]: https://arxiv.org/abs/1608.06696

Re: Paxos in 25 Lines

#27

Post by jakewins »

jasonwatkinspdx wrote: post #26
jakewins wrote: post #20

Earlier quoted context omitted.

Mostly unrelated, but a fun fact about quorums that I enjoy noting whenever I can because it still seems under-explored: A quorum != a majority. Currently most (all?) production implementations I've seen of RAFT and the various Paxoses use "majority" as the quorum algorithm, so the two get mostly conflated. In my layman understanding: Given a set, a quorum is some method to choosing a sub set, such that any two such…

I think you'd be interested in Flexible Paxos[1] if you haven't run into it. [1]: https://arxiv.org/abs/1608.06696

Oh man, that is a really cool paper, thanks a bunch for sharing that. I've got next week off and lots of itch to try Go for network code.. might try this out!

Re: Paxos in 25 Lines

#28

Post by amagumori »

d0vs wrote: post #21
cortesoft wrote: post #11

Earlier quoted context omitted.

Number of lines is the most ridiculous metric anyway. Most languages have no line length limit, just replace all newlines with semicolons, and you have a one line program!

> Most languages have no line length limit Some languages do?

the ANSI C standard has a line length limit, so there are no guarantees that compilers have to function properly with longer lines than given in the standard.

Re: Paxos in 25 Lines

#29

Post by dllthomas »

elvinyung wrote: post #22
jakewins wrote: post #20

Earlier quoted context omitted.

Mostly unrelated, but a fun fact about quorums that I enjoy noting whenever I can because it still seems under-explored: A quorum != a majority. Currently most (all?) production implementations I've seen of RAFT and the various Paxoses use "majority" as the quorum algorithm, so the two get mostly conflated. In my layman understanding: Given a set, a quorum is some method to choosing a sub set, such that any two such…

I would argue that by the time you've chosen Paxos or some other majority quorum commit protocol, you're already well aware that you're building a CP system, and that availability and latency aren't your main concern. A majority quorum is basically the most obvious (and somewhat brute force) way of providing serializable consistency in the system. The one non-majority quorum commit protocol that most people are proba…

> you're already well aware that you're building a CP system, and that availability and latency aren't your main concern

Assuming you've chosen correctly between CP and AP approaches, this tells us that availability and latency aren't as important as consistency. But there's nothing that says they aren't arbitrarily close...

Re: Paxos in 25 Lines

#30

Post by elvinyung »

dllthomas wrote: post #29
elvinyung wrote: post #22

Earlier quoted context omitted.

I would argue that by the time you've chosen Paxos or some other majority quorum commit protocol, you're already well aware that you're building a CP system, and that availability and latency aren't your main concern. A majority quorum is basically the most obvious (and somewhat brute force) way of providing serializable consistency in the system. The one non-majority quorum commit protocol that most people are proba…

> you're already well aware that you're building a CP system, and that availability and latency aren't your main concern Assuming you've chosen correctly between CP and AP approaches, this tells us that availability and latency aren't as important as consistency. But there's nothing that says they aren't arbitrarily close...

Yeah, definitely -- I agree that the decision doesn't mean to just to blindly throw away availability optimizations once you've decided that consistency is important.

Actually, invoking CAP probably didn't add to my message. What I meant to say is that people don't talk about non-majority quorum commits that much because the interesting part is that the serializability comes with majority/overlapping quorums.

Post reply on HN