chord

Documentation

Index

• Constants
• Variables
• func Between(low, target, high uint64, inclusive bool) bool
• func ErrorIsRetryable(err error) bool
• func ErrorMapper(err error) error
• func Hash(b []byte) uint64
• func ModuloSum(x, y uint64) uint64
• func Random() uint64
• type Error
  • func (e *Error) Error() string
• type KV
• type KVProvider
• type LeaseKV
• type PrefixKV
• type SimpleKV
• type State
  • func (i State) String() string
• type VNode
  • func MakeSuccListByAddress(immediate VNode, successors []VNode, maxLen int) []VNode
  • func MakeSuccListByID(immediate VNode, successors []VNode, maxLen int) []VNode
  • func WrapRetryKV(vnode VNode, interval time.Duration, maxAttempts uint) VNode
• type VNodeMembership

Constants

const (
	MaxFingerEntries         int    = 48 // Also known as m in the original paper
	ExtendedSuccessorEntries int    = 4  // Also known as L in the second paper
	MaxIdentitifer           uint64 = 1 << MaxFingerEntries
)

Variables

var (
	ErrJoinInvalidState     = errorDef("chord/membership: node cannot handle join request at the moment", true)
	ErrJoinTransferFailure  = errorDef("chord/membership: failed to transfer keys to joiner node", true)
	ErrJoinInvalidSuccessor = errorDef("chord/membership: join request was routed to the wrong successor node", true)
	ErrLeaveInvalidState    = errorDef("chord/membership: node cannot handle leave request at the moment", true)
	ErrLeaveTransferFailure = errorDef("chord/membership: failed to transfer keys to successor node", true)
	ErrKVStaleOwnership     = errorDef("chord/kv: processing node no longer has ownership over requested key", true)
	ErrKVPendingTransfer    = errorDef("chord/kv: kv transfer inprogress, state may be outdated", true)

	ErrNodeGone          = errorDef("chord: node is not part of the chord ring", false)
	ErrNodeNotStarted    = errorDef("chord: node is not running", false)
	ErrNodeNoSuccessor   = errorDef("chord: node has no successor, possibly invalid chord ring", false)
	ErrNodeNil           = errorDef("chord: node cannot be nil", false)
	ErrDuplicateJoinerID = errorDef("chord/membership: joining node has duplicate ID as its successor", false)
	ErrKVSimpleConflict  = errorDef("chord/kv: simple key was concurrently modified", false)
	ErrKVPrefixConflict  = errorDef("chord/kv: child already exists under prefix", false)
	ErrKVLeaseConflict   = errorDef("chord/kv: lease has not expired or was acquired by a different requester", false)
	ErrKVLeaseExpired    = errorDef("chord/kv: lease has expired with the given token", false)
	ErrKVLeaseInvalidTTL = errorDef("chord/kv: lease ttl must be greater than a second", false)
)

Functions

func Between

func Between(low, target, high uint64, inclusive bool) bool

func ErrorIsRetryable

func ErrorIsRetryable(err error) bool

func ErrorMapper

func ErrorMapper(err error) error

this is needed because RPC call squash type information, so in call site with signature if err == ErrABC will fail (but err.Error() == ErrABC.Error() will work).

func Hash

func Hash(b []byte) uint64

func ModuloSum

func ModuloSum(x, y uint64) uint64

func Random

func Random() uint64

Types

type Error

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

func (*Error) Error

func (e *Error) Error() string

type KV

type KV interface {
	SimpleKV
	PrefixKV
	LeaseKV
	// Import is used when a node is transferring its KV to a remote node.
	// Used when a new node joins or a node leaves gracefully
	Import(ctx context.Context, keys [][]byte, values []*protocol.KVTransfer) error
	// ListKeys is used when a node is traversing the network to list keys
	// based on a prefix
	ListKeys(ctx context.Context, prefix []byte) ([]*protocol.KeyComposite, error)
}

type KVProvider

type KVProvider interface {
	KV
	// Export is used when a Local node is retrieving relevant keys to transfer.
	// Only used locally, not used for RPC
	Export(keys [][]byte) []*protocol.KVTransfer
	// RangeKeys retrieve actual byte values of the keys, given the [low, high]
	// range of key hashes.
	// Only used locally, not used for RPC
	RangeKeys(low, high uint64) [][]byte
	// RemoveKeys hard delete keys from local node.
	// Only used locally, not used for RPC
	RemoveKeys(keys [][]byte)
}

