CODEWITHSUNDEEP
algorithmdistributed-computingdistributed-systemraft
Dillion Wang
Dillion Wang

Reputation: 361

How does Raft guarantee log consistency?

I'm learning Raft, and I already know the basic mechanism of Raft.

When a Leader is elected, it is responsible to update the Followers' log to the Leader's one. When updating a Follower, it finds the first matched <entry, term> backwards, and update the Follower with the following logs.

How does Raft guarantee the logs of the Leader and the Follower before the matched <entry, term> are the same? Will this case happen:

                |
Leader          v  
Entry   : 1 2 3 4 5 6 7 8 9 10
Term    : 1 1 1 2 2 3 3 3 3 3 

Follower
Entry   : 1 2 3 4 5 6 7
Term    : 1 1 1 1 2 3 3

Upvotes: 0

Views: 421

Answers (1)

msantl
msantl

Reputation: 391

This property of the Raft algorithm is called Log Matching.

If two logs contain an entry with the same index and term, then the logs are identical in all entries up through the given index

This holds because:

When sending an AppendEntries RPC, the leader includes the index and term of the entry in its log that immediately precedes the new entries. If the follower does not find an entry in its log with the same index and term, then it refuses the new entries. The consistency check acts as an induction step: the initial empty state of the logs satisfies the Log Matching Property, and the consistency check preserves the Log Matching Property whenever logs are extended. As a result, whenever AppendEntries returns successfully, the leader knows that the follower’s log is identical to its own log up through the new entries.

Source https://raft.github.io/raft.pdf

Upvotes: 3

Related Questions