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
- type InmemTransport
- type 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
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func MingleNodes ¶
func MingleNodes(nodes ...*Node)
MingleNodes lets each node know about the other, including itself.
Types ¶
type AcceptorState ¶
AcceptorState is the state that is maintained by an acceptor/node
type Ballot ¶
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 ¶
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.
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 (*Node) Accept ¶
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 ¶
AddMetadata adds metadata to a node. eg name=myNode, env=production
func (*Node) AddTransport ¶
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
Source Files ¶
Directories ¶
Path | Synopsis |
---|---|
examples
|
|
Package httpTransport provides a sample implementation of kshaka's transport interface This implementation uses net/http to communicate between different kshaka Nodes.
|
Package httpTransport provides a sample implementation of kshaka's transport interface This implementation uses net/http to communicate between different kshaka Nodes. |