routing

package
v0.0.0-...-e07b07e Latest Latest
Warning

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

 Go to latest Published: Apr 19, 2024 License: Apache-2.0, MIT Imports: 17 Imported by: 0

Documentation

Index

Constants

View Source 
const BootstrapQueryID = coordt.QueryID("bootstrap")

BootstrapQueryID is the id for the query operated by the bootstrap process

View Source 
const ExploreQueryID = coordt.QueryID("explore")

ExploreQueryID is the id for the query operated by the explore process

Variables

This section is empty.

Functions

func NewNodeValueList 

func NewNodeValueList[K kad.Key[K], N kad.NodeID[K]]() *nodeValueList[K, N]

Types

type Bootstrap 

type Bootstrap[K kad.Key[K], N kad.NodeID[K]] struct {
	// contains filtered or unexported fields
}

func NewBootstrap 

func NewBootstrap[K kad.Key[K], N kad.NodeID[K]](self N, cfg *BootstrapConfig) (*Bootstrap[K, N], error)

func (*Bootstrap[K, N]) Advance 

func (b *Bootstrap[K, N]) Advance(ctx context.Context, ev BootstrapEvent) (out BootstrapState)

Advance advances the state of the bootstrap by attempting to advance its query if running.

type BootstrapConfig 

type BootstrapConfig struct {
	Timeout            time.Duration // the time to wait before terminating a query that is not making progress
	RequestConcurrency int           // the maximum number of concurrent requests that each query may have in flight
	RequestTimeout     time.Duration // the timeout queries should use for contacting a single node
	Clock              clock.Clock   // a clock that may replaced by a mock when testing

	// Tracer is the tracer that should be used to trace execution.
	Tracer trace.Tracer

	// Meter is the meter that should be used to record metrics.
	Meter metric.Meter
}

BootstrapConfig specifies optional configuration for a Bootstrap

func DefaultBootstrapConfig 

func DefaultBootstrapConfig() *BootstrapConfig

DefaultBootstrapConfig returns the default configuration options for a Bootstrap. Options may be overridden before passing to NewBootstrap

func (*BootstrapConfig) Validate 

func (cfg *BootstrapConfig) Validate() error

Validate checks the configuration options and returns an error if any have invalid values.

type BootstrapEvent 

type BootstrapEvent interface {
	// contains filtered or unexported methods
}

BootstrapEvent is an event intended to advance the state of a bootstrap.

type BootstrapState 

type BootstrapState interface {
	// contains filtered or unexported methods
}

BootstrapState is the state of a bootstrap.

type DynamicExploreSchedule 

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

A DynamicExploreSchedule calculates an explore schedule dynamically

func NewDynamicExploreSchedule 

func NewDynamicExploreSchedule(maxCpl int, start time.Time, interval time.Duration, multiplier float64, jitter float64) (*DynamicExploreSchedule, error)

NewDynamicExploreSchedule creates a new dynamic explore schedule.

maxCpl is the maximum CPL (common prefix length) that will be scheduled. interval is the base time interval to leave between explorations of the same CPL. multiplier is a factor that is applied to interval for CPLs lower than the maximum to increase the interval between explorations for lower CPLs (which contain nodes that are more distant). jitter is a factor that is used to increase the calculated interval for the next explore operation by a small random amount. It must be between 0 and 0.05. When zero, no jitter is applied.

The interval to the next explore is calculated using the following formula: 

interval + (maxCpl - CPL) x interval x multiplier + interval * rand(jitter)

For example, given an a max CPL of 14, an interval of 1 hour, a multiplier of 1 and 0 jitter the following schedule will be created: 

CPL 14 explored every hour
CPL 13 explored every two hours
CPL 12 explored every three hours
...
CPL 0 explored every 14 hours

For example, given an a max CPL of 14, an interval of 1 hour, a multiplier of 1.5 and 0.01 jitter the following schedule will be created: 

CPL 14 explored every 1 hour + up to 6 minutes random jitter
CPL 13 explored every 2.5 hours + up to 6 minutes random jitter
CPL 12 explored every 4 hours + up to 6 minutes random jitter
...
CPL 0 explored every 22 hours + up to 6 minutes random jitter

func (*DynamicExploreSchedule) NextCpl 

func (s *DynamicExploreSchedule) NextCpl(ts time.Time) (int, bool)

type EventBootstrapFindCloserFailure 

