The Paxos Algorithm
Вставка
- Опубліковано 23 лип 2024
- 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. - Наука та технологія
One of the best presentations on Paxos!! Great job Luis. Very easy to understand and simple examples make it clearer!
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"
Well Done. The slides showing communications between nodes made for great examples. Thank you!
I have an exam tomorrow and this video helped me a lot! Thank you very much!
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.
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.
great presentation! i was confused between log pos and Prepare Id. but it all made sense when i realized they are different things.
This is the best explanation of Paxos I've come across, thanks
I have watched quite a lot of videos about Paxos. The one is the most enjoyable. Thanks
It is great, Luis. Thanks for your time explaining Paxos!
Brilliant Sir!! Looking forward to more such talks from you :D
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
Thank you Luis. It was indeed a beautiful presentation explained with simple diagrams.
Thank you Luis for this super clear presentation on how Paxos works!
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!
Thanks a lot for the video :). I watched it a couple of times to be sure to understand every detail. You saved my exam
Thank you soo much Luis!!!! It's no surprise, how these videos are better at teaching (for Free!) than my University!
Thank you. Also would be nice to get an overview of scenarios when nodes, including proposers, fail and then come back alive
exactly that's the core of fault tolerance
I was familiar with Raft before I saw this. This is a really understandable explanation! Thanks!
This was very insightful! Thank you so much, Luis.
Great presentation Luis. You made it very easy.
What do you mean by piggyback? It’s very confusing
Best explanation of Paxos that i've seen so far!
Excellent !! Please prepare the same type presentation for other type Paxoses.
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?
it is funny the practical case is presented as "a distributed storage" : ) Thanks a lot for the video.
Great Presentation! Simple and lucid.
Great Presentation Luis👍
Love the video, thanks Luis.
Muchas gracias luis por una explanación clarísima
OMG. Thank you so much for the great explanation!!!
Huge help! Thank you!
Good simplification of Paxos , thanks
Simply the best sir great learning
Great!! It Helped very much.
Thanks! Great talk.
Thank you for the nice presentation
Thank you very much, this helped a lot!
Thanks Luis
it helps a lot, thank you
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!
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
Thank you for the presentation. Now I'm convinced that Paxos no different from Tether, but with a backdoor.
How does the proposer know how many majority acceptors are present in the network?
Great video!
best tutorial. Thanks!
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.
Thank U, Luis
Good one, Thank you.!
May I use this video in the EDpuzzle platform?
So how easy is this to implement? Great vid btw
This is a good simplified version of Paxos, but does lack a lot of detail.
thank You
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.
Dinner in afternoon 😮
thanks!
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.
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.
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?
Yup I would like to know the second one too.
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
good question, I also want to know the answer
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.
Listen to ua-cam.com/video/d7nAGI_NZPk/v-deo.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.
Well explained. Lucid with necessary and sufficient details
Are we assuming none of the proposers/acceptors are malicious in this?
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 presentation but it seems like everyone wants to use financial incentives and a lot of energy to reach a consensus lol
what if proposer A start with Prepare "infinity". or aka Prepare "Max Value". proposer A will always win. How to prevent that?
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.
You cannot ensure that proposer A is the first one to reach a majority of accepted values.
That's a byzantine failure and would require BFT to be implemented
If a proposer does not follow the Paxos rules, it is considered to be a Byzantine fault.
Paxos only guarantees consistency without byzantine faults.
Tx a lot.
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...
Replica C will also launch a Paxos run during which it will learn the new log position.
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.
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.
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).
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.
*_...consensus by majority is indistinguishable from random-coin flipping, until the majority is outside the entropic zone σ√2π : σ ≈ ½√N..._*
Fantastic! Thank you
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