chord

package module
v0.0.0-...-9c1aef7 Latest Latest
Warning

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

 Go to latest Published: Oct 15, 2017 License: MIT Imports: 20 Imported by: 3

README

Go Chord Build Status

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 separated from the implementation of an underlying network transport or RPC mechanism. Instead Chord relies on a transport implementation. A GRPCTransport implementation as been provided.

Additions

The following features have been added on top of the standard Chord protocol:

  • Vivaldi coordinate tracking to measure inter-vnode distance
  • An additional binary metadata field for each vnode to allow user definable custom properties

Roadmap

  • Faster convergence times
Acknowledgements

Most of the original code comes from the following libraries:

Many thanks for the initial groundwork.

Documentation

Overview

Package chord is used to provide an implementation of the Chord network protocol.

Package chord is a generated protocol buffer package.

It is generated from these files: 

net.proto

It has these top-level messages: 

Vnode
Response
VnodeList
FindSuccReq
StringParam
VnodePair

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func RegisterChordServer 

func RegisterChordServer(s *grpc.Server, srv ChordServer)

Types

type BlackholeTransport 

type BlackholeTransport struct{}

BlackholeTransport is used to provide an implemenation of the Transport that does nothing. Any operation will result in an error.

func (*BlackholeTransport) ClearPredecessor 

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

ClearPredecessor is a no-op call

func (*BlackholeTransport) FindSuccessors 

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

FindSuccessors is a no-op call

func (*BlackholeTransport) GetCoordinate 

func (*BlackholeTransport) GetCoordinate(vn *Vnode) (*coordinate.Coordinate, error)

GetCoordinate is a no-op call

func (*BlackholeTransport) GetPredecessor 

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

GetPredecessor is a no-op call

func (*BlackholeTransport) ListVnodes 

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

ListVnodes is a no-op call

func (*BlackholeTransport) Notify 

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

Notify is a no-op call

func (*BlackholeTransport) Ping 

func (*BlackholeTransport) Ping(self, target *Vnode) (bool, *coordinate.Coordinate, error)

Ping is a no-op call

func (*BlackholeTransport) Register 

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

Register is a no-op call

func (*BlackholeTransport) SkipSuccessor 

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

SkipSuccessor is a no-op call

type ChordClient 

type ChordClient interface {
	ListVnodesServe(ctx context.Context, in *StringParam, opts ...grpc.CallOption) (*VnodeList, error)
	PingServe(ctx context.Context, in *VnodePair, opts ...grpc.CallOption) (*Response, error)
	NotifyServe(ctx context.Context, in *VnodePair, opts ...grpc.CallOption) (*VnodeList, error)
	GetPredecessorServe(ctx context.Context, in *Vnode, opts ...grpc.CallOption) (*Response, error)
	FindSuccessorsServe(ctx context.Context, in *FindSuccReq, opts ...grpc.CallOption) (*VnodeList, error)
	ClearPredecessorServe(ctx context.Context, in *VnodePair, opts ...grpc.CallOption) (*Response, error)
	SkipSuccessorServe(ctx context.Context, in *VnodePair, opts ...grpc.CallOption) (*Response, error)
	GetCoordinateServe(ctx context.Context, in *Vnode, opts ...grpc.CallOption) (*Vnode, error)
}

func NewChordClient 

func NewChordClient(cc *grpc.ClientConn) ChordClient

type ChordServer 

type ChordServer interface {
	ListVnodesServe(context.Context, *StringParam) (*VnodeList, error)
	PingServe(context.Context, *VnodePair) (*Response, error)
	NotifyServe(context.Context, *VnodePair) (*VnodeList, error)
	GetPredecessorServe(context.Context, *Vnode) (*Response, error)
	FindSuccessorsServe(context.Context, *FindSuccReq) (*VnodeList, error)
	ClearPredecessorServe(context.Context, *VnodePair) (*Response, error)
	SkipSuccessorServe(context.Context, *VnodePair) (*Response, error)
	GetCoordinateServe(context.Context, *Vnode) (*Vnode, error)
}

