paxos

package
v0.0.0-...-9789875 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 10, 2021 License: MIT Imports: 11 Imported by: 0

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.