paxos

Documentation

Overview

Package paxos provides some Paxos-related structures that are shared by some of the different Paxos modules.

This includes things like messages which are shared between Fast Paxos, MultiPaxos, MultiPaxosLr. It also includes slot maps used by the various actors of the Paxos variants, and basic utility functions.

Index

• Variables
• type Accept
• type Acceptor
• type AcceptorSlot
• type AcceptorSlotMap
  • func CopyAccSlotMapRange(afterSlotID SlotID, sourceSlotMap *AcceptorSlotMap) *AcceptorSlotMap
  • func NewAcceptorSlotMap() *AcceptorSlotMap
  • func (sm *AcceptorSlotMap) GetSlot(id SlotID) *AcceptorSlot
• type Actor
• type Adu
  • func NewAdu(sid SlotID) *Adu
  • func (a *Adu) Increment()
  • func (a *Adu) String() string
  • func (a *Adu) Value() SlotID
• type CatchUpRequest
• type CatchUpResponse
• type Learn
• type Learner
• type LearnerLrSlot
• type LearnerLrSlotMap
  • func NewLearnerLrSlotMap() *LearnerLrSlotMap
  • func (llrsm *LearnerLrSlotMap) GetSlot(id SlotID) *LearnerLrSlot
• type LearnerSlot
• type LearnerSlotMap
  • func NewLearnerSlotMap() *LearnerSlotMap
  • func (llrsm *LearnerSlotMap) GetSlot(id SlotID) *LearnerSlot
• type Pack
• type Prepare
• type Promise
• type Proposer
• type ProposerRound
  • func NewProposerRound(id grp.ID) *ProposerRound
  • func (pr *ProposerRound) Compare(opr ProposerRound) int
  • func (pr *ProposerRound) Next()
  • func (pr *ProposerRound) SetOwner(id grp.ID)
• type ProposerSlot
• type ProposerSlotMap
  • func NewProposerSlotMap() *ProposerSlotMap
  • func (sm *ProposerSlotMap) GetSlot(id SlotID) *ProposerSlot
• type RangeTuple
• type ReconfigCmd
• type ResponseTuple
• type SlotID
• type Value
  • func (v *Value) Equal(o Value) bool
  • func (v *Value) Hash() uint32
• type ValueType
  • func (vt ValueType) String() string

Variables

var ZeroRound = ProposerRound{0, grp.NewIDFromInt(0, 0)}

The zero-value of a ProposerRound

Types

type Accept

type Accept struct {
	ID   grp.ID
	Slot SlotID
	Rnd  ProposerRound
	Val  Value
}

type Acceptor

type Acceptor interface {
	Actor
	GetState(afterSlot SlotID, release <-chan bool) *AcceptorSlotMap
	GetMaxSlot(release <-chan bool) *AcceptorSlotMap
	SetState(slotmap *AcceptorSlotMap)
	SetLowSlot(slot SlotID)
}

The interface an Acceptor must fulfill.

type AcceptorSlot

type AcceptorSlot struct {
	ID   SlotID
	VRnd ProposerRound // The highest proposal number in which we have casted a vote
	VVal Value         // The value voted for with proposal number vrnd
}

In MultiPaxos we need to maintain multiple instances of Paxos. We call each of these instances a slot. In this case, this AcceptorSlot contains the slot state that is used by an Acceptor.

type AcceptorSlotMap

type AcceptorSlotMap struct {
	Slots   map[SlotID]*AcceptorSlot
	Rnd     ProposerRound // The highest proposal number in which we have participated
	MaxSeen SlotID
}

An AcceptorSlotMap allows easy maintenance of slots. It contains a map from SlotId to an AcceptorSlot, as well as the highest accessed SlotId.

func CopyAccSlotMapRange

func CopyAccSlotMapRange(afterSlotID SlotID, sourceSlotMap *AcceptorSlotMap) *AcceptorSlotMap

func NewAcceptorSlotMap

func NewAcceptorSlotMap() *AcceptorSlotMap

Construct a new AcceptorSlotMap.

func (*AcceptorSlotMap) GetSlot

func (sm *AcceptorSlotMap) GetSlot(id SlotID) *AcceptorSlot

Given a SlotId, get the corresponding AcceptorSlot. Also may modify MaxSeen, the highest accessed SlotId.

type Actor

type Actor interface {
	Start()
	Stop()
}

A Paxos actor implements Start() and Stop() methods. Maybe this could be generalized as an interface for a Module which we Start() and Stop() in the server module.

type Adu

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

func NewAdu

func NewAdu(sid SlotID) *Adu

func (*Adu) Increment

func (a *Adu) Increment()

func (*Adu) String

func (a *Adu) String() string

func (*Adu) Value

func (a *Adu) Value() SlotID

type CatchUpRequest

type CatchUpRequest struct {
	ID     grp.ID
	Ranges []RangeTuple
}

type CatchUpResponse

type CatchUpResponse struct {
	ID   grp.ID
	Vals []ResponseTuple
}

type Learn

type Learn struct {
	ID          grp.ID
	Slot        SlotID
	Rnd         ProposerRound
	Val         Value
	EpochVector []grp.Epoch
}

type Learner

type Learner interface {
	Actor
}

The interface a Learner must fulfill.

type LearnerLrSlot

type LearnerLrSlot struct {
	ID         SlotID
	Learned    bool
	Rnd        ProposerRound
	Learns     []*Learn
	Votes      uint
	Voted      map[grp.ID]bool
	LearnedVal Value
	Decided    bool
	CheckVQ    bool
}

The state that a LrLearner needs to maintain for every Slot.

type LearnerLrSlotMap

