Documentation
¶
Overview ¶
Package frontier is the in-partition crawl frontier: the bounded-memory Mercator-style queue that turns a partition's URL records into a stream of dispatch decisions in priority-then-politeness order. It owns the front banks (priority queues that decide what to crawl next) and the back banks (per-host FIFOs that enforce one in-flight fetch per host), the host heap keyed by each host's next-eligible time, and the scheduler loop that drains them against a stub or real fetcher.
This is the M1 milestone. The package is a placeholder until then so the layout the spec pins exists from the first commit.
Package frontier is meguri's scheduler: the decision layer that holds the set of URLs to crawl and answers, at every moment, which URL to fetch next. It sits between ami (網), which fetches bytes, and tsumugi (紡), which stores and ranks them, and it never touches the network itself. It hands a fetch.Fetcher a Request and consumes the meguri.Outcome that comes back (D18).
This is the M1 engine: a single partition, fully resident, implementing the Mercator model of doc 05. URLs enter a front bank ordered by priority (D4). A distributor binds them to per-host back queues, one in flight per host. A host heap parks hosts whose politeness window is closed and a ready bank holds hosts that may dispatch now, ordered by their best URL. Dispatch therefore honors two rules at once: never fetch from a host inside its minimum interval, and among hosts that may be fetched, always prefer the higher-priority URL.
The resident state is bounded by the number of active hosts, not by the size of the frontier: at most `target` hosts hold a back queue at any time, and the rest of the URLs wait in the front bank. A checkpoint serializes the whole engine into a .meguri partition (D1, D12) and a recovery rebuilds an identical scheduler, so the dispatch sequence survives a restart unchanged.
Index ¶
- func HostOf(u string) string
- func PathOf(u string) string
- type Dispatched
- type DueURL
- type Frontier
- func (f *Frontier) Checkpoint() *format.Partition
- func (f *Frontier) CheckpointBytes() ([]byte, error)
- func (f *Frontier) Discover(d meguri.Discovery, now uint32) bool
- func (f *Frontier) Dispatch(now uint32) (fetch.Request, bool)
- func (f *Frontier) DispatchShard(now uint32, shard int) (fetch.Request, bool)
- func (f *Frontier) Drain(ctx context.Context, start uint32, fr fetch.Fetcher) ([]Dispatched, error)
- func (f *Frontier) DueURLs(before uint32, host uint64, limit int) []DueURL
- func (f *Frontier) ImportHostSignal(h meguri.HostSignal)
- func (f *Frontier) ImportURLSignal(u meguri.URLSignal)
- func (f *Frontier) Len() int
- func (f *Frontier) NextEligible() (uint32, bool)
- func (f *Frontier) Pending() int
- func (f *Frontier) Prioritizer() *prioritize.Prioritizer
- func (f *Frontier) Report(o meguri.Outcome, now uint32)
- func (f *Frontier) Seed(url, host string, priority float32, firstSeen, nextDue uint32, ...)
- func (f *Frontier) SeedBatch(seeds []SeedSpec)
- func (f *Frontier) Stats(now uint32) Stats
- func (f *Frontier) Warm(key meguri.URLKey, etag string, lastModified uint32, prevDigest uint64)
- type Option
- func WithDispatchShards(w int) Option
- func WithDispatchThreads(threads int) Option
- func WithFreshness(p freshness.Params, budgetPerHour float64) Option
- func WithLinkRouter(sink func([]meguri.Discovery) []meguri.Discovery) Option
- func WithPoliteness(c politeness.Config) Option
- func WithPrioritizer(p prioritize.Params) Option
- func WithResolver(r dns.Resolver) Option
- func WithResolverCache(c *dns.Cache) Option
- func WithRobots(agent string) Option
- func WithScheduleIndex() Option
- func WithStateMachine() Option
- func WithTarget(n int) Option
- type SeedSpec
- type Stats
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func HostOf ¶
HostOf and PathOf split a URL into the host grouping and the path-and-query remainder the URLKey halves hash from. They are the deliberately minimal split the discovery path uses until full canonicalization lands with the seen-set in M2: no scheme normalization, no PSL folding, no default-port or case handling. They match the fallback the format's corpus loader uses, so a URL keys the same whether it enters through the loader or through Seed.
Types ¶
type Dispatched ¶
Dispatched is one entry of a dispatch stream: which URL went out, for which host, at what clock time.
type DueURL ¶
DueURL is one entry of the due-time schedule: a URL whose next_due has come around, with its canonical string and the hour it is due, the row a `meguri schedule` line prints.
type Frontier ¶
type Frontier struct {
// contains filtered or unexported fields
}
Frontier is the single-partition resident scheduler.
func New ¶
New returns an empty frontier for partition id, stamped created (epoch-hours) as its build time.
func Recover ¶
Recover rebuilds a frontier from a checkpoint partition. The resident pools are derived from the durable state: every host comes back with its politeness time, every uncrawled URL re-enters the front bank in URLKey order, and any URL caught in flight at the checkpoint resets to scheduled so it dispatches again. Rebuilding in URLKey order with the same deterministic tie-breaks reproduces the exact dispatch sequence the original would have continued.
func (*Frontier) Checkpoint ¶
Checkpoint serializes the live frontier into a .meguri partition (D1, D12): every URL record sorted by URLKey, every host record sorted by HostKey with its live politeness window (already maintained in the record), and the string arena. Recover rebuilds an identical scheduler from it.
func (*Frontier) CheckpointBytes ¶
CheckpointBytes checkpoints and encodes to the on-disk .meguri image.
func (*Frontier) Discover ¶
Discover is the idempotent intake of a routed out-link (doc 08, section 9.3, onDiscovery). It is the M2 closed-loop entry the link extractor feeds: a Discovery carries a canonical URLKey, its depth from the seed, and the OPIC cash the source link grants. Discover deduplicates the key against the seen-set and, for a genuinely new URL, applies the blunt trap defense (doc 08, section 8.2): a discovery too deep or over the host's budget is parked in Trapped rather than scheduled, so the row exists and dedups rediscoveries but does not consume crawl budget. It returns true when a new schedulable URL entered the frontier.
Delivering the same discovery twice creates at most one record, which is what lets the discovery transport be at-least-once (D16).
func (*Frontier) Dispatch ¶
Dispatch returns the next URL to fetch at clock time now (epoch-seconds), or ok=false when no host may be fetched at now. A false result does not mean the frontier is drained: call NextEligible to learn whether advancing the clock would open a host. The caller fetches the returned Request and feeds the outcome back through Report.
func (*Frontier) DispatchShard ¶
DispatchShard is Dispatch for dispatch thread `shard` of the threaded engine (audit 140): it draws the next polite host from that thread's shard of the ready bank, stealing the best-headed sibling shard when its own has drained, so W threads share the frontier without one idling while another shard still holds ready hosts. The frontier stays single-writer: the engine serializes the W threads' calls, so the sharding only steers where each thread looks for work. Plain Dispatch is thread 0, which on a one-shard bank is the single dispatch loop unchanged.
func (*Frontier) Drain ¶
Drain dispatches every schedulable URL, advancing a logical clock from start over politeness waits, and returns the dispatch order. It is the synchronous driver the M1 gate runs: fetch through fr, feed each outcome straight back, and record what went out in what order. A real engine dispatches many hosts at once; Drain serializes them so the ordering guarantees are checkable.
func (*Frontier) DueURLs ¶
DueURLs lists the URLs due at or before before, sorted by due time, the live form of the schedule command's "what is due to be crawled" question (doc 13). host filters to a single host group when nonzero; limit caps the result when positive (0 returns all). A URL counts when its status still wants a fetch and its next_due has come around, the same eligibility the dispatcher reads. The walk is O(urls); the resident frontier already holds the strings, so this is the rich, human-readable side the cold reader's key-only pushdown cannot give.
func (*Frontier) ImportHostSignal ¶
func (f *Frontier) ImportHostSignal(h meguri.HostSignal)
ImportHostSignal applies one imported host_score, the dense host half of a tsumugi import (doc 09, D16). A resident host takes the score on its record at once; a host not yet seen has the score parked so newHost stamps it when the host first appears. The blend reads HostRecord.HostScore, so an imported score flows into priority through the existing host-quality term with no other wiring.
func (*Frontier) ImportURLSignal ¶
ImportURLSignal applies one imported per-page PageRank, the sparse URL half of a tsumugi import the signal router delivered for a host this partition owns (doc 09, D16). It overwrites any prior rank for the URL, because a newer computation supersedes an older one, and is a no-op when prioritization is off since there is nothing to blend the rank into.
func (*Frontier) NextEligible ¶
NextEligible returns the earliest epoch-seconds at which some parked host becomes eligible, or ok=false when no host is waiting (the frontier is drained for this run). When Dispatch returns false, the scheduler advances its clock to this time and tries again.
func (*Frontier) Pending ¶
Pending reports the number of URLs still waiting to be dispatched, in the front bank or a back queue.
func (*Frontier) Prioritizer ¶
func (f *Frontier) Prioritizer() *prioritize.Prioritizer
Prioritizer returns the frontier's importance policy when prioritization is on, or nil when it is off. It is a read-only handle for inspecting the accumulated signals (OPIC score, cross-host in-degree), the way a caller confirms a routed cross-partition link credited cash and reputation to its target on this partition (doc 09, doc 12 D16).
func (*Frontier) Report ¶
Report records the outcome of a dispatched URL at clock time now. It marks the URL crawled, clears the host's in-flight flag, and re-places the host: back in the wait heap behind its fresh politeness window if it still has work, or out of the active set if its back queue drained.
func (*Frontier) Seed ¶
func (f *Frontier) Seed(url, host string, priority float32, firstSeen, nextDue uint32, crawlDelay uint16)
Seed inserts a first-crawl candidate. url is the canonical URL, host its grouping string, priority its initial importance, firstSeen and nextDue epoch-hours, and crawlDelay the host's politeness interval in deciseconds. A URL already present is ignored, so seeding is idempotent. Without the schedule index every seed is immediately schedulable; with it on (WithScheduleIndex) a seed dated into the future waits in the due-time wheel until its hour.
func (*Frontier) SeedBatch ¶ added in v0.2.0
SeedBatch is the scale form of Seed: it intakes a whole window of candidates in one pass, so the dedup authority pays one batched insert per bucket instead of a sorted-slice shift per key. The per-key Seen path is O(n^2) on a host's run because each new key shifts half its HostKey bucket (the memmove a seed-stage CPU profile is dominated by); SeedBatch checks membership with the cheap binary search and defers every insert to one DRUM InsertBatch, turning the intake into O(n log n). The scheduling, host setup, and prioritization per accepted seed are identical to Seed, so a frontier seeded by SeedBatch is byte-for-byte the one seeded by the equivalent Seed loop. Within-window duplicates dedup against the first occurrence, and a key already resident (a prior batch, a recovery) is skipped, so SeedBatch is idempotent exactly as Seed is.
func (*Frontier) Stats ¶
Stats walks the resident records once and folds the counters. now is the epoch-hour the due count is measured against; a URL counts as due when its next_due has come around and its status still wants a fetch. The walk is O(urls) and allocates only the small per-status map, so it is cheap to call between crawl passes.
func (*Frontier) Warm ¶
Warm pre-populates a never-crawled URL with the validators a prior crawl left, so its first fetch this campaign goes straight to a conditional GET (doc 13's seed pre-population). It stamps the ETag, the Last-Modified epoch-hours, and the prior content fingerprint a seed list carried from an earlier crawl. It is a no-op on a missing record or one already crawled this campaign, so re-warming a live URL never rewrites fresher state. The prior fingerprint seeds the change-rate comparison, so the first refetch is classified as change or no-change rather than treated as a first sighting.
type Option ¶
type Option func(*Frontier)
Option configures a Frontier at construction.
func WithDispatchShards ¶
WithDispatchShards shards the ready-host bank into w shards, one per dispatch thread of the threaded engine (audit 140, doc 05 [M1+]). Each thread draws work from its own shard with DispatchShard and steals the best-headed sibling shard when its own drains, so W threads share the frontier without one idling behind a host bound to another thread's shard. Off by default (w <= 1), so the single dispatch loop runs one shard and every earlier milestone's dispatch sequence is byte-for-byte unchanged. Sharding is orthogonal to WithDispatchThreads, which sizes the active-host floor; pair them so the bank has a shard per thread and the floor keeps every shard fed.
func WithDispatchThreads ¶
WithDispatchThreads tells the frontier how many dispatch threads its engine runs, so it can hold doc 05's invariant that the active-host set never drops below k*threads back queues (k = backQueuesPerThread). It floors the effective target at k*threads even under a tighter WithTarget memory cap, and it turns on the anti-starvation sweep that promotes front-bank URLs aged past frontAgePromoteHours. A value <= 0 is ignored.
func WithFreshness ¶
WithFreshness turns on the Poisson rescheduler (doc 06): a crawled URL's change rate is estimated from its history, its recrawl interval is set by the water-filling allocation against a global water level retuned toward budgetPerHour refresh crawls per hour, and its next_due is spaced deterministically. Without it a crawled URL parks a flat week out, the M1 placeholder. A budgetPerHour <= 0 disables the budget pressure, leaving every URL funded to its own optimal rate under the per-host politeness cap.
func WithLinkRouter ¶
WithLinkRouter routes a crawl's out-links to their owning partitions (doc 04, doc 12). sink receives every out-link after the OPIC cash split, ships the remote ones to their owners, and returns the subset this partition owns for the local intake. Without it every out-link is treated as local, the single-partition behavior. The engine wires the router's RouteLinks behind this so the fold splits local from remote in one place.
func WithPoliteness ¶
func WithPoliteness(c politeness.Config) Option
WithPoliteness sets the politeness policy (interval band and AIMD constants) and rebuilds the per-IP table around its IP floor. The default is politeness.DefaultConfig (doc 07).
func WithPrioritizer ¶
func WithPrioritizer(p prioritize.Params) Option
WithPrioritizer turns on OPIC importance ordering (doc 09): a seed endows its cash, every discovered out-link credits its OPIC cash and cross-host reputation to its target, the target host's crawl budget tracks the distinct other domains that link to it (STAR), and a crawl distributes the source's cash across its out-links so the front bank orders by online importance refined as the crawl runs. Imported PageRank or host quality from a prior tsumugi crawl is blended in through the Prioritizer when present. Without it a URL keeps the flat seed or link-weight priority of the earlier milestones.
func WithResolver ¶
WithResolver turns on DNS: hosts are prefetched off the dispatch path, their resolved IP rides on each fetch.Request so ami can pin the connection, and the per-IP politeness bucket is keyed on the address many vhosts may share. Without it the frontier crawls host-only, with no per-IP throttle.
func WithResolverCache ¶
WithResolverCache points the frontier at a resolver cache it shares with the other partitions on the same machine, instead of building its own (doc 11, the machine-local shared resolver cache). A host resolved for any partition is then hot for all of them, so a name the vhosts across many partitions share resolves once per machine rather than once per partition, and the prefetch pool's in-flight dedup keeps two partitions from resolving the same name at once. The frontier does not own a shared cache: the machine harness that built it closes it once every partition has stopped. Use WithResolver instead when a partition runs alone and owns its cache. A nil cache is ignored.
func WithRobots ¶
WithRobots turns on robots.txt: a host fetches and parses robots before any of its content URLs dispatch, disallowed URLs are excluded, and a robots Crawl-delay raises the host's politeness floor. agent is the product token its groups are matched against. Without it the frontier does not consult robots.
func WithScheduleIndex ¶
func WithScheduleIndex() Option
WithScheduleIndex turns on the resident due-time schedule index (doc 06, doc 05 near tier, M6): a hashed timing wheel that defers a not-yet-due URL until its NextDue arrives instead of leaving it in the front bank for the dispatch path to keep skipping. With it on, a future-dated seed waits until its hour and a crawled URL re-enters the schedule as DueRecrawl when its recrawl interval elapses, so recrawl actually runs in the live loop rather than a crawl being terminal. Off by default, so the earlier milestones treat every seed as immediately schedulable and their dispatch sequences are byte-for-byte unchanged. The wheel is derived from the URL table's NextDue and Status, so Recover rebuilds it without serializing it. Pair it with WithStateMachine and WithFreshness for a live recrawling partition.
func WithStateMachine ¶
func WithStateMachine() Option
WithStateMachine turns on the full outcome state machine (doc 13, the state update). Without it every outcome marks the URL Crawled, the earlier milestones' behavior. With it the outcome drives the URL through its transitions: a 200 or 304 to Crawled, a transient failure (Retryable, or a 429/5xx) backed off and re-queued up to a retry limit then to Gone, a 404 or 410 to Gone, and a redirect to Crawled with the target canonicalized, created as its own record, and the source's redirect_ref pointed at it. The engine turns this on for a live crawl; the scheduler-only gates leave it off so their dispatch counts stay exact.
func WithTarget ¶
WithTarget caps the number of hosts that hold a back queue at once, bounding resident memory. A value <= 0 is ignored. The default is effectively unbounded. A bounded target can starve a low-priority host whose URLs never win a slot, so pair it with WithDispatchThreads, which both floors the active set at k*threads and turns on the front-bank age-promotion sweep.
type SeedSpec ¶ added in v0.2.0
type SeedSpec struct {
URL string
Host string
Priority float32
FirstSeen uint32
NextDue uint32
CrawlDelay uint16
}
SeedSpec is one candidate for SeedBatch: the same arguments Seed takes, carried as a value so a caller can accumulate a window of seeds and intake them in one DRUM pass.
type Stats ¶
type Stats struct {
URLs int
Hosts int
Pending int
Due int
ByStatus map[meguri.URLStatus]int
SeenKeys int
SeenBitsPerURL float64
NextDueHours uint32 // earliest scheduled crawl, 0 when nothing is scheduled
}
Stats is a point-in-time snapshot of a frontier's counters: the totals, the pending dispatch count, the per-status URL distribution, the count due at or before now, and the seen-set occupancy with its modeled false-positive rate. It is what `meguri stats` reads off a live partition (doc 13, the stats command): the numbers that say whether the frontier is growing or maintaining.
Source Files