type EventBootstrapFindCloserFailure[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N     // the node the message was sent to
	Error  error // the error that caused the failure, if any
}

EventBootstrapFindCloserFailure notifies a bootstrap that an attempt to find closer nodes has failed.

type EventBootstrapFindCloserResponse 

type EventBootstrapFindCloserResponse[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID      N   // the node the message was sent to
	CloserNodes []N // the closer nodes sent by the node
}

EventBootstrapFindCloserResponse notifies a bootstrap that an attempt to find closer nodes has received a successful response.

type EventBootstrapPoll 

type EventBootstrapPoll struct{}

EventBootstrapPoll is an event that signals the bootstrap that it can perform housekeeping work such as time out queries.

type EventBootstrapStart 

type EventBootstrapStart[K kad.Key[K], N kad.NodeID[K]] struct {
	KnownClosestNodes []N
}

EventBootstrapStart is an event that attempts to start a new bootstrap

type EventExploreFindCloserFailure 

type EventExploreFindCloserFailure[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N     // the node the message was sent to
	Error  error // the error that caused the failure, if any
}

EventExploreFindCloserFailure notifies a explore that an attempt to find closer nodes has failed.

type EventExploreFindCloserResponse 

type EventExploreFindCloserResponse[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID      N   // the node the message was sent to
	CloserNodes []N // the closer nodes sent by the node
}

EventExploreFindCloserResponse notifies a explore that an attempt to find closer nodes has received a successful response.

type EventExplorePoll 

type EventExplorePoll struct{}

EventExplorePoll is an event that signals the explore that it can perform housekeeping work such as time out queries.

type EventIncludeAddCandidate 

type EventIncludeAddCandidate[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N // the candidate node
}

EventIncludeAddCandidate notifies an Include that a node should be added to the candidate list.

type EventIncludeConnectivityCheckFailure 

type EventIncludeConnectivityCheckFailure[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N     // the node the message was sent to
	Error  error // the error that caused the failure, if any
}

EventIncludeConnectivityCheckFailure notifies an Include that a requested connectivity check has failed.

type EventIncludeConnectivityCheckSuccess 

type EventIncludeConnectivityCheckSuccess[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N // the node the message was sent to
}

EventIncludeConnectivityCheckSuccess notifies an Include that a requested connectivity check has received a successful response.

type EventIncludePoll 

type EventIncludePoll struct{}

EventIncludePoll is an event that signals an Include to perform housekeeping work such as time out queries.

type EventProbeAdd 

type EventProbeAdd[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N // the node to be probed
}

EventProbeAdd notifies a probe that a node should be added to its list of nodes.

type EventProbeConnectivityCheckFailure 

type EventProbeConnectivityCheckFailure[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N     // the node the message was sent to
	Error  error // the error that caused the failure, if any
}

EventProbeConnectivityCheckFailure notifies a Probe that a requested connectivity check has failed.

type EventProbeConnectivityCheckSuccess 

type EventProbeConnectivityCheckSuccess[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N // the node the message was sent to
}

EventProbeConnectivityCheckSuccess notifies a Probe that a requested connectivity check has received a successful response.

type EventProbeNotifyConnectivity 

type EventProbeNotifyConnectivity[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N
}

EventProbeNotifyConnectivity notifies a probe that a node has confirmed connectivity from another source such as a query.

type EventProbePoll 

type EventProbePoll struct{}

EventProbePoll is an event that signals the probe that it can perform housekeeping work such as time out queries.

type EventProbeRemove 

type EventProbeRemove[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N // the node to be removed
}

EventProbeRemove notifies a probe that a node should be removed from its list of nodes and the routing table.

type Explore 

type Explore[K kad.Key[K], N kad.NodeID[K]] struct {
	// contains filtered or unexported fields
}

The Explore state machine is used to discover new nodes at various distances from the local node in order to improve the occupancy of routing table buckets.

For each bucket a random key is generated that would occupy the bucket and a query initiated to find the nodes close to it. Dicovered nodes are added to the candidate queue for inclusion in the routing table. During the course of the query discovered nodes may result in being included in buckets other than the one being processed.

The explore operation processes buckets in order of distance from the local node and waits for query completion before proceeding to the next bucket.

The frequency of running an explore varies by bucket distance, such that closer buckets are processed more frequently.

func NewExplore 

