qkstore

README

qkstore

qkstore - Queuelle Kidd Storage. A CASPaxos distributed database written in Go by Anwar Ali and Analou Ellis. This is for education.

We found peterbourgon/caspaxos which looks like a good start. We are going to fork it then begin modifying it for our purposes.

Documentation

Index

• Variables
• func GrowCluster(ctx context.Context, target Acceptor, proposers ...Proposer) error
• func ShrinkCluster(ctx context.Context, target Acceptor, proposers ...Proposer) error
• type Accepter
• type Acceptor
• type Addresser
• type Ballot
  • func (b Ballot) String() string
• type ChangeFunc
• type ConflictError
  • func (ce ConflictError) Error() string
• type LocalProposer
  • func NewLocalProposer(id uint64, logger log.Logger, initial ...Acceptor) *LocalProposer
  • func (p *LocalProposer) AddAccepter(target Acceptor) error
  • func (p *LocalProposer) AddPreparer(target Acceptor) error
  • func (p *LocalProposer) Propose(ctx context.Context, key string, f ChangeFunc) (newState []byte, err error)
  • func (p *LocalProposer) RemoveAccepter(target Acceptor) error
  • func (p *LocalProposer) RemovePreparer(target Acceptor) error
• type MemoryAcceptor
  • func NewMemoryAcceptor(addr string, logger log.Logger) *MemoryAcceptor
  • func (a *MemoryAcceptor) Accept(ctx context.Context, key string, b Ballot, value []byte) (err error)
  • func (a *MemoryAcceptor) Address() string
  • func (a *MemoryAcceptor) Prepare(ctx context.Context, key string, b Ballot) (value []byte, current Ballot, err error)
• type Preparer
• type Proposer

Variables

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")
)

Functions

func GrowCluster

func GrowCluster(ctx context.Context, target Acceptor, proposers ...Proposer) error

GrowCluster adds the target acceptor to the cluster of proposers.

func ShrinkCluster

func ShrinkCluster(ctx context.Context, target Acceptor, proposers ...Proposer) error

ShrinkCluster removes the target acceptor from the cluster of proposers.

Types

type Accepter

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

Accepter models the second-phase responsibilities of an acceptor.

type Acceptor

type Acceptor interface {
	Addresser
	Preparer
	Accepter
}

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 Addresser

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

Addresser models something with a unique address.

type Ballot

type Ballot struct {
	Counter uint64
	ID      uint64
}

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 ConflictError

type ConflictError struct {
	Proposed Ballot
	Existing Ballot
}

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

func (ConflictError) Error

func (ce ConflictError) Error() string

type LocalProposer

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

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

func NewLocalProposer

func NewLocalProposer(id uint64, logger log.Logger, initial ...Acceptor) *LocalProposer

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

func (*LocalProposer) AddAccepter

func (p *LocalProposer) 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 (*LocalProposer) AddPreparer

func (p *LocalProposer) 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 (*LocalProposer) Propose

func (p *LocalProposer) Propose(ctx context.Context, key string, f ChangeFunc) (newState []byte, err error)

Propose a change from a client into the cluster.

func (*LocalProposer) RemoveAccepter

func (p *LocalProposer) 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 (*LocalProposer) RemovePreparer

func (p *LocalProposer) 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.

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, 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, b Ballot) (value []byte, current Ballot, err error)

Prepare implements the first-phase responsibilities of an acceptor.

type Preparer

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

Preparer models the first-phase responsibilities of an acceptor.

type Proposer

type Proposer interface {
	Propose(ctx context.Context, key string, f ChangeFunc) (newState []byte, err error)

	AddAccepter(target Acceptor) error
	AddPreparer(target Acceptor) error
	RemovePreparer(target Acceptor) error
	RemoveAccepter(target Acceptor) error
}

Proposer models a concrete proposer.