toystore

README

toystore

Toystore is an implementation of the Dynamo distributed database, which relies on an adapted SWIM gossip protocol to keep track of cluster membership.

Full API documentation

Differences from the paper

The purpose of this project was primarily educational so we took some short cuts where it made sense.

Data Versioning

Dynamo uses vector clocks to handle data conflicts between nodes. This has the advantage of allowing the client to decide how to merge these conflicts in the case of a partition, but we opted for the more straight-forward last-write-wins approach. This has drawbacks, but because we're testing with simple key/value pairs rather than updating fields within encoded data we decided it was good enough.

Permanent Failures

Dynamo classifies two types of failures: transient and permanent. Transisent failures are the most common and can be cause by network partitions, node crashes, and slow running processes. We're handling these temporary failures using the hinted handoff approach described in the paper. However, Dynamo handles failures that have persisted for a longer time (e.g. more than 24 hours) differently by removing them from the cluster and rebalancing the key range. We decided not to implement this for now.

Virtual Nodes

Dynamo has the concept of virtual nodes, which allow a single physical host to store multiple key ranges. This has two benefits: spread the nodes over the hash ring more effectively and allow for non-homogenous hosts (e.g. some servers can store more keys than others). As we're testing this locally and therefor don't have different hardware to consider we decided to not implement this feature.

Setup

We assume you have loopback addresses on 127.0.0.2:127.0.0.24. If you're running OSX this won't be the case so you'll need add these addresses or use a VM.

Run the server

We've provided an example app in the examples directory. Run it with:

$ # Start the seed node
$ go run examples/http.go 127.0.0.2
$ # Start other nodes
$ go run examples/http.go 127.0.0.{n}

Testing

$ go test

Note: we're not cleaning up properly between integration tests yet, so they need to be run individually. E.g.:

$ go test -run Partitions

Admin

If you prefer to use a browser based tool you can run an example admin interface using rlayte/toystore-admin

Documentation

Overview

Package toystore is a simple implementation of a Dynamo database - http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

For more information see the project's readme - https://github.com/rlayte/toystore

Index

• type Config
• type GetArgs
• type GetReply
• type HintArgs
• type HintReply
• type HintedHandoff
  • func NewHintedHandoff(config Config, client Transferrer) *HintedHandoff
  • func (h *HintedHandoff) Put(value *data.Data, hint string)
• type Member
• type Memberlist
  • func NewMemberlist(t *Toystore, seed string) *Memberlist
  • func (m *Memberlist) Join(seed string)
  • func (m *Memberlist) Len() int
  • func (m *Memberlist) Members() []Member
  • func (m *Memberlist) Setup(t *Toystore)
• type MemberlistEvents
  • func (m *MemberlistEvents) NotifyJoin(node *memberlist.Node)
  • func (m *MemberlistEvents) NotifyLeave(node *memberlist.Node)
  • func (m *MemberlistEvents) NotifyUpdate(node *memberlist.Node)
• type MemberlistNode
  • func (m *MemberlistNode) Address() string
  • func (m *MemberlistNode) Meta() []byte
  • func (m *MemberlistNode) Name() string
• type Members
• type PeerClient
• type PeerHandler
• type PutArgs
• type PutReply
• type RpcClient
  • func NewRpcClient() *RpcClient
  • func (r *RpcClient) CoordinateGet(address string, key string) (*data.Data, bool)
  • func (r *RpcClient) CoordinatePut(address string, value *data.Data) bool
  • func (r *RpcClient) Get(address string, key string) (*data.Data, bool)
  • func (r *RpcClient) HintPut(address string, hint string, data *data.Data) bool
  • func (r *RpcClient) Put(address string, value *data.Data) bool
  • func (r *RpcClient) Transfer(address string, data []*data.Data) bool
• type RpcHandler
  • func NewRpcHandler(store *Toystore) *RpcHandler
  • func (r *RpcHandler) CoordinateGet(args *GetArgs, reply *GetReply) error
  • func (r *RpcHandler) CoordinatePut(args *PutArgs, reply *PutReply) error
  • func (r *RpcHandler) Get(args *GetArgs, reply *GetReply) error
  • func (r *RpcHandler) HintPut(args *HintArgs, reply *HintReply) error
  • func (r *RpcHandler) Put(args *PutArgs, reply *PutReply) error
  • func (r *RpcHandler) Transfer(args *TransferArgs, reply *TransferReply) error
