kshaka

README

Kshaka

Kshaka is a Go implementation of the CASPaxos consensus protocol.
It's name is derived from the Kenyan hip hop group, Kalamashaka.

CASPaxos is a replicated state machine (RSM) kshaka. Unlike Raft and Multi-Paxos, it doesn’t use leader election and log replication, thus avoiding associated complexity.
Its symmetric peer-to-peer approach achieves optimal commit latency in wide-area networks and doesn’t cause transient unavailability when any [N−1] of N nodes crash." - The CASPaxos whitepaper

This is work in progress, do not use it anywhere you would regret. API will change over time.

Installation

• todo

Usage

package main

import (
	"fmt"

	"github.com/hashicorp/raft-boltdb"
	"github.com/komuw/kshaka"
)

func main() {
	// The store should, ideally be disk persisted.
	// Any that implements hashicorp/raft StableStore interface will suffice
	boltStore, err := raftboltdb.NewBoltStore("/tmp/bolt.db")
	if err != nil {
		panic(err)
	}

	// The function that will be applied by CASPaxos.
	// This will be applied to the current value stored
	// under the key passed into the Propose method of the proposer.
	var setFunc = func(val []byte) kshaka.ChangeFunction {
		return func(current []byte) ([]byte, error) {
			return val, nil
		}
	}

	// Note that, in practice, nodes ideally should be
	// in different machines each with its own store.
	node1 := kshaka.NewNode(1, boltStore)
	node2 := kshaka.NewNode(2, boltStore)
	node3 := kshaka.NewNode(3, boltStore)

	transport1 := &kshaka.InmemTransport{Node: node1}
	transport2 := &kshaka.InmemTransport{Node: node2}
	transport3 := &kshaka.InmemTransport{Node: node3}
	node1.AddTransport(transport1)
	node2.AddTransport(transport2)
	node3.AddTransport(transport3)

	kshaka.MingleNodes(node1, node2, node3)

	key := []byte("name")
	val := []byte("Masta-Ace")

	// make a proposition; consensus via CASPaxos will happen
	newstate, err := node2.Propose(key, setFunc(val))
	if err != nil {
		fmt.Printf("err: %v", err)
	}
	fmt.Printf("\n newstate: %v \n", newstate)
}

System design

1. Intro:

• Clients initiate a request by communicating with a proposer; clients may be stateless, the system may have arbitrary numbers of clients.

• Proposers perform the initialization by communicating with acceptors. Proposers keep minimal state needed to generate unique increasing update IDs (Ballot numbers), the system may have arbitrary numbers of proposers.

• Acceptors store the accepted value; the system should have 2F+1 acceptors to tolerate F failures.

• It’s convenient to use tuples as Ballot numbers. To generate it a proposer combines its numerical ID with a local increasing counter: (counter, ID). To compare Ballot tuples, we should compare the first component of the tuples and use ID only as a tiebreaker.

• When a proposer receives a conflicting message from an acceptor, it should fast-forward its counter to avoid a conflict in the future. If an acceptor returns a conflict if it already saw a greater Ballot number during the prepare message, does the Proposer retry with a higher Ballot number or does it just stop? Ans: It doesn't matter from the protocol's point of view and different implementations may implement it in different ways. - https://twitter.com/rystsov/status/971797758284677120
  Proposers in Kshaka will, for the time been, will not retry after conflicts.

• Clients change its value by submitting side-effect free functions which take the current state as an argument and yield new as a result. Out of the concurrent requests only one can succeed; we should acquire a lock:: https://github.com/gryadka/js/blob/dfc6ed6f7580c895a9db44d06756a3dd637e47f6/core/src/Proposer.js#L47-L48

2. Algo:

A. Prepare phase

