chord

package
v0.0.0-...-ecfc0d7 Latest Latest
Warning

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

 Go to latest Published: Sep 28, 2024 License: Apache-2.0 Imports: 20 Imported by: 11

Documentation

Index

Constants

View Source 
const (
	// BroadcastTreeRoutingNumWorkers determines how many concurrent goroutines
	// are handling broadcast tree messages
	BroadcastTreeRoutingNumWorkers = 1
)
View Source 
const (
	// RelayRoutingNumWorkers determines how many concurrent goroutines are
	// handling relay messages
	RelayRoutingNumWorkers = 1
)

Variables

This section is empty.

Functions

func Between 

func Between(id1, id2, key []byte) bool

Between checks if a key is between two ID exclusively

func BetweenIncl 

func BetweenIncl(id1, id2, key []byte) bool

BetweenIncl checks if a key is between two ID, both inclusive

func BetweenLeftIncl 

func BetweenLeftIncl(id1, id2, key []byte) bool

BetweenLeftIncl checks if a key is between two ID, left inclusive

func BetweenRightIncl 

func BetweenRightIncl(id1, id2, key []byte) bool

BetweenRightIncl checks if a key is between two ID, right inclusive

func BigIntToID 

func BigIntToID(i big.Int, m uint32) []byte

BigIntToID converts a big.Int with m bit rate to Chord ID bytes

func CompareID 

func CompareID(id1, id2 []byte) int

CompareID returns -1, 0, 1 if id1 <, =, > id2 respectively

func Distance 

func Distance(a, b []byte, m uint32) *big.Int

Distance gcomputes the forward distance from a to b modulus a ring size

func GetSuccAndPred 

func GetSuccAndPred(remoteNode *node.RemoteNode, numSucc, numPred uint32, msgIDBytes uint8) ([]*pbnode.Node, []*pbnode.Node, error)

GetSuccAndPred sends a GetSuccAndPred message to remote node and returns its successors and predecessor if no error occurred

func IDToBigInt 

func IDToBigInt(id []byte) big.Int

IDToBigInt converts a Chord ID bytes to big.Int

func NewGetSuccAndPredMessage 

func NewGetSuccAndPredMessage(numSucc, numPred uint32, msgIDBytes uint8) (*pbmsg.Message, error)

NewGetSuccAndPredMessage creates a GET_SUCC_AND_PRED message to get the successors and predecessor of a remote node

func NextID 

func NextID(id []byte, m uint32) []byte

NextID computes (id + 1) % (2^m)

func Offset 

func Offset(id []byte, offset *big.Int, m uint32) []byte

Offset computes (id + offset) % (2^m)

func PowerOffset 

func PowerOffset(id []byte, exp uint32, m uint32) []byte

PowerOffset computes (id + 2^exp) % (2^m)

func PrevID 

func PrevID(id []byte, m uint32) []byte

PrevID computes (id - 1) % (2^m)

Types

type BroadcastTreeRouting 

type BroadcastTreeRouting struct {
	*routing.Routing
	// contains filtered or unexported fields
}

BroadcastTreeRouting is for message from a remote node to all other nodes in the network following spanning tree

func NewBroadcastTreeRouting 

func NewBroadcastTreeRouting(localMsgChan chan<- *node.RemoteMessage, rxMsgChan <-chan *node.RemoteMessage, chord *Chord) (*BroadcastTreeRouting, error)

NewBroadcastTreeRouting creates a new BroadcastTreeRouting

func (*BroadcastTreeRouting) GetNodeToRoute 

func (btr *BroadcastTreeRouting) GetNodeToRoute(remoteMsg *node.RemoteMessage) (*node.LocalNode, []*node.RemoteNode, error)

GetNodeToRoute returns the local node and remote nodes to route message to

func (*BroadcastTreeRouting) Start 

func (btr *BroadcastTreeRouting) Start() error

Start starts handling broadcast tree message from rxChan

type Chord 

type Chord struct {
	*overlay.Overlay
	// contains filtered or unexported fields
}

Chord is the overlay network based on Chord DHT

func NewChord 

func NewChord(localNode *node.LocalNode) (*Chord, error)

NewChord creates a Chord overlay network

func (Chord) ApplyMiddleware 

func (store Chord) ApplyMiddleware(mw interface{}) error

ApplyMiddleware add a middleware to the store

func (*Chord) Connect 

func (c *Chord) Connect(n *pbnode.Node) error

Connect connects to a node. The Addr field of the node is required.

func (*Chord) FindPredecessors 

func (c *Chord) FindPredecessors(key []byte, numPred uint32) ([]*pbnode.Node, error)

FindPredecessors sends a FindPredecessors message and returns numPred predecessors of a given key id

func (*Chord) FindSuccAndPred 

func (c *Chord) FindSuccAndPred(key []byte, numSucc, numPred uint32) ([]*pbnode.Node, []*pbnode.Node, error)

