Golang implements the Paxos distributed consensus algorithm

Understanding Paxos contains only pseudocode, which is helpful but not fun. Now that everyone is paying attention to Talk is cheap. Show me the code. This time, I will use the Go language to realize the pseudo-code in the article, hoping to help friends feel the details in the Paxos paper more intuitively.

But we need to simplify the algorithm a little bit. How simple is it? We do not persist any variables and use CHAN directly instead of RPC calls.

Code address: github.com/tangwz/paxo…

Remember to switch to the Naive branch.

Define related structures

We define a Proposer as follows:

type proposer struct {
	// server id
	id int
	// the largest round number the server has seen
	round int
	// proposal number = (round number, serverID)
	number int
	// proposal value
	value     string
	acceptors map[int]bool
	net       network
}
Copy the code

The members of these structures are easy to understand. Acceptors are used primarily to store the addresses of acceptors and to record the success/failure responses we receive from acceptors.

Acceptor constructs:

type acceptor struct {
	// server id
	id int
	// the number of the proposal this server will accept, or 0 if it has never received a Prepare request
	promiseNumber int
	// the number of the last proposal the server has accepted, or 0 if it never accepted any.
	acceptedNumber int
	// the value from the most recent proposal the server has accepted, or null if it has never accepted a proposal
	acceptedValue string

	learners []int
	net      network
}
Copy the code

There are notes for the main members’ explanations. In short, we need to record three pieces of information:

• promiseNumber: Proposal number of the commitment
• acceptedNumber: Number of the proposal accepted
• acceptedValue: Accepted proposal value

Define the message structure

The message structure defines the protocol between proposers and acceptors and between acceptors and leaners. The most important is the Paxos two-phase four messages.

• Phase 1 Request: Proposal number
• Phase 1 response: If any proposal was Accepted, the proposal number and proposal value are returned
• Phase 2 Request: Proposal number and proposal value
• Phase 2 response: Accepted proposal number and proposal value

In this way, all our message structure needs is the proposal number and proposal value, plus a message type that distinguishes the phase of the message. The message structure is defined in message.go as follows:

// MsgType represents the type of a paxos phase.
type MsgType uint8

const (
	Prepare MsgType = iota
	Promise
	Propose
	Accept
)

type message struct {
	tp     MsgType
	from   int
	to     int
	number int    // proposal number
	value  string // proposal value
}
Copy the code

The network

There are many choices and optimizations you can make on the network, but for simplicity’s sake, let’s define the network as an interface. This can be done with RPC or API (yes, I’ve already implemented a version of Go RPC).

type network interface {
	send(m message)
	recv(timeout time.Duration) (message, bool)}Copy the code

Next, we will implement the network interface:

type Network struct {
	queue map[int]chan message
}

func newNetwork(nodes ...int) *Network {
	pn := &Network{
		queue: make(map[int]chan message, 0),}for _, a := range nodes {
		pn.queue[a] = make(chan message, 1024)}return pn
}

func (net *Network) send(m message) {
	log.Printf("net: send %+v", m)
	net.queue[m.to] <- m
}

func (net *Network) recvFrom(from int, timeout time.Duration) (message, bool) {
	select {
	case m := <-net.queue[from]:
		log.Printf("net: recv %+v", m)
		return m, true
	case <-time.After(timeout):
		return message{}, false}}Copy the code

Queue is used to record the chan of each node, and key is the server ID of the node.

Sending a Message sends the Message to the CHAN of the target node. Receiving the Message reads the data directly from the CHAN and waits for the corresponding timeout.

You don’t have to do anything else with network addresses and packages, so it’s pretty simple. The details are in the network.go file.

Implementing unit tests

In this project, go unit tests were mainly used to verify correctness. We mainly tested two scenarios:

• TestSingleProposer (single Proposer)
• TestTwoProposers (a number of proposers)

The test code checks that the proposal value returned by Chosen meets expectations by running Paxos.

Implementation algorithm flow

The files are numbered numbered numbered numbered. Go, acceptor. Go, and learner.

It is easy to implement Phases 1 and 2 as described in pseudocode, treating each Phase’s request response as a function, as we walk through it step by step.

First round Prepare RPCs request phase:

// Phase 1. (a) A proposer selects a proposal number n
// and sends a prepare request with number n to a majority of acceptors.
func (p *proposer) prepare(a) []message {
	p.round++
	p.number = p.proposalNumber()
	msg := make([]message, p.majority())
	i := 0

	for to := range p.acceptors {
		msg[i] = message{
			tp:     Prepare,
			from:   p.id,
			to:     to,
			number: p.number,
		}
		i++
		if i == p.majority() {
			break}}return msg
}