type Config 

type Config struct {
	Hostname string // Local host name

	Region string // General region
	Zone   string // Zone within a region
	Sector string // Sector within a zone
	Meta   Meta   // User defined metadata

	NumVnodes     int // Number of vnodes per physical node
	NumSuccessors int // Number of successors to maintain

	HashFunc func() hash.Hash `json:"-"` // Hash function to use

	StabilizeMin time.Duration // Minimum stabilization time
	StabilizeMax time.Duration // Maximum stabilization time
	// Setting this to anything greater than 0 enables adaptive stabilization.
	// If eneabled the above min and max are used as starting values.
	StabilizeThresh time.Duration
	// Number of interations to stay at start before stepping
	StabilizeStayCount int

	Coordinate        *coordinate.Config // vivaldi coordinate configuration
	Delegate          Delegate           `json:"-"` // Invoked to handle ring events
	DelegateQueueSize int                // Number of delegate calls to hold in the queue
	// contains filtered or unexported fields
}

Config for Chord nodes

func DefaultConfig 

func DefaultConfig(hostname string) *Config

DefaultConfig returns the default Ring configuration. It uses SHA1 as the default hash function

func (*Config) HashBits 

func (config *Config) HashBits() int

HashBits returns the number of hash bits

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 FindSuccReq 

type FindSuccReq struct {
	VN    *Vnode `protobuf:"bytes,1,opt,name=VN" json:"VN,omitempty"`
	Count int32  `protobuf:"varint,2,opt,name=count" json:"count,omitempty"`
	Key   []byte `protobuf:"bytes,3,opt,name=key,proto3" json:"key,omitempty"`
}

func (*FindSuccReq) Descriptor 

func (*FindSuccReq) Descriptor() ([]byte, []int)

func (*FindSuccReq) GetCount 

func (m *FindSuccReq) GetCount() int32

func (*FindSuccReq) GetKey 

func (m *FindSuccReq) GetKey() []byte

func (*FindSuccReq) GetVN 

func (m *FindSuccReq) GetVN() *Vnode

func (*FindSuccReq) ProtoMessage 

func (*FindSuccReq) ProtoMessage()

func (*FindSuccReq) Reset 

func (m *FindSuccReq) Reset()

func (*FindSuccReq) String 

func (m *FindSuccReq) String() string

type GRPCTransport 

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

GRPCTransport used by chord

func NewGRPCTransport 

func NewGRPCTransport(rpcTimeout, connMaxIdle time.Duration) *GRPCTransport

NewGRPCTransport creates a new grpc transport using the provided listener and grpc server.

func (*GRPCTransport) ClearPredecessor 

func (cs *GRPCTransport) ClearPredecessor(target, self *Vnode) error

ClearPredecessor clears a predecessor if it matches a given vnode. Used to leave.

func (*GRPCTransport) ClearPredecessorServe 

func (cs *GRPCTransport) ClearPredecessorServe(ctx context.Context, in *VnodePair) (*Response, error)

ClearPredecessorServe serves a ClearPredecessor request

func (*GRPCTransport) FindSuccessors 

func (cs *GRPCTransport) FindSuccessors(vn *Vnode, n int, k []byte) ([]*Vnode, error)

FindSuccessors given the vnode upto n successors

func (*GRPCTransport) FindSuccessorsServe 

func (cs *GRPCTransport) FindSuccessorsServe(ctx context.Context, in *FindSuccReq) (*VnodeList, error)

FindSuccessorsServe serves a FindSuccessors request

func (*GRPCTransport) GetCoordinate 

func (cs *GRPCTransport) GetCoordinate(vn *Vnode) (*coordinate.Coordinate, error)

GetCoordinate gets the coordinates for the given remote vnode

func (*GRPCTransport) GetCoordinateServe 

func (cs *GRPCTransport) GetCoordinateServe(ctx context.Context, vn *Vnode) (*Vnode, error)

GetCoordinateServe serves a GetCoordinate request returning the Coordinate for this node

func (*GRPCTransport) GetPredecessor 

func (cs *GRPCTransport) GetPredecessor(vn *Vnode) (*Vnode, error)

GetPredecessor requests a vnode's predecessor

func (*GRPCTransport) GetPredecessorServe 

func (cs *GRPCTransport) GetPredecessorServe(ctx context.Context, in *Vnode) (*Response, error)

GetPredecessorServe serves a GetPredecessor request

func (*GRPCTransport) ListVnodes 

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

ListVnodes gets a list of the vnodes on the box

func (*GRPCTransport) ListVnodesServe 

func (cs *GRPCTransport) ListVnodesServe(ctx context.Context, in *StringParam) (*VnodeList, error)

ListVnodesServe is the server side call

func (*GRPCTransport) Notify 

func (cs *GRPCTransport) Notify(target, self *Vnode) ([]*Vnode, error)

Notify our successor of ourselves

func (*GRPCTransport) NotifyServe 

func (cs *GRPCTransport) NotifyServe(ctx context.Context, in *VnodePair) (*VnodeList, error)

NotifyServe serves a notify request

func (*GRPCTransport) Ping 

func (cs *GRPCTransport) Ping(self, target *Vnode) (bool, *coordinate.Coordinate, error)

Ping pings a Vnode to check for liveness and updates the vnode coordinates. Self is the caller Vnode and is used to determine rtt's from its vnodes perspective.

func (*GRPCTransport) PingServe 

func (cs *GRPCTransport) PingServe(ctx context.Context, in *VnodePair) (*Response, error)

PingServe serves a ping request

func (*GRPCTransport) Register 

func (cs *GRPCTransport) Register(v *Vnode, o VnodeRPC)

Register vnode rpc's for a vnode.

func (*GRPCTransport) RegisterServer 

func (cs *GRPCTransport) RegisterServer(server *grpc.Server)

RegisterServer registers the transport with the grpc server and starts the connection reaper

func (*GRPCTransport) Shutdown 

func (cs *GRPCTransport) Shutdown()

Shutdown signals a shutdown on the transport, closing all outbound connections.

func (*GRPCTransport) SkipSuccessor 

func (cs *GRPCTransport) SkipSuccessor(target, self *Vnode) error

SkipSuccessor instructs a node to skip a given successor. Used to leave.

func (*GRPCTransport) SkipSuccessorServe 

func (cs *GRPCTransport) SkipSuccessorServe(ctx context.Context, in *VnodePair) (*Response, error)

SkipSuccessorServe serves a SkipSuccessor request

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

ClearPredecessor calls ClearPredecessor on a local or remote Vnode

func (*LocalTransport) Deregister 

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

Deregister de-registers a Vnode from the transport

func (*LocalTransport) FindSuccessors 

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

FindSuccessors calls FindSuccessors on a local or remote Vnode

func (*LocalTransport) GetCoordinate 

func (lt *LocalTransport) GetCoordinate(vn *Vnode) (*coordinate.Coordinate, error)

GetCoordinate gets the coordinates for a vnode

func (*LocalTransport) GetPredecessor 

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

GetPredecessor calls GetPredecessor on a local or remote Vnode

func (*LocalTransport) ListVnodes 

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

ListVnodes requests a list of vnodes from host

func (*LocalTransport) Notify 

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

Notify calls Notify on a local or remote Vnode

func (*LocalTransport) Ping 

func (lt *LocalTransport) Ping(self, target *Vnode) (bool, *coordinate.Coordinate, error)

Ping pings a local or remote Vnode

func (*LocalTransport) Register 

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

Register registers a Vnode with its RPC calls

func (*LocalTransport) SkipSuccessor 

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

SkipSuccessor calls SkipSuccessor on a local or remote Vnode

type Meta 

type Meta map[string][]byte

Meta holds metadata for a node

func (Meta) MarshalBinary 

func (meta Meta) MarshalBinary() ([]byte, error)

MarshalBinary marshals Meta to '=' and ',' delimited bytes

func (Meta) MarshalJSON 

func (meta Meta) MarshalJSON() ([]byte, error)

MarshalJSON is used to marshal keys and values to a string map.

func (Meta) String 

func (meta Meta) String() string

func (Meta) UnmarshalBinary 

func (meta Meta) UnmarshalBinary(b []byte) error

UnmarshalBinary unmarshals '=' and ',' delimited bytes into Meta

type Response 

type Response struct {
	Vnode *Vnode `protobuf:"bytes,1,opt,name=Vnode" json:"Vnode,omitempty"`
}

Generic response fields. This is need as we cannot send nil responses over grpc

func (*Response) Descriptor 

func (*Response) Descriptor() ([]byte, []int)

func (*Response) GetVnode 

func (m *Response) GetVnode() *Vnode

func (*Response) ProtoMessage 

func (*Response) ProtoMessage()

func (*Response) Reset 

func (m *Response) Reset()

func (*Response) String 

func (m *Response) String() string

type Ring 

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

Ring stores the state required for a Chord ring

func Create 

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

Create a new Chord ring given the config and transport

func Join 

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

Join an existing Chord ring

func (*Ring) GetCoordinate 

func (r *Ring) GetCoordinate() *coordinate.Coordinate

GetCoordinate returns the coorindates for this node on the ring

func (*Ring) Leave 

func (r *Ring) Leave() error

Leave 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) ([]byte, []*Vnode, error)

Lookup does a lookup for up to N successors on the hash of a key. It returns the hash of the key used to perform the lookup, the closest vnode and up to N successors.

func (*Ring) LookupCoordinate 

func (r *Ring) LookupCoordinate(vn *Vnode) (*coordinate.Coordinate, error)

LookupCoordinate returns the coordinate for the given vnode

func (*Ring) LookupHash 

func (r *Ring) LookupHash(n int, hash []byte) ([]*Vnode, error)

LookupHash does a lookup for up to N successors of a hash. It returns the predecessor and up to N successors. The hash size must match the hash function used when init'ing the ring.

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) Status 

func (r *Ring) Status() *Status

Status returns ring information of this node

func (*Ring) Swap 

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

Swap swaps the vnodes with indexes i and j.

type Status 

type Status struct {
	Hostname   string
	HashBits   int
	Meta       Meta
	Coordinate *coordinate.Coordinate
	Vnodes     []*VnodeStatus
}

Status represents the status of a node

type StringParam 

type StringParam struct {
	Value string `protobuf:"bytes,1,opt,name=value" json:"value,omitempty"`
}

func (*StringParam) Descriptor 

func (*StringParam) Descriptor() ([]byte, []int)

func (*StringParam) GetValue 

func (m *StringParam) GetValue() string

func (*StringParam) ProtoMessage 

func (*StringParam) ProtoMessage()

func (*StringParam) Reset 

func (m *StringParam) Reset()

func (*StringParam) String 

func (m *StringParam) String() string

type Transport 

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

	// Get the coordinates for a vnode
	GetCoordinate(vn *Vnode) (*coordinate.Coordinate, error)

	// Ping a Vnode, return liveness and/or coordinates
	Ping(self, target *Vnode) (bool, *coordinate.Coordinate, 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)
}

Transport implements the methods needed for a Chord ring

func InitLocalTransport 

func InitLocalTransport(remote Transport) Transport

InitLocalTransport creates a local transport to wrap a remote transport

type Vnode 

type Vnode struct {
	Id         []byte                 `protobuf:"bytes,1,opt,name=id,proto3" json:"id,omitempty"`
	Host       string                 `protobuf:"bytes,2,opt,name=host" json:"host,omitempty"`
	Region     string                 `protobuf:"bytes,3,opt,name=region" json:"region,omitempty"`
	Zone       string                 `protobuf:"bytes,4,opt,name=zone" json:"zone,omitempty"`
	Sector     string                 `protobuf:"bytes,5,opt,name=sector" json:"sector,omitempty"`
	Meta       [][]byte               `protobuf:"bytes,6,rep,name=meta,proto3" json:"meta,omitempty"`
	Coordinate *coordinate.Coordinate `protobuf:"bytes,7,opt,name=Coordinate" json:"Coordinate,omitempty"`
}

