The Paxos Algorithm

[Music] hello my name is Luis Casa Torres I work a site reliability engineer at Google a site reliability engineers we often work on large-scale systems some of which rely on algorithms to reach consensus so that changes to a certain entity are eventually perceived by the distributed fleet in a certain order consistently one of these algorithms is the Praxis algorithm which is what I'm going to talk about today first I will present what is the paxos algorithm and why we need it then I will introduce a cassava in the mid-south and finally I will discuss practical

case which is a distributed storage system based on boxes what is paxos Paxos is a family of distributed algorithms used to reach consensus a family means there are many variants of the algorithm we will only talk about the vanilla Paxos algorithm the cv that means it runs in a set of computers or nodes and consensus we will discuss in one minute what reaching consensus means the paxos algorithm was proposed in the paper that is listed at the bottom of the slide what is to reach consensus with paxos imagine you are together with some friends and

you want to agree on on what to do this afternoon you really don't care about exactly what you do you want to do something together so someone could start by proposing going to the cinema someone else could back it up okay let's go to a cinema in the meanwhile someone that hasn't been listening may propose something different like why don't we all have dinner and even some other people may agree with them and say yeah I am in let's go have dinner eventually in order to reach consensus some of these people will have to change

their mind in this case let's say someone switches from going to the cinema to going have dinner and eventually the last person will go for that too but fine let's go have dinner consensus is agreeing on one result once a majority agrees on a proposal in the faxes world that will be considered consensus so once three people know they want to go for dinner everyone will go for dinner it only may take some time for them to view any reached consensus can be eventually known by everyone they could ask around what whether a consensus was

reached and what the agreement was in paxos they involved parties want to agree on any result not on their proposal so they will contribute towards reaching consensus finally communication channels may be faulty that is messages can get lost in this case you observed that someone wasn't listening they proposed a different thing to do in the end an agreement was reached why do systems need to reach consensus you mind you have this the workstation at your home you write a server you make it public you start getting visits from people and it's kind of becoming a

success so more and more people are using it and at some point your computer is too slow you're running out of resources so you upgrade the run great the CPU and it happens again it's still more and more people using it you are credit again but that has a limit you can have an infinitely powerful and scalable single computer you have to go for something different you either go for a leader and replicas schema in which one node is the leader and the other nodes are repeaters and whenever someone wants to propose writing a value

they would talk to the leader and the leader would serialize the different proposals and send them to all the replicas all the data would be written in all these nodes or you go for a peer-to-peer schema in which all nodes are the same and behave the same whenever they want to propose a new value they send the proposals to each other to agree on what is the next proposal to be accepted to be performed by everyone so that everything is applied in the same order everywhere eventually in the first case if the leader becomes unavailable

notes must reach consensus to elect anyone otherwise the whole system would be stalled in the second one the nodes must reach consensus continuously so as to count it consistency so that operations are applied in the same order everywhere in both cases you need to reach consensus that said let's move on to some boxes basics paxos defines three rows proposers who propose values to reach consensus on acceptors who contribute to reaching the consensus itself and learners who learn the agreed-upon value they can be later queried for what the consensus value was in practice access nodes can

take multiple roles even all of them so a single node a single server can send proposals to other nodes they can contribute to reaching consensus and they learn the final agreed-upon value so that you can call them for it later but those nodes must know how many acceptors a majority is this is important because of a property which is to majorities will always overlap in at least one node we will see these being needed several times through the algorithm in order to guarantee a set of properties access nodes must be persistent so even though the

communication channels may be faulty the box's nodes cannot forget what they accepted there are variants of paxos that can deal with that but vanilla pod sauce won't a boxes run aims at reaching a single consensus this is usually a source of confusion so you can only agree on one value once a consensus has been reached on a certain value it won't progress to any other consensus any other different value which means if you want a value to mutate over time a different paxos from must happen we will see this in depth in the practical case

by the end of the presentation now we can move to introducing the actual paxos Albert let's say we have a proposer on three acceptors so the majority of acceptors would be two and let's say that proposer wants to propose a certain value it will send a prepare ID message to a majority or all of the acceptors the ID must be unique could be for example the timestamp in nanoseconds it's loaded by the proposal so that proposal number one can choose IDs 1 3 5 and so on and propose her to can choose IDs 2 4

