toystore

package module
v0.0.0-...-8291e36 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 4, 2015 License: MIT Imports: 11 Imported by: 0

README

toystore

GoDoc

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

Visual Representation

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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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.

Source Files

View all Source files

Directories

Path Synopsis
Package data is used to represent key/value pairs internally and transmit them over RPC between nodes.
 Package data is used to represent key/value pairs internally and transmit them over RPC between nodes.
api/http is an example application of Toystore.
 api/http is an example application of Toystore.
memory
Package memory is an example Store implementation that saves values to local memory.
 Package memory is an example Store implementation that saves values to local memory.
redis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.