type LearnerLrSlotMap struct {
	Slots   map[SlotID]*LearnerLrSlot
	MaxSeen SlotID
}

A LearnerSlotMap allows easy access to the slots of a Learner.

func NewLearnerLrSlotMap

func NewLearnerLrSlotMap() *LearnerLrSlotMap

Construct a new LearnerSlotMap.

func (*LearnerLrSlotMap) GetSlot

func (llrsm *LearnerLrSlotMap) GetSlot(id SlotID) *LearnerLrSlot

Given a SlotId, return the associated LearnerSlot, as well as possibly modify MaxSeen.

type LearnerSlot

type LearnerSlot struct {
	ID         SlotID
	Learned    bool
	Rnd        ProposerRound
	Learns     []*Learn
	Votes      uint
	LearnedVal Value
	Decided    bool
}

The state that a Learner needs to maintain for every Slot.

type LearnerSlotMap

type LearnerSlotMap struct {
	Slots   map[SlotID]*LearnerSlot
	MaxSeen SlotID
}

A LearnerSlotMap allows easy access to the slots of a Learner.

func NewLearnerSlotMap

func NewLearnerSlotMap() *LearnerSlotMap

Construct a new LearnerSlotMap.

func (*LearnerSlotMap) GetSlot

func (llrsm *LearnerSlotMap) GetSlot(id SlotID) *LearnerSlot

Given a SlotId, return the associated LearnerSlot, as well as possibly modify MaxSeen.

type Pack

type Pack struct {
	ID          grp.ID
	Gm          grp.GroupManager
	StopCheckIn *sync.WaitGroup

	Config        *config.Config
	NrOfNodes     uint
	NrOfAcceptors uint

	RunProp bool
	RunAcc  bool
	RunLrn  bool

	Dmx net.Demuxer
	Ld  liveness.LeaderDetector

	Ucast  chan<- net.Packet
	Bcast  chan<- interface{}
	BcastP chan<- interface{}
	BcastA chan<- interface{}
	BcastL chan<- interface{}

	PropChan        <-chan *Value // Proposal values
	DcdChan         chan<- *Value // Decided values
	NewDcdChan      chan bool
	DcdSlotIDToProp chan SlotID

	LocalAdu        *Adu
	FirstSlot       SlotID
	NextExpectedDcd SlotID
}

A Pack is used during the construction of the Paxos actors. This Pack is passed to each of the actor constructors upon instantiation. The actors can then pull the information they need from this pack to function.

For example, each actor will need to pull the Bcast and Ucast channels from this pack and store them locally so that they can send messages to the other replicas:

func NewMultiProposer(pp px.Pack) *MultiProposer {
  return &MultiProposer{
    ...
    ucast:          pp.Ucast,
    bcast:          pp.Bcast,
    ...
  }
}

type Prepare

type Prepare struct {
	ID   grp.ID
	CRnd ProposerRound
	Slot SlotID
}

type Promise

type Promise struct {
	ID          grp.ID
	Rnd         ProposerRound
	AccSlots    []AcceptorSlot
	EpochVector []grp.Epoch
}

type Proposer

type Proposer interface {
	Actor
	SetNextSlot(ns SlotID)
}

The interface a Proposer must fulfill, also includes the base PaxosActor methods.

type ProposerRound

type ProposerRound struct {
	Rnd uint
	ID  grp.ID
}

A ProposerRound, which is guaranteed to be unique among all the Proposers due to the fact that it is based on the Proposer's Id as well as the round number.

func NewProposerRound

func NewProposerRound(id grp.ID) *ProposerRound

func (*ProposerRound) Compare

func (pr *ProposerRound) Compare(opr ProposerRound) int

Compare two ProposerRounds. Returns -1 if pr is less tha opr, 0 if they are equal, or 1 if pr is greater than opr.

func (*ProposerRound) Next

func (pr *ProposerRound) Next()

Incremenent the ProposerRound.

func (*ProposerRound) SetOwner

func (pr *ProposerRound) SetOwner(id grp.ID)

Change the ownership of the ProposerRound.

type ProposerSlot

type ProposerSlot struct {
	ID        SlotID
	Proposal  *Accept
	SentCount uint8
}

The state that a Proposer needs to maintain for every Slot.

type ProposerSlotMap

type ProposerSlotMap struct {
	Slots   map[SlotID]*ProposerSlot
	MaxSeen SlotID
}

A PropserSlotMap allows easy access to the slots of a Proposer.

func NewProposerSlotMap

func NewProposerSlotMap() *ProposerSlotMap

Construct a new ProposerSlotMap.

func (*ProposerSlotMap) GetSlot

func (sm *ProposerSlotMap) GetSlot(id SlotID) *ProposerSlot

Given a SlotId, return the associated ProposerSlot, as well as possibly modify MaxSeen.

type RangeTuple

type RangeTuple struct {
	From SlotID
	To   SlotID
}

type ReconfigCmd

type ReconfigCmd struct {
	Nodes map[grp.ID]grp.Node
	New   grp.ID
}

For now only allowing replacement through reconfiguration. Nodes is the new NodeMap to be used. New is the id of the replaced node in the node map. Should be expanded to allow different types of reconfiguration commands: add, remove, replace etc.

type ResponseTuple

type ResponseTuple struct {
	Slot SlotID
	Val  Value
}

type SlotID

type SlotID uint

type Value

type Value struct {
	Vt ValueType
	Cr []*client.Request
	Rc *ReconfigCmd
}

func (*Value) Equal

func (v *Value) Equal(o Value) bool

func (*Value) Hash

func (v *Value) Hash() uint32

type ValueType

type ValueType int

const (
	Noop ValueType = iota
	App
	Reconfig
)

func (ValueType) String

func (vt ValueType) String() string