• A client submits the f change function to a proposer.
• The proposer generates a Ballot number, B, and sends ”prepare” messages containing that number(and it's ID) to the acceptors.
• Acceptor returns a conflict if it already saw a greater Ballot number, it also submits the Ballot and accepted value it has. Persists the Ballot number as a promise and returns a confirmation either with an empty value (if it hasn’t accepted any value yet) or with a tuple of an accepted value and its Ballot number.
• Proposer waits for the F + 1 confirmations.

B. Accept phase

• If they(prepare replies from acceptors) all contain the empty value, then the proposer defines the current state as ∅ otherwise it picks the value of the tuple with the highest Ballot number.
• Proposer applies the f function to the current state and sends the result, new state, along with the generated Ballot number B (an ”accept” message) to the acceptors.
• Accept returns a conflict if it already saw a greater Ballot number, it also submits the Ballot and accepted value it has. Erases the promise, marks the received tuple (Ballot number, value) as the accepted value and returns a confirmation

C. End

• Proposer waits for the F + 1 confirmations.
• Proposer returns the new state to the client.

3. Cluster membership change

• todo

4. Deleting record/s

• todo

5. Optimizations

• todo

dev

debug one test;

dlv test -- -test.v -test.run ^Test_proposer_Propose

Documentation

Overview

Package kshaka is a pure Go implementation of the CASPaxos consensus protocol. It's name is derived from the Kenyan hip hop group, Kalamashaka.

"CASPaxos is a replicated state machine (RSM) kshaka. Unlike Raft and Multi-Paxos, it doesn't use leader election and log replication, thus avoiding associated complexity. Its symmetric peer-to-peer approach achieves optimal commit latency in wide-area networks and doesn't cause transient unavailability when any [N−1] of N nodes crash." - The CASPaxos whitepaper, https://github.com/rystsov/caspaxos/blob/master/latex/caspaxos.pdf

Example usage:

package main

import (
	"fmt"

	"github.com/hashicorp/raft-boltdb"
	"github.com/komuw/kshaka"
)

func main() {
	// The store should, ideally be disk persisted.
	// Any that implements hashicorp/raft StableStore interface will suffice
	boltStore, err := raftboltdb.NewBoltStore("/tmp/bolt.db")
	if err != nil {
		panic(err)
	}

	// The function that will be applied by CASPaxos.
	// This will be applied to the current value stored
	// under the key passed into the Propose method of the proposer.
	var setFunc = func(val []byte) kshaka.ChangeFunction {
		return func(current []byte) ([]byte, error) {
			return val, nil
		}
	}

	// Note that, in practice, nodes ideally should be
	// in different machines each with its own store.
	node1 := kshaka.NewNode(1, boltStore)
	node2 := kshaka.NewNode(2, boltStore)
	node3 := kshaka.NewNode(3, boltStore)

	transport1 := &kshaka.InmemTransport{Node: node1}
	transport2 := &kshaka.InmemTransport{Node: node2}
	transport3 := &kshaka.InmemTransport{Node: node3}
	node1.AddTransport(transport1)
	node2.AddTransport(transport2)
	node3.AddTransport(transport3)

	kshaka.MingleNodes(node1, node2, node3)

	key := []byte("name")
	val := []byte("Masta-Ace")

	// make a proposition; consensus via CASPaxos will happen
	newstate, err := node2.Propose(key, setFunc(val))
	if err != nil {
		fmt.Printf("err: %v", err)
	}
	fmt.Printf("\n newstate: %v \n", newstate)
}

TODO: add system design here.

Index

• func MingleNodes(nodes ...*Node)
• type AcceptorState
• type Ballot
• type ChangeFunction
• type InmemStore
  • func (i *InmemStore) Get(key []byte) ([]byte, error)
  • func (i *InmemStore) GetUint64(key []byte) (uint64, error)
  • func (i *InmemStore) Set(key []byte, val []byte) error
  • func (i *InmemStore) SetUint64(key []byte, val uint64) error
• type InmemTransport
  • func (it *InmemTransport) TransportAccept(b Ballot, key []byte, state []byte) (AcceptorState, error)
  • func (it *InmemTransport) TransportPrepare(b Ballot, key []byte) (AcceptorState, error)
• type Node
  • func NewNode(ID uint64, store StableStore) *Node
  • func (n *Node) Accept(b Ballot, key []byte, newState []byte) (AcceptorState, error)
  • func (n *Node) AddMetadata(metadata map[string]string)
  • func (n *Node) AddTransport(t Transport)
  • func (n *Node) Prepare(b Ballot, key []byte) (AcceptorState, error)
  • func (n *Node) Propose(key []byte, changeFunc ChangeFunction) ([]byte, error)
• type ProposerAcceptor
• type StableStore
• type Transport

Functions

func MingleNodes

func MingleNodes(nodes ...*Node)

MingleNodes lets each node know about the other, including itself.

Types

type AcceptorState

type AcceptorState struct {
	PromisedBallot Ballot
	AcceptedBallot Ballot
	State          []byte
}

AcceptorState is the state that is maintained by an acceptor/node

type Ballot

type Ballot struct {
	Counter uint64
	NodeID  uint64
}

Ballot is unique increasing updateID It’s convenient to use tuples as Ballot numbers. To generate it a proposer combines its numerical ID with a local increasing counter: (counter, ID). To compare Ballot tuples, we should compare the first component of the tuples and use ID only as a tiebreaker.

type ChangeFunction

type ChangeFunction func(currentState []byte) ([]byte, error)

ChangeFunction is the function that clients send to proposers. The function takes the current state as an argument and yields the new value(state) as a result.

An example ChangeFunction is given below:

var readFunc ChangeFunction = func(current []byte) ([]byte, error) {
	return current, nil
}

A client can send the above change function to a proposer, when the client wants to read the value stored at a key named foo. The proposer will apply that function to the current state(ie to the current value stored at key foo) and return the new value stored at that key and an error.

type InmemStore

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

InmemStore implements the StableStore interface. It should NEVER be used for production. It is used only for unit tests. Use the github.com/hashicorp/raft-mdb implementation instead. This InmemStore is based on the one defined in hashicorp/raft; with the difference been that this only satisfies the StableStore interface whereas the hashicorp/raft one also satisfies the LogStore interface. However CASPaxos(and kshaka by extension) unlike Raft and Multi-Paxos doesn’t use log replication.

func (*InmemStore) Get

func (i *InmemStore) Get(key []byte) ([]byte, error)

Get implements the StableStore interface.

func (*InmemStore) GetUint64

func (i *InmemStore) GetUint64(key []byte) (uint64, error)

GetUint64 implements the StableStore interface.

func (*InmemStore) Set

func (i *InmemStore) Set(key []byte, val []byte) error

Set implements the StableStore interface.

func (*InmemStore) SetUint64

func (i *InmemStore) SetUint64(key []byte, val uint64) error

SetUint64 implements the StableStore interface.

type InmemTransport

type InmemTransport struct {
	Node *Node
}

InmemTransport Implements the Transport interface, to allow kshaka/CASPaxos to be tested in-memory without going over a network.

func (*InmemTransport) TransportAccept

func (it *InmemTransport) TransportAccept(b Ballot, key []byte, state []byte) (AcceptorState, error)

TransportAccept implements the Transport interface.

func (*InmemTransport) TransportPrepare

func (it *InmemTransport) TransportPrepare(b Ballot, key []byte) (AcceptorState, error)

TransportPrepare implements the Transport interface.

type Node

type Node struct {
	// ID should be unique to each node in the cluster.
	ID       uint64
	Metadata map[string]string
	Ballot   Ballot

	// In general the "prepare" and "accept" operations affecting the same key should be mutually exclusive.
	// How to achieve this is an implementation detail.
	// eg in Gryadka it doesn't matter because the operations are implemented as Redis's stored procedures and Redis is single threaded. - Denis Rystsov
	// the mux protects the state(acceptorStore)
	sync.Mutex

	Trans Transport
	// contains filtered or unexported fields
}

Node satisfies the ProposerAcceptor interface. A Node is both a proposer and an acceptor. Most people will be interacting with a Node instead of a Proposer/Acceptor. note: the fields; acceptorStore, Trans and nodes should not be nil/default values

func NewNode

func NewNode(ID uint64, store StableStore) *Node

NewNode creates a new node.

func (*Node) Accept

func (n *Node) Accept(b Ballot, key []byte, newState []byte) (AcceptorState, error)

Accept handles the accept phase for an acceptor(node). An Acceptor returns a conflict if it already saw a greater Ballot number, it also submits the Ballot and accepted value it has. Erases the promise, marks the received tuple (Ballot number, value) as the accepted value and returns a confirmation

func (*Node) AddMetadata

func (n *Node) AddMetadata(metadata map[string]string)

AddMetadata adds metadata to a node. eg name=myNode, env=production

func (*Node) AddTransport

func (n *Node) AddTransport(t Transport)

AddTransport adds transport to a node.

func (*Node) Prepare

func (n *Node) Prepare(b Ballot, key []byte) (AcceptorState, error)

Prepare handles the prepare phase for an acceptor(node). An Acceptor returns a conflict if it already saw a greater Ballot number, it also submits the Ballot and accepted value it has. Persists the Ballot number as a promise and returns a confirmation either with an empty value (if it hasn’t accepted any value yet) or with a tuple of an accepted value and its Ballot number.

func (*Node) Propose

func (n *Node) Propose(key []byte, changeFunc ChangeFunction) ([]byte, error)

Propose is the method that clients call when they want to submit the f change function to a proposer. It takes the key whose value you want to apply the ChangeFunction to and also the ChangeFunction that will be applied to the value(contents) of that key.

type ProposerAcceptor

type ProposerAcceptor interface {
	Propose(key []byte, changeFunc ChangeFunction) ([]byte, error)
	AddTransport(t Transport)
	// contains filtered or unexported methods
}

ProposerAcceptor is an entity that is both a proposer and an acceptor.

type StableStore

type StableStore interface {
	Set(key []byte, val []byte) error
	// Get returns the value for key, or an empty byte slice if key was not found.
	Get(key []byte) ([]byte, error)
	SetUint64(key []byte, val uint64) error
	// GetUint64 returns the uint64 value for key, or 0 if key was not found.
	GetUint64(key []byte) (uint64, error)
}

StableStore is used to provide stable storage of key configurations to ensure safety. This interface is the same as the one defined in hashicorp/raft

type Transport

type Transport interface {
	TransportPrepare(b Ballot, key []byte) (AcceptorState, error)
	TransportAccept(b Ballot, key []byte, state []byte) (AcceptorState, error)
}

Transport provides an interface for network transports to allow kshaka/CASPaxos to communicate with other nodes. An example is github.com/komuw/kshaka/httpTransport