Raft (algorithm): Difference between revisions

Revision as of 09:24, 17 August 2017

Revision as of 15:03, 17 August 2017

Line 5:

=== Approach of the consensus problem in Raft ===

Raft implements consensus by a leader approach. The servercluster has one and only one elected leader which is fully responsible for managing log replication on the other servers of the cluster. It means that the leader can decide of new entries placement and establishment of data flow between it and the other servers without consulting other servers. A leader leads until it fails or disconnects, in which case a new leader is elected.

The consensus problem is decomposed in Raft into three relatively independent subproblems listed down below.

Line 19:

==== Log Replication ====

The leader is responsible for the log replication. It accepts client requests. TheEach client request consist in a command to be executed by the replicated state machines in the cluster. After being appended to the leader's log as a new entry, each of the requests areis forwarded to the followers in AppendEntries messages. OnceIn thecase leaderof receivesunavailability confirmationof fromthe followers, the majorityleader ofretries itsAppendEntries followersmessages indefinitely, until the requestlog entry is consideredenventually committed.<refstored name="paper"/><refby name="secretlives"/>all of the followers.

Once the leader receives confirmation from the majority of its followers that the entry as been replicated, the leader apply the entry to its local state machine, and the request is considered ''committed''.<ref name="paper" /><ref name="secretlives" /> This event also commits all previous entries in the leader's log. Once a follower learns that a log entry is committed, it applies the entry to its local state machine. It provides consistency for the logs between all the servers through the cluster, insuring that the safety rule of Log Matching is respected.

In the case of leader crash, the logs can be left inconsistent, with some logs from the old leader not being fully replicated through the cluster. The new leader will then handle inconsistency by forcing the followers to duplicate its own log. To do so, for each of its followers, the leader will compare its log with the log from the follower, find the last entry where they agree, then delete all the entries coming after this critical entry in the follower log and replace it with its own log entries. This mechanism will restore log consistency in a cluster subject to failures.

==== Safety ====