• type Toystore
  • func New(config Config) *Toystore
  • func (t *Toystore) AddMember(member Member)
  • func (t *Toystore) CoordinateGet(key string) (*data.Data, bool)
  • func (t *Toystore) CoordinatePut(value *data.Data) bool
  • func (t *Toystore) Get(key string) (interface{}, bool)
  • func (t *Toystore) GetString(key string) (string, bool)
  • func (t *Toystore) Merge(data *data.Data) bool
  • func (t *Toystore) Put(key string, value interface{}) (ok bool)
  • func (t *Toystore) RemoveMember(member Member)
  • func (t *Toystore) Transfer(address string)
• type TransferArgs
• type TransferReply
• type Transferrer

Types

type Config

type Config struct {
	// Number of nodes to store a key on.
	ReplicationLevel int

	// W is the number of times a key must be replicated for a Put operation
	// to be successful.
	W int

	// R is the number of nodes a key must be read from for a Get operation
	// to be successful.
	R int

	// RPCPort is the port Toystore will use for RPC between nodes.
	RPCPort int

	// GossipPort is the port Toystore will use for membership updates via
	// its gossip protocol.
	GossipPort int

	// Host is the ip Toystore will bind to.
	Host string

	// SeedAddress is a known Toystore node that used to initial join the
	// cluster.
	SeedAddress string

	// Store is an implementation of the Store interface the handles persisting
	// data.
	Store store.Store

	// HandoffInterval is the time between scans of the hinted handoff list.
	HandoffInterval time.Duration
}

Config defines the variables used for a Toystore node.

type GetArgs

type GetArgs struct {
	Key string
}

GetArgs is used to request data from other nodes.

type GetReply

type GetReply struct {
	Value *data.Data
	Ok    bool
}

GetReply is used to send data to other nodes.

type HintArgs

type HintArgs struct {
	Data *data.Data
	// Address where the data should be stored.
	Hint string
}

HintArgs is used to store hinted data temporarily on other nodes.

type HintReply

type HintReply struct {
	Ok bool
}

HintReply is used to return hint status to other nodes.

type HintedHandoff

type HintedHandoff struct {
	ScanInterval time.Duration
	// contains filtered or unexported fields
}

HintedHandoff keeps track of data that should be stored on other nodes. It periodically scans this data and attempts to transfer it to the correct node. It then removes any data that is transferred.

func NewHintedHandoff

func NewHintedHandoff(config Config, client Transferrer) *HintedHandoff

NewHintedHandoff returns a new instance and starts the scan process using the HandoffInterval defined in config.

func (*HintedHandoff) Put

func (h *HintedHandoff) Put(value *data.Data, hint string)

Put adds a new value for the hinted location.

type Member

type Member interface {
	Name() string
	Address() string
	Meta() []byte
}

Member interface represents an individual node in the cluster.

type Memberlist

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

Memberlist is an implementation of Members using hashicorp's memberlist.

func NewMemberlist

func NewMemberlist(t *Toystore, seed string) *Memberlist

NewMemberlist returns a new instance of Memberlist, sets up the gossip server, and attempts to join the seed node's cluster.

func (*Memberlist) Join

func (m *Memberlist) Join(seed string)

Join attempts to join the cluster that the seed node is a member of.

func (*Memberlist) Len

func (m *Memberlist) Len() int

Len returns the number of members in the cluster.

func (*Memberlist) Members

func (m *Memberlist) Members() []Member

Members return a list of all current members in the cluster.

func (*Memberlist) Setup

func (m *Memberlist) Setup(t *Toystore)

Setup creates a new instance of memberlist, assigns it to list, and sets the local nodes meta data as the rpc address.

type MemberlistEvents

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

MemberlistEvents implements memberlist.Events which acts as a delegate for membership changes.

func (*MemberlistEvents) NotifyJoin