func NewExplore[K kad.Key[K], N kad.NodeID[K]](self N, rt RoutingTableCpl[K, N], cplFn NodeIDForCplFunc[K, N], schedule ExploreSchedule, cfg *ExploreConfig) (*Explore[K, N], error)

func (*Explore[K, N]) Advance 

func (e *Explore[K, N]) Advance(ctx context.Context, ev ExploreEvent) (out ExploreState)

Advance advances the state of the explore by attempting to advance its query if running.

type ExploreConfig 

type ExploreConfig struct {
	// Clock is  a clock that may replaced by a mock when testing
	Clock clock.Clock

	// Tracer is the tracer that should be used to trace execution.
	Tracer trace.Tracer

	// Meter is the meter that should be used to record metrics.
	Meter metric.Meter

	// Timeout is maximum time to allow for performing an explore for a CPL.
	Timeout time.Duration

	RequestConcurrency int           // the maximum number of concurrent requests that each query may have in flight
	RequestTimeout     time.Duration // the timeout queries should use for contacting a single node
}

ExploreConfig specifies optional configuration for an Explore

func DefaultExploreConfig 

func DefaultExploreConfig() *ExploreConfig

DefaultExploreConfig returns the default configuration options for an Explore. Options may be overridden before passing to NewExplore.

func (*ExploreConfig) Validate 

func (cfg *ExploreConfig) Validate() error

Validate checks the configuration options and returns an error if any have invalid values.

type ExploreEvent 

type ExploreEvent interface {
	// contains filtered or unexported methods
}

ExploreEvent is an event intended to advance the state of an Explore.

type ExploreSchedule 

type ExploreSchedule interface {
	// NextCpl returns the first cpl to be explored whose due time is before or equal to the given time.
	// The due time of the cpl should be updated by its designated interval so that its next due time is increased.
	// If no cpl is due at the given time NextCpl should return -1, false
	NextCpl(ts time.Time) (int, bool)
}

An ExploreSchedule provides an ordering for explorations of each cpl in a routing table.

type ExploreState 

type ExploreState interface {
	// contains filtered or unexported methods
}

ExploreState is the state of an Explore.

type Include 

type Include[K kad.Key[K], N kad.NodeID[K]] struct {
	// contains filtered or unexported fields
}

func NewInclude 

func NewInclude[K kad.Key[K], N kad.NodeID[K]](rt kad.RoutingTable[K, N], cfg *IncludeConfig) (*Include[K, N], error)

func (*Include[K, N]) Advance 

func (in *Include[K, N]) Advance(ctx context.Context, ev IncludeEvent) (out IncludeState)

Advance advances the state of the include state machine by attempting to advance its query if running.

type IncludeConfig 

type IncludeConfig struct {
	QueueCapacity int           // the maximum number of nodes that can be in the candidate queue
	Concurrency   int           // the maximum number of include checks that may be in progress at any one time
	Timeout       time.Duration // the time to wait before terminating a check that is not making progress
	Clock         clock.Clock   // a clock that may replaced by a mock when testing

	// Tracer is the tracer that should be used to trace execution.
	Tracer trace.Tracer

	// Meter is the meter that should be used to record metrics.
	Meter metric.Meter
}

IncludeConfig specifies optional configuration for an Include

func DefaultIncludeConfig 

func DefaultIncludeConfig() *IncludeConfig

DefaultIncludeConfig returns the default configuration options for an Include. Options may be overridden before passing to NewInclude

func (*IncludeConfig) Validate 

func (cfg *IncludeConfig) Validate() error

Validate checks the configuration options and returns an error if any have invalid values.

type IncludeEvent 

type IncludeEvent interface {
	// contains filtered or unexported methods
}

IncludeEvent is an event intended to advance the state of an Include.

type IncludeState 

type IncludeState interface {
	// contains filtered or unexported methods
}

IncludeState is the state of a include.

type NoWaitExploreSchedule 

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

A NoWaitExploreSchedule implements an explore schedule that cycles through each cpl without delays

func NewNoWaitExploreSchedule 

func NewNoWaitExploreSchedule(maxCpl int) *NoWaitExploreSchedule

func (*NoWaitExploreSchedule) NextCpl 

func (n *NoWaitExploreSchedule) NextCpl(ts time.Time) (int, bool)

type NodeIDForCplFunc 

