chord

package module
v0.0.0-...-725de0d Latest Latest
Warning

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

 Go to latest Published: Jan 3, 2017 License: MIT Imports: 14 Imported by: 1

README

Go Chord

This package provides a Golang implementation of the Chord protocol. Chord is used to organize nodes along a ring in a consistent way. It can be used to distribute work, build a key/value store, or serve as the underlying organization for a ring overlay topology.

The protocol is seperated from the implementation of an underlying network transport or RPC mechanism. Instead Chord relies on a transport implementation. A TCPTransport is provided that can be used as a reliable Chord RPC mechanism.

Documentation

To view the online documentation, go here.

Documentation

Overview

This package is used to provide an implementation of the Chord network protocol.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BlackholeTransport 

type BlackholeTransport struct {
}

BlackholeTransport is used to provide an implemenation of the Transport that does not actually do anything. Any operation will result in an error.

func (*BlackholeTransport) ClearPredecessor 

func (*BlackholeTransport) ClearPredecessor(target, self *Vnode) error

func (*BlackholeTransport) FindSuccessors 

func (*BlackholeTransport) FindSuccessors(vn *Vnode, n int, key []byte) ([]*Vnode, error)

func (*BlackholeTransport) GetPredecessor 

func (*BlackholeTransport) GetPredecessor(vn *Vnode) (*Vnode, error)

func (*BlackholeTransport) ListVnodes 

func (*BlackholeTransport) ListVnodes(host string) ([]*Vnode, error)

func (*BlackholeTransport) Notify 

func (*BlackholeTransport) Notify(vn, self *Vnode) ([]*Vnode, error)

func (*BlackholeTransport) Ping 

func (*BlackholeTransport) Ping(vn *Vnode) (bool, error)

func (*BlackholeTransport) Register 

func (*BlackholeTransport) Register(v *Vnode, o VnodeRPC)

func (*BlackholeTransport) SkipSuccessor 

func (*BlackholeTransport) SkipSuccessor(target, self *Vnode) error

type Config 

type Config struct {
	Hostname      string           // Local host name
	NumVnodes     int              // Number of vnodes per physical node
	HashFunc      func() hash.Hash // Hash function to use
	StabilizeMin  time.Duration    // Minimum stabilization time
	StabilizeMax  time.Duration    // Maximum stabilization time
	NumSuccessors int              // Number of successors to maintain
	Delegate      Delegate         // Invoked to handle ring events
	// contains filtered or unexported fields
}

Configuration for Chord nodes

func DefaultConfig 

func DefaultConfig(hostname string) *Config

Returns the default Ring configuration

type Delegate 

type Delegate interface {
	NewPredecessor(local, remoteNew, remotePrev *Vnode)
	Leaving(local, pred, succ *Vnode)
	PredecessorLeaving(local, remote *Vnode)
	SuccessorLeaving(local, remote *Vnode)
	Shutdown()
}

Delegate to notify on ring events

type LocalTransport 

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

LocalTransport is used to provides fast routing to Vnodes running locally using direct method calls. For any non-local vnodes, the request is passed on to another transport.

func (*LocalTransport) ClearPredecessor 

func (lt *LocalTransport) ClearPredecessor(target, self *Vnode) error

func (*LocalTransport) Deregister 

func (lt *LocalTransport) Deregister(v *Vnode)

func (*LocalTransport) FindSuccessors 

func (lt *LocalTransport) FindSuccessors(vn *Vnode, n int, key []byte) ([]*Vnode, error)

func (*LocalTransport) GetPredecessor 

func (lt *LocalTransport) GetPredecessor(vn *Vnode) (*Vnode, error)

func (*LocalTransport) ListVnodes 

func (lt *LocalTransport) ListVnodes(host string) ([]*Vnode, error)

func (*LocalTransport) Notify 

func (lt *LocalTransport) Notify(vn, self *Vnode) ([]*Vnode, error)

func (*LocalTransport) Ping 

func (lt *LocalTransport) Ping(vn *Vnode) (bool, error)

func (*LocalTransport) Register 

func (lt *LocalTransport) Register(v *Vnode, o VnodeRPC)

func (*LocalTransport) SkipSuccessor 

func (lt *LocalTransport) SkipSuccessor(target, self *Vnode) error

type Ring 

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

Stores the state required for a Chord ring

func Create 

func Create(conf *Config, trans Transport) (*Ring, error)

Creates a new Chord ring given the config and transport

func Join 

func Join(conf *Config, trans Transport, existing string) (*Ring, error)