func (m *MemberlistEvents) NotifyJoin(node *memberlist.Node)

NotifyJoin is called whenever a new member is discovered and adds it to the Toystore instance.

func (*MemberlistEvents) NotifyLeave

func (m *MemberlistEvents) NotifyLeave(node *memberlist.Node)

NotifyLeave is called whenever a node appears to be dead or leaves the cluster and then removes the node from the Toystore instance.

func (*MemberlistEvents) NotifyUpdate

func (m *MemberlistEvents) NotifyUpdate(node *memberlist.Node)

NotifyUpdate is called whenever an existing node's data is changed.

type MemberlistNode

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

MemberlistNode is an implementation of Member that wraps hashicorp's memberlist.Node

func (*MemberlistNode) Address

func (m *MemberlistNode) Address() string

Address returns node.Meta as a string

func (*MemberlistNode) Meta

func (m *MemberlistNode) Meta() []byte

Meta returns the raw value of node.Meta

func (*MemberlistNode) Name

func (m *MemberlistNode) Name() string

Name returns node.Name

type Members

type Members interface {
	Setup(t *Toystore)
	Join(seed string)
	Members() []Member
	Len() int
}

Members repsents the current nodes in the cluster.

type PeerClient

type PeerClient interface {
	Get(address string, key string) (value *data.Data, status bool)
	Put(address string, value *data.Data) (status bool)
	CoordinateGet(address string, key string) (value *data.Data, status bool)
	CoordinatePut(address string, value *data.Data) (status bool)
	HintPut(address string, hint string, value *data.Data) (status bool)
}

PeerClient defines the possible interactions between nodes in the cluster. Should be implemented with a specific transport client.

type PeerHandler

type PeerHandler interface {
	Get(args *GetArgs, reply *GetReply) error
	Put(args *PutArgs, reply *PutReply) error
	CoordinateGet(args *GetArgs, reply *GetReply) error
	CoordinatePut(args *PutArgs, reply *PutReply) error
}

PeerHandler defines the methods that a node should expose to other nodes in the cluster.

type PutArgs

type PutArgs struct {
	Value *data.Data
}

PutArgs is used to write data on other nodes.

type PutReply

type PutReply struct {
	Ok bool
}

PutReply is used to send write status to other nodes.

type RpcClient

type RpcClient struct {
}

RpcClient implements PeerClient using Go's RPC package.

func NewRpcClient

func NewRpcClient() *RpcClient

NewRpcClient returns a new RpcClient instance.

func (*RpcClient) CoordinateGet

func (r *RpcClient) CoordinateGet(address string, key string) (*data.Data, bool)

CoordinateGet forwards the key to the coordinating node so it can organize the Get operation.

func (*RpcClient) CoordinatePut

func (r *RpcClient) CoordinatePut(address string, value *data.Data) bool

CoordinatePut forwards the Data value to the coordinating node so it can organize the Put operation.

func (*RpcClient) Get

func (r *RpcClient) Get(address string, key string) (*data.Data, bool)

Get makes an RPC to the address to find the specified key and returns the value and an existence bool.

func (*RpcClient) HintPut

func (r *RpcClient) HintPut(address string, hint string, data *data.Data) bool

HintPut makes an RPC to add hint data to the specified node.

func (*RpcClient) Put

func (r *RpcClient) Put(address string, value *data.Data) bool

Put makes an RPC to the address to add the Data value and returns a boolean representing the status of this operation.

func (*RpcClient) Transfer

func (r *RpcClient) Transfer(address string, data []*data.Data) bool

Transfer makes an RPC call to send a set of keys to the specified address.

type RpcHandler

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

RpcHandler implements PeerHandler using Go's RPC package.

func NewRpcHandler

func NewRpcHandler(store *Toystore) *RpcHandler

NewRpcHandler returns a new RpcHandler instance and starts serving requests.

func (*RpcHandler) CoordinateGet

func (r *RpcHandler) CoordinateGet(args *GetArgs, reply *GetReply) error

CoordinateGet kicks off the coordination process from a non-coordinator node.

func (*RpcHandler) CoordinatePut

func (r *RpcHandler) CoordinatePut(args *PutArgs, reply *PutReply) error

