<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Diwakar Bhardwaj on Medium]]></title>
        <description><![CDATA[Stories by Diwakar Bhardwaj on Medium]]></description>
        <link>https://medium.com/@diwakarbhardwaj?source=rss-2725bdf60d1d------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*1tSJ7mUSylXApqDf.</url>
            <title>Stories by Diwakar Bhardwaj on Medium</title>
            <link>https://medium.com/@diwakarbhardwaj?source=rss-2725bdf60d1d------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 20:16:30 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@diwakarbhardwaj/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Raft and Paxos: A brief introduction to the basic consensus protocols powering distributed systems…]]></title>
            <link>https://medium.com/the-sixt-india-blog/raft-and-paxos-a-brief-introduction-to-the-basic-consensus-protocols-powering-distributed-systems-1a0ef7ca3acb?source=rss-2725bdf60d1d------2</link>
            <guid isPermaLink="false">https://medium.com/p/1a0ef7ca3acb</guid>
            <category><![CDATA[development]]></category>
            <category><![CDATA[distributed-systems]]></category>
            <category><![CDATA[engineering]]></category>
            <dc:creator><![CDATA[Diwakar Bhardwaj]]></dc:creator>
            <pubDate>Tue, 04 Feb 2020 09:33:48 GMT</pubDate>
            <atom:updated>2020-02-04T09:33:48.566Z</atom:updated>
            <content:encoded><![CDATA[<h3>Raft and Paxos: A brief Introduction to the Basic Consensus Protocols Powering the Distributed Systems Today</h3><h4>Can we all agree….. ?</h4><p>Many of the institutions we depend on as a modern society like hospitals, banks, stock exchanges and airports, need highly reliable and available computer systems to work. Unfortunately, single machines are not up to the task; they’re susceptible to crashes and downtime, and need regular maintenance. The solution, of course is to have multiple machines doing the same job, but how do we get them to do so? This is not a simple problem; the network connections between the machines are not reliable, the machines themselves may crash and we don’t want to involve people to fix things at 3 AM on a Sunday. Consensus is a fundamental part of building replicated systems and getting these machines to work together. The idea of getting them to work together is to have them all store the same data or commands in their logs. This increases the overall system reliability, because if one machine fails, another machine can take up its work.</p><p>Consensus helps us in solving a number of problems in distributed systems. Some of these are:</p><ol><li><strong>Leader election: </strong>A group of servers electing a leader amongst themselves and letting everyone know about it. An example of this would be a leader election in etcd. etcd is a distributed key value database used by Kubernetes. Both etcd and Kubernetes are backbones of microservices infrastructure in Sixt.</li><li><strong>Mutual Exclusion:</strong> A group of servers ensuring mutually exclusive access to a critical resource.</li><li><strong>Membership failure &amp; detection:</strong> A group of servers maintaining a list of each other, updating it as someone enters or leaves the group.</li><li><strong>Reliable multicasting:</strong> A group of servers attempting to receive the same updates in the same order as each other.</li><li><strong>Load balancing:</strong> Distributing incoming network traffic across a group of backend servers.</li></ol><p>Other problems include maintaining a distributed ledger in blockchain technologies in cryptocurrencies, clock synchronisations between servers etc.</p><p>There are a variety of consensus protocols available which solve these problems directly or indirectly. We’ll have a look at two of them going ahead.</p><h3>Paxos</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/400/1*_82i21lZdhDaSp_9N0Do7A.jpeg" /></figure><p>Paxos is the oldest consensus protocol published way back in 1989 by <a href="https://en.wikipedia.org/wiki/Leslie_Lamport">Leslie Lamport</a>. Paxos is used in multiple graph databases like neo4j. It is also used in column store database Cassandra for leader election.</p><p>Let’s take a real life example of how Paxos works:</p><p>There are 4 friends named Rajesh, Rohit, Suresh and Vijay hanging out at Rohit’s place. Rajesh is listening to music with his earplugs on, and not listening to what others are saying. Suresh suggests that they all should go for a movie, and Vijay agrees with him. Then, Rajesh removes his earplugs and suggests they all should go for bowling. Rohit agrees with him, and Vijay changes his decision and agrees with Rohit for bowling. Since the other three agree on bowling, Suresh has no choice but to go for bowling.</p><h4>Paxos algorithm</h4><p>There are 3 roles in Paxos:</p><ol><li>Proposers (Suresh and Rajesh)</li><li>Acceptors (Vijay and Rohit)</li><li>Listeners (Rajesh after a consensus reached on bowling)</li></ol><p>As you can see above, any actor can take on any role at a given point in time.</p><p><strong>Proposer</strong> wants to propose a value <strong><em>v </em></strong>and wants the system to reach a consensus on this value. Hence, it sends a <strong><em>prepare</em></strong> request along with an <strong><em>id</em></strong> to all the acceptors and expects a <strong><em>promise</em></strong> response along with a value. There can be 3 cases here:</p><ol><li>If he gets a majority number (quorum) of promise response with null value <strong><em>v</em></strong> (This means there is no other value <strong><em>v1 </em></strong>onto which a consensus has been reached and he can propose his own value<strong><em> v</em></strong>), he sends an <strong><em>accept</em></strong> request which contains a this value <strong><em>v</em></strong> and previously accepted <strong><em>id </em></strong>to all the acceptors. If again he gets a majority of responses with same <strong><em>id</em></strong> and value <strong><em>v, </em></strong>it indicates that a consensus has been reached on value <strong><em>v. </em></strong>This is what Suresh did above</li><li>If he gets a majority number (quorum) of promise response with a different value <strong><em>v1, </em></strong>that means a consensus has already been reached on a value proposed by a different proposer and it will accept value<strong><em> v1 </em></strong>as well. This is similar to what Rajesh did in our example above.</li><li>If he doesn’t get a majority number of promise response, he will try with a higher <strong><em>id</em></strong> again.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*K6ZovzbCdUq_nJ2li3UF1A.png" /><figcaption>Typical Proposer flow</figcaption></figure><p><strong>Acceptors</strong> maintain a couple of fields in their local memory, a maximum id (<strong><em>max_id</em></strong>) and already accepted value(<strong><em>v</em></strong>).</p><ol><li>If the <strong><em>id</em></strong> proposed by the Proposer is higher than the <strong><em>max_id</em></strong> and the Acceptor has not accepted any value so far, then it accepts that <strong><em>id</em></strong>, returns the response with null value and stores this <strong><em>id</em></strong> as the new <strong><em>max_id</em></strong> in its local memory.</li><li>If the <strong><em>id</em></strong> proposed by the Proposer is higher than the <strong><em>max_id </em></strong>but the Acceptor has already accepted a different value <strong><em>v</em></strong>, then it accepts that <strong><em>id,</em></strong> returns the response with value <strong><em>v</em></strong> and stores this <strong><em>id</em></strong> as the new <strong><em>max_id</em></strong> in its local memory.</li><li>If the <strong><em>id </em></strong>proposed by the Proposer is lower than the <strong><em>max_id</em></strong>, then the Acceptor will ignore this request.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jbsMXOqfeTzaYfZ9svO6eg.png" /></figure><p>Let’s consider another example to understand a basic interaction between all these roles</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*49ewzEPJLB45WwSsdxaTnQ.png" /></figure><p>As you can see, the Proposer proposes id, it gets accepted by a majority, and then the Proposer proposes a value with that id. Please note that Acceptor 3 has not responded with Promise id. A consensus has been reached for this value and this value is propagated to all the nodes including listener.</p><p>Now, let’s add another Proposer to this whole setup. Also, now Acceptor 3 has woken up</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tjjGAVmzfpbxXHUFhzwcjg.png" /></figure><p>New Proposer 2 sent a Prepare request with an id which is lesser than the accepted id. Acceptor 1 and 2 ignored this request. Acceptor 3 which has just woken up accepted it and sent a Promise. But since it was the only one which sent a prepare and a majority has not sent a Prepare, Proposer 2 ignored that response.</p><p>Now Proposer 2 sent another Prepare request with an id which is higher than the accepted id. This time, Acceptor 1 and 2 responded but with an accepted value. After receiving the promise response with a value, Proposer 2 identified that there is an already accepted consensus on value and it accepted that value as well.</p><p>There can be a case of infinite loop here, when 2 proposers keep outbidding each other with higher id. They will not give enough time to each other to send accept-request to acceptors. We can solve this problem by waiting for a backoff period before sending the next Promise request.</p><h3>Raft</h3><p>Raft can be described as a simpler version of Paxos. It was designed for being more understandable than Paxos. It is a fairly new protocol, being developed in 2014. Raft is used in etcd, consul, docker to name a few. All of these systems are used in Sixt.</p><p>Raft decomposes consensus into leader election and log propagation phases. After leader election, leader takes all the decisions and communicates to other nodes through ordered logs.</p><p>There are 3 possible states for a node in Raft consensus protocol:</p><ol><li>Leader</li><li>Follower</li><li>Candidate</li></ol><p>All the nodes start off with a Follower state. If followers don’t hear from a leader then they can become a candidate. The candidate then requests votes from other nodes. The candidate becomes the leader if it gets votes from a majority of nodes. This process is called a <strong>Leader election.</strong></p><p>All changes to the system now go through the leader. Each change is added as an entry in the node’s log. Values remain in uncommitted state and get written to the log first, and then these logs are replicated to other nodes. Once a majority of nodes respond, the value gets committed to the leader node as well.The leader then notifies the followers that the entry is committed, so that the followers can commit the value as well. The cluster has now come to consensus about the system state. This process is called <strong>Log replication.</strong></p><h4>Leader election</h4><p>Every follower waits for a certain amount of time before becoming a candidate. This time is called the <strong>election timeout. </strong>After the election timeout the follower becomes a candidate and starts a new <strong>election term. </strong>It Votes for itself and sends out Request Vote messages to other nodes. If the receiving node hasn’t voted yet in this term then it votes for the candidate and the node resets its election timeout.Once a candidate has a majority of votes it becomes leader. Leader keeps sending regular messages to followers to keep it’s status as leader. This message is called a <strong>heartbeat message</strong>. If a follower doesn’t receive a heartbeat message in a certain time interval, it can become a candidate and the whole cycle of leader election will repeat.</p><p>For example, there are 3 nodes acting as a follower. Each has a different election time out window.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/535/1*7OZmnVKsxGXOLILRsCkeag.png" /></figure><p>Follower with the lowest election timeout value becomes a candidate and asks for vote.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/533/1*yfX4AmukGsAySVYnxlh8Og.png" /></figure><p>After the votes has been granted, candidate becomes leader.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/534/1*xlbmCSB6mnBnKcGr5PFhmQ.png" /></figure><p>Now, when everybody has voted. We have a leader.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/544/1*ToywTcisdn6w1rjeHp5ceQ.png" /></figure><h4>Log replication</h4><p>Once we have a leader elected, we need to replicate all changes to our system to all nodes. This is done by using <strong>Append Entries </strong>messages to the followers.</p><p>It works like this:</p><ol><li>Client sends a change to the elected leader.</li><li>The change is appended to the leader’s log.</li><li>Then the change is sent to the followers on the next heartbeat.</li><li>An entry is committed once a majority of followers acknowledge it and a response is sent to the client.</li></ol><p>This is usually called a <strong>2 Phase commit</strong>.</p><p>There are other protocols that solves different problems.</p><ol><li>ZAB (Zookeeper Atomic Broadcast) was used in zookeeper for setting a master-slave system.</li><li>Gossip protocol is used in consul for membership detection and failures.</li><li>Viewstamped Replication is another state machine replication protocol, and it provides consensus too.</li></ol><h4><strong>References</strong></h4><ol><li><a href="https://raft.github.io/raft.pdf">https://raft.github.io/raft.pdf</a></li><li><a href="https://lamport.azurewebsites.net/pubs/paxos-simple.pdf">https://lamport.azurewebsites.net/pubs/paxos-simple.pdf</a></li><li><a href="https://engineering.linkedin.com/distributed-systems/log-what-every-software-engineer-should-know-about-real-time-datas-unifying">https://engineering.linkedin.com/distributed-systems/log-what-every-software-engineer-should-know-about-real-time-datas-unifying</a></li><li><a href="https://www.youtube.com/watch?v=_KUV-34fg3A">https://www.youtube.com/watch?v=_KUV-34fg3A</a></li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1a0ef7ca3acb" width="1" height="1" alt=""><hr><p><a href="https://medium.com/the-sixt-india-blog/raft-and-paxos-a-brief-introduction-to-the-basic-consensus-protocols-powering-distributed-systems-1a0ef7ca3acb">Raft and Paxos: A brief introduction to the basic consensus protocols powering distributed systems…</a> was originally published in <a href="https://medium.com/the-sixt-india-blog">Sixt Research &amp; Development India</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>