FindSuccAndPred sends a FindSuccAndPred message and returns numSucc successors and numPred predecessors of a given key id

func (*Chord) FindSuccessors 

func (c *Chord) FindSuccessors(key []byte, numSucc uint32) ([]*pbnode.Node, error)

FindSuccessors sends a FindSuccessors message and returns numSucc successors of a given key id

func (*Chord) FingerTable 

func (c *Chord) FingerTable() [][]*node.RemoteNode

FingerTable returns the remote nodes in finger table

func (*Chord) FingerTableIdxInRemoteNode 

func (c *Chord) FingerTableIdxInRemoteNode(remoteNodeID []byte) (int, int)

FingerTableIdxInRemoteNode returns the finger table index (index of finger, index in finger) of local node in remote node's finger table. Returns -1 index if local node is not in remote node's finger table.

func (*Chord) Join 

func (c *Chord) Join(seedNodeAddr string) error

Join joins an existing chord network starting from the seedNodeAddr

func (*Chord) MaybeStopRemoteNode 

func (c *Chord) MaybeStopRemoteNode(remoteNode *node.RemoteNode) bool

MaybeStopRemoteNode removes an outbound node that is no longer in successors, predecessor, or finger table

func (*Chord) NewFindSuccAndPredMessage 

func (c *Chord) NewFindSuccAndPredMessage(key []byte, numSucc, numPred uint32) (*pbmsg.Message, error)

NewFindSuccAndPredMessage creates a FIND_SUCC_AND_PRED message to find numSucc successors and numPred predecessors of a key

func (*Chord) NewFindSuccAndPredReply 

func (c *Chord) NewFindSuccAndPredReply(replyToID []byte, successors, predecessors []*pbnode.Node) (*pbmsg.Message, error)

NewFindSuccAndPredReply creates a FIND_SUCC_AND_PRED reply to send successors and predecessors

func (*Chord) NewGetSuccAndPredReply 

func (c *Chord) NewGetSuccAndPredReply(replyToID []byte, successors, predecessors []*pbnode.Node) (*pbmsg.Message, error)

NewGetSuccAndPredReply creates a GET_SUCC_AND_PRED reply to send successors and predecessor

func (*Chord) Predecessors 

func (c *Chord) Predecessors() []*node.RemoteNode

Predecessors returns the remote nodes in predecessor list

func (*Chord) Start 

func (c *Chord) Start(isCreate bool) error

Start starts the runtime loop of the chord network

func (*Chord) Stop 

func (c *Chord) Stop(err error)

Stop stops the chord network

func (*Chord) Successors 

func (c *Chord) Successors() []*node.RemoteNode

Successors returns the remote nodes in succesor list

type FingerTableAdded 

type FingerTableAdded struct {
	Func     func(*node.RemoteNode, int, int) bool
	Priority int32
}

FingerTableAdded is called when a new remote node has been added to the finger table. This does not necessarily mean the remote node has just established a new connection with local node, but may also because another remote node previously in finger table was disconnected or removed. When being called, it will also pass the index of finger table and the index of the remote node in that finger table after it is added. Returns if we should proceed to the next middleware.

type FingerTableRemoved 

type FingerTableRemoved struct {
	Func     func(*node.RemoteNode, int) bool
	Priority int32
}

FingerTableRemoved is called when a remote node has been removed from the finger table. This does not necessarily mean the remote node has just disconnected with local node, but may also because another remote node is added to the finger table. Returns if we should proceed to the next middleware.

type NeighborAdded 

type NeighborAdded struct {
	Func     func(*node.RemoteNode, int) bool
	Priority int32
}

NeighborAdded is called when a new remote node has been added to the neighbor list. When being called, it will also pass the index of the remote node in neighbor list after it is added. Returns if we should proceed to the next middleware.

type NeighborList 

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

NeighborList is a list of nodes with minimal key that is greater than key

func NewNeighborList 

func NewNeighborList(startID, endID []byte, nodeIDBits, maxNumNodes uint32, reversed bool) (*NeighborList, error)

NewNeighborList creates a NeighborList

func (*NeighborList) AddOrReplace 

func (sl *NeighborList) AddOrReplace(remoteNode *node.RemoteNode) (bool, *node.RemoteNode, error)

AddOrReplace add a node to NeighborList, replace an existing one if there are more than maxNumNodes nodes in list. Returns if node is added, the node that is replaced or nil if not, and error if any

func (*NeighborList) Cap 

func (sl *NeighborList) Cap() uint32

Cap returns the maximal number of remote nodes that it can store

func (*NeighborList) Exists 

func (sl *NeighborList) Exists(id []byte) bool

Exists returns if an id is in NeighborList

func (*NeighborList) GetByID 

func (sl *NeighborList) GetByID(id []byte) *node.RemoteNode

GetByID returns the remote node in NeighborList with give id, or nil if no such node exists

func (*NeighborList) GetFirst 

