Independent digital publication
Archive

September 26, 2026 · Vishal Shukla

How to Come Up With the Raft Consensus Algorithm Yourself

A step-by-step derivation of Raft, built from first principles instead of memorized rules.

If someone asks you to explain Raft, you might hear a list of terms like:

It can feel like a lot of unrelated rules.

But what if we didn't start with Raft?

What if we started with a problem and tried to design the system ourselves?

That's what we're going to do.

We will start with three completely ordinary servers and gradually add rules whenever something breaks.

By the end, we'll discover that we've recreated most of Raft's core ideas.

The Problem

Suppose we have three servers:

       ┌───────┐
       │   A   │
       └───────┘

       ┌───────┐
       │   B   │
       └───────┘

       ┌───────┐
       │   C   │
       └───────┘

A client sends commands to our system:

SET x = 10
SET x = 20
SET x = 30

We want all three servers to eventually execute these commands in exactly this order.

Why?

Because if A executes:

x = 10
x = 20
x = 30

while B executes:

x = 10
x = 30
x = 20

our replicated system is no longer consistent.

So our first requirement is simple:

Every server must agree on the same sequence of commands.

How would you design this?

1. Let's Start With a Leader

The first problem is coordination.

If every server can independently decide what command comes next, we're going to have a difficult time making them agree.

So let's simplify: what if one server is responsible for deciding the order?

Let's make A the leader:

              Client
                 │
                 ▼
             ┌───────┐
             │   A   │
             │ Leader│
             └───┬───┘
                / \
               /   \
              ▼     ▼
          ┌─────┐ ┌─────┐
          │  B  │ │  C  │
          └─────┘ └─────┘

Now the client sends:

SET x = 10

to A.

A decides that this command should be the first entry in the log:

A: [SET x = 10]

Much simpler.

But we immediately have a problem.

2. What If the Leader Dies Before Replicating?

Suppose A writes the command to its own log and immediately tells the client SUCCESS — and then crashes.

A: [SET x = 10]  💀

B: []
C: []

The client believes the operation succeeded.

But the other servers know nothing about it.

If A never comes back, we've lost a successful write.

So:

A local write isn't enough.

The leader needs to replicate the entry to other servers before acknowledging success.

3. Do We Need Every Server?

Let's modify the process.

The client sends:

SET x = 10

A writes it locally:

A: [10]
B: []
C: []

A now sends the entry to B and C:

A ── 10 ──> B
A ── 10 ──> C

Suppose B receives it:

A: [10]
B: [10]
C: []

Do we need to wait for C?

Not necessarily — with three servers, two already make a majority:

A + B = 2/3

If A and B have the entry, we've got a quorum.

So here's our first important rule:

A write becomes committed once it has been replicated to a majority of servers.

Now the leader can safely tell the client:

SUCCESS

C can catch up later.

There's a subtlety worth calling out here:

Committed does not mean every server has the entry.

It means enough servers have it that the system can preserve it across failures.

4. What If the Acknowledgement Gets Lost?

Our system works, but distributed systems have another annoying property:

messages can disappear.

Suppose A sends an entry to B:

A ── SET x=20 ──> B

B successfully stores it:

B: [10, 20]

and sends an acknowledgement:

B ── ACK ──> A

But the network drops the ACK.

A never receives it.

From A's perspective:

"Did B receive the entry?"

It doesn't know.

So A retries:

A ── SET x=20 ──> B

We obviously don't want B to end up with:

[10, 20, 20]

The operation needs to be safe to retry.

So B should recognize:

"I already have this entry."

and simply acknowledge it again.

Which gets us to the next rule:

Replication must be safe to retry.

5. We Need a Way to Replace a Dead Leader

So far, A is the leader.

But machines crash.

Suppose:

A = Leader

and then:

A 💀

We still have:

B
C

Our system needs another leader.

But who gets to decide?

What if both B and C say:

"I'm the leader!"

Now we've recreated the problem we were trying to solve.

We need an election.

6. Let's Hold an Election

Suppose B decides to become leader.

It asks the other servers for votes:

B ── RequestVote ──> C

B votes for itself.

C votes for B.

Now B has:

B + C = 2/3

A majority.

Therefore:

B = Leader

Put differently, here's the rule:

A server can become leader only after receiving votes from a majority.

But there's another problem.

What's stopping a server from voting for B and then changing its mind and voting for C?

We need:

A server can vote only once during an election.

