mirbft

README

MirBFT Library

MirBFT is a library implementing the Mir byzantine fault tolerant consensus protocol in a network transport, storage, and cryptographic algorithm agnostic way. MirBFT hopes to be a building block of a next generation of distributed systems, providing an implementation of atomic broadcast which can be utilized by any distributed system.

MirBFT improves on traditional atomic broadcast protocols like PBFT and Raft which always have a single active leader by allowing concurrent leaders and reconciling total order in a deterministic and provably safe way. The multi-leader nature of Mir should lead to exceptional performance especially on wide area networks but should be suitable for LAN deployments as well.

MirBFT, like the original PBFT protocol, emphasizes consenting over digests, rather than over actual request data. This allows for more novel methods of request dissemination, and in the optimal case, the state machine may never need to fetch request data.

MirBFT, also like the original PBFT shuns signatures internally, instead preferring to collect quorum certificates during epoch change and other such events. In many ways, this complicates the internal implementation of the library, but it drastically simplifies the external interface and prevents signature validation from becoming a bottleneck under certain workloads.

Architecture

The high level structure of the MirBFT library steals heavily from the architecture of etcdraft. A single threaded state machine is mutated by short lived, non-blocking operations. Operations which might block or which have any degree of computational complexity (like hashing, network calls, etc.) are delegated to the caller.

The required components not dictated by the implementation include:

1. A write-ahead-log for persisting the state machine log entries. (or use the provided one).
2. A hashing implementation (such as the builtin sha256).
3. A request store for persisting application requests while they are consented upon (or use the provided one).
4. An application state which can apply committed requests and may be snapshotted.

For basic applications, only (4) may need to be written, though for applications which wish to optimize for throughput (for instance avoiding committing request data to disk twice), a custom implementation of (3) which integrates with (4) may be desirable.

For more information, see the detailed design document. Note, the documentation has fallen a bit behind based on the implementation work that has happened over the last few months. The documentation should be taken with a grain of salt.

Using Mir

This repository is a new project and under active development and as such, unless you're interested in contributing, it's probably not a good choice for your project (yet!). Most all basic features are present, including state transfer and reconfiguration. For now, if you'd like to see a sample application based on some older code, please look at mirbft-sample, but this can and should be updated..

Preview

Currently, the Mir APIs are mostly stable, but there are significant caveats associated with assorted features. There are APIs for reconfiguration, but it does not entirely work, and there are some assorted unhandled internal cases (like some known missing validation in new epoch messages, poor new epoch leader selection, and more). However, the overall code architecture is finalizing, and it should be possible to parse it and begin to replicate the patterns and begin contributing.

networkState := mirbft.StandardInitialNetworkState(4, 0)

nodeConfig := &mirbft.Config{
	ID:     uint64(i),
	Logger: mirbft.ConsoleInfoLogger,
	BatchSize: 20,
	HeartbeatTicks:       2,
	SuspectTicks:         4,
	NewEpochTimeoutTicks: 8,
	BufferSize:           500,
}

applicationLog := MyNewApplicationLog(networkState)

node, err := mirbft.StartNewNode(nodeConfig, networkState, applicationLog.Snap())
// handle err

processor := &mirbft.SerialProcessor{
	Node:      node,
	Hasher:    sha256.New,
	Log:       applicationLog,   // mirbft.Log interface impl
	Link:      network,          // mirbft.Link interface impl
}

go func() {
	ticker := time.NewTicker(time.Millisecond)
	defer ticker.Stop()

	for {
		select {
		case actions := <-node.Ready():
			node.AddResults(processor.Process(&actions))
		case <-ticker.C:
			node.Tick()
		case <-node.Err():
			return
		}
	}
}()

// Perform application logic
err := node.Propose(context.TODO(), &pb.Request{
	ClientId: 0,
	ReqNo: 0,
	Data: []byte("some-data"),
})
...

Documentation

Overview

Package mirbft is a consensus library, implementing the Mir BFT consensus protocol.

This library can be used by applications which desire distributed, byzantine fault tolerant consensus on message order. Unlike many traditional consensus algorithms, Mir BFT is a multi-leader protocol, allowing throughput to scale with the number of nodes (even over WANs), where the performance of traditional consenus algorithms begin to degrade.

Index

• Variables
• func StandardInitialNetworkState(nodeCount int, clientCount int) *msgs.NetworkState
• type Config
• type LogLevel
• type Logger
• type Node
  • func NewNode(id uint64, config *Config, processorConfig *ProcessorConfig) (*Node, error)
  • func (n *Node) ProcessAsNewNode(exitC <-chan struct{}, tickC <-chan time.Time, ...) error
  • func (n *Node) RestartProcessing(exitC <-chan struct{}, tickC <-chan time.Time) error
  • func (n *Node) Status(ctx context.Context) (*status.StateMachine, error)
  • func (n *Node) Step(ctx context.Context, source uint64, msg *msgs.Msg) error