func (sl *NeighborList) GetFirst() *node.RemoteNode

GetFirst returns the remote node in NeighborList that has the smallest distance from/to its startID. This is faster than calling ToRemoteNodeList and then take the first element

func (*NeighborList) GetIndex 

func (sl *NeighborList) GetIndex(id []byte) int

GetIndex returns the index of the node with an id when NeighborList is sorted. Returns -1 if id not found.

func (*NeighborList) GetLast 

func (sl *NeighborList) GetLast() *node.RemoteNode

GetLast returns the remote node in NeighborList that has the greatest distance from/to its startID. This is faster than calling ToRemoteNodeList and then take the last element

func (*NeighborList) IsEmpty 

func (sl *NeighborList) IsEmpty() bool

IsEmpty returns if there is at least one remote node in NeighborList

func (*NeighborList) IsIDInRange 

func (sl *NeighborList) IsIDInRange(id []byte) bool

IsIDInRange returns if id is in the range of NeighborList

func (*NeighborList) Len 

func (sl *NeighborList) Len() uint32

Len returns the number of remote nodes stored in NeighborList

func (*NeighborList) Remove 

func (sl *NeighborList) Remove(remoteNode *node.RemoteNode) bool

Remove remove a node from NeighborList, returns if node is in NeighborList

func (*NeighborList) SetMaxNumNodes 

func (sl *NeighborList) SetMaxNumNodes(maxNumNodes uint32)

SetMaxNumNodes changes the maximal number of remote nodes that it can store

func (*NeighborList) ToProtoNodeList 

func (sl *NeighborList) ToProtoNodeList(sorted bool) []*pbnode.Node

ToProtoNodeList returns a list of protobuf.Node that are in NeighborList

func (*NeighborList) ToRemoteNodeList 

func (sl *NeighborList) ToRemoteNodeList(sorted bool) []*node.RemoteNode

ToRemoteNodeList returns a list of RemoteNode that are in NeighborList

type NeighborRemoved 

type NeighborRemoved struct {
	Func     func(*node.RemoteNode) bool
	Priority int32
}

NeighborRemoved is called when a remote node has been removed from the neighbor list. Returns if we should proceed to the next middleware.

type PredecessorAdded 

type PredecessorAdded struct {
	Func     func(*node.RemoteNode, int) bool
	Priority int32
}

PredecessorAdded is called when a new remote node has been added to the predecessor list. This does not necessarily mean the remote node has just established a new connection with local node, but may also because another remote node previously in predecessor list was disconnected or removed. When being called, it will also pass the index of the remote node in predecessor list after it is added. Returns if we should proceed to the next middleware.

type PredecessorRemoved 

type PredecessorRemoved struct {
	Func     func(*node.RemoteNode) bool
	Priority int32
}

PredecessorRemoved is called when a remote node has been removed from the predecessor list. This does not necessarily mean the remote node has just disconnected with local node, but may also because another remote node is added to the predecessor list. Returns if we should proceed to the next middleware.

type RelayPriority 

type RelayPriority struct {
	Func     func(*node.RemoteNode, float64) (float64, bool)
	Priority int32
}

RelayPriority is called when computing the priority of next hop candidate. Node that has the highest priority value will be selected. Initial priority is negative latency in unit of ms. When being called, it will also pass the current priority value. Returns the new priority value and whether we should proceed to the next middleware.

type RelayRouting 

type RelayRouting struct {
	*routing.Routing
	// contains filtered or unexported fields
}

RelayRouting is for message from a remote node to another remote node or local node

func NewRelayRouting 

func NewRelayRouting(localMsgChan chan<- *node.RemoteMessage, rxMsgChan <-chan *node.RemoteMessage, chord *Chord) (*RelayRouting, error)

NewRelayRouting creates a new RelayRouting

func (*RelayRouting) GetNodeToRoute 

func (rr *RelayRouting) GetNodeToRoute(remoteMsg *node.RemoteMessage) (*node.LocalNode, []*node.RemoteNode, error)

GetNodeToRoute returns the local node and remote nodes to route message to

func (*RelayRouting) Start 

func (rr *RelayRouting) Start() error

Start starts handling relay message from rxChan

type SuccessorAdded 

type SuccessorAdded struct {
	Func     func(*node.RemoteNode, int) bool
	Priority int32
}

SuccessorAdded is called when a new remote node has been added to the successor list. This does not necessarily mean the remote node has just established a new connection with local node, but may also because another remote node previously in successor list was disconnected or removed. When being called, it will also pass the index of the remote node in successor list after it is added. Returns if we should proceed to the next middleware.

type SuccessorRemoved 

type SuccessorRemoved struct {
	Func     func(*node.RemoteNode) bool
	Priority int32
}

SuccessorRemoved is called when a remote node has been removed from the successor list. This does not necessarily mean the remote node has just disconnected with local node, but may also because another remote node is added to the successor list. Returns if we should proceed to the next middleware.

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.