routing

type Bootstrap ¶

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

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

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

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() *BootstrapConfig

func (cfg *BootstrapConfig) Validate() error

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(maxCpl int, start time.Time, interval time.Duration, multiplier float64, jitter float64) (*DynamicExploreSchedule, error)

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

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

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 (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[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 (e *Explore[K, N]) Advance(ctx context.Context, ev ExploreEvent) (out ExploreState)

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() *ExploreConfig

func (cfg *ExploreConfig) Validate() error

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[K kad.Key[K], N kad.NodeID[K]](rt kad.RoutingTable[K, N], cfg *IncludeConfig) (*Include[K, N], error)

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

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() *IncludeConfig

func (cfg *IncludeConfig) Validate() error

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(maxCpl int) *NoWaitExploreSchedule

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[K kad.Key[K], N kad.NodeID[K]](rt RoutingTableCpl[K, N], cfg *ProbeConfig) (*Probe[K, N], error)

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

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() *ProbeConfig

func (cfg *ProbeConfig) Validate() error

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.