protocol

package
v0.0.0-...-6e7a5f8 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 31, 2018 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Overview

Package protocol implements the core CASPaxos types and behaviors.

Index

Constants

This section is empty.

Variables

View Source 
var (
	// ErrPrepareFailed indicates a failure during the first "prepare" phase.
	ErrPrepareFailed = errors.New("not enough confirmations during prepare phase; proposer ballot was fast-forwarded")

	// ErrAcceptFailed indicates a failure during the first "accept" phase.
	ErrAcceptFailed = errors.New("not enough confirmations during accept phase")

	// ErrDuplicate indicates the same acceptor was added twice.
	ErrDuplicate = errors.New("duplicate")

	// ErrNotFound indicates an attempt to remove a non-present acceptor.
	ErrNotFound = errors.New("not found")
)
View Source 
var ErrNotEqual = errors.New("not equal")

ErrNotEqual indicates the tombstone value sent as part of a delete request doesn't correspond to the stored value we have for that key.

Functions

func GarbageCollect 

func GarbageCollect(ctx context.Context, key string, proposers []FastForwarder, acceptors []RejectRemover, logger log.Logger) error

GarbageCollect removes a key as described in section 3.1 "How to delete a record" in the paper. Any error is treated as fatal to this GC attempt, and the caller should retry if IsRetryable(err) is true.

func GrowCluster 

func GrowCluster(ctx context.Context, target Acceptor, proposers []ConfigurationChanger) error

GrowCluster adds the target acceptor to the cluster of proposers.

func IsRetryable 

func IsRetryable(err error) bool

IsRetryable indicates the error, received from the GarbageCollect function, is non-terminal, and the client can retry the operation.

func ShrinkCluster 

func ShrinkCluster(ctx context.Context, target Acceptor, proposers []ConfigurationChanger) error

ShrinkCluster removes the target acceptor from the cluster of proposers.

Types

type Accepter 

type Accepter interface {
	Accept(ctx context.Context, key string, age Age, b Ballot, value []byte) error
}

Accepter models the second-phase responsibilities of an acceptor.

type Acceptor 

type Acceptor interface {
	Addresser
	Preparer
	Accepter
	RejectRemover
	StateWatcher
}

Acceptor models a complete, uniquely-addressable acceptor.

Here we have a little fun with names: use Acceptor (-or) as a noun, to model the whole composite acceptor, and Accepter (-er) as a verb, to model the second-phase "accept" responsibilities only.

type AcceptorLister 

type AcceptorLister interface {
	ListPreparers() ([]string, error)
	ListAccepters() ([]string, error)
}

AcceptorLister allows operators to introspect the state of proposers. For debug and operational work, not necessary for the core protocol.

type Addresser 

type Addresser interface {
	Address() string // typically "protocol://host:port"
}

Addresser models something with a unique address.

type Age 

type Age struct {
	Counter uint64
	ID      string
}

Age of a proposer, incremented by GC process.

rystsov: "In theory we can use ballot numbers as age, but in practice if we use caching (1 RTT optimization) we don't want to do it, because then a deletion of a single key will invalidate all caches, which isn't a nice behavior. Acceptors should keep the age of proposers. It can be zero in the beginning, and the GC process is responsible for updating it. Proposers should include their age as part of each message they send."

func (Age) String 

func (a Age) String() string

type AgeError 

type AgeError struct {
	Incoming Age
	Existing Age
}

AgeError is returned by acceptors when there's an age conflict.

func (AgeError) Error 

func (ae AgeError) Error() string

type Ballot 

type Ballot struct {
	Counter uint64
	ID      string
}

Ballot models a ballot number, which are maintained by proposers and cached by acceptors.

From the paper: "It's convenient to use tuples as ballot numbers. To generate it a proposer combines its numerical ID with a local increasing counter: (counter, ID)."

func (Ballot) String 

func (b Ballot) String() string

type ChangeFunc 

type ChangeFunc func(current []byte) (new []byte)

ChangeFunc models client change proposals.

type ConfigurationChanger 

type ConfigurationChanger interface {
	IdentityRead(ctx context.Context, key string) error
	AddAccepter(target Acceptor) error
	AddPreparer(target Acceptor) error
	RemovePreparer(target Acceptor) error
	RemoveAccepter(target Acceptor) error
}

ConfigurationChanger models the grow/shrink cluster responsibilities of a proposer.

type ConflictError 

type ConflictError struct {
	Proposed     Ballot
	Existing     Ballot
	ExistingKind string // e.g. promise or accepted
}

ConflictError is returned by acceptors when there's a ballot conflict.

func (ConflictError) Error 

func (ce ConflictError) Error() string

type FastForwarder 

type FastForwarder interface {
	FullIdentityRead(ctx context.Context, key string) (state []byte, b Ballot, err error)
	FastForwardIncrement(ctx context.Context, key string, b Ballot) (Age, error)
}

FastForwarder models the garbage collection responsibilities of a proposer.

type MemoryAcceptor 

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

MemoryAcceptor persists data in-memory.

func NewMemoryAcceptor 

func NewMemoryAcceptor(addr string, logger log.Logger) *MemoryAcceptor

NewMemoryAcceptor returns a usable in-memory acceptor. Useful primarily for testing.

func (*MemoryAcceptor) Accept 

func (a *MemoryAcceptor) Accept(ctx context.Context, key string, age Age, b Ballot, value []byte) (err error)

Accept implements the second-phase responsibilities of an acceptor.

func (*MemoryAcceptor) Address 

func (a *MemoryAcceptor) Address() string

Address implements Addresser.