CoordinatePut kicks off the coordination process from a non-coordinator node.

func (*RpcHandler) Get

func (r *RpcHandler) Get(args *GetArgs, reply *GetReply) error

Get looks up and item from Toystore's underlying Store data.

func (*RpcHandler) HintPut

func (r *RpcHandler) HintPut(args *HintArgs, reply *HintReply) error

HintPut adds a new data hint to the node's HintedHandoff list.

func (*RpcHandler) Put

func (r *RpcHandler) Put(args *PutArgs, reply *PutReply) error

Put adds a value directly to Toystore's underlying Store data.

func (*RpcHandler) Transfer

func (r *RpcHandler) Transfer(args *TransferArgs, reply *TransferReply) error

Transfer adds a set of data to the node.

type Toystore

type Toystore struct {
	// Number of nodes to replicate each data item.
	ReplicationLevel int

	// Number of successful writes required.
	W int

	// Number of successful reads required.
	R int

	// Port number to serve RPC requests between nodes.
	RPCPort int

	// Host address to bind to.
	Host string

	// Concrete Store implementation to persist data.
	Data store.Store

	// Hash ring for nodes in the cluster.
	Ring ring.Ring

	// Concrete Members implementation to represent the current cluster state.
	Members Members

	// Store of hinted data meant for other nodes.
	Hints *HintedHandoff
	// contains filtered or unexported fields
}

Toystore represents an individual node in a Toystore cluster.

func New

func New(config Config) *Toystore

New creates a new Toystore instance using the config variables. It starts the RPC server and gossip protocols to handle node communication between the cluster.

func (*Toystore) AddMember

func (t *Toystore) AddMember(member Member)

AddMember adds a new node to the hash ring. If the new node is adjacent to the current node then it transfers any keys in its range that should be owned by the new node.

func (*Toystore) CoordinateGet

func (t *Toystore) CoordinateGet(key string) (*data.Data, bool)

CoordinateGet organizes the get request between the collaborating nodes. It sends get requests to all nodes in the key's preference list and keeps track of success/failures. If there are more successful reads than config.R it returns the value and true. Otherwise it returns the value and false.

func (*Toystore) CoordinatePut

func (t *Toystore) CoordinatePut(value *data.Data) bool

CoordinatePut organizes the put request between the collaborating nodes. It sends put requests to all nodes in the key's preference list and keeps track of success/failures. If there are more successful writes than config.W it returns true. Otherwise it returns false.

If any nodes in the key's preference list are dead it will attempt to put the value on other nodes with a hint to its correct location.

func (*Toystore) Get

func (t *Toystore) Get(key string) (interface{}, bool)

Get finds the key on the correct node in the cluster and returns the value and an existence bool. If the key is on the current node then it coordinates the operation. Otherwise it sends the coordination request to the correct node.

func (*Toystore) GetString

func (t *Toystore) GetString(key string) (string, bool)

GetString returns a string of the value for the specified key/value pair.

func (*Toystore) Merge

func (t *Toystore) Merge(data *data.Data) bool

Merge updates the data object only if its Timestamp is later than the current value. If the key doesn't exist it adds it. Requires Store implementation to be thread safe.

func (*Toystore) Put

func (t *Toystore) Put(key string, value interface{}) (ok bool)

Put finds the key on the correct node in the cluster, sets the value and returns a status bool. If the key is owned by current node then it coordinates the operation. Otherwise it sends the coordination request to the correct node.

func (*Toystore) RemoveMember

func (t *Toystore) RemoveMember(member Member)

RemoveMember removes a member from the hash ring.

func (*Toystore) Transfer

func (t *Toystore) Transfer(address string)

Transfer sends a list of keys to another node in the cluster.

type TransferArgs

type TransferArgs struct {
	Data []*data.Data
}

TransferArgs is used to send chunks of data to other nodes.

type TransferReply

type TransferReply struct {
	Ok bool
}

TransferReply is used to send transfer status to other nodes.

type Transferrer

type Transferrer interface {
	Transfer(address string, data []*data.Data) (status bool)
}

Transferrer defines the method for transferring blocks of data between nodes.