raft algorithm - distributed systems

[00:00:04]Hi everyone, welcome to this video. My name is Osana Madua. In this video, we will talk about Raft. Raft is a consensus algorithm and by the end of this video, you'll be able to understand it and explain it to others. So, let's get started.

[00:00:23]Uh imagine you have five servers that basically these servers store the same data and this is called this is your replicated log. Uh basically a list of operations that each s server should apply in the same order. Uh now imagine that two of those servers crash and the remaining actually need to figure out they need to function correctly um and agree on the current state. Uh they cannot just call a meeting or vote.

[00:00:55]They're basically computers and they need a protocol that will help them uh to function. This protocol is basically called uh consensus algorithm. And before uh raft uh the only thing on the town was basically called something like paxis which is famously notoriously legendarily difficult to understand and the authors of raft actually say that uh by the way for this video I used this paper as a reference and I read the paper and uh basically the authors they say that they couldn't really understood the paxes until they had better uh alternative. So it also uh took them almost a year to figure out. So we can clearly say that rough was born out of frustration and it only exists to do what pexis does but in a way that human being can actually follow and from even the uh paper I would like to add this quote that it says that rough's primary design goal was understandability.

[00:02:08]Okay, so distributed consensus consensus answers only one question. How a bunch of machines agree on something when any of them might crash or go unreachable at any time. Uh think of it as a group chat where some people have no signal. They still need to uh they still need the group to make a decision or they cannot just wait forever for everyone to respond. So basically uh raft gives that raft gives you this three guarantees. First is the safety. It will never tell you the wrong answer. Second it's availability. It keeps working as long as majority of servers are are alive. And and five servers means that you can actually lose two and still would be fine. Third one is correctness. So it does not really depend on timing. uh even like slow networks can just slow um and they will not they do not corrupt results. So the real systems you already know like zookeeper, Google's chubby, hfs all rely on algorithms like this underneath but ra is just a version you can actually read and understand it. Okay. Now I would like to move on to the key component sections and here I will talk about the three roles. So basically Rust simplifies everything by just having a clear hierarchy. At any moment every server is one of these three roles. Uh we have leader. Leader is basically the single boss. Every client request goes through the leader. So it decides the order of operations or tells everyone else what to do. This is basically exactly like there's only one exact leader at a time and no other debates.

[00:04:02]We also have followers here. Basically followers are the passive ones. Um they they basically sit there wait for the instructions from the leader and then they respond. Uh they do not initiate anything on their own. They basically obey the rules. uh candidates are the ones the candidates are basically first followers and they're just tired of waiting. So if a follower hasn't heard from the leader for a while and then what Raft calls election timeout. So it assumes that the leader is dead and decides to run for uh election himself election itself. So it transitions to candidate state and then so basically the flow is like this. We have every server in the beginning is a follower and then some of the followers are uh turning into candidates potential leaders and we have only one leader at a time and if there's timeout uh candidates runs election by themselves.

[00:05:09]So this is very interesting. So can you think of a real world an analogy for this exact situation? Um now I would like to actually move into the very interesting part which is the leader election. So in raft like how does a leader actually get selected? So basically raft uses something beautifully simple randomness like basically randomized timer. So every follower has an election timeout, a random value which is typically between 150 and 300 milliseconds and if it does not uh hear from a leader before the timer expires, it assumes that leader is gone and basically it need it starts election. You can ask like why randomize? Because if everybody had the same time out, uh they'd start an election at exactly the same moment and no one actually would win. So basically randomness uh spreads them out so that no server actually fires first.

[00:06:14]But the candidate increments what Raft calls this term. Think of think the term as a logical clock or let's say election cycle. WS it for itself sends uh request v messages to everyone um to every other server. So let's say um if it gets votes from the majority let's say for five server it means three uh it basically wins. It immediately sends heartbeat messages and uh it says to the followers that a new leader is elected basically. Uh let's say if two candidates fire at the same time and split the vote. Uh basically here in this scenario they both time time out again pick a new random delay and try again. Basically Raph guarantees this this whole situation resolved quickly.

[00:07:12]And uh this is basically what we call democracy. Now we are moving into the logger application. Basically once there's a leader uh it accepts client requests and each request is a command let's say uh maybe x= to 5 uh leader appends this message this command to its own log and it's log is basically sequential list of operations and it sends it to the followers using basically what raft calls append entries RPC and RPCs are basically just messages between servers. Once a majority of servers write the entry to their log and confirm it, the leader basically commits the entry, applies to the state machine and sends the result back to the client.

[00:08:03]Um you may notice that um you actually do not need all servers to respond just a majority because uh let's say some servers let's say in one server uh scenario one server is maybe just slow or temporarily unreachable. So the system always needs to keep moving. Uh the slow server will catch up later. Uh another important thing is that logs only ever flow in one direction from leader to followers. There's no negotiation. The leader log is the only truth. Let's say it's the only ground truth. And another important thing is that the leader append only property. I would like to mention that a leader never overrides or deletes its own log entries. It only always like appends.

[00:08:59]talk about committed entries uh in raft committing an entry is basically the single truth moment in raft because before an entry is committed uh it's actually provisional so it may get overwritten if the leader decides or like things go wrong but it's when it's committed it's permanent raft guarantees that the future leader will also have this information uh even if the current leader crashes is the next leader will have it. And uh let's say the formal property here u we can call it state machine safety.

[00:09:39]If any server applies let's say comment C at index 5 um no other uh server will apply it um different command in index 5. They will basically execute it in the same history in the same order. Just to know that committed means a safe, permanent, agreed upon by everyone who matters by the majority let's say.

[00:10:07]Now let's see how Raft handles an actual failure scenario. We start with five servers. S1 is the leader and S2 through S5 are followers. Everything is working normally. The leader is replicating log entries and sending heartbeats. Then suddenly S1 crashes. The followers stop receiving heartbeats. After a short time out, S2 reacts first. It becomes a candidate, starts a new election term, and sends requests vote RPCs to the other servers. S3 and S4 grant their votes, giving S2 a majority, three out of five servers. That officially makes S2 the new leader. As soon as S2 wins, it begin it begins sending heartbeats to the cluster. The election stops. The followers synchronize with the new leader and normal operation resumes.

[00:11:05]From the client's perspective, this interruption is very small, usually around one election timeout, roughly 150 to 300 milliseconds.

[00:11:16]And if the old leader S1 leader comes back online, it sees the newer term number and safely returns as a follower.

[00:11:24]No split brain situation occurs. Now I want to quickly wrap up this video. So basically as you understand from this lecture that rock is a consensus algorithm. It's a way of cluster of computers to agree on the same log of operations even when the servers fail.

[00:11:41]It does this through uh it does it uh on three key ideas. One leader at a time elected by majority of the walks and a replicated log that flows only from leader to followers and committed entries are the guaranteed uh ones to survive any future crash. uh the whole thing was designed to be understandable and I hope that today's lecture also showed that um show that in this video.

[00:12:12]Uh that's Raft. Thanks for watching and uh remember that in distributed systems the real animals are not bugs. Their messages that never arrive.