Raft protocol

raft.md

RAFT

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

Replicated state machine

• Replicated state machines are typically implemented using a replicated log.

  • Each server stores a log containing a series of commands, which its state machine executes in order.
  • Each log contains the same commands in the same order, so each state machine processes the same sequence of commands.
  • Since the state machines are deterministic, each computes the same state and the same sequence of outputs.

• Keeping the replicated log consistent is the job of the consensus algorithm.

  • The consensus module on a server receives commands from clients and adds them to its log.
  • It communicates with the consensus modules on other servers to ensure that every log eventually contains the same requests in the same order, even if some servers fail.
  • Once commands are properly replicated, each server’s state machine processes them in log order, and the outputs are returned to clients.
  • As a result, the servers appear to form a single, highly reliable state machine

• Consensus algorithms for practical systems typically have the following properties:

  • They ensure safety (never returning an incorrect result) under all non-Byzantine conditions, including network delays, partitions, and packet loss, duplication, and reordering.
  • They are fully functional (available) as long as any majority of the servers are operational and can communicate with each other and with clients .
  • They do not depend on timing to ensure the consistency of the logs: faulty clocks and extreme message delays can, at worst, cause availability problems.
  • In the common case, a command can complete as soon as a majority of the cluster has responded to a single round of remote procedure calls; a minority of slow servers need not impact overall system performance.

The Raft consensus algorithm

• Raft implements consensus by first electing a distinguished leader, then giving the leader complete responsibility for managing the replicated log.

  • The leader accepts log entries from clients, replicates them on other servers, and tells servers when it is safe to apply log entries to their state machines.
  • Having a leader simplifies the management of the replicated log.
  • For example, the leader can decide where to place new entries in the log without consulting other servers, and data flows in a simple fashion from the leader to other servers
  • A leader can fail or become disconnected from the other servers, in which case a new leader is elected.

• Raft decomposes the consensus problem into three relatively independent subproblems.

  • Leader election: a new leader must be chosen when an existing leader fails.
  • Log replication: the leader must accept log entries from clients and replicate them across the cluster, forcing the other logs to agree with its own.
  • Safety: the key safety property for Raft is the State Machine Safety Property: if any server has applied a particular log entry to its state machine, then no other server may apply a different command for the same log index.