raft

README

ABOUT

This package implements the Raft protocol described in Diego Ongarno's PhD thesis.

Features

Almost all major features outlined in the Raft thesis have been implemented -

• leader election and log replication
• membership changes
• snapshotting, streaming and log compaction
• batching and pipelining
• ReadIndex protocol for read-only queries
• quiesce mode
• leadership transfer
• non-voting members
• idempotent updates transparent to applications
• stateful requests

Third Party Code

This package is a new implementation of the Raft protocol with influence from etcd raft -

• all relevant etcd raft tests have been ported to this project
• a similar iterative style interface is employed as it yields high throughput

Check source code files for copyright information.

Comparison

This package is significantly different from etcd raft -

• brand new implementation
• better bootstrapping procedure
• much higher proposal throughput
• three stage log
• zero disk read when replicating raft log entries
• committed entries are applied in a fully asynchronous manner
• snapshots are applied in a fully asynchronous manner
• replication messages can be serialized and sent in fully asynchronous manner
• pagination support when applying committed entries
• fully batched making proposal implementation
• fully batched ReadIndex implementation
• the quiesce feature requires assistance from the upper layer
• unsafe read-only queries that rely on local clock is not supported
• more pessimistic when handling membership change
• non-voting members are implemented as a special raft state
• non-voting members can initiate both new proposal and ReadIndex requests
• PreVote is being worked on, it is expected to be supported in the next major release

Status

Production ready

Documentation

Overview

Package raft is a distributed consensus package that implements the Raft protocol.

This package is internally used by Dragonboat, applications are not expected to import this package.

Index

• Constants
• Variables
• func ClusterID(clusterID uint64) string
• func IsLocalMessageType(t pb.MessageType) bool
• func NodeID(nodeID uint64) string
• type ILogDB
• type Peer
  • func LaunchPeer(config *config.Config, logdb ILogDB, addresses []PeerAddress, initial bool, ...) (*Peer, error)
  • func (rc *Peer) ApplyConfigChange(cc pb.ConfigChange)
  • func (rc *Peer) Campaign()
  • func (rc *Peer) Commit(ud pb.Update)
  • func (rc *Peer) DumpRaftInfoToLog(addrMap map[uint64]string)
  • func (rc *Peer) GetLeaderID() uint64
  • func (rc *Peer) GetUpdate(moreEntriesToApply bool) pb.Update
  • func (rc *Peer) Handle(m pb.Message)
  • func (rc *Peer) HasUpdate(moreEntriesToApply bool) bool
  • func (rc *Peer) LocalStatus() Status
  • func (rc *Peer) NotifyRaftLastApplied(lastApplied uint64)
  • func (rc *Peer) ProposeConfigChange(configChange pb.ConfigChange, key uint64)
  • func (rc *Peer) ProposeEntries(ents []pb.Entry)
  • func (rc *Peer) QuiescedTick()
  • func (rc *Peer) ReadIndex(ctx pb.SystemCtx)
  • func (rc *Peer) RejectConfigChange()
  • func (rc *Peer) ReportSnapshotStatus(nodeID uint64, reject bool)
  • func (rc *Peer) ReportUnreachableNode(nodeID uint64)
  • func (rc *Peer) RequestLeaderTransfer(target uint64)
  • func (rc *Peer) RestoreRemotes(ss pb.Snapshot)
  • func (rc *Peer) Tick()
• type PeerAddress
• type State
  • func (st State) String() string
• type Status
  • func (s *Status) IsFollower() bool
  • func (s *Status) IsLeader() bool

Constants

const (
	// NoLeader is the flag used to indcate that there is no leader or the leader
	// is unknown.
	NoLeader uint64 = 0
	// NoNode is the flag used to indicate that the node id field is not set.
	NoNode uint64 = 0
)

const (
	// RaftLogTypeName is the type name of the raft log
	RaftLogTypeName = "three-stage"
)

Variables

var ErrCompacted = errors.New("requested entry has been compacted")

ErrCompacted is the error returned to indicate that the requested entries are no longer in the LogDB due to compaction.

var ErrSnapshotOutOfDate = errors.New("snapshot out of date")

ErrSnapshotOutOfDate is the error returned to indicate that the concerned snapshot is considered as out of date.

var ErrUnavailable = errors.New("requested entry at index is unavailable")

ErrUnavailable is the error returned to indicate that requested entries are not available in LogDB.

Functions

func ClusterID

func ClusterID(clusterID uint64) string

ClusterID returns a human friendly form of ClusterID for logging purposes.

func IsLocalMessageType

func IsLocalMessageType(t pb.MessageType) bool

IsLocalMessageType returns a boolean value indicating whether the specified message type is a local message type.

func NodeID

func NodeID(nodeID uint64) string

NodeID returns a human friendly form of NodeID for logging purposes.

Types

type ILogDB