6 cetera the point is that no ID is used twice ever in the case of a time out the proposal will retry with a new higher ID so this proposal wants to propose a certain value it sends prepare 5 to all the acceptors now whenever an acceptor receives a preparer message for a certain ID it checks if it promised to ignore requests with this ID if it did promise it will ignore them if it didn't promise it promises to ignore any requests lower than that ID it will reply with promised ID you can observe there's

an interrelation mark in there I will have to add something here in the future this acceptor gotta prepare 5 message and will reply a promise 5 message to the proposal once a majority of acceptors promise no ID lower than that ID can make it through so if you get a majority of promise 5 there's no way a majority of acceptors will promise for because the two majorities would overlap a majority of them would ignore the request with Ivy for whenever proposers get a majority of promise messages for a specific ID it will send accept requests

with that ID and the value to a majority or all of the acceptors for now let's say the proposer will pick any value it once so whatever they wanted to propose at the beginning of the taxes run in this case this proposal gets a majority of promise five messages and it sends accept requests five cut to all the acceptors if an acceptor receives an accept request message for a certain ID and value they check did it promise to ignore requests with these ID if they promised and please note this the promise that we talked about

before if they promise they ignore it this request won't make it through this acceptor if they did even promised they'd send accept with that ID and that value and will also send it to all the learners so these acceptors that get accept request five cut they didn't promise to ignore requests five they promised to ignore anything lower than five they send accept five cut to the proposer and to all the learners if a majority of acceptors accept a certain ID and value consensus is reached and that means consensus is and will always be on value

not necessarily the ID the ID is some paxos internal artefact that doesn't show up outside of taxes so let's assume that a majority of acceptors replies except five cut the consensus has been reached on cut and then the proposers or learners get except messes for ID on body if a proposer or a learner gets a majority of accept messages for a certain ID they know that consensus has been reached on that value not on the ID I can the ID may change so if the proposer gets to accept five cut it knows that it's proposal

made it to consensus and the learners can figure out the value the same way there are three milestones that always happens sequentially in a taxes run I will mark them with stars in their slide first of acceptors promise on a certain ID so no IV lower than that can make it through ever second majority of acceptors accept a certain ID unvalued consensus is reached on that value and third whenever a proposal or learner gets a majority of accept messages for a set an ID they know that the consensus has been reached on the value and

now let's see the couple of cases that we are missing let's introduce a second proposer who is unaware of any consensus and wants to propose something different let's say it sends a prepare for message to all the acceptors and these acceptors get the message a majority of them promised five so maybe one of them would reply promised four but there is no way that a majority of acceptors will promise for so they propose her time's out three tries again the new higher ID which would be let's say six and since a new prepare six message

to all the acceptors the acceptors checked whether they promise to ignore requests with this ID they didn't promise to ignore any requests with that ID so they will have to reply with promised ID but I'm going to add a little piece of logic there they check did I ever accept any value if they didn't which was the case before with promise fight if they didn't ever accept any value they reply with promise ID like before they hadn't sent out any accept message so promise five is five but right now they have already accepted any proposal

so they are forced to reply with promise six which is the ID of the current proposal but I have accepted five cut in the past they send it to the proposer and the proposer gets a majority of promise messages for ib6 before we said it would pick any value it wanted but let's complete that with some extra piece of logic it checks if it has got any already accepted value from promises so any piggybacked value if they haven't got any value they could pick any value they wanted like anything but given that they got up

a piggybacked value they are forced to pick the value with the highest accepted ID that they vote in this case it was five cut so they are forced to send except requests six which is this new proposal ID but the piggybacked value was that the rest is the same acceptors receive except request messages for these ID and value they didn't promise to ignore it so days and accept six that to the proposer and the learner's they proposed her the learners get these accept messages and figure out what the consensus was this is the whole Paxos

algorithm let's review some of the key points here in a little bit more detail first of all let's talk about majority of promises let's say we have two proposals and we have three acceptors proposal one sends a prepare five message to the three acceptors and even gets one promised already in the meanwhile proposal to sends a prepare for message to the three acceptors which please note can get there in a different order because different notes may be located in different places the latencies may be different at the point proposer one gets promised five it has

