paxos

Documentation

Overview

Package paxos provides paxos components for the strong consistency.

The paxos peers as a whole manage a sequential agreed values. Every paxos peer should be wrapped in an application instance. All the instances build up a whole system to keep the data consistency. Notice that the set of peers is fixed.

The data decided by the paxos peers could be operations, which could constitute a State Machine to reveal the state transferring of the actual data. The typical application is the key-value database.

Fault-tolerance Model

The crash and restart won't happen, because the memory is not consistent. But the followings should be considered.

• The network partition.
• Message loss or long latency in a channel.

API

The paxos library provides 6 interfaces.

Initialize paxos peer.

px = paxos.Make(peers []string, me string) -- Create a paxos peer in the
  specific group.

Consensus interfaces (Core API).

px.Start(seq int, v interface{}) -- Start agreement on new instance with the
  sequence number. v is the proposal value which maybe not be chosen.
  Because there is another value has been chosen in the progress.
px.Status(seq int) (Fate, v interface{}) -- Get the info of the instance
  with the sequence number. Fate is the status: Chosen, Pending or
  Forgotten. v is the chosen value.

The following three are for the memory efficience.

px.Done(seq int) -- Tell all the peers that all instances <= seq could be
  forgotten to release some memory space.
px.Max() int -- Get the highest instance seq known, or -1.
px.Min() int -- Get the lowest instance seq that all the lower seq instances
  than it have been forgotten.

Index

• type AcceptArgs
• type AcceptReply
• type Acceptor
• type ChooseArgs
• type ChooseReply
• type Fate
• type Paxos
  • func Make(peers []string, me int, rpcs *rpc.Server) *Paxos
  • func (px *Paxos) Accept(args *AcceptArgs, reply *AcceptReply) error
  • func (px *Paxos) Choose(args *ChooseArgs, reply *ChooseReply) error
  • func (px *Paxos) Done(seq int)
  • func (px *Paxos) Kill()
  • func (px *Paxos) Max() int
  • func (px *Paxos) Min() int
  • func (px *Paxos) Prepare(args *PrepareArgs, reply *PrepareReply) error
  • func (px *Paxos) Start(seq int, v interface{})
  • func (px *Paxos) Status(seq int) (Fate, interface{})
  • func (px *Paxos) UpdateDoneSeqs(args *SeqArgs, reply *SeqReply) error
• type PrepareArgs
• type PrepareReply
• type Proposer
  • func (proposer *Proposer) Propose()
• type SeqArgs
• type SeqReply

Types

type AcceptArgs

type AcceptArgs struct {
	Seq int
	N   int
	V   interface{}
}

AcceptArgs is Accept RPC args.

type AcceptReply

type AcceptReply struct {
	N    int // for choosing next proposing number
	Succ bool
}

AcceptReply is Accept RPC reply.

type Acceptor

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

Acceptor is the Acceptor role for one paxos instance.

type ChooseArgs

type ChooseArgs struct {
	Seq int
	V   interface{}
}

ChooseArgs is Choose RPC args.

type ChooseReply

type ChooseReply bool

ChooseReply is Choose RPC reply.

type Fate

type Fate int

Fate is the status of the paxos instance which could be viewed by px.Status() interface.

const (
	// The value on the instance is chosen.
	Chosen Fate = iota + 1
	// The value has been chosen yet.
	Pending
	// The value one the instance is chosen but forgotten.
	Forgotten
)

Fate of the paxos instance.

type Paxos

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

Paxos is the paxos peer of one paxos group. Every paxos peer is an isolated process (of course a thread or a goroutine). It has more than one paxos instances with the sequential numbers. Every instance burden the three roles (agents in "Paxos made simple") : Proposer, Acceptor and Leaner.

func Make

func Make(peers []string, me int, rpcs *rpc.Server) *Paxos

Make creates a paxos peer and start the service. Peers are the addresses of all the paxos peers (including itself). Me is the index of the peer of itself.

func (*Paxos) Accept

func (px *Paxos) Accept(args *AcceptArgs, reply *AcceptReply) error

Accept is RPC routine invoked by Paxos peers.

func (*Paxos) Choose

func (px *Paxos) Choose(args *ChooseArgs, reply *ChooseReply) error

Choose is RPC routine invoked by Paxos peers.

func (*Paxos) Done

func (px *Paxos) Done(seq int)

Done reminds that all the instances (<= seq) have been done and can be forgetten. It aims to free up memory in long-term running paxos-based services.

If the application thinks the old records can be discarded, the Done() will try to forget the all information about all instances (<=seq). We say "try", because only if all the peers ack that one instance has been done, then the instance could be forgotten.

Paxos peers need to exchange their highest Done() arguments in order to affect the return value of Min(). These exchanges can be piggybacked on ordinary Paxos agreement protocol messages, so it is OK if one peers Min does not reflect another Peers Done() until after the next instance is agreed to.

See more details in Min().

func (*Paxos) Kill

func (px *Paxos) Kill()

Kill shuts down this peer to make network failures for testing.

func (*Paxos) Max

func (px *Paxos) Max() int

Max returns the highest instance sequence number known to this paxos peer.

func (*Paxos) Min

func (px *Paxos) Min() int

Min returns the lowest instance seq that all the lower seq instances than it have been forgotten. In other words, it's 1 + min(Highest(Done_arg)_i). Highest(Done_arg)_i is the highest number ever passed to Done() on peer i, which is -1 if Done() has never been invoked on peer i.

The fact is that Min() can't increase until all paxos peers have been heard from. If a peer is dead or unreachable, other peers Min() will not increase even if all reachable peers in its network partition call Done. Since when the unreachable peer recovers, it will catch up the missing instances, but it won't work it others forget these instances.

func (*Paxos) Prepare

func (px *Paxos) Prepare(args *PrepareArgs, reply *PrepareReply) error

Prepare is RPC routine invoked by Paxos peers.

func (*Paxos) Start

func (px *Paxos) Start(seq int, v interface{})

Start proposes the value v on the instance with seq. It just do a proposal, which doesn't mean the proposal will be chosen. It returns immediately. The application can check the status of the paxos instance by Status().

func (*Paxos) Status

func (px *Paxos) Status(seq int) (Fate, interface{})

Status gets the status of the instance with the seq to reveal whether the value is chosen and if so what the chosen value is. Status() just inspects the local peer state, instead of communicating with other paxos peers.

func (*Paxos) UpdateDoneSeqs

func (px *Paxos) UpdateDoneSeqs(args *SeqArgs, reply *SeqReply) error

UpdateDoneSeqs is RPC routine invoked by paxos peers.

type PrepareArgs

type PrepareArgs struct {
	Seq int
	N   int
}

PrepareArgs is Prepare RPC args.

type PrepareReply

type PrepareReply struct {
	N    int // for choosing next proposing number
	NA   int
	VA   interface{}
	Succ bool
}

PrepareReply is Prepare RPC reply.

type Proposer

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

Proposer is the Proposer role for one paxos instance.

func (*Proposer) Propose

func (proposer *Proposer) Propose()

Propose proposes the given value on the specific instance until the instance makes a chosen value or gets dead.

type SeqArgs

type SeqArgs struct {
	Sender int
	Seq    int
}

SeqArgs is UpdateDoneSeqs args.

type SeqReply

type SeqReply bool

SeqReply is UpdateDoneSeqs reply.