The Paxos Algorithm
Ғылым және технология
A Google TechTalk, 2/2/18, presented by Luis Quesada Torres.
ABSTRACT: This Tech Talk presents the Paxos algorithm and discusses a fictional distributed storage system (i.e. simplified Megastore) based on Paxos.
The Paxos algorithm is one of the most common consensus algorithms. Consensus algorithms are one of the mechanisms that allow satisfying consistency constraints in distributed systems with consistency constraints, whether they follow a leader-replica schema or a peer-to-peer schema.
Leader-replica systems consist of a leader node that proposes, manages, accepts, and serializes changes, and replica nodes that propose changes to the current leader node. Given that a single entity is in charge of acception and serialization, leader-replica systems do not require consensus algorithms in order to agree on what the next state is. However, if the leader node becomes unreachable, the replica nodes need to agree on which one should become the next leader node, and they usually run consensus algorithms to reach that agreement.
Peer-to-peer systems consist of nodes that can propose changes and participate in accepting changes. The nodes need to agree on what the next state is in order to establish consistency, and they usually run consensus algorithms to reach that agreement.
SREs within and outside Google work with highly scalable (and therefore distributed) systems that have consistency constraints and involve consensus algorithms.
About the Speaker: Luis Quesada Torres is a Senior Software Engineer in Google's Site Reliability Engineering team.
Пікірлер: 91
One of the best presentations on Paxos!! Great job Luis. Very easy to understand and simple examples make it clearer!
Far more useful than my thousand-euro uni course that, after 4 hours, made me go home crying and with a headache. You've saved me hours of disappointment and confusion, wish you all the best
I have an exam tomorrow and this video helped me a lot! Thank you very much!
Thank you Luis. It was indeed a beautiful presentation explained with simple diagrams.
Well Done. The slides showing communications between nodes made for great examples. Thank you!
This is the best explanation of Paxos I've come across, thanks
Great presentation! Especially I like the presentations in which the algorithm is tweaked/changed as they go through examples, revealing the reasoning behind any subtle part of it. But I wish you also went through the case the proposer receives two different values accepted. That would have shed more light on it. Anyway, thank you for this video.
great presentation! i was confused between log pos and Prepare Id. but it all made sense when i realized they are different things.
Thank you kind sir. Really covered all the cases that I had in mind. Keep up the great teaching skills. I really like the visual support too!
It is great, Luis. Thanks for your time explaining Paxos!
I have watched quite a lot of videos about Paxos. The one is the most enjoyable. Thanks
Switching the metaphor from *voting and politics* to *deciding what to do together when we just want to do something together but don't so much care what* was super helpful to me. Thanks.
Thank you soo much Luis!!!! It's no surprise, how these videos are better at teaching (for Free!) than my University!
Thanks a lot for the video :). I watched it a couple of times to be sure to understand every detail. You saved my exam
Brilliant Sir!! Looking forward to more such talks from you :D
Thank you Luis for this super clear presentation on how Paxos works!
oh my gawd! That initial conversation between friends trying to decide on what to do is such a great example for explaining the additional logic of saying "fiiiiine I'll accept the piggybacked value as others have already reached consensus"
I was familiar with Raft before I saw this. This is a really understandable explanation! Thanks!
Great Presentation Luis👍
What do you mean by piggyback? It’s very confusing
This was very insightful! Thank you so much, Luis.
Great presentation Luis. You made it very easy.
Love the video, thanks Luis.
Good simplification of Paxos , thanks
Huge help! Thank you!
Best explanation of Paxos that i've seen so far!
Excellent !! Please prepare the same type presentation for other type Paxoses.
OMG. Thank you so much for the great explanation!!!
Muchas gracias luis por una explanación clarísima
Thanks Luis
Great Presentation! Simple and lucid.
it helps a lot, thank you
Great!! It Helped very much.
it is funny the practical case is presented as "a distributed storage" : ) Thanks a lot for the video.
Thank you. Also would be nice to get an overview of scenarios when nodes, including proposers, fail and then come back alive
@gouravkhanijoe1059
2 жыл бұрын
exactly that's the core of fault tolerance
Thank you very much, this helped a lot!
Thanks! Great talk.
Simply the best sir great learning
How does the proposer know how many majority acceptors are present in the network?
Thank you for the nice presentation
Thank you for the awesome presentation! I'd like to organize it in my blog, can I use the image in The Paxos Algorithm slide?
Good one, Thank you.!
Thank U, Luis
Great video!
best tutorial. Thanks!
This is a good simplified version of Paxos, but does lack a lot of detail.
Thank you for the presentation. Now I'm convinced that Paxos no different from Tether, but with a backdoor.
Excellent tutorial for Paxos, if the example scenario were provided before the protocol explanation, it would better to understand the overall concepts before going into details.
Great presentation but it seems like everyone wants to use financial incentives and a lot of energy to reach a consensus lol
Thanks for the clear explanation Luis! Just a couple of things: 1. Could you elaborate further on the 'exponential backoff' strategy that is put in place to avoid an infinite run of Paxos? 2. Could you provide more examples such as the bank storage system and highlight particularly on corner cases? Any reliable links would do too! Thanks!
@GP-ez5ms
4 жыл бұрын
1. When proposer gets a timeout (probably due to acceptors ignoring his proposal) - he waits for N + random(100) milliseconds and repeats again. If it happens again - he waits for 2N + random (100) seconds. Or something like that
What about the proposer who wasn’t in the majority and consensus was reached? Even with the exponential back off, when does that proposer node “accept” the consensus? Edit: proposer will propose a value, acceptors will piggy back the existing value. Got it.
May I use this video in the EDpuzzle platform?
thank You
Well explained. Lucid with necessary and sufficient details
thanks!
Tx a lot.
I don't understand how Paxos run is finished, because acceptor will send piggyback promise for each new promise request and proposer have to send accept request with that value instead of wanted value.
@iamtheonetheonlybug
5 жыл бұрын
Proposer 2 compares its own understanding of the current state with the "value" returned back in the latest (given by proposalId) accept-request. In the example given at 14:20, Proposer 2 compares its own understanding and will therefore notice the discrepancy and send out the value "cat" so all the acceptors will be sure to have the latest accepted value. Proposer 2 will then decide whether the update it was planning should now be sent as Prepare 8.
Dinner in afternoon 😮
*_...consensus by majority is indistinguishable from random-coin flipping, until the majority is outside the entropic zone σ√2π : σ ≈ ½√N..._*
So how easy is this to implement? Great vid btw
Fantastic! Thank you
Are we assuming none of the proposers/acceptors are malicious in this?
@miaoumiaoucoincoin
2 жыл бұрын
Indeed, all nodes trust each other. Security isn't coming from Paxos but would be from the network layer through encryption and authentication. In practice all nodes would be under your control and running the same code.
Great talk, Luis. I'm still not sure of a few details. For instance, how do the nodes communicate to each other that a new Paxos run is starting? How is starting a new Paxos run different from just issuing new promises in the same Paxos run?
@tejvepa8521
6 жыл бұрын
Yup I would like to know the second one too.
@ravikanth8695
6 жыл бұрын
Consensus has bueen reached on that value. That is fundamental to a paxos run. One value one consensus one run. Different value different consensus and different run
@chenjames9505
5 жыл бұрын
good question, I also want to know the answer
@iamtheonetheonlybug
5 жыл бұрын
A Paxos run is just referring to the process to reach the next value for consensus. Once a value has been agreed, the next "Paxos run" starts.
@sourabhsingh5286
11 ай бұрын
Listen to kzread.info/dash/bejne/lmuio6mCj7HAgM4.html carefully again. "Paxos will have consensus on one value that will never mutate". To start a new paxos run, you just work on a different value. Taking the "practical example in the video", the consensus on log position 0 (is paxos run 0), the consensus on log position 1 (is paxod run 1) and so on and so forth. Thus the consensus on log position 0 will be $100 for eternity and consensus on log position 1 will be $150 for eternity. The application just uses the latest log position as the balance.
what if proposer A start with Prepare "infinity". or aka Prepare "Max Value". proposer A will always win. How to prevent that?
@MoveYorAss
5 жыл бұрын
For me it seems like it doesn't matter who wins here. The main goal is to let someone win, so there is nothing to prevent in this case.
@WBCIWYG
5 жыл бұрын
You cannot ensure that proposer A is the first one to reach a majority of accepted values.
@sohanpatil6410
4 жыл бұрын
That's a byzantine failure and would require BFT to be implemented
@jamesbalajan3850
4 жыл бұрын
If a proposer does not follow the Paxos rules, it is considered to be a Byzantine fault. Paxos only guarantees consistency without byzantine faults.
In the bank account example, if the user reads from Replica C (before Replica C "catches up" and gets Log pos. 3), won't it get Log pos. 2? Isn't this inconsistent? I mean, if the client instead reads from Replica A or B, it'll get Log pos. 3...
@watcherSL
5 жыл бұрын
Replica C will also launch a Paxos run during which it will learn the new log position.
@chenjames9505
5 жыл бұрын
When Replica C received a request from client(actually ,every paxos node will do the same steps), 1) first, he will start a proposing with (User luis, Log positon 2) to other Paxos node, 2) and then Acceptor (Replica A or B ) will return (User luis, Log position 3 and value) to Replica C 3) Replica C will append these message to his Log 4) at last ,he wil respond to the client with the right value.
@hasnainmamdani
5 жыл бұрын
Paxos guarantees safety (or consistency), which ensures two distinct nodes will never learn different values. However, it does not guarantee the 'timing' of when consistency is achieved. In your example, the returned value (stale or updated) will depend on the implementation of 'get' (or 'read'), which in turn will depend on the use case.
@blasttrash
3 жыл бұрын
what happens if during this time some nodes go down? Say there are 7 nodes and 4 nodes have latest value, and 3 are still to "catch up". At this point, client makes a request to 7th node, but the first 4 nodes which had correct value go down. So therefore client will get wrong value from 3 nodes which were yet to "catch up"(but not cannot catch up because those 4 nodes with correct value are down).
@ryanstankiewicz9358
Жыл бұрын
If read is triggering a paxos run, then I believe the system is strongly consistent. If not, then it's eventually consistent. This means that yes, you would get an inconsistent value from replica c in the situation you described.
They could simply go to the cinema and then have dinner. Problem solved!
¿borrando comentarios que no te gustan porque te hacen una crítica? : demuestras realmente "tu nivel".
Lawsuit incoming...
A great Paxos explanation here: angus.nyc/2012/paxos-by-example/
CD >:(
Thanks Luis