paxos

Documentation

Index

• Constants
• func DPrintf(format string, a ...interface{}) (n int, err error)
• func DPrintfCall(format string, a ...interface{}) (n int, err error)
• func DPrintfRPC(format string, a ...interface{}) (n int, err error)
• type Instance
• type Paxos
  • func Make(peers []string, me int, rpcs *rpc.Server) *Paxos
  • func (px *Paxos) Done(seq int)
  • func (px *Paxos) Kill()
  • func (px *Paxos) Max() int
  • func (px *Paxos) Min() int
  • func (px *Paxos) RPCAccept(args *RPCAcceptArgs, reply *RPCAcceptReply) error
  • func (px *Paxos) RPCDecide(args *RPCDecideArgs, reply *RPCDecideReply) error
  • func (px *Paxos) RPCPrepare(args *RPCPrepareArgs, reply *RPCPrepareReply) error
  • func (px *Paxos) Start(seq int, v interface{})
  • func (px *Paxos) Status(seq int) (bool, interface{})
• type RPCAcceptArgs
• type RPCAcceptReply
• type RPCDecideArgs
• type RPCDecideReply
• type RPCPrepareArgs
• type RPCPrepareReply

Constants

const PEER_ID_BITS int = 8

Functions

func DPrintf

func DPrintf(format string, a ...interface{}) (n int, err error)

func DPrintfCall

func DPrintfCall(format string, a ...interface{}) (n int, err error)

func DPrintfRPC

func DPrintfRPC(format string, a ...interface{}) (n int, err error)

Types

type Instance

type Instance struct {
	HighestAcN  int         // Na: highest accepted proposal
	HighestAcV  interface{} // Va: value
	HighestSeen int         // Np: highest seen proposal number
	Decided     bool
	DecidedV    interface{}
}

type Paxos

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

func Make

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

Make the application wants to create a paxos peer. the ports of all the paxos peers (including this one) are in peers[]. this servers port is peers[me].

func (*Paxos) Done

func (px *Paxos) Done(seq int)

Done Called by the application when the application on this machine is done with all instances <= seq. see the comments for Min() for more explanation.

func (*Paxos) Kill

func (px *Paxos) Kill()

Kill tell the peer to shut itself down. for testing. please do not change this function.

func (*Paxos) Max

func (px *Paxos) Max() int

Max the application wants to know the highest instance sequence known to this peer.

func (*Paxos) Min

func (px *Paxos) Min() int

Min should return one more than the minimum among z_i, where z_i is the highest number ever passed to Done() on peer i. A peers z_i is -1 if it has never called Done().

Paxos is required to have forgotten all information about any instances it knows that are < Min(). The point is to free up memory in long-running Paxos-based servers.

Paxos peers need to exchange their highest Done() arguments in order to implement 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.

The fact that Min() is defined as a minimum over *all* Paxos peers means that Min() cannot increase until all peers have been heard from. So if a peer is dead or unreachable, other peers Min()s will not increase even if all reachable peers call Done. The reason for this is that when the unreachable peer comes back to life, it will need to catch up on instances that it missed -- the other peers therefore cannot forget these instances.

func (*Paxos) RPCAccept

func (px *Paxos) RPCAccept(args *RPCAcceptArgs, reply *RPCAcceptReply) error

RPCAccept This function handles paxos accept request There are two scenarios: 1st: Argument N >= The Highest Scene N for sequence number "seq". 2nd: Argument N < The Highest Scene N for sequence number "seq".

func (*Paxos) RPCDecide

func (px *Paxos) RPCDecide(args *RPCDecideArgs, reply *RPCDecideReply) error

RPCDecide This function handles paxos decide request As we are not considering byzantine nodes. We mark a sequence number as decided if the peer request says so.

func (*Paxos) RPCPrepare

func (px *Paxos) RPCPrepare(args *RPCPrepareArgs, reply *RPCPrepareReply) error

RPCPrepare This function handles paxos prepare request There are two scenarios: 1st: Argument N > The Highest Scene N for sequence number "seq". 2nd: Argument N <= The Highest Scene N for sequence number "seq".

func (*Paxos) Start

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

Start the application wants paxos to start agreement on instance seq, with proposed value v. Start() returns right away; the application will call Status() to find out if/when agreement is reached.

func (*Paxos) Status

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

Status the application wants to know whether this peer thinks an instance has been decided, and if so what the agreed value is. Status() should just inspect the local peer state; it should not contact other Paxos peers.

type RPCAcceptArgs

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

type RPCAcceptReply

type RPCAcceptReply struct {
	OK bool
	N  int
}

type RPCDecideArgs

type RPCDecideArgs struct {
	Seq int
	V   interface{}
}

type RPCDecideReply

type RPCDecideReply struct {
	OK bool
}

type RPCPrepareArgs

type RPCPrepareArgs struct {
	Seq    int
	N      int
	Sender int
	Done   int
}

RPCPrepareArgs we exchange Done only in Prepare (but both in args and reply).

type RPCPrepareReply

type RPCPrepareReply struct {
	OK   bool
	Na   int
	Va   interface{}
	Done int
}