type NodeIDForCplFunc[K kad.Key[K], N kad.NodeID[K]] func(k K, cpl int) (N, error)

NodeIDForCplFunc is a function that given a cpl generates a kad.NodeID with a key that has a common prefix length with k of length cpl. Invariant: CommonPrefixLength(k, node.Key()) = cpl

type Probe 

type Probe[K kad.Key[K], N kad.NodeID[K]] struct {
	// contains filtered or unexported fields
}

The Probe state machine performs regular connectivity checks for nodes in a routing table.

The state machine is notified of a new entry in the routing table via the EventProbeAdd event. This adds the node to an internal list and sets a time for a check to be performed, based on the current time plus a configurable interval.

Connectivity checks are performed in time order, so older nodes are processed first. The connectivity check performed is the same as for the Include state machine: ask the node for closest nodes to itself and confirm that the node returns at least one node in the list of closer nodes. The state machine emits the StateProbeConnectivityCheck state when it wants to check the status of a node.

The state machine expects to be notified either with the EventProbeConnectivityCheckSuccess or the [EventProbeConnectivityCheckSuccessFailure] events to determine the outcome of the check. If neither are received within a configurable timeout the node is marked as failed.

Nodes that receive a successful response have their next check time updated to the current time plus the configured [ProbeConfig.CheckInterval].

Nodes that fail a connectivity check, or are timed out, are removed from the routing table and from the list of nodes to check. The state machine emits the StateProbeNodeFailure state to notify callers of this event.

The state machine accepts a EventProbePoll event to check for outstanding work such as initiating a new check or timing out an existing one.

The EventProbeRemove event may be used to remove a node from the check list and from the routing table.

The state machine accepts the EventProbeNotifyConnectivity event as a notification that an external system has performed a suitable connectivity check, such as when the node responds to a query. The probe state machine treats these events as if a successful response had been received from a check by advancing the time of the next check.

func NewProbe 

func NewProbe[K kad.Key[K], N kad.NodeID[K]](rt RoutingTableCpl[K, N], cfg *ProbeConfig) (*Probe[K, N], error)

func (*Probe[K, N]) Advance 

func (p *Probe[K, N]) Advance(ctx context.Context, ev ProbeEvent) (out ProbeState)

Advance advances the state of the probe state machine by attempting to advance its query if running.

type ProbeConfig 

type ProbeConfig struct {
	CheckInterval time.Duration // the minimum time interval between checks for a node
	Concurrency   int           // the maximum number of probe checks that may be in progress at any one time
	Timeout       time.Duration // the time to wait before terminating a check that is not making progress
	Clock         clock.Clock   // a clock that may be replaced by a mock when testing

	// Tracer is the tracer that should be used to trace execution.
	Tracer trace.Tracer

	// Meter is the meter that should be used to record metrics.
	Meter metric.Meter
}

ProbeConfig specifies optional configuration for a Probe

func DefaultProbeConfig 

func DefaultProbeConfig() *ProbeConfig

DefaultProbeConfig returns the default configuration options for a Probe. Options may be overridden before passing to NewProbe

func (*ProbeConfig) Validate 

func (cfg *ProbeConfig) Validate() error

Validate checks the configuration options and returns an error if any have invalid values.

type ProbeEvent 

type ProbeEvent interface {
	// contains filtered or unexported methods
}

ProbeEvent is an event intended to advance the state of a probe.

type ProbeState 

type ProbeState interface {
	// contains filtered or unexported methods
}

ProbeState is the state of the Probe state machine.

type RoutingTableCpl 

type RoutingTableCpl[K kad.Key[K], N kad.NodeID[K]] interface {
	kad.RoutingTable[K, N]

	// Cpl returns the longest common prefix length the supplied key shares with the table's key.
	Cpl(kk K) int

	// CplSize returns the number of nodes in the table whose longest common prefix with the table's key is of length cpl.
	CplSize(cpl int) int
}

type StateBootstrapFindCloser 

type StateBootstrapFindCloser[K kad.Key[K], N kad.NodeID[K]] struct {
	QueryID coordt.QueryID
	Target  K // the key that the query wants to find closer nodes for
	NodeID  N // the node to send the message to
	Stats   query.QueryStats
}

StateBootstrapFindCloser indicates that the bootstrap query wants to send a find closer nodes message to a node.

type StateBootstrapFinished 

type StateBootstrapFinished struct {
	Stats query.QueryStats
}

