paxos

Documentation

Overview

Package paxos is a Paxos-simple protocol implementation for Go. It abstract away from transport layer and storage implementation by providing interfaces for proposer and acceptor nodes. Each node should implement transport over network via API to expose API to nodes. Some standard storage implementations are available at `storage.go` file, or custom storage could be used.

Index

• func MultiplexTMs(tms []tcommit.Manager) tcommit.Manager
• func NewTMClient(accs []Acceptor, tmRemote tcommit.Manager, node tcommit.NodeID) tcommit.Manager
• type Acceptor
  • func NewAcceptorNode(prop Proposer, storage Storage) Acceptor
• type AcceptorClient
  • func NewAcceptorClient(grpcClient pb.AcceptorServiceClient, nodeID tcommit.NodeID, txID tcommit.TxID) *AcceptorClient
  • func (ac *AcceptorClient) Accept(ctx context.Context, msg Px2A) error
  • func (ac *AcceptorClient) Prepare(ctx context.Context, msg Px1A) error
• type Ballot
• type Proposal
  • func (p Proposal) Compare(o Proposal) int
• type Proposer
• type ProposerClient
  • func NewProposerClient(grpcClient pb.ProposerServiceClient, nodeID tcommit.NodeID, txID tcommit.TxID) *ProposerClient
  • func (pc *ProposerClient) Accepted(ctx context.Context, msg Px2B) error
  • func (pc *ProposerClient) Promise(ctx context.Context, msg Px1B) error
  • func (pc *ProposerClient) Reject(ctx context.Context, bal Ballot) error
• type Px1A
• type Px1B
• type Px2A
• type Px2B
• type Storage
• type Value

Functions

func MultiplexTMs

func MultiplexTMs(tms []tcommit.Manager) tcommit.Manager

MultiplexTMs sends delivers remote calls to each TM from the list. It could be used for fault-tolerance across TM nodes. If any TM node fails another can handle all operations. Since we're using distributed transaction state storage across Paxos acceptors, all TMs will make conflictless decision based on distributed vote data.

func NewTMClient

func NewTMClient(accs []Acceptor, tmRemote tcommit.Manager, node tcommit.NodeID) tcommit.Manager

NewTMClient creates a client interface for TM(s) using Paxos commit protocol for communication. On begin, this client proposes vote as a Paxos proposal to all acceptors and waits for promise message from acceptors. When vote is accepted by acceptors, it performs `begin` TM remote call. Finish remote call goes directly to remote TM.

Types

type Acceptor

type Acceptor interface {
	// Prepare takes Paxos 1A message. The proposer chooses ballot number
	// that it believes to be larger than any ballot number for which
	// phase 1 has been performed, and sends it to every acceptor for prepare.
	Prepare(ctx context.Context, msg Px1A) error

	// Accept takes Paxos 2A message. The proposer uses ballot number it has
	// already prepared and acceptor promised to reject all proposals fewer than
	// prepared one. It tries to accept a vote by proposal. If the bigger ballot
	// number was prepared by acceptor between these two operations, acceptor may
	// respond with reject.
	Accept(ctx context.Context, msg Px2A) error
}

Acceptor - Paxos acceptor API for proposer

func NewAcceptorNode

func NewAcceptorNode(prop Proposer, storage Storage) Acceptor

NewAcceptorNode creates a node for acceptor with provided storage and proposer API

type AcceptorClient

type AcceptorClient struct {
	NodeID tcommit.NodeID
	TxID   tcommit.TxID
	// contains filtered or unexported fields
}

AcceptorClient implemets paxos.Acceptor interface. It is assumed to be a part of the resource manager for remote procedure calls.

func NewAcceptorClient

func NewAcceptorClient(grpcClient pb.AcceptorServiceClient, nodeID tcommit.NodeID,
	txID tcommit.TxID) *AcceptorClient

NewAcceptorClient with a given gRPC client. NodeID and TxID are necessary to identify Paxos instance in a multi-transactional model.

func (*AcceptorClient) Accept

func (ac *AcceptorClient) Accept(ctx context.Context, msg Px2A) error

Accept message RPC

func (*AcceptorClient) Prepare

func (ac *AcceptorClient) Prepare(ctx context.Context, msg Px1A) error

Prepare message RPC

type Ballot

type Ballot uint16

Ballot number of proposals in Paxos algorithm

type Proposal

type Proposal struct {
	// Ballot number of the proposal
	Ballot
	// Proposer ID, it should be unique number for each
	// proposer participating in the transaction.
	Proposer uint32
}

Proposal for Paxos protocol

func (Proposal) Compare

func (p Proposal) Compare(o Proposal) int

Compare two proposals

type Proposer

type Proposer interface {
	// Promise is a 1B message from acceptor.
	// was prepared succesffully, it includes a proposal ballot
	// number. Promise means that acceptor promises to proposer
	// to reject all next messages if ballot number of such message
	// are less than ballot number of promise.
	Promise(ctx context.Context, msg Px1B) error

	// Accepted message is sent by acceptor as a 2B message, if it
	// successfully accepted 2A message from a proposer.
	Accepted(ctx context.Context, msg Px2B) error

	// Reject is a optimization of Paxos. Instead of ignoring 1A message with
	// small ballot numbers (less than ballot number that acceptor perofrmed any action),
	// acceptor may send a reject message to avoid proposer restarts by timeout and
	// sends a hint with ballot number to help choosing proposer next ballot number
	// greater than any received: bal=max([]rejects)+1
	Reject(ctx context.Context, bal Ballot) error
}

Proposer - Paxos proposer API for acceptor

type ProposerClient

type ProposerClient struct {
	NodeID tcommit.NodeID
	TxID   tcommit.TxID
	// contains filtered or unexported fields
}

ProposerClient implemets paxos.Proposer interface. It is assumed to be a part of the resource manager for remote procedure calls.

func NewProposerClient

func NewProposerClient(grpcClient pb.ProposerServiceClient, nodeID tcommit.NodeID,
	txID tcommit.TxID) *ProposerClient

NewProposerClient with a given gRPC client. NodeID and TxID are necessary to identify Paxos instance in a multi-transactional model.

func (*ProposerClient) Accepted

func (pc *ProposerClient) Accepted(ctx context.Context, msg Px2B) error

Accepted message RPC

func (*ProposerClient) Promise

func (pc *ProposerClient) Promise(ctx context.Context, msg Px1B) error

Promise message RPC

func (*ProposerClient) Reject

func (pc *ProposerClient) Reject(ctx context.Context, bal Ballot) error

Reject message RPC

type Px1A

type Px1A struct {
	Proposal
}

Px1A - Paxos 1A message sent from proposer to acceptor

type Px1B

type Px1B struct {
	Max, Acc Proposal
	Value
}

Px1B - Paxos 1B message sent from acceptor to proposer, it contains maximum and accepted proposal and optional value

type Px2A

type Px2A struct {
	Proposal
	Value
}

Px2A - Paxos 2A message sent from proposer to acceptor

type Px2B

type Px2B struct {
	Ballot
}

Px2B - Paxos 2B message sent from acceptor to proposer

type Storage

type Storage interface {
	// Get current value
	Get() ([]byte, error)
	// Put value
	Put([]byte) error
}

Storage for acepted value on consensus to persist

type Value

type Value encoding.BinaryMarshaler

Value binary of message