// proposal number = (round number, serverID)
func (p *proposer) proposalNumber(a) int {
	return p.round<< 16 | p.id
}
Copy the code

In the Prepare request phase we send round+1 and send it to the majority Acceptors.

Note: Many blogs and tutorials here send the Prepare RPC to all Acceptors. The 6.824 PAXOS experiment sent the RPC to all Acceptors. To a majority of acceptors.

The first round of Prepare RPCs response stage:

Next process the request in the acceptor.go file:

func (a *acceptor) handlePrepare(args message) (message, bool) {
	if a.promiseNumber >= args.number {
		return message{}, false
	}
	a.promiseNumber = args.number
	msg := message{
		tp:     Promise,
		from:   a.id,
		to:     args.from,
		number: a.acceptedNumber,
		value:  a.acceptedValue,
	}
	return msg, true
}
Copy the code

• ifargs.numberIs greater thanacceptor.promiseNumber, promises not to receive numbers less than or equal toargs.numberThe proposal (i.ea.promiseNumber = args.number). The response should also contain a.aceptedNumber and A.aceptedValue if a previous proposal was Accepted.
• Otherwise ignore and returnfalse.

Second Round Accept RPCs request stage:

func (p *proposer) accept(a) []message {
	msg := make([]message, p.majority())
	i := 0
	for to, ok := range p.acceptors {
		if ok {
			msg[i] = message{
				tp:     Propose,
				from:   p.id,
				to:     to,
				number: p.number,
				value:  p.value,
			}
			i++
		}

		if i == p.majority() {
			break}}return msg
}
Copy the code

When a Proposer receives a response with a majority of acceptors, it sends a request to those acceptors with a proposal number and proposal value.

The second round of Accept RPCs response stage:

func (a *acceptor) handleAccept(args message) bool {
	number := args.number
	if number >= a.promiseNumber {
		a.acceptedNumber = number
		a.acceptedValue = args.value
		a.promiseNumber = number
		return true
	}

	return false
}
Copy the code

An Acceptor receives an Accept() request, and if an Acceptor does not Promise another Acceptor number larger than a.plomenumber during this period, it accepts the proposal.

Remember: Learning a Chosen Value!!

There’s a very confusing concept in Paxos: Chosen Value and Accepted Value, but if you’ve seen the paper, it’s pretty straightforward. Section 2.3 of the paper begins with Learning a Chosen Value:

To learn that a value has been chosen, a learner must find out that a proposal has been accepted by a majority of acceptors.

So an Acceptor will broadcast the Accepted proposal to Leaners. Once a Leaners receives more than half of the Acceptors’ Accepted proposals, we know that the proposal is Chosen.

func (l *learner) chosen(a) (message, bool) {
	acceptCounts := make(map[int]int)
	acceptMsg := make(map[int]message)

	for _, accepted := range l.acceptors {
		ifaccepted.number ! =0 {
			acceptCounts[accepted.number]++
			acceptMsg[accepted.number] = accepted
		}
	}

	for n, count := range acceptCounts {
		if count >= l.majority() {
			return acceptMsg[n], true}}return message{}, false
}
Copy the code

Run and test

After the code is pulled down, run directly:

go test
Copy the code

Write in the back

Why not use MIT 6.824 course code?

Before, I pushed the answer Raft of MIT 6.824 to my Github, but when the course started in 2020, the TEACHING assistant of MIT sent me an email asking me to make my code private, because this would lead to the students of the course to directly search the code, and the homework could not be completed independently.

Indeed, experiment is the most indispensable part of computer. Using PAxOS code of MIT 6.824 2015 will lead many learners to search the code directly on the Internet instead of solving difficulties by themselves, which will lead to poor learning effect and violate the original intention of MIT.

Of course, you can also say that various codes for 6.824 are easy to find on the Internet, but DUE to the previous email from MIT ta, I will not send out the assignment code directly.

Interested students can go to the 2015 version of the study: nil.csail.mit.edu/6.824/2015/

Future plans

• Implement a complete Paxos (including network and storage)
• Based on Paxos to achieve a Paxos KV storage
• Implement other Paxos variants

Welcome friends urge more……

conclusion

This code is on Github, if there is anything missing or wrong in this article, or any new ideas from friends, welcome to issue discussion.

Recommended reading

• Understand Paxos (including pseudocode)

• Paxos variants 1: How did multi-Paxos convince people to choose Raft

• Paxos by Raft. What score would you get?