Paxos protocol framework
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
abd rename Nov 14, 2018
bin rename Nov 14, 2018
blockchain multicast to quorum Oct 5, 2018
client binary Uvarint Apr 21, 2018
cmd binary Uvarint Apr 21, 2018
dynamo read from any replica May 19, 2018
epaxos fix test Oct 15, 2018
kpaxos global config + transport codec Feb 16, 2018
lib dynamo + hash ring Feb 23, 2018
log add description Oct 15, 2018
master fix build Apr 21, 2018
model renew model Oct 17, 2018
paxos multicast to quorum Oct 5, 2018
paxos_group multicast to quorum Oct 5, 2018
ppaxos forward in same thread Mar 26, 2018
server rename Nov 14, 2018
tla full package name etc. Dec 8, 2017
vpaxos multicast to quorum Oct 5, 2018
wankeeper multicast to quorum Oct 5, 2018
wpaxos fast read May 28, 2018
.gitignore local branch Oct 22, 2018
.travis.yml fix go version Apr 21, 2018
LICENSE socket + REST client Nov 8, 2017
README.md update Apr 22, 2018
ballot.go epaxos needs fix Feb 16, 2018
ballot_test.go linear checker Jan 15, 2018
benchmark.go update Apr 22, 2018
checker.go rename Nov 14, 2018
checker_test.go optimise encoding Feb 20, 2018
client.go rename Nov 14, 2018
codec.go fast read May 28, 2018
codec_test.go optimise encoding Feb 20, 2018
config.go rename Nov 14, 2018
db.go remove todo Mar 15, 2018
history.go rename Nov 14, 2018
http.go partition nemesis Apr 9, 2018
http_test.go fix test Oct 15, 2018
id.go optimize Mar 16, 2018
init.go increase http connection Mar 16, 2018
message.go fix Apr 26, 2018
node.go node level fast read Oct 21, 2018
operation.go partition nemesis Apr 9, 2018
policy.go add description Oct 15, 2018
policy_test.go update May 13, 2018
quorum.go add description Oct 15, 2018
rate.go rate limit in total for all workers Mar 14, 2018
rate_test.go limit key generation not client Mar 15, 2018
socket.go multicast to quorum Oct 5, 2018
socket_test.go fix test Oct 15, 2018
stat.go add description Oct 15, 2018
state_machine.go global config + transport codec Feb 16, 2018
transport.go fast read May 28, 2018
transport_test.go non blocking Feb 24, 2018
util.go dynamo + hash ring Feb 23, 2018

README.md

GoDoc Go Report Card Build Status

What is Paxi?

Paxi is the framework that implements WPaxos and other Paxos protocol variants. Paxi provides most of the elements that any Paxos implementation or replication protocol needs, including network communication, state machine of a key-value store, client API and multiple types of quorum systems.

Warning: Paxi project is still under heavy development, with more features and protocols to include. Paxi API may change too.

What is WPaxos?

WPaxos is a multileader Paxos protocol that provides low-latency and high-throughput consensus across wide-area network (WAN) deployments. Unlike statically partitioned multiple Paxos deployments, WPaxos perpetually adapts to the changing access locality through object stealing. Multiple concurrent leaders coinciding in different zones steal ownership of objects from each other using phase-1 of Paxos, and then use phase-2 to commit update-requests on these objects locally until they are stolen by other leaders. To achieve fast phase-2 commits, WPaxos adopts the flexible quorums idea in a novel manner, and appoints phase-2 acceptors to be close to their respective leaders.

WPaxos (WAN Paxos) paper (first version) can be found in https://arxiv.org/abs/1703.08905.

What is included?

Algorithms:

Features:

  • Benchmarking
  • Linerizability checker
  • Fault injection
  • Transactions
  • Dynamic quorums

How to build

  1. Install Go 1.10.
  2. Use go get command or Download Paxi source code from GitHub page.
go get github.com/ailidani/paxi
  1. Compile everything from paxi/bin folder.
cd github.com/ailidani/paxi/bin
./build.sh

After compile, Golang will generate 3 executable files under bin folder.

  • server is one replica instance.
  • client is a simple benchmark that generates read/write reqeust to servers.
  • cmd is a command line tool to test Get/Set requests.

How to run

Each executable file expects some parameters which can be seen by -help flag, e.g. ./server -help.

  1. Generate the configuration file according to the example, then start server with -config FILE_PATH option, default to "config.json" when omit.

  2. Start 6 servers with different ids in format of "ZONE_ID.NODE_ID".

./server -id 1.1 &
./server -id 1.2 &
./server -id 2.1 &
./server -id 2.2 &
./server -id 3.1 &
./server -id 3.2 &
  1. Start benchmarking client that connects to server ID 1.1 and benchmark parameters specified in config.json.
./client -id 1.1 -bconfig benchmark.json

When flag id is absent, client will randomly select any server for each operation.

The algorithms can also be running in simulation mode, where all nodes are running in one process and transport layer is replaced by Go channels. Check simulation.sh script on how to run.

How to implement algorithms in Paxi

Replication algorithm in Paxi follows the message passing model, where several message types and their handle function are registered. We use Paxos as an example for our step-by-step tutorial.

  1. Define messages, register with gob in init() function if using gob codec. As show in msg.go.

  2. Define a Replica structure embeded with paxi.Node interface.

type Replica struct {
	paxi.Node
	*Paxos
}

Define handle function for each message type. For example, to handle client Request

func (r *Replica) handleRequest(m paxi.Request) {
	if r.Config().Adaptive {
		if r.Paxos.IsLeader() || r.Paxos.Ballot() == 0 {
			r.Paxos.HandleRequest(m)
		} else {
			go r.Forward(r.Paxos.Leader(), m)
		}
	} else {
		r.Paxos.HandleRequest(m)
	}

}
  1. Register the messages with their handle function using Node.Register(interface{}, func()) interface in Replica constructor.

Replica use Send(to ID, msg interface{}), Broadcast(msg interface{}) functions in Node.Socket to send messages.

For data-store related functions check db.go file.

For quorum types check quorum.go file.

Client uses a simple RESTful API to submit requests. GET method with URL "http://ip:port/key" will read the value of given key. POST method with URL "http://ip:port/key" and body as the value, will write the value to key.