dynamo

README

dynamo

Notes

• Store objects that are relatively small (less than 1 MB)
• ACID leads to poor availability
• Dynamo makes the trade-off of having weaker consistency to have better availability.
• No isolation
• No locks that improves performance
• Has to be very efficient (focus on latency and throughoutput)
• Dynamo should be running in a non-hostile environment
• Dynamo was built under the assumption that each part of Amazon should have their own dynamo instance. For example checkout has it's own dynamo instance the store page etc. This means that the scalability doesn't need to target thousands of nodes rather it's more targeted at a few hundred nodes.
• It should be easy to add and remove physical nodes
• Every node should have the same responsibility
• Heterogenity aka should be able to have physical nodes with different performance capabilities and still function well.

Documentation

Index

• Variables
• type BadgerStorage
  • func NewBadgerStore(path string) (*BadgerStorage, error)
  • func (b *BadgerStorage) Close() error
  • func (b *BadgerStorage) Get(key []byte) ([]byte, error)
  • func (b *BadgerStorage) GetVersioned(key []byte) ([]byte, *VectorClock, error)
  • func (b *BadgerStorage) Put(key, value []byte) error
  • func (b *BadgerStorage) PutVersioned(key, value []byte, vc *VectorClock) error
• type Config
• type ConflictSet
  • func (cs ConflictSet) Resolve() (VersionedValue, bool)
• type DynamoNode
  • func NewDynamoNode(config Config, bindAddr string, seeds []string, rpcAddr string) (*DynamoNode, error)
  • func (n *DynamoNode) ClientGet(key []byte) ([]byte, error)
  • func (n *DynamoNode) ClientPut(key, value []byte) error
  • func (n *DynamoNode) Close() error
  • func (n *DynamoNode) Get(args *RPCArgs, reply *RPCReply) error
  • func (n *DynamoNode) GetLocal(args *RPCArgs, reply *RPCReply) error
  • func (n *DynamoNode) Put(args *RPCArgs, reply *RPCReply) error
  • func (n *DynamoNode) PutLocal(args *RPCArgs, reply *RPCReply) error
• type Member
  • func (m Member) String() string
• type RPCArgs
• type RPCReply
• type RpcClient
• type StorageEngine
• type VectorClock
  • func NewVectorClock() *VectorClock
  • func (vc *VectorClock) Compare(other *VectorClock) int
  • func (vc *VectorClock) Copy() *VectorClock
  • func (vc *VectorClock) Deserialize(data []byte) error
  • func (vc *VectorClock) Increment(nodeID string)
  • func (vc *VectorClock) Merge(other *VectorClock)
  • func (vc *VectorClock) Serialize() []byte
• type VersionedValue

Variables

var ErrNotEnoughReplicas = errors.New("not enough replicas for parameters")

ErrNotEnoughReplicas happens when where trying to either will write or read quorums and the amount of nodes is not enough to fullfill the configuration provided to the node.

Types

type BadgerStorage

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

BadgerStorage implements the StorageEngine interface using BadgerDB

func NewBadgerStore

func NewBadgerStore(path string) (*BadgerStorage, error)

NewBadgerStorage creates a new BadgerStorage instance

func (*BadgerStorage) Close

func (b *BadgerStorage) Close() error

Close closes the BadgerDB instance

func (*BadgerStorage) Get

func (b *BadgerStorage) Get(key []byte) ([]byte, error)

Get retrieves the value for a given key

func (*BadgerStorage) GetVersioned

func (b *BadgerStorage) GetVersioned(key []byte) ([]byte, *VectorClock, error)

GetVersioned -- see interface documentation

func (*BadgerStorage) Put

func (b *BadgerStorage) Put(key, value []byte) error

Put stores a key-value pair

func (*BadgerStorage) PutVersioned

func (b *BadgerStorage) PutVersioned(key, value []byte, vc *VectorClock) error

PutVersioned stores a key-value pair with a vector clock

type Config

type Config struct {
	N int // The number of nodes that store replicas of data
	R int // The number of nodes that must participate in a successful read operation
	W int // The number of nodes that must participate in a successful write operation
}

Config represents the configuration parameters for Amazon DynamoDB's consistency model. These settings allow for fine-tuning the trade-offs between consistency, availability, and partition tolerance (CAP theorem) in a distributed database system.

DynamoDB uses these parameters to manage its replication strategy and determine the behavior of read and write operations across multiple nodes. By adjusting these values, users can optimize their DynamoDB setup for either stronger consistency guarantees or higher availability, depending on their specific application requirements.

The relationship between N, R, and W influences the system's behavior: - If R + W > N: The system favors strong consistency over availability. - If R + W <= N: The system may return stale data in some scenarios, favoring availability.

Typical DynamoDB deployments often use N=3 as a default replication factor.

