Documentation
¶
Overview ¶
Package freshness is the rescheduler, the heart of meguri (doc 06). It decides when each URL comes around again and why. It estimates a per-URL change rate from the crawl history with the Cho and Garcia-Molina no-change-ratio estimator, allocates the refresh budget by the non-monotone water-filling rule of Azar et al (refined by the Kolobov per-host politeness cap), spaces the crawls deterministically per Coffman, Liu, and Weber, and writes next_due back for the schedule.
The whole model runs off a tiny sufficient statistic already on the record: CrawlCount, ChangeCount, NoChangeStreak, FirstSeen, LastCrawled, plus Lambda and NextDue it maintains. It reads the change signal the frontier classifies from each Outcome (304, content fingerprint, simhash longevity gate) and the importance weight from Priority, and produces a NextDue time and a refresh shadow price tau.
This is the M4 milestone. The estimator and allocator are pure functions over meguri.URLRecord and meguri.HostRecord; the frontier wires them in opt-in through WithFreshness so the earlier milestones' dispatch sequences are unchanged when freshness is off.
Index ¶
- func Estimate(rec *meguri.URLRecord, p Params) float64
- func ObserveChange(rec *meguri.URLRecord, o meguri.Outcome) bool
- func SetNextDue(rec *meguri.URLRecord, intervalHours float64, now uint32, p Params)
- func TargetInterval(rec *meguri.URLRecord, h *meguri.HostRecord, tau float64, p Params) float64
- func ValueDensity(rec *meguri.URLRecord, p Params) float64
- type Params
- type TauController
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Estimate ¶
Estimate recomputes a URL's Poisson change rate lambda from its sufficient statistics (section 3): the no-change ratio over the crawl history, inverted through the Poisson no-change probability, smoothed against the small-sample degeneracy, and pulled toward the recent stability a no-change streak implies. It is a pure function of the record's counters and timestamps, the whole point of choosing an estimator with a tiny sufficient statistic.
The naive count X/(nT) is biased low because a visit cannot distinguish one change from several between crawls; this estimator works off the no-change fraction, which is observed exactly, so it is consistent and does not saturate on fast pages (section 3, "Why the naive estimator is wrong").
func ObserveChange ¶
ObserveChange decides whether one crawl saw a meaningful change, applying the trust order of section 7 and the longevity gate of section 5. It returns true only for a real, content-level change, so the change-rate estimate tracks meaningful change rather than cosmetic byte churn.
- A 304 (NotModified) is a definitive no-change, the cheapest signal.
- An identical content fingerprint is a no-change.
- A differing fingerprint within the simhash near-dup threshold is cosmetic churn (a rotating ad, a ticking timestamp) and does not count.
- A differing fingerprint past the threshold is a meaningful change.
A first fetch (no stored fingerprint) is not a change: there is nothing to compare against, so it only seeds the signal.
func SetNextDue ¶
SetNextDue turns the optimizer's target interval into a concrete schedule time, deterministically (Coffman, Liu, Weber even spacing, not Poisson; section 6). It adds a small deterministic per-URL spread so a host's URLs do not all come due in the same hour and slam its politeness cap, which is the even-spacing principle applied across a host's URLs rather than across one URL's crawls. The monotonic discipline holds: next_due never lands in the past. now is in epoch-hours. It moves the URL to DueRecrawl, the Crawled -> DueRecrawl transition of the state machine (doc 03).
func TargetInterval ¶
TargetInterval turns the allocation into a concrete recrawl interval in hours for one URL under the current water level tau and its host's politeness cap (section 4). A URL whose value density is at or below tau is starved to the slow re-probe rate; a URL above tau is funded to the rate where its marginal value meets tau. Either way the rate is clamped to the host's share of its politeness cap and to the global rate band, and the interval is the inverse.
func ValueDensity ¶
ValueDensity is the per-URL quantity the water-filling rule thresholds on: the importance-weighted marginal freshness gain a crawl buys, measured at the partition reference rate (section 4). It is high for medium-rate important pages and low for near-static and hyper-volatile pages alike, the hump. The importance weight is the embarrassment proxy (section 1), the page's Priority.
Types ¶
type Params ¶
type Params struct {
// Estimator (section 3).
Alpha float64 // no-change-ratio smoothing pseudo-count, the tuned stand-in for the paper's small-sample constant
MinRate float64 // lambda floor, changes/hour: a never-changed page still gets a slow re-probe, never a rate of zero
MaxRate float64 // lambda ceiling, changes/hour: a cap for numeric stability, the optimizer starves above it anyway
RecencyHalfLife float64 // no-change intervals over which a streak pulls lambda down toward the streak-implied rate
// Longevity gate (section 5). The frontier applies the simhash gate when it
// classifies a change; this is carried for completeness and the standalone
// estimator path.
SimhashNearDupThreshold int // Hamming distance separating cosmetic churn from meaningful change, the doc 08 k=3 point
// Allocation (section 4, 8).
RefRate float64 // the partition's feasible reference crawl rate, changes/hour: the point the marginal freshness gain is measured at, the source of the hump
ReprobeRate float64 // crawls/hour for starved URLs: a slow re-probe so a page coming back to life is eventually observed
// Spacing (section 6).
MinReprobeGap uint32 // minimum hours before a rescheduled URL is due again, so next_due never lands in the past
HostSpreadWindow uint32 // hours over which a host's due times are spread, breaking the thundering herd deterministically
}
Params are the rescheduler's tunable knobs (doc 06, section 12). The defaults are starting points for the benchmark sweep, not proven optimums: doc 14 validates them against real crawl data before any are published as recommended (D19). Rates are in changes per hour, intervals in hours, to match the epoch-hours timestamps of the data model (doc 03).
func DefaultParams ¶
func DefaultParams() Params
DefaultParams returns the section-12 defaults: a 0.5 smoothing pseudo-count, a yearly lambda floor and a four-per-hour ceiling, a recency half-life of eight intervals, the k=3 simhash threshold, a one-crawl-per-day reference rate, a fortnightly re-probe floor, and a one-hour minimum gap with a one-day host spread.
type TauController ¶
type TauController struct {
// contains filtered or unexported fields
}
TauController maintains the global water level tau for a partition (section 8). tau is the dual price of a refresh crawl, one number per partition, read by every per-URL reschedule and adjusted on a slow background cadence so the total scheduled refresh rate tracks the budget B. It moves slowly because it is set by the aggregate of a whole partition and no single crawl moves the aggregate much, which is what lets the rescheduler stay incremental instead of running a stop-the-world batch (section 8, "Why meguri re-solves incrementally").
This is the Edwards et al closed loop made incremental: the estimates and the schedule co-evolve through a slowly-moving tau, never a global re-solve.
func NewTauController ¶
func NewTauController(budget float64) *TauController
NewTauController returns a controller targeting budget crawls per period, seeded at a small positive water level so the first ticks have something to scale. A non-positive budget yields a controller that funds nothing.
func (*TauController) Tau ¶
func (c *TauController) Tau() float64
Tau returns the current water level, the value a reschedule thresholds value densities against. It is safe to read between ticks; the controller only ever nudges it by a small step.
func (*TauController) Tick ¶
func (c *TauController) Tick(scheduledRate float64)
Tick folds the partition's current total scheduled crawl rate into the water level (section 8). Too much scheduled rate (over budget) raises tau, starving more pages; too little lowers it, funding more. The step is multiplicative and small, because tau moves slowly and overshoot wastes budget. A dead band around the budget keeps tau still when the schedule already fits, so it does not hunt. The controller is run on a slow cadence, not on the crawl hot path.
Source Files