The Paxos Algorithm

Подписаться 345 тыс.

Просмотров 116 тыс.

50% 1

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.

Наука

Опубликовано:

13 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 91

@pavan8085 6 лет назад

One of the best presentations on Paxos!! Great job Luis. Very easy to understand and simple examples make it clearer!

@lifnacs589 4 месяца назад

Thank you Luis. It was indeed a beautiful presentation explained with simple diagrams.

@Error-rp4dk 7 месяцев назад

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

@clinthall9011 6 лет назад

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.

@joshuablaeser4100 3 года назад

Well Done. The slides showing communications between nodes made for great examples. Thank you!

@MasoudGhaffarinia 4 года назад

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.

@yicain756 Год назад

I have watched quite a lot of videos about Paxos. The one is the most enjoyable. Thanks

@brandonkarai 5 лет назад

This is the best explanation of Paxos I've come across, thanks

@pawanravish Год назад

Great Presentation Luis👍

@baytravelbee 4 года назад

It is great, Luis. Thanks for your time explaining Paxos!

@mienislav Месяц назад

I have an exam tomorrow and this video helped me a lot! Thank you very much!

@nomad7317 3 года назад

Thank you soo much Luis!!!! It's no surprise, how these videos are better at teaching (for Free!) than my University!

@shitaoweng4235 3 года назад

great presentation! i was confused between log pos and Prepare Id. but it all made sense when i realized they are different things.

@vitonimal5107 3 года назад

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!

@arazsharma4781 3 года назад

Brilliant Sir!! Looking forward to more such talks from you :D

@rameshkrishnan618 2 года назад

Good simplification of Paxos , thanks

@langhaozhong6785 5 лет назад

Thank you Luis for this super clear presentation on how Paxos works!

@camillegoze4923 6 лет назад

Thanks a lot for the video :). I watched it a couple of times to be sure to understand every detail. You saved my exam

@lynch8888 3 года назад

Thanks Luis

@contactrajpal Год назад

Excellent !! Please prepare the same type presentation for other type Paxoses.

@supermajic 9 месяцев назад

Muchas gracias luis por una explanación clarísima

@nickpatella1525 4 года назад

I was familiar with Raft before I saw this. This is a really understandable explanation! Thanks!

@happywhale1786 2 года назад

it helps a lot, thank you

@ManadayMavani 2 года назад

This was very insightful! Thank you so much, Luis.

@kurodragon7 Год назад

Huge help! Thank you!

@orges13eminem 5 лет назад

Great presentation Luis. You made it very easy.

@katpham457 3 года назад

Best explanation of Paxos that i've seen so far!

@thepigol 3 года назад

Great Presentation! Simple and lucid.

@cesarr77 4 года назад

Love the video, thanks Luis.

@submagr 3 года назад

OMG. Thank you so much for the great explanation!!!

@stevehe5713 3 года назад

What do you mean by piggyback? It’s very confusing

@o3bvv 4 года назад

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

@mhcbon4606 6 лет назад

it is funny the practical case is presented as "a distributed storage" : ) Thanks a lot for the video.

@CreedWylder Год назад

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"

@raghavendravernekar4103 3 года назад

Simply the best sir great learning

@fernandosantosdefreitas8061 4 года назад

Great!! It Helped very much.

@mortenbrodersen8664 6 лет назад

Thanks! Great talk.

@kevin-munch 5 лет назад

Thank you very much, this helped a lot!

@Bill-xl4iv 4 года назад

Thank U, Luis

@tuktuk0130 4 года назад

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?

@dgk0 4 года назад

Thank you for the nice presentation

@agilc9092 3 года назад

Good one, Thank you.!

@ainemra 5 лет назад

Great video!

@bobslave7063 4 месяца назад

best tutorial. Thanks!

@flain283 2 года назад

This is a good simplified version of Paxos, but does lack a lot of detail.

@luanemmanuel1173 5 лет назад

Thank you for the presentation. Now I'm convinced that Paxos no different from Tether, but with a backdoor.

@croncoder862 3 года назад

How does the proposer know how many majority acceptors are present in the network?

@SanghoOh 4 года назад

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.

@CaribbeanCryptoTips 2 года назад

Great presentation but it seems like everyone wants to use financial incentives and a lot of energy to reach a consensus lol

@suhasshrinivasan 5 лет назад

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

@anoopmourya3574 2 года назад

thank You

@chickentikkasauce1301 4 года назад

So how easy is this to implement? Great vid btw

@user-nr4qv7zn7e 2 года назад

thanks!

@sonakshimehra5365 5 лет назад

Dinner in afternoon 😮

@johnalexandersanabriaordon1851 4 года назад

May I use this video in the EDpuzzle platform?

@rkpetry 4 года назад

*_...consensus by majority is indistinguishable from random-coin flipping, until the majority is outside the entropic zone σ√2π : σ ≈ ½√N..._*

@7Powers 3 года назад

Well explained. Lucid with necessary and sufficient details

@chickentikkasauce1301 4 года назад

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.

@abbhinaw 5 лет назад

Tx a lot.

@waffleboot 5 лет назад

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.

@tylerkeeling5806 4 года назад

Fantastic! Thank you

@RobertWarrenGilmore 6 лет назад

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 ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-d7nAGI_NZPk.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.

@liuzhen2008 4 года назад

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.

@user-gu5sq5yl1j 5 лет назад

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.

@mnfchen 5 лет назад

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.