Golang implementation of the Raft consensus protocol
Go Makefile
Latest commit 5f09c4f Aug 24, 2016 @slackpad slackpad committed on GitHub Merge pull request #152 from F21/patch-1
Fix grammar in README.md
Permalink
Failed to load latest commit information.
bench bench: fix up initializations Jan 31, 2015
.gitignore Added makefile Nov 5, 2013
.travis.yml Travis: build on more recent versions of go Mar 17, 2016
LICENSE Initial commit Nov 5, 2013
Makefile Make raft_test.go far more resilient Mar 31, 2016
README.md Fix grammar in README.md Aug 24, 2016
commands.go converge/recover a followers log faster after a partition. fixes hash… Dec 16, 2015
config.go doc fixes, goroutine WaitGroup, export Leader field Jun 29, 2016
discard_snapshot.go More doc comment fixes Jun 30, 2015
discard_snapshot_test.go Adding DiscardSnapshotStore Jun 1, 2015
file_snapshot.go Check for errors from `ReapSnapshot()` Jun 30, 2016
file_snapshot_test.go Snapshot store with log.Logger Sep 5, 2015
fsm.go doc fixes, goroutine WaitGroup, export Leader field Jun 29, 2016
future.go doc fixes, goroutine WaitGroup, export Leader field Jun 29, 2016
future_test.go doc fixes, goroutine WaitGroup, export Leader field Jun 29, 2016
inflight.go Minor documentation updates Jul 22, 2015
inflight_test.go More doc comment fixes Jun 30, 2015
inmem_store.go More doc comment fixes Jun 30, 2015
inmem_transport.go Do not reuse transports that have been shut down Mar 21, 2016
inmem_transport_test.go Add LoopbackTransport, WithPeers interfaces Mar 21, 2016
integ_test.go Use the logger object in the RaftEnv vs the global logger object Jun 30, 2016
log.go doc fixes, goroutine WaitGroup, export Leader field Jun 29, 2016
log_cache.go Simplify LogCache implementation Jan 14, 2015
log_cache_test.go Simplify LogCache implementation Jan 14, 2015
net_transport.go Don't shadow an already allocated error. Jun 30, 2016
net_transport_test.go log.Logger versions of tcp/net transport Sep 5, 2015
observer.go Merge pull request #129 from rogpeppe/minor-doc-and-future-fixes Jul 7, 2016
peer.go More doc comment fixes Jun 30, 2015
peer_test.go Do not reuse transports that have been shut down Mar 21, 2016
raft.go Document map fields returned by Stats() Jul 16, 2016
raft_test.go Initialize peers properly Jun 30, 2016
replication.go remove lastLogIndexOnly() from state.go, use idx,term version everywhere Mar 21, 2016
snapshot.go doc fixes, goroutine WaitGroup, export Leader field Jun 29, 2016
stable.go log.Logger versions of tcp/net transport Sep 5, 2015
state.go doc fixes, goroutine WaitGroup, export Leader field Jun 29, 2016
tcp_transport.go log.Logger versions of tcp/net transport Sep 5, 2015
tcp_transport_test.go log.Logger versions of tcp/net transport Sep 5, 2015
transport.go doc fixes, goroutine WaitGroup, export Leader field Jun 29, 2016
transport_test.go Rename variables to be more adherent to common conventions Jun 30, 2016
util.go Remove unused function: `uint64ToBytes()` Jun 30, 2016
util_test.go Remove unused code: `asyncNotify()` and subsequent tests. Jun 30, 2016

README.md

raft Build Status

raft is a Go library that manages a replicated log and can be used with an FSM to manage replicated state machines. It is a library for providing consensus.

The use cases for such a library are far-reaching as replicated state machines are a key component of many distributed systems. They enable building Consistent, Partition Tolerant (CP) systems, with limited fault tolerance as well.

Building

If you wish to build raft you'll need Go version 1.2+ installed.

Please check your installation with:

go version

Documentation

For complete documentation, see the associated Godoc.

To prevent complications with cgo, the primary backend MDBStore is in a separate repository, called raft-mdb. That is the recommended implementation for the LogStore and StableStore.

A pure Go backend using BoltDB is also available called raft-boltdb. It can also be used as a LogStore and StableStore.

Protocol

raft is based on "Raft: In Search of an Understandable Consensus Algorithm"

A high level overview of the Raft protocol is described below, but for details please read the full Raft paper followed by the raft source. Any questions about the raft protocol should be sent to the raft-dev mailing list.

Protocol Description

Raft nodes are always in one of three states: follower, candidate or leader. All nodes initially start out as a follower. In this state, nodes can accept log entries from a leader and cast votes. If no entries are received for some time, nodes self-promote to the candidate state. In the candidate state nodes request votes from their peers. If a candidate receives a quorum of votes, then it is promoted to a leader. The leader must accept new log entries and replicate to all the other followers. In addition, if stale reads are not acceptable, all queries must also be performed on the leader.

Once a cluster has a leader, it is able to accept new log entries. A client can request that a leader append a new log entry, which is an opaque binary blob to Raft. The leader then writes the entry to durable storage and attempts to replicate to a quorum of followers. Once the log entry is considered committed, it can be applied to a finite state machine. The finite state machine is application specific, and is implemented using an interface.

An obvious question relates to the unbounded nature of a replicated log. Raft provides a mechanism by which the current state is snapshotted, and the log is compacted. Because of the FSM abstraction, restoring the state of the FSM must result in the same state as a replay of old logs. This allows Raft to capture the FSM state at a point in time, and then remove all the logs that were used to reach that state. This is performed automatically without user intervention, and prevents unbounded disk usage as well as minimizing time spent replaying logs.

Lastly, there is the issue of updating the peer set when new servers are joining or existing servers are leaving. As long as a quorum of nodes is available, this is not an issue as Raft provides mechanisms to dynamically update the peer set. If a quorum of nodes is unavailable, then this becomes a very challenging issue. For example, suppose there are only 2 peers, A and B. The quorum size is also 2, meaning both nodes must agree to commit a log entry. If either A or B fails, it is now impossible to reach quorum. This means the cluster is unable to add, or remove a node, or commit any additional log entries. This results in unavailability. At this point, manual intervention would be required to remove either A or B, and to restart the remaining node in bootstrap mode.

A Raft cluster of 3 nodes can tolerate a single node failure, while a cluster of 5 can tolerate 2 node failures. The recommended configuration is to either run 3 or 5 raft servers. This maximizes availability without greatly sacrificing performance.

In terms of performance, Raft is comparable to Paxos. Assuming stable leadership, committing a log entry requires a single round trip to half of the cluster. Thus performance is bound by disk I/O and network latency.