type ConflictSet

type ConflictSet []VersionedValue

ConflictSet is a slice of Versionedvalues, representing conflicting versions.

func (ConflictSet) Resolve

func (cs ConflictSet) Resolve() (VersionedValue, bool)

Resolve attemps to resolve conflicts in the ConflictSet It returns the resolved VersionValue and a boolean indicating if resolution was succesful.

type DynamoNode

type DynamoNode struct {
	Storage StorageEngine
	// contains filtered or unexported fields
}

DynamoNode represents a physical node in the dynamo system.

func NewDynamoNode

func NewDynamoNode(config Config, bindAddr string, seeds []string, rpcAddr string) (*DynamoNode, error)

func (*DynamoNode) ClientGet

func (n *DynamoNode) ClientGet(key []byte) ([]byte, error)

func (*DynamoNode) ClientPut

func (n *DynamoNode) ClientPut(key, value []byte) error

func (*DynamoNode) Close

func (n *DynamoNode) Close() error

func (*DynamoNode) Get

func (n *DynamoNode) Get(args *RPCArgs, reply *RPCReply) error

func (*DynamoNode) GetLocal

func (n *DynamoNode) GetLocal(args *RPCArgs, reply *RPCReply) error

func (*DynamoNode) Put

func (n *DynamoNode) Put(args *RPCArgs, reply *RPCReply) error

Put stores a key-value pair, implementing a quorum. 1. Generate a new version number based on the current timestamp. 2. Find the N closest nodes that should store the data (based on consistent hashing) 3. Attempt to write to these nodes in parallel. 4. If the write quorum is reached, consider the operation succesful.

func (*DynamoNode) PutLocal

func (n *DynamoNode) PutLocal(args *RPCArgs, reply *RPCReply) error

type Member

type Member struct {
	serf.Member
}

Member wraps serf.Member to implement consistent.Member interface

func (Member) String

func (m Member) String() string

String returns the name of the member.

type RPCArgs

type RPCArgs struct {
	Key   []byte
	Value []byte
	Clock *VectorClock
}

type RPCReply

type RPCReply struct {
	Value []byte
	Clock *VectorClock
}

type RpcClient

type RpcClient interface {
	Call(serviceMethod string, args interface{}, reply interface{}) error
	Close() error
}

RpcClient defines the basic methods needed for RPC communication. This is used instead of rpc.Client since this can be mocked easily and we can write tests easier.

type StorageEngine

type StorageEngine interface {
	// Get gets the corresponding value of a key from the data store.
	Get(key []byte) ([]byte, error)

	// Put stores a simple key-value pair into the data store.
	Put(key, value []byte) error

	// GetVersioned is an extension of the Get method where the version metadata is read from the
	// value before returned. NOTE: That GetVersioned should only be used to read items that are
	// inserted using PutVersioned
	GetVersioned(key []byte) ([]byte, *VectorClock, error)

	// PutVersioned writes a given key value pair and adds a version at the start of the value that
	// is then written into the data store. NOTE: This value should only be read by using GetVersioned
	// otherwise this will cause problems.
	PutVersioned(key, value []byte, vectorClock *VectorClock) error

	// Close clear out any left over resources etc if those need to be cleared
	Close() error
}

StorageEngine is a common interface that implements all of the methods that are needed to store data on disk or anywhere else etc.

type VectorClock

type VectorClock struct {
	Counter map[string]uint64
	// contains filtered or unexported fields
}

VectorClock represents the vector clock for a particular value.

func NewVectorClock

func NewVectorClock() *VectorClock

NewVectorClock creates a new vector clock.

func (*VectorClock) Compare

func (vc *VectorClock) Compare(other *VectorClock) int

Compare compares this VectorClock with another vector clock -1 if this clock is less than the other 0 if they are qual or concurrent 1 if this clock is greater than the other

func (*VectorClock) Copy

func (vc *VectorClock) Copy() *VectorClock

Copy creates a deep copy of a given VectorClock

func (*VectorClock) Deserialize

func (vc *VectorClock) Deserialize(data []byte) error

Deserialize reads a given byte array and creates and fill the VectorClock from that.

func (*VectorClock) Increment

func (vc *VectorClock) Increment(nodeID string)

Increment increases the counter for the given node.

func (*VectorClock) Merge

func (vc *VectorClock) Merge(other *VectorClock)

Merge combines two VectorClocks to be equal.

func (*VectorClock) Serialize

func (vc *VectorClock) Serialize() []byte

Serialize convers the VectorClock to a byte slice. Format is: [length of nodeID (8 bytes)][nodeID][count (8 bytes)] for each entry

type VersionedValue

type VersionedValue struct {
	Value []byte
	Clock *VectorClock
}

Versionedvalue represents a value with its associated VectorClock