type ILogDB interface {
	// GetRange returns the range of the entries in LogDB.
	GetRange() (uint64, uint64)
	// SetRange updates the ILogDB to extend the entry range known to the ILogDB.
	SetRange(index uint64, length uint64)
	// NodeState returns the state of the node persistented in LogDB.
	NodeState() (pb.State, pb.Membership)
	// SetState sets the persistent state known to ILogDB.
	SetState(ps pb.State)
	// CreateSnapshot sets the snapshot known to ILogDB
	CreateSnapshot(ss pb.Snapshot) error
	// ApplySnapshot makes the sbapshot known to ILogDB and also update the entry
	// range known to ILogDB.
	ApplySnapshot(ss pb.Snapshot) error
	// Term returns the entry term of the specified entry.
	Term(index uint64) (uint64, error)
	// Entries returns entries between [low, high) with total size of entries
	// limited to maxSize bytes.
	Entries(low uint64, high uint64, maxSize uint64) ([]pb.Entry, error)
	// Snapshot returns the metadata for the most recent snapshot known to the
	// LogDB.
	Snapshot() pb.Snapshot
	// Compact performs entry range compaction on ILogDB up to the entry
	// specified by index.
	Compact(index uint64) error
	// Append makes the given entries known to the ILogDB instance. This is
	// usually not how entries are persisted.
	Append(entries []pb.Entry) error
}

ILogDB is a read-only interface to the underlying persistent storage to allow the raft package to access raft state, entries, snapshots stored in the persistent storage. Entries stored in the persistent storage accessible via ILogDB is usually not required in normal cases.

type Peer

type Peer struct {
	// contains filtered or unexported fields
}

Peer is the interface struct for interacting with the underlying Raft protocol implementation.

func LaunchPeer

func LaunchPeer(config *config.Config, logdb ILogDB,
	addresses []PeerAddress, initial bool, newNode bool) (*Peer, error)

LaunchPeer starts or restarts a Raft node.

func (*Peer) ApplyConfigChange

func (rc *Peer) ApplyConfigChange(cc pb.ConfigChange)

ApplyConfigChange applies a raft membership change to the local raft node.

func (*Peer) Campaign

func (rc *Peer) Campaign()

Campaign starts the campaign procedure.

func (*Peer) Commit

func (rc *Peer) Commit(ud pb.Update)

Commit commits the Update state to mark it as processed.

func (*Peer) DumpRaftInfoToLog

func (rc *Peer) DumpRaftInfoToLog(addrMap map[uint64]string)

DumpRaftInfoToLog prints the raft state to log for debugging purposes.

func (*Peer) GetLeaderID

func (rc *Peer) GetLeaderID() uint64

GetLeaderID returns the leader id.

func (*Peer) GetUpdate

func (rc *Peer) GetUpdate(moreEntriesToApply bool) pb.Update

GetUpdate returns the current state of the Peer.

func (*Peer) Handle

func (rc *Peer) Handle(m pb.Message)

Handle processes the given message.

func (*Peer) HasUpdate

func (rc *Peer) HasUpdate(moreEntriesToApply bool) bool

HasUpdate returns a boolean value indicating whether there is any Update ready to be processed.

func (*Peer) LocalStatus

func (rc *Peer) LocalStatus() Status

LocalStatus returns the current local status of the raft node.

func (*Peer) NotifyRaftLastApplied

func (rc *Peer) NotifyRaftLastApplied(lastApplied uint64)

NotifyRaftLastApplied passes on the lastApplied index confirmed by the RSM to the raft state machine.

func (*Peer) ProposeConfigChange

func (rc *Peer) ProposeConfigChange(configChange pb.ConfigChange, key uint64)

ProposeConfigChange proposes a raft membership change.

func (*Peer) ProposeEntries

func (rc *Peer) ProposeEntries(ents []pb.Entry)

ProposeEntries proposes specified entries in a batched mode using a single MTPropose message.

func (*Peer) QuiescedTick

func (rc *Peer) QuiescedTick()

QuiescedTick moves the logical clock forward by one tick in quiesced mode.

func (*Peer) ReadIndex

func (rc *Peer) ReadIndex(ctx pb.SystemCtx)

ReadIndex starts a ReadIndex operation. The ReadIndex protocol is defined in the section 6.4 of the Raft thesis.

func (*Peer) RejectConfigChange

func (rc *Peer) RejectConfigChange()

RejectConfigChange rejects the currently pending raft membership change.

func (*Peer) ReportSnapshotStatus

func (rc *Peer) ReportSnapshotStatus(nodeID uint64, reject bool)

ReportSnapshotStatus reports the status of the snapshot to the local raft node.

func (*Peer) ReportUnreachableNode

func (rc *Peer) ReportUnreachableNode(nodeID uint64)

ReportUnreachableNode marks the specified node as not reachable.

func (*Peer) RequestLeaderTransfer

func (rc *Peer) RequestLeaderTransfer(target uint64)

RequestLeaderTransfer makes a request to transfer the leadership to the specified target node.

func (*Peer) RestoreRemotes

func (rc *Peer) RestoreRemotes(ss pb.Snapshot)

RestoreRemotes applies the remotes info obtained from the specified snapshot.

func (*Peer) Tick

func (rc *Peer) Tick()

Tick moves the logical clock forward by one tick.

type PeerAddress

type PeerAddress struct {
	NodeID  uint64
	Address string
}

PeerAddress is the basic info for a peer in the Raft cluster.

type State

type State uint64

State is the state of a raft node defined in the raft paper, possible states are leader, follower, candidate and observer. Observer is non-voting member node.

func (State) String

func (st State) String() string

type Status

type Status struct {
	NodeID    uint64
	ClusterID uint64
	Applied   uint64
	LeaderID  uint64
	NodeState State
	pb.State
}

Status is the struct that captures the status of a raft node.

func (*Status) IsFollower

func (s *Status) IsFollower() bool

IsFollower returns a boolean value indicating whether the node is a follower.

func (*Status) IsLeader

func (s *Status) IsLeader() bool

IsLeader returns a boolean value indicating whether the node is leader.