Consensus & Organising Coffee - Computerphile

Key Takeaways

consensus in terms of computing is similar to consensus in terms of humans if you're a group of friends who's organizing to go to coffee and you're trying to pick a time in which to go you may have some friends that don't reply some messages might get lost you might ask a friend to ask another friend they might forget about it one friend might be off having a nap and doesn't reply to your message despite all of that you still manage to to reach agreement you seem still managed to reach consensus between you when we're talking about consensus we're normally talking often inside a data center using the coffee analogy so if you've got a group of free friends Alice Bob and Charlie Alice wants to go for coffee she'll message Bob and Charlie and say hey guys do you want to go for coffee at 2:00 and if these are nice reliable friends they'll message back and say yep great let's do 2:00 and then Alice will message both Bob and Charlie to confirm that that time is okay and the agreement has been reached in practice however anyone who's tried to organize anything will know that things aren't that straightforward Alice May message Bob and Charlie they may respond and then Alice May confirm with Bob but she may get distracted maybe she has a nap maybe she's busy in a meeting she may never confirm with Charlie Charlie now doesn't know what's going on Charlie could try to maybe try to contact Bob and find out what's going on so you may have other parties that are trying trying to organize things during the day we've got D for Danny here and Danny may be saying hey can you come to a meeting at 2 but Charlie doesn't know because Charlie's basically blocked until he finds out for sure what's going on with Alice and the same is true for computer systems if you've got a bank Alice has £100 and Bob has £50 you have this database you replicate it across three different machines then you have some clients so these might be an ATM might be a website for online banking you might have a online bookstore and then you might have a shop in a restaurant and these clients will put in requests and say things like how much money does Alice have so this machine could respond and say Alice has 100 but during this time another guy could say Alice wants to spend £50 we could change it value here and reduce it to 50 and respond but it would then be inconsistent with the value here so these three machines need to communicate in the same way that Alice Bob and Charlie did to reach agreement about how much money Alice has in her bank account so we can look at Alice requesting to take out 50 out of an ATM in the same way that we uh did this coffee example between Alice Bob and Charlie so the machine contacts the other machines and says how much money does Alice have these guys respond let's assume that's back at 100 again and once this machine has got the responses can say okay thank you and return the back importantly these machines say yes that would be okay but they don't actually take the money out of the account at that point in the same way that when someone says um can you do coffee at too you don't immediately put it in your calendar you wait for them to confirm before you do that so then this machine once it sees that the other machines are all happy to put this request through we respond and say okay put that through all of the machines will reduce the money down to 50 and respond to the cash machine to say that Alice has enough credit to get the money out of the machine this protocol is called two-phase commit and um it's a good starting point for a lot of consensus algorithms it requires each note to ask another node and come back so the time it takes to speak to a node and come back is known as the round trip R time or rtt because it's a two-phase commit there's two phases of it it takes two rtts to reach consensus in this situation there are however problems with it because failures can still occur for example the node that was doing the coordination here might fail and it might not be clear whether these other guys should take the £50 out or not that's the worst scenario where Alice asks the cash machine for 50 Quid the cash machine says Services down you can't have your 50 Quid but the 50 Quid goes out of her bank account anyway uh what we can do instead is use free Phase commit so this adds an extra step to the two-phase commit so here the client comes and says can we deduct 50 from Alice's bank account the server asks the other two as before they respond to say Alice has sufficient balance to do so now we add an extra phase this is called the prepare phase so this is where once server tells the others okay we're ready to do this but don't do it just yet these guys say okay we'll wait to hear some more for you and then once uh the server hears from everybody it responds and tells everybody hey guys you can now decrement Alice's money 50 this extra stage is important because if the server who was doing the coordination was to fail these guys know that consensus was already reached so they just have a timer and if they don't hear from server who was coordinating the transaction at the time they can then apply the transaction knowing that it was s that it safely went through this does have problems however for example um before we talked about how two- faase commit was 2times the rtt well this protocol now has three phases so it now takes three times the rtt to reach consensus and there's some more problems too here we're assuming that the network is reliable and that all these messages get through but in practice this network might not be reliable there might be different kinds of partitions and the nose could actually fail one of the ways that we deal with this is we work with what's called majorities and minorities so if you have five nodes you do not need to involve every node in every transaction the whole reason why we need multiple machines in the first place is because you've got tons of traffic being thrown at these distributed systems like a web server if there wasn't much traffic we could just have one machine and this wouldn't be so much of a problem because you're going to want to have all this traffic you don't want every single machine to be involved in every single request because you've not made your situation actually any better so what we do instead is say that a majority of nodes must agree before you go ahead with a request if you always work with a majority you get an interesting thing which is called the majority intersection property majority intersection property means that if you pick any two majorities there will always be an overlap of at least one one node so we have five nodes here if you pick three of them which is a majority you can't make a set of three again without including at least one node from the previous set so this means if a group of three of these nodes decided that Alice took £50 out and then you try to take another £70 out of the bank account at least one of the nodes that would be involved in the process must have seen that Alice has already taken out 50 this is really useful because it reduces the load on the servers it means you now need almost half as many servers when you're processing any one transaction it also means that if any minority of servers were to fail you can carry on as you were before and it also means if you have a partition which isolates a few of the nodes you can carry on as you were before even though you have this partition interfering with things so a lot of the protocol that we use nowadays are based on a protocol called paxos paxos was invented by a famous computer scientist called Leslie Lamport who won the touring award last year