type LeaseKV

type LeaseKV interface {
	// Acquire obtains a lease with given time-to-live, and returns a token for
	// later renewal and release.
	// On conflicting lease acquisition, ErrKVLeaseConflict error is returned.
	// If ttl is less than a second, ErrKVLeaseInvalidTTL error is returned.
	// Not to be confused with memory ordering acquire/release semantics.
	Acquire(ctx context.Context, lease []byte, ttl time.Duration) (token uint64, err error)
	// Renew extends the lease with given time-to-live, given that prevToken
	// is still valid. If the renewal occurs after a previous acquire
	// has expired and a different lease was acquired, ErrKVLeaseExpired error is returned.
	// If ttl is less than a second, ErrKVLeaseInvalidTTL error is returned.
	Renew(ctx context.Context, lease []byte, ttl time.Duration, prevToken uint64) (newToken uint64, err error)
	// Release relinquish the lease held previously by the given token.
	// If the lease holder has changed, ErrKVLeaseExpired error is returned.
	// Not to be confused with memory ordering acquire/release semantics.
	Release(ctx context.Context, lease []byte, token uint64) error
}

type PrefixKV

type PrefixKV interface {
	// PrefixAppend appends the child under the prefix. This is useful for tracking
	// hierarchical structure such as directories.
	// If the child already exist, ErrKVPrefixConflict error is returned.
	// Note that Prefix methods can share the same keyspace as Put/Get, and
	// Delete will not remove the Prefix children.
	PrefixAppend(ctx context.Context, prefix []byte, child []byte) error
	// PrefixList returns the children under the prefix.
	PrefixList(ctx context.Context, prefix []byte) (children [][]byte, err error)
	// PrefixContains checks if the child is in the prefix children
	PrefixContains(ctx context.Context, prefix []byte, child []byte) (bool, error)
	// PrefixRemove removes the matching child under the prefix.
	// If the child did not exist, this is an no-op
	PrefixRemove(ctx context.Context, prefix []byte, child []byte) error
}

type SimpleKV

type SimpleKV interface {
	// Put will store the value to a node in the Chord network responsible for the given key.
	// If the key did not exist, a new entry will be added.
	// If the key already exist, the value will be overwrriten.
	// If the key was concurrently modified by another request, ErrKVSimpleConflict error is returned.
	Put(ctx context.Context, key, value []byte) error
	// Get will fetch the value from a node in the Chord network.
	Get(ctx context.Context, key []byte) (value []byte, err error)
	// Delete will hard delete the key from the Chord network.
	// If the key was concurrently modified by another request, ErrKVSimpleConflict error is returned.
	// Note that Put/Get methods can share the same keyspace as Prefix methods, and
	// Delete will not remove the Prefix children.
	Delete(ctx context.Context, key []byte) error
}

type State

type State uint64

const (
	// Node not running, default state
	Inactive State = iota
	// In the progress of joining the network
	Joining
	// Ready to handle lookup and KV requests
	Active
	// Handling join request from another node
	Transferring
	// Leaving and transferring keys to successor
	Leaving
	// No longer an active node
	Left
)

func (State) String

func (i State) String() string

type VNode

type VNode interface {
	KV

	ID() uint64
	Identity() *protocol.Node

	Ping() error
	Notify(predecessor VNode) error

	FindSuccessor(key uint64) (VNode, error)
	GetSuccessors() ([]VNode, error)
	GetPredecessor() (VNode, error)

	VNodeMembership
}

func MakeSuccListByAddress

func MakeSuccListByAddress(immediate VNode, successors []VNode, maxLen int) []VNode

make successor list that will not have duplicate VNodes

func MakeSuccListByID

func MakeSuccListByID(immediate VNode, successors []VNode, maxLen int) []VNode

make successor list that will not have duplicate VNodes

func WrapRetryKV

func WrapRetryKV(vnode VNode, interval time.Duration, maxAttempts uint) VNode

WrapRetryKV wraps a given VNode to provide automatic retry on retryable KV errors

type VNodeMembership

type VNodeMembership interface {
	RequestToJoin(joiner VNode) (predecessor VNode, succList []VNode, err error)
	FinishJoin(stabilize bool, release bool) error

	RequestToLeave(leaver VNode) error
	FinishLeave(stabilize bool, release bool) error
}