got a majority of promises that means no ID is lower than that can make it through the prepare for message will be ignored by acceptor one will be ignored by acceptor - even though it is possible that proposal - gets a promise message from a different acceptor just due to latency propulsor one can continue with accept request five whatever value they want to propose but request for will never make it indeed you may have observed that these may cause convention for example proposal one may send a prepare 5 message to a majority of acceptors who

may promise on it propose sir - in the meanwhile and prepare 6 message and gets a majority of promises - that means request number five will never make it through it will be ignored by at least a majority of acceptors so maybe proposal one times out and retries with a new higher ID prepare 7 gets a majority of promises which steps over the with I v6 from propulsor - which will be in or by a majority of nodes so proposal - may want to retry with a higher ID several proposals on the same taxes run

can cause hotspots that yield convention it can really stall the boxes run potential solution is to set an exponential back-off in place so that in the case this is happening and the exponential back-off will leave enough time for any of the proposals to go through entirely at some point of there are some iterations and exponential back-off maybe you prepare eight will get the promised eight proposer one will be waiting because of the back off and proposal too will have enough time to send accept request and get it accepted at which point consensus has been reached

and the boxes one is over the other case is majority of accepts so let's say also one sends prepare five gets a majority of promises since accept requests five that gets a majority of accepts and at that point consensus has been reached and is that value that no accept requests with lower ID will be accepted by a majority because that would require a majority of promises for the lower ID but we got it for the higher one so they would ignore the lower one also no accept requests with higher ID and the different value will

be accepted by a majority because at least an acceptor will piggyback this ID and value in their promise which will propagate to the accept requests so while you can still have higher IDs they will be on the same value in this case let's say propose our two cents prefer six message to a majority of acceptors it is guaranteed that at least one of them will piggyback they accepted five cut in their promise which means proposed r2 can only send an acceptor quest six per idea but value that which will be can be accepted and this

is actually how proposal and learners can learn about boxes consensus if they missed a majority of except my C's in the past a proposer will try to propose a value and the acceptors will pick about the consensus value and proposal will have to propose it and will get it accepted finally let's briefly discuss practical case which is at suited storage system based on the boxes algorithm this is a fictional storage system which is an extreme simplification of some parts of mega store the original mega store paper is listed at the bottom of the slide in

case you want to check it let's say we have on a user and we have a bank account for this user and we have it replicated we have replicas a or bigger B replicas C so they are in different places and we want to have the balance for the bank account of the user we discussed before that taxes can only reach consensus on one value that will never mutate that doesn't work for a bank account because we want to transfer money in we want to withdraw money and so on the solution to this is we

are going to have a replicated log these would be the log position 0 which is the initial state of the bank account they stayed at opening date of their bank account any time we want the value to me a date we will start a new consensus that will be on the next low position if we want to transfer $50 in we have to propose that low position one for user Lewis will be plus $50 and maybe you can even piggyback that the balance is $150 just for efficiency reasons then if the user wants to withdraw

money this has to be recorded in a different logo position a new consensus will start on lock position 2 for user list so that amount of money that isn't the account is $130 because the user withdrawn $20 the client would interact with this storage system as follows let's say we have storage servers in each of the replicas that act as boxes note let's a proposer acceptor and learner all together the user talks to the storage server can do a read or can propose how right let's say the user wants to write withdraw of $30 the

storage server will act as a Paxos proposer and will send this proposal to all the boxes acceptors which are 3 itself on the other two accepters hat will accept the request and maybe some other note accepts the request so consensus has been reached and at the point the proposer knows that consensus has been reached the value can be written and starts to be propagated it's fine if only two of the replicas right the value the third one will eventually figure out the value by some mechanism to catch up or when trying to propose any value

they will try to propose it for low position 3u service which is the same boxes from which we'll get the $30 throw be debugged in the accept message so eventually the third replica will figure out what the right value is this is actually I said a very simplified storage system but this is the way to use Paxos to implement a distributed storage system with that we came to the end I hope this helped you learn boxes and I hope you enjoyed the presentation I certainly did thanks a lot [Music] Oh