DEV Community

Vishal Shukla
Vishal Shukla

Posted on

How to Come Up With the Raft Consensus Algorithm Yourself

#distributedsystems #algorithms #programming #architecture

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

  • Leader election
  • Terms
  • RequestVote
  • AppendEntries
  • Log replication
  • Commit index
  • Quorum
  • nextIndex
  • matchIndex

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   │
       └───────┘
Enter fullscreen mode Exit fullscreen mode

A client sends commands to our system:

SET x = 10
SET x = 20
SET x = 30
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

while B executes:

x = 10
x = 30
x = 20
Enter fullscreen mode Exit fullscreen mode

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  │
          └─────┘ └─────┘
Enter fullscreen mode Exit fullscreen mode

Now the client sends:

SET x = 10
Enter fullscreen mode Exit fullscreen mode

to A.

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

A: [SET x = 10]
Enter fullscreen mode Exit fullscreen mode

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: []
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

A writes it locally:

A: [10]
B: []
C: []
Enter fullscreen mode Exit fullscreen mode

A now sends the entry to B and C:

A ── 10 ──> B
A ── 10 ──> C
Enter fullscreen mode Exit fullscreen mode

Suppose B receives it:

A: [10]
B: [10]
C: []
Enter fullscreen mode Exit fullscreen mode

Do we need to wait for C?

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

A + B = 2/3
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

B successfully stores it:

B: [10, 20]
Enter fullscreen mode Exit fullscreen mode

and sends an acknowledgement:

B ── ACK ──> A
Enter fullscreen mode Exit fullscreen mode

But the network drops the ACK.

A never receives it.

From A's perspective:

"Did B receive the entry?"
Enter fullscreen mode Exit fullscreen mode

It doesn't know.

So A retries:

A ── SET x=20 ──> B
Enter fullscreen mode Exit fullscreen mode

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

[10, 20, 20]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

and then:

A 💀
Enter fullscreen mode Exit fullscreen mode

We still have:

B
C
Enter fullscreen mode Exit fullscreen mode

Our system needs another leader.

But who gets to decide?

What if both B and C say:

"I'm the leader!"
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

B votes for itself.

C votes for B.

Now B has:

B + C = 2/3
Enter fullscreen mode Exit fullscreen mode

A majority.

Therefore:

B = Leader
Enter fullscreen mode Exit fullscreen mode

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!"
Enter fullscreen mode Exit fullscreen mode

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
...
Enter fullscreen mode Exit fullscreen mode

Let's call it a term.

Now:

A = Leader, Term 1
Enter fullscreen mode Exit fullscreen mode

After A dies:

B = Leader, Term 2
Enter fullscreen mode Exit fullscreen mode

When A comes back and discovers:

Term 2 > Term 1
Enter fullscreen mode Exit fullscreen mode

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)]
Enter fullscreen mode Exit fullscreen mode

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)]
Enter fullscreen mode Exit fullscreen mode

Both logs have three entries.

So their last index is the same:

index = 3
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Now we can compare the last entries using:

(index, term)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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)]
Enter fullscreen mode Exit fullscreen mode

A reconnects with:

[10(t1), 20(t1), 30(t2), 35(t2)]
Enter fullscreen mode Exit fullscreen mode

They agree here:

10(t1)
20(t1)
Enter fullscreen mode Exit fullscreen mode

But at index 3:

B: 40(t3)
A: 30(t2)
     ↑
  conflict
Enter fullscreen mode Exit fullscreen mode

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)]
Enter fullscreen mode Exit fullscreen mode

A checks:

Do I have index 2 with term 1?
Enter fullscreen mode Exit fullscreen mode

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)]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

So the leader can send:

entry 3
entry 4
entry 5
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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

If you enjoyed this kind of first-principles breakdown, I write more like it at vishalshukla.in.

Top comments (0)