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: 2

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL