chord

package module
v0.2.0 Latest Latest
Warning

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

 Go to latest Published: Jan 1, 2017 License: MIT Imports: 21 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 separated from the implementation of an underlying network transport or RPC mechanism. Instead Chord relies on a transport implementation.

Transport Interfaces

  • GRPCTransport
  • UTPTransport

Acknowledgements

The original chord implementation is based on Armon's code available here.

Documentation

Overview

This package 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
VnodeError
VnodeListErr
BoolErr
FindSuccReq
StringParam
VnodePair
ErrResponse

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 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 BoolErr 

type BoolErr struct {
	Ok  bool   `protobuf:"varint,1,opt,name=ok" json:"ok,omitempty"`
	Err string `protobuf:"bytes,2,opt,name=err" json:"err,omitempty"`
}

func (*BoolErr) Descriptor 

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

func (*BoolErr) GetErr 

func (m *BoolErr) GetErr() string

func (*BoolErr) GetOk 

func (m *BoolErr) GetOk() bool

func (*BoolErr) ProtoMessage 

func (*BoolErr) ProtoMessage()

func (*BoolErr) Reset 

func (m *BoolErr) Reset()

func (*BoolErr) String 

func (m *BoolErr) String() string

type ChordClient 

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

func NewChordClient 

func NewChordClient(cc *grpc.ClientConn) ChordClient

type ChordServer 

type ChordServer interface {
	ListVnodesServe(context.Context, *StringParam) (*VnodeListErr, error)
	PingServe(context.Context, *Vnode) (*BoolErr, error)
	NotifyServe(context.Context, *VnodePair) (*VnodeListErr, error)
	GetPredecessorServe(context.Context, *Vnode) (*VnodeError, error)
	FindSuccessorsServe(context.Context, *FindSuccReq) (*VnodeListErr, error)
	ClearPredecessorServe(context.Context, *VnodePair) (*ErrResponse, error)
	SkipSuccessorServe(context.Context, *VnodePair) (*ErrResponse, error)
}

type Config 

type Config struct {
	Hostname      string           // Local host name
	NumVnodes     int              // Number of vnodes per physical node
	HashFunc      func() hash.Hash `json:"-"` // 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         `json:"-"` // Invoked to handle ring events
	// contains filtered or unexported fields
}

Config for Chord nodes

func DefaultConfig 

func DefaultConfig(hostname string) *Config

DefaultConfig 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 ErrResponse 

type ErrResponse struct {
	Err string `protobuf:"bytes,1,opt,name=err" json:"err,omitempty"`
}

func (*ErrResponse) Descriptor 

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

func (*ErrResponse) GetErr 

func (m *ErrResponse) GetErr() string

func (*ErrResponse) ProtoMessage 

func (*ErrResponse) ProtoMessage()

func (*ErrResponse) Reset 

func (m *ErrResponse) Reset()

func (*ErrResponse) String 

func (m *ErrResponse) String() string

type FindSuccReq 

type FindSuccReq struct {
	VN    *Vnode `protobuf:"bytes,1,opt,name=VN,json=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(sock net.Listener, gserver *grpc.Server, 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

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

func (*GRPCTransport) ClearPredecessorServe 

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

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) (*VnodeListErr, error)

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) (*VnodeError, error)

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) (*VnodeListErr, 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) (*VnodeListErr, error)

NotifyServe the client

func (*GRPCTransport) Ping 

func (cs *GRPCTransport) Ping(target *Vnode) (bool, error)

Ping a Vnode, check for liveness

func (*GRPCTransport) PingServe 

func (cs *GRPCTransport) PingServe(ctx context.Context, in *Vnode) (*BoolErr, error)

func (*GRPCTransport) Register 

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

func (*GRPCTransport) Shutdown 

func (cs *GRPCTransport) Shutdown()

Shutdown the TCP transport

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) (*ErrResponse, error)

func (*GRPCTransport) Status 

func (cs *GRPCTransport) Status() map[string]interface{}

type IDecoder 

type IDecoder interface {
	Decode(interface{}) error
}

type IEncoder 

type IEncoder interface {
	Encode(interface{}) error
}

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
}

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

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

ListVnodes for a given host

func (*Ring) Lookup 

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

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

	// 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)
}

Transport 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 UTPTransport 

type UTPTransport struct {
	RPCServe func(IEncoder, IDecoder) (interface{}, error)
	// contains filtered or unexported fields
}

func InitUTPTransport 

func InitUTPTransport(layer *mux.Layer, dialTimeout, rpcTimeout, maxConnIdle time.Duration) (*UTPTransport, error)

InitUTPTransport creates a new UTP transport on the given listen address with the configured timeout duration. A RPC function can be given to implement additional rpc's. maxConnIdle is the maximum age of a connection

func (*UTPTransport) ClearPredecessor 

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

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

func (*UTPTransport) FindSuccessors 

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

FindSuccessors for the given vnode and key upto n successors

func (*UTPTransport) GetPredecessor 

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

GetPredecessor requests a nodes predecessor

func (*UTPTransport) ListVnodes 

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

ListVnodes gets a list of the vnodes on the box

func (*UTPTransport) Notify 

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

Notify our successor of ourselves

func (*UTPTransport) Ping 

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

Ping a Vnode, check for liveness

func (*UTPTransport) Register 

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

Register for an RPC callbacks

func (*UTPTransport) Shutdown 

func (t *UTPTransport) Shutdown()

Shutdown the TCP transport

func (*UTPTransport) SkipSuccessor 

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

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

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"`
}

func (*Vnode) Descriptor 

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

func (*Vnode) GetHost 

func (m *Vnode) GetHost() string

func (*Vnode) GetId 

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

func (*Vnode) ProtoMessage 

func (*Vnode) ProtoMessage()

func (*Vnode) Reset 

func (m *Vnode) Reset()

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 VnodeError 

type VnodeError struct {
	VN  *Vnode `protobuf:"bytes,1,opt,name=VN,json=vN" json:"VN,omitempty"`
	Err string `protobuf:"bytes,2,opt,name=err" json:"err,omitempty"`
}

func (*VnodeError) Descriptor 

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

func (*VnodeError) GetErr 

func (m *VnodeError) GetErr() string

func (*VnodeError) GetVN 

func (m *VnodeError) GetVN() *Vnode

func (*VnodeError) ProtoMessage 

func (*VnodeError) ProtoMessage()

func (*VnodeError) Reset 

func (m *VnodeError) Reset()

func (*VnodeError) String 

func (m *VnodeError) String() string

type VnodeListErr 

type VnodeListErr struct {
	Err    string   `protobuf:"bytes,1,opt,name=err" json:"err,omitempty"`
	Vnodes []*Vnode `protobuf:"bytes,2,rep,name=vnodes" json:"vnodes,omitempty"`
}

func (*VnodeListErr) Descriptor 

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

func (*VnodeListErr) GetErr 

func (m *VnodeListErr) GetErr() string

func (*VnodeListErr) GetVnodes 

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

func (*VnodeListErr) ProtoMessage 

func (*VnodeListErr) ProtoMessage()

func (*VnodeListErr) Reset 

func (m *VnodeListErr) Reset()

func (*VnodeListErr) String 

func (m *VnodeListErr) 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
}

VnodeRPC contains 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.