Raft (protocol)

Raft (protocol)
source
Name	Raft (protocol)
Author	Diego Ongaro; John Ousterhout
Developer	Stanford University
Introduced	2013
Paradigm	Consensus algorithm; distributed systems
License	Academic

Raft (protocol) Raft is a consensus algorithm for managing a replicated log in distributed computing systems. Developed to provide a more understandable alternative to Paxos-family algorithms, Raft coordinates a collection of servers to maintain a fault-tolerant, consistent state despite crashes and network partitions. It has influenced both academic research and industrial systems through its clarity, formal analysis, and practical implementations.

Overview

Raft divides consensus into leader election, log replication, and safety mechanisms to ensure consistency across replicas. The protocol assumes a cluster of servers drawn from models used in Lamport’s work and operates in asynchronous networks similar to environments studied by Leslie Lamport, Nancy Lynch, and Christos Papadimitriou. Raft’s original presentation, published by researchers at Stanford University, was motivated by deficiencies identified in literature surrounding Paxos and related protocols such as Viewstamped Replication and Byzantine Fault Tolerance research exemplified by Miguel Castro and Barbara Liskov.

Design and Goals

Raft’s design emphasizes understandability, decomposing consensus into discrete subproblems: election, log replication, and safety. The goals echoed concerns from projects at Google and Amazon Web Services where practical consensus underpins distributed filesystems like Google File System and databases such as Spanner and DynamoDB. Raft frames leader election as a state-machine coordination similar to roles in Chubby and Zookeeper, targeting systems employing state machines discussed by Leslie Lamport and used in implementations inspired by Doug Terry and Samza.

Algorithm Details

Raft defines three server states: follower, candidate, and leader, modeled after roles examined in consensus literature linked to Lamport and Ongaro. Time is divided by election timeouts, and the leader handles client requests, appending commands to a replicated log like designs in Log-Structured Merge-tree research contexts used by Facebook and Twitter storage systems. Raft uses term numbers akin to logical clocks introduced by Leslie Lamport and employs AppendEntries and RequestVote RPCs, concepts parallel to RPC frameworks from Andrew Tanenbaum and Sun Microsystems research. The protocol enforces a leader’s role in committing entries once a majority acknowledgement has been received, reflecting majority-quorum techniques also central to Paxos and applied in systems like Hadoop and Cassandra.

Safety and Liveness Properties

Raft ensures safety by preventing committed entries from being overwritten, adopting invariants comparable to those formalized by Nancy Lynch and others in distributed computing theory. Liveness in Raft depends on eventual synchrony assumptions similar to conditions in the FLP impossibility result discussions by Fischer, Lynch, and Paterson. Raft’s leader election and follower behavior are constructed to guarantee progress when a majority of servers are functioning and network delays stabilize, paralleling progress guarantees used in protocols implemented by Google’s Chubby and Spanner.

Implementation and Variants

Multiple implementations of Raft span languages and ecosystems, from systems built in C++, Go, Java, and Rust to libraries integrated into projects at companies like HashiCorp, CoreOS, and Docker. Variants extend Raft with features for dynamic membership similar to proposals in Viewstamped Replication and tackle membership changes as explored by researchers at UC Berkeley and MIT. Other variants integrate Raft with Byzantine fault-tolerant extensions inspired by work at IBM Research and MIT CSAIL, or optimize for geo-distributed deployments studied in projects such as Spanner and Megastore.

Performance and Evaluation

Evaluations compare Raft to Paxos implementations showing similar throughput and latency under typical workloads, with differences often attributed to implementation choices in RPC stacks and storage subsystems influenced by LMDB and RocksDB. Benchmarks performed in academic papers and engineering blogs from Google and Red Hat analyze leader contention, log compaction, snapshotting, and the cost of membership changes, leveraging analysis techniques found in research by Bar-Yossef and practical tracing tools like those from Dapper (tracing) and Zipkin. Performance tuning often focuses on batching, heartbeats, and snapshot frequency, strategies also used in distributed databases from Facebook and Twitter.

Use Cases and Adoption

Raft is widely adopted for coordination, configuration, and metadata management in systems such as etcd, Consul, and TiKV, and informs distributed databases and orchestration tools used by Kubernetes and OpenStack. Its clarity made Raft a choice for educational courses at institutions like Stanford University and MIT, and for startups and enterprises building fault-tolerant services at Netflix, Uber, and Dropbox. The protocol’s influence persists across open-source projects and research exploring consensus in cloud-native infrastructures pioneered by organizations such as Cloud Native Computing Foundation and industrial labs at Microsoft Research.

Category:Distributed computing protocols