komuw/kshaka

Kshaka is a Go implementation of the CASPaxos consensus protocol.

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

kshaka's Issues

better way to handle error `not found` from StableStore

• Most implementations[1][2] of raft StableStore interface; when you do a get for a key and the value returned happens to be a nil []byte, then they return an error.
• Since we are using StableStore interface to persist (ballots and state), we need to check if the state exists(ie do a get). But instead of throwing an error if state is nil []byte, we need to 'catch' it and set it to nil.

state, err := a.acceptorStore.Get(key)
if err != nil && err.Error() == "not found" {
    state, err = nil, nil
}
if err != nil {
    return acceptorState{}, errors.Wrap(err, fmt.Sprintf("unable to get state for key:%v from acceptor:%v", key, a.ID))
}

• it looks hideous and should be replaced with something better.

ref:

1. https://github.com/hashicorp/raft-boltdb/blob/6e5ba93211eaf8d9a2ad7e41ffad8c6f160f9fe3/bolt_store.go#L243-L245
2. https://github.com/hashicorp/raft-mdb/blob/55f29473b9e604b3678b93a8433a6cf089e70f76/mdb_store.go#L328-L329

add fuzzing

how to use

i want to use this package for my use case:
i'm try to write key/val storage that uses ceph crushmap to determine on which nodes data placed and do data replication.
i need to know when node down to disable it in crushmap., so i think about caspaxos to solve this issue by replicate node state to all cluster members. Also i need to transfer new crushmap (if i add or delete node) to all nodes consistently.
What do you think?

plans for this package

Hi! great to see caspaxos implementation, i don't know why https://github.com/peterbourgon/caspaxos archived, so you implementation is only one that exists. Can you provide info what needs to be done, and what is the state of this package?

maybe use hashicorp/raft transport interface ?

https://github.com/hashicorp/raft/blob/master/transport.go

fix gometalinter in ci

gometalinter ain't running in circleCI, fix it.

invalid