Scale By The Bay 2018: Yifan Xing, Consensus Algorithms in Distributed Systems
Recording: Scale By The Bay 2018: Yifan Xing, Consensus Algorithms in Distributed Systems
in this talk I just want to mention one thing so I realized that in when I give this talk usually people ask questions and their questions will be answered in a later slide so I would really appreciate if you could ask questions and at the end I am a really awkward person full disclosure so I sometimes I joke a lot but not people don't always get my joke or laugh at the point where I want them to laugh at so I did you all a favor I have a automatic soundtrack over there that it will laugh I would really appreciate if you could join it when you hear the sound okay so today well I promised the the conference that I'm gonna talk about consensus algorithms but let's just don't I I lied we're not going to talk about consensus algorithms first of all I have to make this slide work one second slideshow there we go okay so let's talk about cakes so the majority amount of the talk will be focusing on cakes instead of consensus algorithms yeah that's a practice run okay okay so first of all I like to start by doing a poll if you could pull up your phone and if you could enter this website called slide oh let's try to display this if you could just join by entering this code 3 3 1 1 let me know if anyone has problem joining this the website and if you could please look up once they're done so that I know when to move on so the website is called slide oh the code is 3 3 1 1 are we all good yeah okay let's move on the first question have you used any software libraries that relies on distributed system so when we talk about software's the libraries I relies on it so it could be simply as email or a web browsers basically have you ever been right okay and if you could please look up once you're done so I see that we have two percent of the population that has never used the Internet it's pretty amazing love to meet you okay if you're done we're gonna move on to the next question can you describe the details of one consensus algorithm so if I describe the details I mean can you even do you can you explain how it's used how to implement it and give some examples of where it's being used okay let's see and please shout out the names the algorithms if you're really familiar with algorithm just like simply the name it's fine anyway yeah oh wow great rafting having pressure cuz I'm gonna talk about rafts what if I get it wrong okay so don't yell at me if I get it wrong though okay cool so we have top person wow that's amazing and a13 okay 50 percent vaguely okay so if we look at the poll result we can see that a majority amount of people have well almost all of us have used distributed system libraries and software's but only 13% of us can really describe one of the concerns that we can expand how computers underneath how they work together so the purpose of this talk is to bridge the gap between those two and help you to understand how computers have consensus so let's switch back to the slides first of all let's define what is a distributed system you can think of it as a components that locates on different parts of the network and they communicate with each other by sending us sending each other messages and by communicating that way so some of the modern examples of distributed system would be the web so you can think of the web browser as the client and the servers are the server's also when you put your l's in your browser's is going to go look up the DNS server and it's going to find how the IP address related to the hostname trying to get you to the right place also BitTorrent which we use for only Linux distributions I'm sure none of you have ever used that for downloading any movies or anything but BitTorrent also is an example of distributed system a fun fact in 1920s American Airline central office used to have this a card for each flight so they have if they have a disk a deck of cards where the traveling agents would call in and asking hey can I buy a seat for the on this flight and they would check if the seat is marked as sold so if it's still available it's going to sell the seat to agent if it's marked sold then it's going to find an available seat so this is a very early example of distributed systems where the traveling agents are the client and the central office is the server distributed systems are great they live in our day to day lives we can't really possibly complete you know we can't really live without them right online so there but but there are also challenges that are linked with digital systems so one of the problems is we said all the servers there are components located on different parts of the network so they need to communicate with each other by sending each by sending messages to each other the problem is that no server has a global knowledge of everything so they have they have knowledge of what what's currently on their own state machine and what are what's in the messages that are sent to them but no server has the global knowledge of everything so how do I make sure that the server has up-to-date information how do we detect inconsistencies in the servers also since we're working with so many different servers they have their own time where so it's possible that we cut we have clock skew how do we know when there are messages that are delayed or duplicated how do we know the order of the messages since we're talking about distributed system it's very common and likely that we have concurrent operations on one single object and when this case happens how do we make sure that these object is in consistent States how do we detect inconsistencies Leslee airport has mentioned that a distribute system is in which the failure of other number of other servers over the network where which you don't even know where that server is but the service failure could cause your own machine unusable so how do we tolerate failures of ourselves and other machines how I tolerate would mean how do we detect them how do we recover and handle them so fortunately we have consistent algorithms which will help maintain the integrity of your machines reliability fault tolerance and availability today we will be focusing on two protocols raft and taxes let's start with taxes taxes compared to other algorithms has a really colorful background it was first implemented and designed by Lynch analyst Gulf so when they designed the algorithm they couldn't find a mathematical proof that would prove that this algorithm actually works so one day Leslie Lamport find this paper and he had a very malicious thought he said I'm going to prove this wrong and by the way Leslie Lamport if you're if you're happening to watching this recording right now please don't be mad at me because I learned all these from my professors you should totally blame them so he had a very malicious thought right he wants to prove this wrong but he accidentally proved it right so he wrote this paper called the part-time Parliament which describes this taxes Island a really cute story of how the islands formed consensus and how everything works and he submit this paper to to conferences and to organizations he got rejected and he tried for about ten years before I venture Lee got accepted so the problem was that people had a hard time understanding what he was talking about because they're you know that the he had really fancy Greek names in the stories and people just simply didn't understand algorithm so one day he was in a conference people said we don't we read your paper we couldn't really understand what paksas really is can you just please explain us and he sat down he explained taxes to people we thought mentioning the stories and people understood it was actually quite simple and he was really inspired he went home he wrote down this paper called paksas made simple basically explaining taxes without the complicated stories and it started making sense so later he wrote another paper called moe type axis which is taxes and complexity so we're gonna talk about basic packs basic taxes and mota taxes today I'll start with basic taxes actually strike that we're gonna talk about cakes how many of you raise your hand if you have a problem picking between chocolate cake and cheese cake I definitely do really we only have one or two few people this talk won't work if you don't have problem with that okay I will just pretend that you all have problems between choosing between chocolate cake and cheese cakes I said the heart the most difficult question in the world so let's say as a group we're gonna after this conference we're gonna all go out we're going to buy a cake buy a huge cake but it has to be one flavor it has to be either a chocolate cake or a cheese cake so how does this usually work can I get a person to volunteer ah stewards yeah I know you okay so let's just say steward would raise his hand and says has that has anyone picked any flavor yet and people will just say no not really we haven't decided yet and steward will say oh why don't we just go for cheesecake cheesecake can't be wrong right it's always great so when people would respond saying that yeah sure let's go for cheesecake antara consensus that is taxes brah you're supposed to press the left button ah there we go pay attention okay so I need you okay so in taxes there's this um there's this proposer idea so you have a proposer that would propose a value and then you have acceptor that would accept and reject value from the proposer how this usually works let's walk through this step stuff so the proposer one server will choose this a proposal number has to be the largest number you've ever seen it's going to broadcast this to all the other servers by sending out this prepare message so this step you can imagine Stewart saying have we hey everyone have we picked any cake flavor yet right so this is the proposer is broadcasting this prepare message to all the other servers and the other server will receive this message and then they will check is this number the largest number that I've seen so far if it is we're going to update this max proposal number we're also going to send back a promise so what we're going to say we promise you that will will only accept your value if your value maintains to be the largest proposal number so this is where we respond to Stewart saying that ah nobody has picked anything yet so go ahead and pick something and now so once the proposer received a majority amount of responses from the server's is going to no it can go ahead and pick a value so it's going to send out this accept message that contains the proposal number that Excite used to use and then also a value that is proposing so it's going to broadcast this to all the servers and then now the acceptor so well that case was Stewart saying let's go for cheesecake so now the acceptors receive this value and it's going to check is this and still the largest number that I've seen basically it's checking is the server the same it's the same one the one that I sent back a promise to so if it is we're going to accept this value and we're going to respond to the proposer and now the proposer gets lots of responses going to checked it I have the majority of server responded to me if I didn't get any rejection that means my value is chosen however if I got any server that rejected my value that means in the system there's another server that proposed a larger number so now I have to start over again from the beginning once I have a value chosen now we have consensus we can go for cheesecake that's taxes so this proposal number in taxes is basically you can form the proposal number using the server ID and the route number the server ID guarantees the uniqueness of the number and the route number gets incremented over time and is shared among all the servers a all the service needs to keep track of the highest route number so when you want to generate a new proposal number you simply increment the max route number and concat sit with the server ID in most hypothesis always say that most high pacts is basically a sequence of instances of basic taxes and it works around log entries so once we have basic taxes we want to have the proposer act as a leader so our client will send the leader information to to the server and it's going to send a command trying to ask the leader to process the request and the leader will use basic faxes trying to figure out which instance and which command it is for we should access key english is hard sorry execute for the current log and then we're going to pick the value have consensus we're going to apply all the command in the previous logs and the current one and then we're going to finally return the results to the client so in moe type axes a leader is the distinguished proposer is it's usually the server with the highest ID is responsible responsible for sending heartbeats was a while to the other servers it's also responsible for accept client requests from from the clients so as a follower if the server did not receive a heartbeat after a while it's going to know is going to automatically assume that the server the leader has died so it's going to step up and trying to act as a leader and act as a proposer if everything works well the follower will just redirect client requests to this to the leader act as a acceptor so it's unlikely that there will be two leaders in paksas however it is possible so impacts us it's designed to be able to handle multiple leaders but it will just won't work as efficient because it needs to constantly fight like who has the larger proposal number etc instead of processing client requests some of the industry example of taxes would be Google chubby the lock service and also Apache zookeeper which uses taxes like algorithms to help people to implement distributed system services ok let's move on to raft raft was designed by Diego on garel and John Auster hurt as Stanford people recognize this as a simpler version of paksas in the industry when people say it's simpler they don't really mean that the algorithm itself it's easier it just means that the paper contains more details about of the algorithm so that it's easier for us audiences to understand and to to implement the algorithm in terms of performance and fault tolerance it's equivalent to taxes on top of consistency and correctness the algorithm was designed around understandability so why did the professors focus so much on understand ability of the server so if you think about it in the industry when we have to implement an algorithm to fit into our own environment sometimes we have to twist the algorithm a little to be able to fit into our own environment right so well we need to implement and twist the algorithm a little bit we really have to understand the algorithms to make it useful to be able to implement it correctly so that's why the algorithm was designed around understandability because they want people to be able to utilize it in the industry and first of all they have to make sure that people understand the algorithm to start with different from Texas raft workaround logs so let's talk let's talk about cakes again I'm going to pick someone different now let's see can I use her name sorry what's her name sorry the second row yeah sorry I see that again buona Mona Mona so as it as a group again we're choosing a cake after this talk right so we're gonna buy either chocolate cake or cheesecake and now we know that Mona in this room is the best person to pick the cake flavor because she's great so we're going to elect her as a leader to pick the cake flavor so what flavor would you like you have to choose either between chocolate cake or cheesecake yes I was just thinking about the same okay so let's go for a chocolate so Mona said we're gonna go for chocolate cake and now we're all gonna go out and buy a chocolate cake to share together so now that's consensus and that is raft latency okay we're gonna just okay see certain latency happens right so in raft we have two phases one is leader election where this phase we elect one server to be the leader and we need to detect leader crashes and then enter reelection phase is the leader crashes so this is the phase where we elect well Morna Mona Mona as a leader and then the second phase will be a log replication so once we have the leader we want to be able to process client requests and we want to be able to get we want to be able to replicate the leaders logs which ensures consistency and consensus among the service which we'll talk about later using examples okay let's first go through leader election so each server has their own timeout time after a server timeout it will become a candidate and so this is saying that I want to be a leader please vote for me so what the server is going to do is going to increment the current term so the current term represents how many election phase that we've been through and what is the current election number and now it's going to vote for itself it wants to become a leader and after that is going to ask the other servers to vote for it so it's going to send out this request vote RPC to the other servers and it's going to three things could happen from here right so one is the other servers would just respond vote by basically saying yes or no I want to vote for you I don't want to vote for you and once the current candidate receive a majority of responses from the other servers going to check today the most servers agree that I can be the leader if that's a yes then we're going to start becoming a leader and then send heartbeats to the other servers act as a leader to handle client requests well the second scenario could be during the process of collecting vote from the other servers it received a heartbeat from the the legit leader so this is the phase where there is a server that became a leader before the current candidate so now it received a heartbeat is going to say okay now I know there's a leader I'm going to step down as a follower so it's going to want to redirect requests to the legit leader well the third scenario is the timeout scenario it's called split vote scenario where we have multiple candidates none of them got a majority of responses or a majority of votes from all of the servers so in this case it will just timeout back and re-enter the election we can talk more about this later so how do I ensure leader election works basically there will always be a leader because each server they can only vote once per term so whichever server wins the majority amount of vote wins the election so for example in this scenario we have five servers the majority will be 5 divided by 2 plus 1 so if a server receives 3 yes from the other servers then you can just step up and become a leader so in this case if server 0 votes for yourself also received a vote from 2 & 3 server 1 votes for yourself received votes from 4 and now the leader will be service 0 so they're eventually in raft it will always be a leader because each server is assigned a randomly election time out time and this random election time would be a Mon usually it's not required but usually among 100 milliseconds to 300 milliseconds which usually one server will timeout first and it will gather it will be able to gather the maturity amount of votes if it's log its complete and then it will become a leader so this is this vote scenario that we mentioned if two machines have let's say the exact same amount of vote but neither of them actually got the majority from the other servers what happens that they both will wait for a period amount time and they will realize that nobody has became a leader and they're in a split vote to tie so they will both time out and reenter the election state so now we covered the election let's talk about log replication so now we have a leader what we want to do is go ahead and process client requests so we want to receive requests from the client once the client tell us to do something we're going to first append it to our own log entry we're gonna remember this command and we will want our followers to also do the same so we're going to send out this append entry RPC asking our servers can you do the same I did the same and then the other servers will respond by appending this command to their own log making sure that their log is the same as the leaders log and it's going to send out this acknowledgement saying that I've done what you asked me to do now the leader once the leader got a majority of responses from the other servers that means it's safe to commit this entry so by commit we mean it's safe to execute the command is safe to return the results to the client so now the leader will execute the command return the results of the client and it will automatically commit this entry to its own log and now it will want the other service to do the same so we will again send out a pendant tree RPC to the other server saying can you please also commit this entry because I did and the other servers will respond and commit the entry so that was if everything works out really well right so what if what happens if we didn't get a maturity of responses from the other servers let's just say in this scenario we have a leader want other servers to append and in their own log but only one server responded an appendage Suntree to the log so the other server didn't respond so once the leader figured I don't have the majority of service responding me the server will just simply keep trying and trying again until it gets a majority amount of responses before moving on because at this state it's not safe to commit this entry yet we've been talking about log entries for a while this is what it looks like you have three things basically the current term records which election term we're at how many elections we've run through also the command for this entry to execute and also obviously you have the index of the log so servers can crash right when one server crashes there could be could cause log inconsistency issues for example server 0 & 2 has a longer log compared to a server 1 this just means that you know server 1 could be partitioned out it could crash during some point now server 0 & 2 has a better and more complete log so how do we resolve this issue how do we detect inconsistencies during raft during the processes and how do we fix them there are basically two parts again there are two phases right the leader election and log replication so during each leader election phase you always trust the leaders log you do not elect any server to be the leader if the server does not have a complete log we're going to give we're going to talk about examples of how to tell whether the candidate has a good log or not also we guarantee that there's no holes in the log basically meaning we always append commands to the end of the log we never ever skip any entries also during log replication processes we repair inconsistency by by copying the leaders log which we'll also talk more later so let's start by talking about how to fix inconsistencies or how to elect a candidate that has a complete log remember that we send out this request a vote remote procedure call during during the candidate election process basically one server sending this message to the other servers asking hey can you vote for me I like to be a leader the request ville RPC contains the following information it has the term which again is the candidates current election term how many elections it has been through and what's the current term until the candidate ID so the service ID has to be unique through the index of the last log entry and the term of the last all at log entry this is how I use it so we can imagine ourselves as a server where the current state machine of the green one as the green server we have a blue server candidate that want us to vote for it so we got this message from this server and we have all the informations about our state machine and the other candidates message right so what we're going to do we're going to compare those information we're first going to look at what's the term so in this case the candidate has a lower term number than ours and our IDs are different which is expected because it has to be unique and now we have the same last login Dex and last log term raise your hand if you think we should vote for this candidate raise your hand great raise your hand if you think we shouldn't vote for this candidate okay and I'm just curious what can you please explain it's okay if you don't but if you want to why do you think we should vote for the candidate so we should vote or Shinzo we shouldn't vote okay yeah correct we shouldn't vote for this candidate because we have a higher term number that means it's more likely that our log is more complete because we've been through more election terms we do not want to trust the candidates log at this point so we reject its vote reject is request and do not vote for it so another example is this okay another example so again we are the blue machine sorry we're the green machine and we we got message from this blue machine asking us to vote for it in this case we have the same term number we have a different log index ours is for the other ones is 3 we have the same term raise your hand if you think we should vote Oh raise your hand if you think we shouldn't vote oh wow cool looks like you're all paying attention I'm happy okay so we shouldn't vote because our last log index is longer that means we have a longer log we do not want to trust the candidate so we do not vote for the candidate we shouldn't vote for some server that does not have the best log and now this example so we now we have the same term different IDs we have a higher index and at the same term so raise your hand if you think we should vote raise your hand if you think we should vote oh okay everyone got it right yay you're right so we shouldn't we should vote because now our last log index is longer that means our log is longer I'm sorry what am I saying the candidate the candidate vlog is longer so we do want to trust the candidate this time we do want to vote for the candidate to become a leader and now how do we went through how do we make sure we elect a server to be the leader that has the most complete log not let's talk about log replication how do we repair how do we detect and then repair inconsistencies in log replication process so remember that we say when when there's a leader we want to send out this a pen entry RPC to the other servers wanting them to append our current log which is the leader log to the other servers log making sure that they are all the same so if this append entry RPC has the following information it has the current entry everything about the current entry so has the index the term and the command and then it also has a little bit information about the preceding entry basically has the index and the term so now how do I use this information when we want as a leader now imagine ourselves as the leader machine we want our candidates to append entry right so we're going to send this entry 5 so we want to append we want to ask the candidate to the other servers who up in entry 5 so we're gonna send everything about entry 5 and a little bit information about entry 4 we're gonna send all the things from information in the appendices C to the other server so server 1 will receive this message and what it will do is it will compare at index 4 do I have the same term as the leader so now in this case at index 4 we have term 2 so does the leader so now it's safe we can basically assume two things one we have the same command as the log as the leaders log does in this current entry unto all the preceding entries are exactly the same so now it means it's safe to replicate the leaders log so now we're going to simply append entry 5 to our own log now what about it what if it doesn't match so let's say the server one I index for it has term 1 instead of term 2 which is different from the log and now we cannot assume that our logs are the same so we'll simply reject leaders requests and we're gonna tell the leader I'm sorry it does not match I'm not gonna append your log and the leader simply won't give up because we're the leader we know that we're right right so we're going to try again by sending more information so now it's going to send entry 4 and 5 and a little information about entry 3 so it's going to than all of those information to server 1 and server 1 will say ok now i ountry i index 3 do i have the same term as the leader and now as you can see they have the same term at the same index that means again we can assume those two things we can assume everything in the current entry is the same and everything in the preceding entries are all the same so now we're going to just simply append the entries log by appending 4 & 5 because we always always trust the leader so now you've fixed the inconsistencies in the server's log so this log matching property in rafts basically says if for each log entry you compare the index and the term if at the same index you have the same term you can assume again two things one you can assume that this two entries store the exact same command and two all the preceding entries are exactly the same or identical so that you can safely append the entry to our own log ok we have consensus algorithm that helped us with lots of problems to fix a lot of problems but they're also problem with consistent algorithms I drew this panda so I'm really proud of it so what are the problems with consistent algorithms well first of all we say that the message is communicate with each of the the service communicate with each other by sending messages and that means we're gonna have overload right overhead we're gonna have to deal with duplicate messages out of older messages what about messages that are lost I've never received the message how do we know you know how do we handle latency in the in the statement in the machine or in the network the service could locate very far away from each other so how do we deal with those kind of problems well again failures we could have the leader failure we could have followers that fell how do we handle partitions how do we make sure that our system can still work with and without those failures confidentiality who has the right to read your data from the server who has the right to write to your server and I really apologize for this really creepy human head I do not how to draw it in a less creepy way so if you have any ideas to talk to me afterwards and ah dinosaur that's much better right it's not as creepy so we could also have militia Spears where you know how do I handle malicious and misbehaving peers we do not want them to abuse the information in the server one example of having malicious peers is this pose in teen generals problem so this is basically you have two generals that try to agree on one thing to do they both have to agree on whether to attacked a castle or retreat from it so if they both agree on one thing then they win right they if they both agree to attack or retreat they went but if they they have if if one chooses attack the other chooses retreat then they just lose this problem seems really simple but the problem is that you they can't communicate face to face they have a messenger that will communicate for them send messages to each other so the problem becomes complicated when you do not know whether the other server is a traitor or not and how this applies to distributed system is you can have a server that acts perfectly fine you can you know you can't really tell what's going on with a server or it's acting as a normal server but instead is a compromised server it could send malicious things to other server to compromised them in this case it's it's really horrible because it could abuse your information to use it to do something else there are algorithms that are modified to handle to be fuzzing teen fault-tolerant there are modified present in taxes and raft but the problem with those algorithm is that they are their overhead is even higher it's more expensive when you want to be fault tolerant to Byzantium failures some of the takeaways to this talk to finally getting to get into that I'm glad nobody has fall asleep yet so that's good yeah so within the industry when you want to implement consensus algorithms well the first thing is try not to do that because understanding the algorithms and being able to implement the algorithm are two complete different things when you're implementing the algorithms not only not only you need to follow it step by step you'll have to prove why your algorithms works and how and why it works correctly right so if you can find an algorithm that has been proven to work correctly then it's better to use that service but if you do have to implement your own algorithms you need to think about is my algorithms is my system resilient against the issues that we've discussed and more importantly do it do I want it to be resilient against those issues it's always a trade-off between reliability and complexity so when it's up to you the developer to determine whether your system your algorithm needs to be resilient against those issues in the academia when you're designing consensus algorithms you need to think about on top of consistency and correctness you want to be able to design an algorithm that's understandable to other people you want people to be able to understand your algorithms so that they can use your algorithm adapt to their own system and that concludes my talk thank you I mean fun and from Northeastern University but wait before we do the like clapping thing again can I just ask how many of you would go for cheesecake raise your hand oh wow what about chocolate cake it's 5050 so I can't take ok well well thank you now I can take questions and thank you for listening and for not falling [Applause] any questions I love the awkward silence after the talk because like it's great it's just I don't I don't get embarrassed if I can't answer a question so I don't mind if you don't ask question but if you want to I'm happy to yeah go ahead [Music] oh it's like a combination okay that's like the most important takeaways for me for this conference thank you for letting me know what's it called what's the name what Oh talk later after anybody has any questions okay well you can always find me afterwards I'll be around thank you I will post my slides on Twitter [Applause] you