Documentation ¶
Overview ¶
Package dendrite implements a distributed hash table (DHT) based on Chord Protocol. Included sub-package 'dtable' is built on top of dendrite and implements distributed in-memory key/value database, with replication and failover support, with query interface to Get() or Set() items with different consistency levels.
For better key distribution, dendrite allows configurable number of virtual nodes per instance (vnodes). The number of replicas in dtable is also configurable.
Calling application can bootstrap the cluster, or join existing one by connecting to any of existing nodes (must be manually specified). Node discovery is not part of the implementation. Use consul (consul.io) or something else for that purpose.
Chord protocol defines ring stabilization. In dendrite, stabilization period is configurable.
Node to node (network) communication is built on top of ZeroMQ sockets over TCP for speed, clustering and reliability. Dendrite starts configurable number of goroutines (default: 10) for load balanced serving of remote requests, but scales that number up and down depending on the load (aka prefork model).
All messages sent through dendrite are encapsulated in ChordMsg structure, where first byte indicates message type, and actual data follows. Data part is serialized with protocol buffers.
Dendrite can be extended through two interfaces:
TransportHook DelegateHook
TransportHook allows other packages to provide additional message types, decoders and handlers, while DelegateHook can be used to capture chord events that dendrite emits:
EvPredecessorJoined EvPredecessorLeft EvReplicasChanged
Index ¶
- func Between(id1, id2, key []byte, rincl bool) bool
- func HashKey(key []byte) []byte
- func KeyFromString(key_str string) []byte
- func Min(a, b int) int
- type ChordMsg
- type Config
- type DelegateHook
- type ErrHookUnknownType
- type EventCtx
- type LocalTransport
- func (lt *LocalTransport) Decode(raw []byte) (*ChordMsg, error)
- func (lt *LocalTransport) Encode(msgtype MsgType, data []byte) []byte
- func (lt *LocalTransport) FindSuccessors(vn *Vnode, limit int, key []byte) ([]*Vnode, error)
- func (lt *LocalTransport) GetPredecessor(vn *Vnode) (*Vnode, error)
- func (lt *LocalTransport) GetVnodeHandler(vnode *Vnode) (VnodeHandler, bool)
- func (lt *LocalTransport) ListVnodes(host string) ([]*Vnode, error)
- func (lt *LocalTransport) Notify(dest, self *Vnode) ([]*Vnode, error)
- func (lt *LocalTransport) Ping(vn *Vnode) (bool, error)
- func (lt *LocalTransport) Register(vnode *Vnode, handler VnodeHandler)
- func (lt *LocalTransport) RegisterHook(th TransportHook)
- type LogLevel
- type MsgType
- type PBProtoAck
- type PBProtoErr
- type PBProtoFindSuccessors
- type PBProtoForward
- type PBProtoGetPredecessor
- type PBProtoLeave
- type PBProtoListVnodes
- type PBProtoListVnodesResp
- type PBProtoNotify
- type PBProtoPing
- type PBProtoVnode
- type Ring
- func (r *Ring) Len() int
- func (r *Ring) Less(i, j int) bool
- func (r *Ring) Logf(level LogLevel, format string, v ...interface{})
- func (r *Ring) Logln(level LogLevel, v ...interface{})
- func (r *Ring) Lookup(n int, keyHash []byte) ([]*Vnode, error)
- func (r *Ring) MaxStabilize() time.Duration
- func (r *Ring) MyVnodes() []*Vnode
- func (r *Ring) RegisterDelegateHook(dh DelegateHook)
- func (r *Ring) Replicas() int
- func (r *Ring) Swap(i, j int)
- type RingEventType
- type Transport
- type TransportHook
- type Vnode
- type VnodeHandler
- type ZMQTransport
- func (transport *ZMQTransport) Decode(data []byte) (*ChordMsg, error)
- func (transport *ZMQTransport) Encode(mt MsgType, data []byte) []byte
- func (transport *ZMQTransport) FindSuccessors(remote *Vnode, limit int, key []byte) ([]*Vnode, error)
- func (transport *ZMQTransport) GetPredecessor(remote *Vnode) (*Vnode, error)
- func (transport *ZMQTransport) GetVnodeHandler(vnode *Vnode) (VnodeHandler, bool)
- func (transport *ZMQTransport) ListVnodes(host string) ([]*Vnode, error)
- func (transport *ZMQTransport) NewErrorMsg(msg string) *ChordMsg
- func (transport *ZMQTransport) Notify(remote, self *Vnode) ([]*Vnode, error)
- func (transport *ZMQTransport) Ping(remote_vn *Vnode) (bool, error)
- func (transport *ZMQTransport) Register(vnode *Vnode, handler VnodeHandler)
- func (t *ZMQTransport) RegisterHook(h TransportHook)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Between ¶
Between checks if key is between id1 and id2, such that:
if rincl (right-included flag) is true:
(id1 > key > id2)
if rincl (right-included flag) is false:
(id1 > key >= id2)
func KeyFromString ¶
KeyFromString decodes hex string to []byte
Types ¶
type ChordMsg ¶
type ChordMsg struct { Type MsgType Data []byte TransportMsg interface{} // unmarshalled data, depending on transport TransportHandler func(*ChordMsg, chan *ChordMsg) // request pointer, response channel }
ChordMsg is lowest entity to be transmited through dendrite.
type Config ¶
type Config struct { Hostname string NumVnodes int // num of vnodes to create StabilizeMin time.Duration StabilizeMax time.Duration NumSuccessors int // number of successor to keep in self log Replicas int // number of replicas to keep by default LogLevel LogLevel // logLevel, 0 = null, 1 = info, 2 = debug }
Config is a main ring configuration struct.
func DefaultConfig ¶
DefaultConfig returns *Config with default values.
type DelegateHook ¶
type DelegateHook interface {
EmitEvent(*EventCtx)
}
DelegateHook provides interface to capture dendrite events in 3rd party packages.
type ErrHookUnknownType ¶
type ErrHookUnknownType string
func (ErrHookUnknownType) Error ¶
func (e ErrHookUnknownType) Error() string
type EventCtx ¶
type EventCtx struct { EvType RingEventType Target *Vnode PrimaryItem *Vnode SecondaryItem *Vnode ItemList []*Vnode ResponseCh chan interface{} }
EventCtx is a generic struct representing an event. Instance of EventCtx is emitted to DelegateHooks.
type LocalTransport ¶
type LocalTransport struct {
// contains filtered or unexported fields
}
LocalTransport implements Transport interface, but is used for communicating between local vnodes.
func (*LocalTransport) Decode ¶
func (lt *LocalTransport) Decode(raw []byte) (*ChordMsg, error)
Decode does nothing in local transport. Just satisfying interface.
func (*LocalTransport) Encode ¶
func (lt *LocalTransport) Encode(msgtype MsgType, data []byte) []byte
Encode does nothing in local transport. Just satisfying interface.
func (*LocalTransport) FindSuccessors ¶
FindSuccessors implements Transport's FindSuccessors() in local transport.
func (*LocalTransport) GetPredecessor ¶
func (lt *LocalTransport) GetPredecessor(vn *Vnode) (*Vnode, error)
GetPredecessor implements Transport's GetPredecessor() in local transport.
func (*LocalTransport) GetVnodeHandler ¶
func (lt *LocalTransport) GetVnodeHandler(vnode *Vnode) (VnodeHandler, bool)
GetVnodeHandler returns registered local vnode handler, if one is found for given vnode.
func (*LocalTransport) ListVnodes ¶
func (lt *LocalTransport) ListVnodes(host string) ([]*Vnode, error)
ListVnodes implements Transport's ListVnodes() in local transport.
func (*LocalTransport) Notify ¶
func (lt *LocalTransport) Notify(dest, self *Vnode) ([]*Vnode, error)
Notify implements Transport's Notify() in local transport.
func (*LocalTransport) Ping ¶
func (lt *LocalTransport) Ping(vn *Vnode) (bool, error)
Ping implements Transport's Ping() in local transport.
func (*LocalTransport) Register ¶
func (lt *LocalTransport) Register(vnode *Vnode, handler VnodeHandler)
Register registers a VnodeHandler within local and remote transports.
func (*LocalTransport) RegisterHook ¶
func (lt *LocalTransport) RegisterHook(th TransportHook)
RegisterHook does nothing in local transport. Just satisfying interface.
type PBProtoAck ¶
type PBProtoAck struct { Version *int64 `protobuf:"varint,1,req,name=version" json:"version,omitempty"` Ok *bool `protobuf:"varint,2,req,name=ok" json:"ok,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoAck is generic response message with boolean 'ok' state.
func (*PBProtoAck) GetOk ¶
func (m *PBProtoAck) GetOk() bool
func (*PBProtoAck) GetVersion ¶
func (m *PBProtoAck) GetVersion() int64
func (*PBProtoAck) ProtoMessage ¶
func (*PBProtoAck) ProtoMessage()
func (*PBProtoAck) Reset ¶
func (m *PBProtoAck) Reset()
func (*PBProtoAck) String ¶
func (m *PBProtoAck) String() string
type PBProtoErr ¶
type PBProtoErr struct { Error *string `protobuf:"bytes,2,req,name=error" json:"error,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoErr defines error message.
func (*PBProtoErr) GetError ¶
func (m *PBProtoErr) GetError() string
func (*PBProtoErr) ProtoMessage ¶
func (*PBProtoErr) ProtoMessage()
func (*PBProtoErr) Reset ¶
func (m *PBProtoErr) Reset()
func (*PBProtoErr) String ¶
func (m *PBProtoErr) String() string
type PBProtoFindSuccessors ¶
type PBProtoFindSuccessors struct { Key []byte `protobuf:"bytes,1,req,name=key" json:"key,omitempty"` Dest *PBProtoVnode `protobuf:"bytes,2,req,name=dest" json:"dest,omitempty"` Limit *int32 `protobuf:"varint,3,opt,name=limit" json:"limit,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoFindSuccessors is a structure to request successors for a key.
func (*PBProtoFindSuccessors) GetDest ¶
func (m *PBProtoFindSuccessors) GetDest() *PBProtoVnode
func (*PBProtoFindSuccessors) GetKey ¶
func (m *PBProtoFindSuccessors) GetKey() []byte
func (*PBProtoFindSuccessors) GetLimit ¶
func (m *PBProtoFindSuccessors) GetLimit() int32
func (*PBProtoFindSuccessors) ProtoMessage ¶
func (*PBProtoFindSuccessors) ProtoMessage()
func (*PBProtoFindSuccessors) Reset ¶
func (m *PBProtoFindSuccessors) Reset()
func (*PBProtoFindSuccessors) String ¶
func (m *PBProtoFindSuccessors) String() string
type PBProtoForward ¶
type PBProtoForward struct { Vnode *PBProtoVnode `protobuf:"bytes,1,req,name=vnode" json:"vnode,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoForward is sent to caller if request should be forwarded to another vnode.
func (*PBProtoForward) GetVnode ¶
func (m *PBProtoForward) GetVnode() *PBProtoVnode
func (*PBProtoForward) ProtoMessage ¶
func (*PBProtoForward) ProtoMessage()
func (*PBProtoForward) Reset ¶
func (m *PBProtoForward) Reset()
func (*PBProtoForward) String ¶
func (m *PBProtoForward) String() string
type PBProtoGetPredecessor ¶
type PBProtoGetPredecessor struct { Dest *PBProtoVnode `protobuf:"bytes,1,req,name=dest" json:"dest,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoGetPredecessor - request immediate predecessor from vnode.
func (*PBProtoGetPredecessor) GetDest ¶
func (m *PBProtoGetPredecessor) GetDest() *PBProtoVnode
func (*PBProtoGetPredecessor) ProtoMessage ¶
func (*PBProtoGetPredecessor) ProtoMessage()
func (*PBProtoGetPredecessor) Reset ¶
func (m *PBProtoGetPredecessor) Reset()
func (*PBProtoGetPredecessor) String ¶
func (m *PBProtoGetPredecessor) String() string
type PBProtoLeave ¶
type PBProtoLeave struct { Source *PBProtoVnode `protobuf:"bytes,1,req,name=source" json:"source,omitempty"` Dest *PBProtoVnode `protobuf:"bytes,2,req,name=dest" json:"dest,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoLeave (not used)
func (*PBProtoLeave) GetDest ¶
func (m *PBProtoLeave) GetDest() *PBProtoVnode
func (*PBProtoLeave) GetSource ¶
func (m *PBProtoLeave) GetSource() *PBProtoVnode
func (*PBProtoLeave) ProtoMessage ¶
func (*PBProtoLeave) ProtoMessage()
func (*PBProtoLeave) Reset ¶
func (m *PBProtoLeave) Reset()
func (*PBProtoLeave) String ¶
func (m *PBProtoLeave) String() string
type PBProtoListVnodes ¶
type PBProtoListVnodes struct {
XXX_unrecognized []byte `json:"-"`
}
PBProtoListVnodes - request the list of vnodes from remote vnode.
func (*PBProtoListVnodes) ProtoMessage ¶
func (*PBProtoListVnodes) ProtoMessage()
func (*PBProtoListVnodes) Reset ¶
func (m *PBProtoListVnodes) Reset()
func (*PBProtoListVnodes) String ¶
func (m *PBProtoListVnodes) String() string
type PBProtoListVnodesResp ¶
type PBProtoListVnodesResp struct { Vnodes []*PBProtoVnode `protobuf:"bytes,1,rep,name=vnodes" json:"vnodes,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoListVnodesResp is a structure for returning multiple vnodes to a caller.
func (*PBProtoListVnodesResp) GetVnodes ¶
func (m *PBProtoListVnodesResp) GetVnodes() []*PBProtoVnode
func (*PBProtoListVnodesResp) ProtoMessage ¶
func (*PBProtoListVnodesResp) ProtoMessage()
func (*PBProtoListVnodesResp) Reset ¶
func (m *PBProtoListVnodesResp) Reset()
func (*PBProtoListVnodesResp) String ¶
func (m *PBProtoListVnodesResp) String() string
type PBProtoNotify ¶
type PBProtoNotify struct { Dest *PBProtoVnode `protobuf:"bytes,1,req,name=dest" json:"dest,omitempty"` Vnode *PBProtoVnode `protobuf:"bytes,2,req,name=vnode" json:"vnode,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoNotify is a message to notify the remote vnode of origin's existence.
func (*PBProtoNotify) GetDest ¶
func (m *PBProtoNotify) GetDest() *PBProtoVnode
func (*PBProtoNotify) GetVnode ¶
func (m *PBProtoNotify) GetVnode() *PBProtoVnode
func (*PBProtoNotify) ProtoMessage ¶
func (*PBProtoNotify) ProtoMessage()
func (*PBProtoNotify) Reset ¶
func (m *PBProtoNotify) Reset()
func (*PBProtoNotify) String ¶
func (m *PBProtoNotify) String() string
type PBProtoPing ¶
type PBProtoPing struct { Version *int64 `protobuf:"varint,1,req,name=version" json:"version,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoPing is simple structure for pinging remote vnodes.
func (*PBProtoPing) GetVersion ¶
func (m *PBProtoPing) GetVersion() int64
func (*PBProtoPing) ProtoMessage ¶
func (*PBProtoPing) ProtoMessage()
func (*PBProtoPing) Reset ¶
func (m *PBProtoPing) Reset()
func (*PBProtoPing) String ¶
func (m *PBProtoPing) String() string
type PBProtoVnode ¶
type PBProtoVnode struct { Id []byte `protobuf:"bytes,1,req,name=id" json:"id,omitempty"` Host *string `protobuf:"bytes,2,req,name=host" json:"host,omitempty"` XXX_unrecognized []byte `json:"-"` }
PBProtoVnode represents Vnode structure.
func (*PBProtoVnode) GetHost ¶
func (m *PBProtoVnode) GetHost() string
func (*PBProtoVnode) GetId ¶
func (m *PBProtoVnode) GetId() []byte
func (*PBProtoVnode) ProtoMessage ¶
func (*PBProtoVnode) ProtoMessage()
func (*PBProtoVnode) Reset ¶
func (m *PBProtoVnode) Reset()
func (*PBProtoVnode) String ¶
func (m *PBProtoVnode) String() string
type Ring ¶
type Ring struct { Stabilizations int // contains filtered or unexported fields }
Ring is the main chord ring object.
func CreateRing ¶
CreateRing bootstraps the ring with given config and local transport.
func (*Ring) MaxStabilize ¶
MaxStabilize returns ring.config.StabilizeMax duration.
func (*Ring) RegisterDelegateHook ¶
func (r *Ring) RegisterDelegateHook(dh DelegateHook)
RegisterDelegateHook registers DelegateHook for emitting ring events.
type RingEventType ¶
type RingEventType int
var ( EvPredecessorJoined RingEventType = 1 EvPredecessorLeft RingEventType = 2 EvReplicasChanged RingEventType = 3 )
type Transport ¶
type Transport interface { // ListVnodes returns list of local vnodes from remote host. ListVnodes(string) ([]*Vnode, error) // Ping sends ping message to a vnode. Ping(*Vnode) (bool, error) // GetPredecessor is a request to get vnode's predecessor. GetPredecessor(*Vnode) (*Vnode, error) // Notify our successor of ourselves. Notify(dest, self *Vnode) ([]*Vnode, error) // FindSuccessors sends request to a vnode, requesting the list of successors for given key. FindSuccessors(*Vnode, int, []byte) ([]*Vnode, error) // GetVnodeHandler returns VnodeHandler interface if requested vnode is local GetVnodeHandler(*Vnode) (VnodeHandler, bool) // Register registers local vnode handlers Register(*Vnode, VnodeHandler) // Encode encodes dendrite msg into two frame byte stream. First frame is a single byte representing // message type, and another frame is protobuf data. Encode(MsgType, []byte) []byte // RegisterHook registers a TransportHook within the transport. RegisterHook(TransportHook) TransportHook }
Transport interface defines methods for communication between vnodes.
func InitLocalTransport ¶
InitLocalTransport initializes LocalTransport.
func InitZMQTransport ¶
InitZMQTransport creates ZeroMQ transport.
It multiplexes incoming connections which are then processed in separate go routines (workers). Multiplexer spawns go routines as needed, but 10 worker routines are created on startup. Every request times out after provided timeout duration. ZMQ pattern is:
zmq.ROUTER(incoming) -> proxy -> zmq.DEALER -> [zmq.REP(worker), zmq.REP...]
type TransportHook ¶
TransportHook provides interface to build additional message types, decoders and handlers through 3rd party packages that can register their hooks and leverage existing transport architecture and capabilities.
type Vnode ¶
Vnode is basic virtual node structure.
func VnodeFromProtobuf ¶
func VnodeFromProtobuf(pb *PBProtoVnode) *Vnode
VnodeFromProtobuf is helper method that creates *Vnode from PBProtoVnode message.
func (*Vnode) ToProtobuf ¶
func (vn *Vnode) ToProtobuf() *PBProtoVnode
ToProtobuf is a helper method which returns PBProtoVnode message from a *Vnode.
type VnodeHandler ¶
type VnodeHandler interface { FindSuccessors([]byte, int) ([]*Vnode, *Vnode, error) // args: key, limit # returns: succs, forward, error FindRemoteSuccessors(int) ([]*Vnode, error) GetPredecessor() (*Vnode, error) Notify(*Vnode) ([]*Vnode, error) }
VnodeHandler interface defines methods (from Transport interface) that are to be called in vnode context. Transports use this interface to avoid duplicate implementations. localVnode implements this interface.
type ZMQTransport ¶
type ZMQTransport struct { ClientTimeout time.Duration ZMQContext *zmq.Context // contains filtered or unexported fields }
ZMQTransport implements Transport interface using ZeroMQ for communication.
func (*ZMQTransport) Decode ¶
func (transport *ZMQTransport) Decode(data []byte) (*ChordMsg, error)
Decode implements Transport's Decode() in ZMQTransport. For request messages it also sets their respective handler to be called when such request comes in. If message type is unknown to this transport, Decode() also checks for registered TransportHooks and runs their Decode() implementation.
func (*ZMQTransport) Encode ¶
func (transport *ZMQTransport) Encode(mt MsgType, data []byte) []byte
Encode implement's Transport's Encode() in ZMQTransport.
func (*ZMQTransport) FindSuccessors ¶
func (transport *ZMQTransport) FindSuccessors(remote *Vnode, limit int, key []byte) ([]*Vnode, error)
FindSuccessors - client request. Implements Transport's FindSuccessors() in ZQMTransport.
func (*ZMQTransport) GetPredecessor ¶
func (transport *ZMQTransport) GetPredecessor(remote *Vnode) (*Vnode, error)
GetPredecessor - client request. Implements Transport's GetPredecessor() in ZQMTransport.
func (*ZMQTransport) GetVnodeHandler ¶
func (transport *ZMQTransport) GetVnodeHandler(vnode *Vnode) (VnodeHandler, bool)
GetVnodeHandler returns registered local vnode handler, if one is found for given vnode.
func (*ZMQTransport) ListVnodes ¶
func (transport *ZMQTransport) ListVnodes(host string) ([]*Vnode, error)
ListVnodes - client request. Implements Transport's ListVnodes() in ZQMTransport.
func (*ZMQTransport) NewErrorMsg ¶
func (transport *ZMQTransport) NewErrorMsg(msg string) *ChordMsg
NewErrorMsg is a helper to create encoded *ChordMsg (PBProtoErr) with error in it.
func (*ZMQTransport) Notify ¶
func (transport *ZMQTransport) Notify(remote, self *Vnode) ([]*Vnode, error)
Notify - client request. Implements Transport's Notify() in ZQMTransport.
func (*ZMQTransport) Ping ¶
func (transport *ZMQTransport) Ping(remote_vn *Vnode) (bool, error)
Ping - client request. Implements Transport's Ping() in ZQMTransport.
func (*ZMQTransport) Register ¶
func (transport *ZMQTransport) Register(vnode *Vnode, handler VnodeHandler)
Register registers a VnodeHandler within ZMQTransport.
func (*ZMQTransport) RegisterHook ¶
func (t *ZMQTransport) RegisterHook(h TransportHook)
RegisterHook registers TransportHook within ZMQTransport.