func (*MemoryAcceptor) Prepare 

func (a *MemoryAcceptor) Prepare(ctx context.Context, key string, age Age, b Ballot) (value []byte, current Ballot, err error)

Prepare implements the first-phase responsibilities of an acceptor.

func (*MemoryAcceptor) RejectByAge 

func (a *MemoryAcceptor) RejectByAge(ctx context.Context, ages []Age) (err error)

RejectByAge implements part of the garbage collection responsibilities of an acceptor. It updates the minimum age expected for the provided set of proposers.

func (*MemoryAcceptor) RemoveIfEqual 

func (a *MemoryAcceptor) RemoveIfEqual(ctx context.Context, key string, state []byte) (err error)

RemoveIfEqual implements part of the garbage collection responsibilities of an acceptor. It removes the key/value pair identified by key, if the stored value is equal to the tombstone's value.

func (*MemoryAcceptor) Watch 

func (a *MemoryAcceptor) Watch(ctx context.Context, key string, states chan<- []byte) (err error)

Watch for changes to key, sending current states along the passed chan.

type MemoryProposer 

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

MemoryProposer (from the paper) "performs the initialization by communicating with acceptors, and keep minimal state needed to generate unique increasing update IDs (ballot numbers)."

func NewMemoryProposer 

func NewMemoryProposer(id string, logger log.Logger, initial ...Acceptor) *MemoryProposer

NewMemoryProposer returns a usable proposer uniquely identified by id. It communicates with the initial set of acceptors.

func (*MemoryProposer) AddAccepter 

func (p *MemoryProposer) AddAccepter(target Acceptor) error

AddAccepter adds the target acceptor to the pool of accepters used in the second phase of proposals. It's the first step in growing the cluster, which is a global process that needs to be orchestrated by an operator.

func (*MemoryProposer) AddPreparer 

func (p *MemoryProposer) AddPreparer(target Acceptor) error

AddPreparer adds the target acceptor to the pool of preparers used in the first phase of proposals. It's the third step in growing the cluster, which is a global process that needs to be orchestrated by an operator.

func (*MemoryProposer) Address 

func (p *MemoryProposer) Address() string

Address of this proposer, which we interpret as the ID.

func (*MemoryProposer) FastForwardIncrement 

func (p *MemoryProposer) FastForwardIncrement(ctx context.Context, key string, b Ballot) (Age, error)

FastForwardIncrement performs part (2b) responsibilities of the GC process.

func (*MemoryProposer) FullIdentityRead 

func (p *MemoryProposer) FullIdentityRead(ctx context.Context, key string) (state []byte, b Ballot, err error)

FullIdentityRead performs an identity read on the given key with a quorum size of 100%. It's used as part of the garbage collection process, to delete keys.

func (*MemoryProposer) IdentityRead 

func (p *MemoryProposer) IdentityRead(ctx context.Context, key string) error

IdentityRead is an alias for propose with an identity change function. It's a separate method to make implementing an e.g. HTTP proposer simpler; serializing change functions is difficult.

func (*MemoryProposer) ListAccepters 

func (p *MemoryProposer) ListAccepters() (addrs []string, err error)

ListAccepters enumerates the accept-stage acceptors that this proposer is configured with.

func (*MemoryProposer) ListPreparers 

func (p *MemoryProposer) ListPreparers() (addrs []string, err error)

ListPreparers enumerates the prepare-stage acceptors that this proposer is configured with.

func (*MemoryProposer) Propose 

func (p *MemoryProposer) Propose(ctx context.Context, key string, f ChangeFunc) (state []byte, b Ballot, err error)

Propose a change from a client into the cluster.

func (*MemoryProposer) RemoveAccepter 

func (p *MemoryProposer) RemoveAccepter(target Acceptor) error

RemoveAccepter removes the target acceptor from the pool of accepters used in the second phase of proposals. It's the third step in shrinking the cluster, which is a global process that needs to be orchestrated by an operator.

func (*MemoryProposer) RemovePreparer 

func (p *MemoryProposer) RemovePreparer(target Acceptor) error

RemovePreparer removes the target acceptor from the pool of preparers used in the first phase of proposals. It's the first step in shrinking the cluster, which is a global process that needs to be orchestrated by an operator.

func (*MemoryProposer) Watch 

func (p *MemoryProposer) Watch(ctx context.Context, key string, states chan<- []byte) error

Watch the given key, emitting all states into the passed channel.

type Preparer 

type Preparer interface {
	Prepare(ctx context.Context, key string, age Age, b Ballot) (value []byte, current Ballot, err error)
}

Preparer models the first-phase responsibilities of an acceptor.

type Proposer 

type Proposer interface {
	Addresser
	Propose(ctx context.Context, key string, f ChangeFunc) (state []byte, b Ballot, err error)
	ConfigurationChanger
	FastForwarder
	AcceptorLister
	StateWatcher
}

Proposer models a concrete proposer.

type RejectRemover 

type RejectRemover interface {
	RejectByAge(ctx context.Context, ages []Age) error
	RemoveIfEqual(ctx context.Context, key string, state []byte) error
}

RejectRemover models the garbage collection responsibilities of an acceptor.

type StateWatcher 

type StateWatcher interface {
	Watch(ctx context.Context, key string, states chan<- []byte) error
}

StateWatcher watches a key, yielding states on a user-supplied channel.

type Tombstone 

type Tombstone struct {
	Ballot Ballot
	State  []byte
}

Tombstone represents the terminal form of a key. Propose some state, likely empty, and collect it with the resulting ballot into a Tombstone, which becomes input to the garbage collection process.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.