• type ProcessorConfig

Variables

var ErrStopped = fmt.Errorf("stopped at caller request")

Functions

func StandardInitialNetworkState

func StandardInitialNetworkState(nodeCount int, clientCount int) *msgs.NetworkState

Types

type Config

type Config struct {
	// Logger provides the logging functions.
	Logger Logger

	// BatchSize determines how large a batch may grow (in number of request)
	// before it is cut. (Note, batches may be cut earlier, so this is a max size).
	BatchSize uint32

	// HeartbeatTicks is the number of ticks before a heartbeat is emitted
	// by a leader.
	HeartbeatTicks uint32

	// SuspectTicks is the number of ticks a bucket may not progress before
	// the node suspects the epoch has gone bad.
	SuspectTicks uint32

	// NewEpochTimeoutTicks is the number of ticks a replica will wait until
	// it suspects the epoch leader has failed.  This value must be greater
	// than 1, as rebroadcast ticks are computed as half this value.
	NewEpochTimeoutTicks uint32

	// BufferSize is the total size of messages which can be held by the state
	// machine, pending application, for each node.  This is necessary because
	// there may be dependencies between messages (for instance, until a checkpoint
	// result is computed, watermarks cannot advance).  This should be set
	// to a minimum of a few MB.
	BufferSize uint32
}

type LogLevel

type LogLevel int

const (
	LevelDebug LogLevel = iota
	LevelInfo
	LevelWarn
	LevelError
)

type Logger

type Logger interface {
	// Log is invoked with the log level, the log message, and key/value pairs
	// of any relevant log details.  The keys are always strings, while the
	// values are unspecified.
	Log(level LogLevel, text string, args ...interface{})
}

Logger is minimal logging interface designed to be easily adaptable to any logging library.

var (
	// ConsoleDebugLogger implements Logger and writes all log messages to stdout.
	ConsoleDebugLogger Logger = consoleLogger(LevelDebug)

	// ConsoleInfoLogger implements Logger and writes all LevelInfo and above log messages to stdout.
	ConsoleInfoLogger Logger = consoleLogger(LevelInfo)

	// ConsoleWarnLogger implements Logger and writes all LevelWarn and above log messages to stdout.
	ConsoleWarnLogger Logger = consoleLogger(LevelWarn)

	// ConsoleErrorLogger implements Logger and writes all LevelError log messages to stdout.
	ConsoleErrorLogger Logger = consoleLogger(LevelError)
)

type Node

type Node struct {
	ID     uint64
	Config *Config

	// Exported as a temporary hack
	ResultEventsC  chan *statemachine.EventList
	ResultResultsC chan *statemachine.ActionList
	Clients        *processor.Clients
	// contains filtered or unexported fields
}

Node is the local instance of the MirBFT state machine through which the calling application proposes new messages, receives delegated actions, and returns action results. The methods exposed on Node are all thread safe, though typically, a single loop handles reading Actions, writing results, and writing ticks, while other go routines Propose and Step.

func NewNode

func NewNode(
	id uint64,
	config *Config,
	processorConfig *ProcessorConfig,
) (*Node, error)

NewNode creates a new node. The processor must be started either by invoking node.Processor.StartNewNode with the initial state or by invoking node.Processor.RestartNode.

func (*Node) ProcessAsNewNode

func (n *Node) ProcessAsNewNode(
	exitC <-chan struct{},
	tickC <-chan time.Time,
	initialNetworkState *msgs.NetworkState,
	initialCheckpointValue []byte,
) error

func (*Node) RestartProcessing

func (n *Node) RestartProcessing(
	exitC <-chan struct{},
	tickC <-chan time.Time,
) error

func (*Node) Status

func (n *Node) Status(ctx context.Context) (*status.StateMachine, error)

Status returns a static snapshot in time of the internal state of the state machine. This method necessarily exposes some of the internal architecture of the system, and especially while the library is in development, the data structures may change substantially. This method returns a nil status and an error if the context ends. If the serializer go routine exits for any other reason, then a best effort is made to return the last (and final) status. This final status may be relied upon if it is non-nil. If the serializer exited at the user's request (because the done channel was closed), then ErrStopped is returned.

func (*Node) Step

func (n *Node) Step(ctx context.Context, source uint64, msg *msgs.Msg) error

type ProcessorConfig

type ProcessorConfig struct {
	Link         processor.Link
	Hasher       processor.Hasher
	App          processor.App
	WAL          processor.WAL
	RequestStore processor.RequestStore
	Interceptor  processor.EventInterceptor
}