Documentation
¶
Overview ¶
Package store pkg/deployment/rf/store/finder.go c2-net-routing
Package store pkg/deployment/rf/store/graph_cache.go c2-net-routing
Package store pkg/deployment/rf/store/graph_full.go c2-net-routing
Package store pkg/deployment/rf/store/landmark.go c2-net-routing
Landmark (transit-node) routing for the route-finder. The base route-finder answers each (src,dst) with a bounded but EXHAUSTIVE BFS over the whole dense transport graph; on the live network a single far/hard pair has been measured at ~8.4s of CPU and pegs the RF host. #4380 (cached graph) and #4385 (per-graph result memo) removed the per-request graph BUILD and the REPEAT BFS, but the first search of any pair is still exhaustive.
This exploits the mesh's structure: a handful of very-high-degree hubs (magnetosphere/prod02/the production exit carry ~1200-1300 transports each vs ~70-120 for a normal node) that most routes already transit, plus deterministic tpids and durable topology (see rf-landmark-routing-rfc.md). We precompute routes between every node and those hubs ONCE per graph, then answer a far (src,dst) by COMPOSING src->hub + hub->dst — ~H*K*K cheap concatenations instead of a graph-wide search.
It is a strict addition: a pair the (budget-bounded) direct BFS resolves cheaply keeps its optimal exhaustive answer; only the pairs that blow past the budget — the multi-second cases that peg the RF — fall to composition, and a composition miss still falls through to the full BFS. Coexists with #4380 and #4385 (the memo caches composed results exactly as it caches BFS results).
Package store pkg/deployment/rf/store/mark_and_sweep.go c2-net-routing
Index ¶
- Constants
- Variables
- func SetLandmarkRouting(on bool)
- type Graph
- func (g *Graph) GetRoute(ctx context.Context, source, destination cipher.PubKey, ...) ([]routing.Route, error)
- func (g *Graph) GetRouteWeighted(ctx context.Context, source, destination cipher.PubKey, ...) ([]routing.Route, error)
- func (g *Graph) MarkAndSweep(ctx context.Context, rootPK cipher.PubKey) ([]cipher.PubKey, error)
- func (g *Graph) Size() (visors, transports int)
- func (g *Graph) StreamRoutes(ctx context.Context, source, destination cipher.PubKey, minLen, maxLen int, ...) error
- func (g *Graph) StreamRoutesWithCap(ctx context.Context, source, destination cipher.PubKey, ...) error
- func (g *Graph) Sweep() []cipher.PubKey
- type GraphCache
Constants ¶
const DefaultCacheRefresh = 15 * time.Second
DefaultCacheRefresh is how old the graph may get before a request triggers a rebuild, when none is given.
const DefaultMaxBFSQueue = 200000
DefaultMaxBFSQueue is the default per-call BFS queue cap when the caller of StreamRoutesWithCap passes 0 / negative. Conservative enough to fit comfortably on a CLI/visor without OOMing dense networks at high --max.
const HopLatencyPenaltyMS = 500.0
HopLatencyPenaltyMS is the latency assumed for a transport that has no measured latency. It keeps latency-weighted routing usable when data is missing: an unmeasured edge is treated as worse than a typical measured one (so measured low-latency edges win), and a route of all-unmeasured edges is effectively ranked by hop count (number of hops × penalty) — degrading to the legacy behavior rather than treating missing data as free.
Variables ¶
var ( //ErrNoRoute no route to destination ErrNoRoute = errors.New("no route to destination") //ErrContextClosed context closed or timed out ErrContextClosed = errors.New("context closed or timed out") //ErrRouteNotFound route not found ErrRouteNotFound = errors.New("route not found") )
var MaxGraphDepth = 10
MaxGraphDepth limits how deep the graph exploration goes from the root. This prevents OOM on large networks. Used as default by NewGraph.
Functions ¶
func SetLandmarkRouting ¶
func SetLandmarkRouting(on bool)
SetLandmarkRouting turns landmark routing on or off for every graph.
Types ¶
type Graph ¶
type Graph struct {
// contains filtered or unexported fields
}
Graph represents a visor's connections graph (skywire network)
func NewGraph ¶
NewGraph creates a new Graph accessing given transport store, such Graph is created by exploring from rootPK cipher PubKey. Uses MaxGraphDepth for depth limiting.
func NewGraphWithDepth ¶
func NewGraphWithDepth(ctx context.Context, s store.Store, rootPK cipher.PubKey, maxDepth int) (*Graph, error)
NewGraphWithDepth creates a new Graph with an explicit depth limit for exploration.
func (*Graph) GetRoute ¶
func (g *Graph) GetRoute(ctx context.Context, source, destination cipher.PubKey, minLen, maxLen, number int) ([]routing.Route, error)
GetRoute returns routes from source to destination with hop counts within [minLen, maxLen], prioritized by shortest hop count first, with no duplicate vertices in the route.
Bounded variant: stops the BFS as soon as `number` valid routes have been collected. Use StreamRoutes for the unbounded streaming form when memory matters more than the convenience of a slice.
func (*Graph) GetRouteWeighted ¶
func (g *Graph) GetRouteWeighted(ctx context.Context, source, destination cipher.PubKey, minLen, maxLen, number int, byLatency bool) ([]routing.Route, error)
GetRouteWeighted returns up to `number` routes source→destination, memoized per Graph. The exhaustive BFS over the (dense) transport graph is expensive — seconds per request for well-connected pairs — and the fleet re-asks for the same pairs constantly (session churn), so without a cache the route-finder re-runs an identical search on every repeat. The memo collapses those to one BFS per unique request for the life of this graph, and its sync.Once also deduplicates a concurrent thundering herd of identical requests into a single search rather than N. Failures are not cached (the entry is dropped) so a transient miss can be retried immediately; only successful route sets persist, until the next graph rebuild swaps in a fresh (empty) memo. Callers must treat the returned slice as read-only.
func (*Graph) MarkAndSweep ¶
MarkAndSweep explores the Graph again from rootPK. It returns the now unreachable nodes pks by comparing with the previous Graph
func (*Graph) Size ¶ added in v1.3.100
Size is how many visors the graph holds and how many transports join them.
func (*Graph) StreamRoutes ¶
func (g *Graph) StreamRoutes(ctx context.Context, source, destination cipher.PubKey, minLen, maxLen int, onRoute func(routing.Route) bool) error
StreamRoutes is the streaming form of GetRoute: it yields each valid path as soon as the BFS finds it, by invoking onRoute. Returning false from onRoute stops the search.
Equivalent to StreamRoutesWithCap with the default queue cap.
func (*Graph) StreamRoutesWithCap ¶
func (g *Graph) StreamRoutesWithCap(ctx context.Context, source, destination cipher.PubKey, minLen, maxLen, queueCap int, onRoute func(routing.Route) bool) error
StreamRoutesWithCap is StreamRoutes with an explicit per-call queue cap. queueCap <= 0 means unbounded (use with caution; dense graphs at high maxLen can OOM).
BFS naturally explores by increasing hop length, so paths are emitted in shortest-first order — no post-search sort is needed, and the caller can stop after collecting enough short paths without paying for deeper exploration.
Memory: the working set is the BFS queue + the path being emitted; we never accumulate every valid path. The queue itself is capped by queueCap, so even count=0 (unbounded) requests have a hard memory ceiling. When the cap is hit, neighbor expansion is suppressed — already-queued paths still drain and emit, but new branches are dropped, so coverage degrades while the process stays alive.
type GraphCache ¶
type GraphCache struct {
// contains filtered or unexported fields
}
GraphCache holds ONE full-network graph, shared across every route request. This removes the per-request, per-source graph construction the route-finder did before — a redis walk that issued a GetTransportsByEdge for every node it discovered from the source, which pegged both the route-finder and redis under load. The cached graph is read-only during a BFS (StreamRoutes never mutates it), so many requests can share it concurrently; a rebuild constructs a fresh graph and swaps the pointer atomically, leaving in-flight requests on the previous one until they finish.
Once started, the graph is rebuilt when a request finds it older than the refresh interval, not on a timer. Rebuilding every 15 s over 93k transports while serving about 10 queries a minute was most of the route finder's CPU and allocation (audit 2026-10-16). A request that finds the graph stale is answered from it while one rebuild runs in the background; only a graph older than staleAfter is rebuilt before answering, so an idle route finder does not route on an old graph.
func NewGraphCache ¶
func NewGraphCache(s store.Store, refresh time.Duration, log logrus.FieldLogger) *GraphCache
NewGraphCache returns an unstarted cache. Call Run (usually in a goroutine) to build it and let requests keep it fresh, or Rebuild once for a synchronous build. Until the first build completes Get returns nil and callers should fall back to a per-request build.
func (*GraphCache) Current ¶
func (c *GraphCache) Current() *Graph
Current returns the graph as last built, never rebuilding it.
func (*GraphCache) Get ¶
func (c *GraphCache) Get() *Graph
Get returns the current full graph, or nil before the first build. On a started cache a graph older than the refresh interval is rebuilt: in the background, or first when it is older than staleFactor intervals.
func (*GraphCache) Rebuild ¶
func (c *GraphCache) Rebuild(ctx context.Context) (*Graph, error)
Rebuild reads the transport set once and swaps in a freshly built full graph. On a read error the previous graph is kept and the error returned.
func (*GraphCache) Run ¶
func (c *GraphCache) Run(ctx context.Context)
Run builds the graph immediately and starts the cache: from then on requests rebuild it when stale (see Get), until ctx is done. A failed initial build is logged, and the next request tries again.
func (*GraphCache) ShareFrom ¶ added in v1.3.99
func (c *GraphCache) ShareFrom(url string)
ShareFrom makes the cache build from the live transport set of a TPD in this process that writes to the redis at url, when there is one — no redis read per rebuild. Call before Run.
Source Files