StateBootstrapFinished indicates that the bootstrap has finished.

type StateBootstrapIdle 

type StateBootstrapIdle struct{}

StateBootstrapIdle indicates that the bootstrap is not running its query.

type StateBootstrapTimeout 

type StateBootstrapTimeout struct {
	Stats query.QueryStats
}

StateBootstrapTimeout indicates that the bootstrap query has timed out.

type StateBootstrapWaiting 

type StateBootstrapWaiting struct {
	Stats query.QueryStats
}

StateBootstrapWaiting indicates that the bootstrap query is waiting for a response.

type StateExploreFailure 

type StateExploreFailure struct {
	Cpl   int // the cpl being explored
	Error error
}

StateExploreFailure indicates that the explore state machine encountered a failure condition when attempting to explore a cpl.

type StateExploreFindCloser 

type StateExploreFindCloser[K kad.Key[K], N kad.NodeID[K]] struct {
	Cpl     int // the cpl being explored
	QueryID coordt.QueryID
	Target  K // the key that the query wants to find closer nodes for
	NodeID  N // the node to send the message to
	Stats   query.QueryStats
}

StateExploreFindCloser indicates that the explore query wants to send a find closer nodes message to a node.

type StateExploreIdle 

type StateExploreIdle struct{}

StateExploreIdle indicates that the explore is not running its query.

type StateExploreQueryFinished 

type StateExploreQueryFinished struct {
	Cpl   int // the cpl being explored
	Stats query.QueryStats
}

StateExploreQueryFinished indicates that an explore query has finished.

type StateExploreQueryTimeout 

type StateExploreQueryTimeout struct {
	Cpl   int // the cpl being explored
	Stats query.QueryStats
}

StateExploreQueryTimeout indicates that an explore query has timed out.

type StateExploreWaiting 

type StateExploreWaiting struct {
	Cpl   int // the cpl being explored
	Stats query.QueryStats
}

StateExploreWaiting indicates that the explore query is waiting for a response.

type StateIncludeConnectivityCheck 

type StateIncludeConnectivityCheck[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N // the node to send the message to
}

StateIncludeConnectivityCheck indicates that an Include is waiting to send a connectivity check to a node. A find node message should be sent to the node, with the target being the node's key.

type StateIncludeIdle 

type StateIncludeIdle struct{}

StateIncludeIdle indicates that an Include is not peforming any work or waiting for any responses..

type StateIncludeRoutingUpdated 

type StateIncludeRoutingUpdated[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N
}

StateIncludeRoutingUpdated indicates the routing table has been updated with a new node.

type StateIncludeWaitingAtCapacity 

type StateIncludeWaitingAtCapacity struct{}

StateIncludeWaitingAtCapacity indicates that an Include is waiting for responses for checks and that the maximum number of concurrent checks has been reached.

type StateIncludeWaitingFull 

type StateIncludeWaitingFull struct{}

StateIncludeWaitingFull indicates that the include subsystem is waiting for responses for checks and that the maximum number of queued candidates has been reached.

type StateIncludeWaitingWithCapacity 

type StateIncludeWaitingWithCapacity struct{}

StateIncludeWaitingWithCapacity indicates that an Include is waiting for responses for checks but has capacity to perform more.

type StateProbeConnectivityCheck 

type StateProbeConnectivityCheck[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N // the node to send the message to
}

StateProbeConnectivityCheck indicates that the probe subsystem is waiting to send a connectivity check to a node. A find node message should be sent to the node, with the target being the node's key.

type StateProbeIdle 

type StateProbeIdle struct{}

StateProbeIdle indicates that the probe state machine is not running any checks.

type StateProbeNodeFailure 

type StateProbeNodeFailure[K kad.Key[K], N kad.NodeID[K]] struct {
	NodeID N
}

StateProbeNodeFailure indicates a node has failed a connectivity check been removed from the routing table and the probe list

type StateProbeWaitingAtCapacity 

type StateProbeWaitingAtCapacity struct{}

StateProbeWaitingAtCapacity indicates that the probe state machine is waiting for responses for checks and the maximum number of concurrent checks has been reached.

type StateProbeWaitingWithCapacity 

type StateProbeWaitingWithCapacity struct{}

StateProbeWaitingWithCapacity indicates that the probe state machine is waiting for responses for checks but has capacity to perform more.

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.