7. How Do We Know Which Election Is Newer?

Imagine A was leader before it crashed.

Later B becomes leader.

Then A comes back:

A: "I'm still the leader!"

But B is already leading the cluster.

We need some notion of leadership generations.

So let's introduce an election number:

Election 1
Election 2
Election 3
...

Let's call it a term.

Now:

A = Leader, Term 1

After A dies:

B = Leader, Term 2

When A comes back and discovers:

Term 2 > Term 1

it knows its leadership is stale.

It must become a follower.

In other words:

A higher term represents a newer leadership generation.

8. But What About the Data?

Now we're getting somewhere.

Suppose A was leader in Term 1:

A: [10(t1), 20(t1), 30(t1)]
B: [10(t1), 20(t1)]
C: [10(t1), 20(t1)]

A crashes.

B wants to become leader.

But what if B's log is missing something that was already committed?

We cannot simply say:

"Whoever asks for votes first becomes leader."

The candidate's log matters.

So when B asks for a vote, a node should also look at B's log.

A candidate with a stale log should not be able to become leader and overwrite committed history.

This leaves us with one more rule:

A server should only vote for a candidate whose log is sufficiently up-to-date.

But how do we determine whether one log is more up-to-date than another?

9. Index Isn't Enough

Consider:

A: [10(t1), 20(t1), 30(t2)]

B: [10(t1), 20(t1), 40(t3)]

Both logs have three entries.

So their last index is the same:

index = 3

But their histories are different.

We need more information.

Every log entry already has an associated term:

index    command    term

  1        10        1
  2        20        1
  3        30        2

Now we can compare the last entries using:

(index, term)

The term tells us which leadership generation created the entry.

When comparing logs:

  1. Compare the term of the last entry.
  2. If the terms are equal, compare the index.

So:

A: last = (3, t2)
B: last = (3, t3)

B's log is considered more up-to-date.

And here's the deeper point:

Terms don't just identify elections. They also become part of the log's identity.

10. How Do We Detect Conflicting Logs?

Now suppose B becomes leader.

B has:

[10(t1), 20(t1), 40(t3), 50(t3)]

A reconnects with:

[10(t1), 20(t1), 30(t2), 35(t2)]

They agree here:

10(t1)
20(t1)

But at index 3:

B: 40(t3)
A: 30(t2)
     ↑
  conflict

B needs a way to tell A:

"Your history doesn't match mine here."

So instead of blindly sending new entries, B sends information about the previous entry:

prevLogIndex = 2
prevLogTerm  = 1
entries      = [40(t3), 50(t3)]

A checks:

Do I have index 2 with term 1?

If yes, their histories match up to that point.

A can replace everything after index 2:

Before:

[10(t1), 20(t1), 30(t2), 35(t2)]

After:

[10(t1), 20(t1), 40(t3), 50(t3)]

We've now arrived at the basic idea behind Raft's AppendEntries.

11. We Need to Track What Each Follower Has

There is one final practical problem.

Suppose:

Leader B:

[10, 20, 30, 40, 50]

Follower C:

[10, 20]

B shouldn't resend the entire log every time.

It needs to know where C's log currently matches.

So the leader tracks two pieces of information for each follower.

matchIndex

The highest log index that the leader knows the follower has replicated.

For example:

C.matchIndex = 2

means:

"I know C has entries through index 2."

nextIndex

The next log index the leader should try sending to that follower.

C.nextIndex = 3

So the leader can send:

entry 3
entry 4
entry 5

rather than starting from the beginning.

If the follower rejects the request because the histories don't match, the leader moves backward and tries again.

And this is how our earlier idea of:

"Find the last matching point and send the suffix."

turns into an actual implementation mechanism.

12. And Suddenly We Have Raft

Look at what happened.

We didn't start with Raft.

We started with:

"Three servers need to agree on the order of commands."

Then every failure forced another piece:

Need one ordering authority
        ↓
      Leader
        ↓
Leader can crash
        ↓
  Replication
        ↓
Don't need everyone
        ↓
    Majority
        ↓
Need to replace dead leader
        ↓
    Election
        ↓
Need to distinguish elections
        ↓
      Terms
        ↓
Need to protect committed history
        ↓
   Log freshness
        ↓
Need to detect conflicting history
        ↓
  Index + Term
        ↓
Need efficient replication
        ↓
nextIndex + matchIndex

What initially looked like a complicated collection of Raft rules is actually a chain of solutions to very natural problems.