func (*Vnode) Descriptor 

func (*Vnode) Descriptor() ([]byte, []int)

func (*Vnode) GetCoordinate 

func (m *Vnode) GetCoordinate() *coordinate.Coordinate

func (*Vnode) GetHost 

func (m *Vnode) GetHost() string

func (*Vnode) GetId 

func (m *Vnode) GetId() []byte

func (*Vnode) GetMeta 

func (m *Vnode) GetMeta() [][]byte

func (*Vnode) GetRegion 

func (m *Vnode) GetRegion() string

func (*Vnode) GetSector 

func (m *Vnode) GetSector() string

func (*Vnode) GetZone 

func (m *Vnode) GetZone() string

func (*Vnode) MarshalJSON 

func (vn *Vnode) MarshalJSON() ([]byte, error)

MarshalJSON is a custom JSON marshaller

func (*Vnode) Metadata 

func (vn *Vnode) Metadata() Meta

Metadata returns the metadata from a slice of byte slices to a map.

func (*Vnode) ProtoMessage 

func (*Vnode) ProtoMessage()

func (*Vnode) Reset 

func (m *Vnode) Reset()

func (*Vnode) SetMetadata 

func (vn *Vnode) SetMetadata(meta Meta)

SetMetadata sets the metadata map to a slice of byte slices per the protobuf

func (*Vnode) String 

func (m *Vnode) String() string

func (*Vnode) StringID 

func (vn *Vnode) StringID() string

StringID converts the ID to a hex encoded string. As grpc uses String() we use StringID() instead.

type VnodeList 

type VnodeList struct {
	Vnodes []*Vnode `protobuf:"bytes,1,rep,name=vnodes" json:"vnodes,omitempty"`
}

func (*VnodeList) Descriptor 

func (*VnodeList) Descriptor() ([]byte, []int)

func (*VnodeList) GetVnodes 

func (m *VnodeList) GetVnodes() []*Vnode

func (*VnodeList) ProtoMessage 

func (*VnodeList) ProtoMessage()

func (*VnodeList) Reset 

func (m *VnodeList) Reset()

func (*VnodeList) String 

func (m *VnodeList) String() string

type VnodePair 

type VnodePair struct {
	Target *Vnode `protobuf:"bytes,1,opt,name=target" json:"target,omitempty"`
	Self   *Vnode `protobuf:"bytes,2,opt,name=self" json:"self,omitempty"`
}

func (*VnodePair) Descriptor 

func (*VnodePair) Descriptor() ([]byte, []int)

func (*VnodePair) GetSelf 

func (m *VnodePair) GetSelf() *Vnode

func (*VnodePair) GetTarget 

func (m *VnodePair) GetTarget() *Vnode

func (*VnodePair) ProtoMessage 

func (*VnodePair) ProtoMessage()

func (*VnodePair) Reset 

func (m *VnodePair) Reset()

func (*VnodePair) String 

func (m *VnodePair) String() string

type VnodeRPC 

type VnodeRPC interface {
	GetPredecessor() (*Vnode, error)
	Notify(*Vnode) ([]*Vnode, error)
	FindSuccessors(int, []byte) ([]*Vnode, error)
	ClearPredecessor(*Vnode) error
	SkipSuccessor(*Vnode) error
	GetCoordinate() *coordinate.Coordinate
	UpdateCoordinate(remote *Vnode, rtt time.Duration) (*coordinate.Coordinate, error)
}

VnodeRPC contains methods to invoke on the registered vnodes

type VnodeStatus 

type VnodeStatus struct {
	ID         string
	Stabilized time.Time
}

VnodeStatus holds the status for a single Vnode

Source Files

View all Source files

Directories

Path Synopsis
Package coordinate is a generated protocol buffer package.
 Package coordinate is a generated protocol buffer package.

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.