Joins an existing Chord ring

func (*Ring) Leave 

func (r *Ring) Leave() error

Leaves a given Chord ring and shuts down the local vnodes

func (*Ring) Len 

func (r *Ring) Len() int

Len is the number of vnodes

func (*Ring) Less 

func (r *Ring) Less(i, j int) bool

Less returns whether the vnode with index i should sort before the vnode with index j.

func (*Ring) Lookup 

func (r *Ring) Lookup(n int, key []byte) ([]*Vnode, error)

Does a key lookup for up to N successors of a key

func (*Ring) Shutdown 

func (r *Ring) Shutdown()

Shutdown shuts down the local processes in a given Chord ring Blocks until all the vnodes terminate.

func (*Ring) Swap 

func (r *Ring) Swap(i, j int)

Swap swaps the vnodes with indexes i and j.

type TCPTransport 

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

TCPTransport provides a TCP based Chord transport layer. This allows Chord to be implemented over a network, instead of only using the LocalTransport. It is meant to be a simple implementation, optimizing for simplicity instead of performance. Messages are sent with a header frame, followed by a body frame. All data is encoded using the GOB format for simplicity.

Internally, there is 1 Goroutine listening for inbound connections, 1 Goroutine PER inbound connection.

func InitTCPTransport 

func InitTCPTransport(listen string, timeout time.Duration) (*TCPTransport, error)

Creates a new TCP transport on the given listen address with the configured timeout duration.

func (*TCPTransport) ClearPredecessor 

func (t *TCPTransport) ClearPredecessor(target, self *Vnode) error

Clears a predecessor if it matches a given vnode. Used to leave.

func (*TCPTransport) FindSuccessors 

func (t *TCPTransport) FindSuccessors(vn *Vnode, n int, k []byte) ([]*Vnode, error)

Find a successor

func (*TCPTransport) GetPredecessor 

func (t *TCPTransport) GetPredecessor(vn *Vnode) (*Vnode, error)

Request a nodes predecessor

func (*TCPTransport) ListVnodes 

func (t *TCPTransport) ListVnodes(host string) ([]*Vnode, error)

Gets a list of the vnodes on the box

func (*TCPTransport) Notify 

func (t *TCPTransport) Notify(target, self *Vnode) ([]*Vnode, error)

Notify our successor of ourselves

func (*TCPTransport) Ping 

func (t *TCPTransport) Ping(vn *Vnode) (bool, error)

Ping a Vnode, check for liveness

func (*TCPTransport) Register 

func (t *TCPTransport) Register(v *Vnode, o VnodeRPC)

Register for an RPC callbacks

func (*TCPTransport) Shutdown 

func (t *TCPTransport) Shutdown()

Shutdown the TCP transport

func (*TCPTransport) SkipSuccessor 

func (t *TCPTransport) SkipSuccessor(target, self *Vnode) error

Instructs a node to skip a given successor. Used to leave.

type Transport 

type Transport interface {
	// Gets a list of the vnodes on the box
	ListVnodes(string) ([]*Vnode, error)

	// Ping a Vnode, check for liveness
	Ping(*Vnode) (bool, error)

	// Request a nodes predecessor
	GetPredecessor(*Vnode) (*Vnode, error)

	// Notify our successor of ourselves
	Notify(target, self *Vnode) ([]*Vnode, error)

	// Find a successor
	FindSuccessors(*Vnode, int, []byte) ([]*Vnode, error)

	// Clears a predecessor if it matches a given vnode. Used to leave.
	ClearPredecessor(target, self *Vnode) error

	// Instructs a node to skip a given successor. Used to leave.
	SkipSuccessor(target, self *Vnode) error

	// Register for an RPC callbacks
	Register(*Vnode, VnodeRPC)
}

Implements the methods needed for a Chord ring

func InitLocalTransport 

func InitLocalTransport(remote Transport) Transport

Creates a local transport to wrap a remote transport

type Vnode 

type Vnode struct {
	Id   []byte // Virtual ID
	Host string // Host identifier
}

Represents an Vnode, local or remote

func (*Vnode) String 

func (vn *Vnode) String() string

Converts the ID to string

type VnodeRPC 

type VnodeRPC interface {
	GetPredecessor() (*Vnode, error)
	Notify(*Vnode) ([]*Vnode, error)
	FindSuccessors(int, []byte) ([]*Vnode, error)
	ClearPredecessor(*Vnode) error
	SkipSuccessor(*Vnode) error
}

These are the methods to invoke on the registered vnodes

Source Files

View all Source files

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.