Documentation
¶
Overview ¶
Package prioritize decides crawl order by importance (doc 09, the M5 milestone). It runs the online OPIC computation that spreads cash from crawled pages to their out-links, blends in any imported PageRank or host-quality signal tsumugi computed over a prior crawl, and produces the Priority the frontier's front bank sorts on. It sets the per-host crawl budget from cross-host in-degree, the STAR reputation signal an adversary cannot forge, and enforces it by deferral, not discard (BEAST). And it carries the spam and trap dampeners, the trap-suspect and depth penalties, that keep a link farm from monopolizing the schedule.
The package owns policy, not storage. OPIC cash and discounted history are resident working state it keeps; the durable result is the URLRecord.Priority column the frontier serializes (doc 03). The frontier wires the package in opt-in: without it the M1 through M4 dispatch order is unchanged, and with it a discovery credits cash and reputation, a crawl distributes cash to its links, and every URL's priority is the blended, penalized importance.
Index ¶
- func Admit(h *meguri.HostRecord, depth uint16) meguri.URLStatus
- func Blend(opic, pageRank float32, havePage bool, hostScore float32, p Params) float32
- func Compress(score float32) float32
- func Crosses(oldPri, newPri float32, numLevels int) bool
- func DepthPenalty(pri float32, depth uint16, p Params) float32
- func Quantize(pri float32, numLevels int) int
- func TrapPenalty(pri float32, h *meguri.HostRecord, p Params) float32
- func UpdateHostBudget(h *meguri.HostRecord, crossHostInDegree uint32, p Params)
- type BudgetSplit
- type CrossHostInDegree
- type OPIC
- type Params
- type Prioritizer
- func (pr *Prioritizer) Credit(d meguri.Discovery) uint32
- func (pr *Prioritizer) CrossHostInDegree(hostKey uint64) uint32
- func (pr *Prioritizer) Distribute(src meguri.URLKey, links []meguri.Discovery)
- func (pr *Prioritizer) ImportPageRank(key meguri.URLKey, rank float32)
- func (pr *Prioritizer) Params() Params
- func (pr *Prioritizer) Priority(rec *meguri.URLRecord, h *meguri.HostRecord) float32
- func (pr *Prioritizer) Score(key meguri.URLKey) float32
- func (pr *Prioritizer) SeedCash(key meguri.URLKey, cash float32)
- type StreamKind
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Admit ¶
func Admit(h *meguri.HostRecord, depth uint16) meguri.URLStatus
Admit decides what state a newly discovered URL enters, enforcing the host's budget by deferral, not discard (BEAST, doc 09). An over-budget or too-deep URL is parked in Trapped: the row stays in the frontier and the seen-set so it dedups rediscoveries, and it can be released back to Scheduled if the host's budget later rises. A zero budget or zero depth cap means unlimited (the blunt M2 default before M5 sets the real numbers). This mirrors dedup.Admit and is the prioritization-owned statement of the same rule.
func Blend ¶
Blend combines the online OPIC estimate with any imported signals into the importance written to URLRecord.Priority (blendedPriority, doc 09). OPIC is always present. The imported per-page PageRank is present only for a URL a prior tsumugi crawl covered; havePage says whether pageRank is real. The imported per-host quality is present for a host tsumugi scored; a zero hostScore means none.
The weights shift toward the import when it exists, because a real PageRank over a real crawl is better evidence than an online estimate, but OPIC never drops to zero even alongside a per-page rank: the import is already stale by the time it lands and OPIC sees the links the prior crawl missed, so a quarter of the weight stays on the live signal. When nothing was imported OPIC is the whole answer, the first-crawl case that lets the engine order a frontier with no global graph at all.
pageRank and hostScore are expected already log-compressed onto the OPIC scale (Compress for both imported signals).
func Compress ¶
Compress puts an imported host quality or per-page PageRank score on the same log-compressed scale as the OPIC estimate, so the blend adds comparable quantities. A zero score (no import) stays zero, contributing nothing. It is the same Log1p heavy-tail compression OPIC's own score applies, the scaling tsumugi uses before serving a PageRank.
func Crosses ¶
Crosses reports whether two priorities fall in different quantization levels, the test that decides when a credited URL must be re-bucketed in the front bank (doc 09, section "Re-bucketing when a signal updates"). Most cash credits move the float without crossing a level, so they update the stored priority without paying the re-bucket; only a credit large enough to change the level triggers the move.
func DepthPenalty ¶
DepthPenalty scales priority down as link depth from the nearest seed grows (doc 09, section "Depth penalties"). Important pages cluster near the seeds; deep pages are disproportionately the long tail and the generated combinatorial spaces. The decay is gentle, a small per-level factor, so a genuinely important deep page can still earn its way up on a strong OPIC cash signal. The hard cut is the depth cap (BEAST, doc 09), which parks URLs past the cap in Trapped; this is the soft tilt below the cap.
func Quantize ¶
Quantize maps a continuous priority in roughly [0, 1) to one of numLevels front-bank buckets (doc 09, section "Quantization to priority levels"). The mapping is monotone, higher priority to a higher-or-equal level, and logarithmic, so the crowded low end where most URLs sit gets fewer levels and the sparse high end where the few important pages sit gets more resolution. This doc's contract to doc 05 is only that the mapping is monotone and the input range is stable; doc 05 owns the bank mechanics and may tune the exact spacing, which the frontier's own frontBucket does for the resident ring.
func TrapPenalty ¶
func TrapPenalty(pri float32, h *meguri.HostRecord, p Params) float32
TrapPenalty scales a URL's priority down when its host is a suspected trap (doc 09, section "Down-weighting HostFlagTrapSuspect"). It does not zero the priority, because a trap-suspect host may still hold real pages: it sinks the host's URLs below genuine work elsewhere so the bounded budget the host does get is spent on its likely-real URLs first. The flag is set by the dedup trap detector (doc 08); this is ordering reading it.
func UpdateHostBudget ¶
func UpdateHostBudget(h *meguri.HostRecord, crossHostInDegree uint32, p Params)
UpdateHostBudget recomputes a host's url_budget from its cross-host in-degree, the count of distinct other host groups that link to it (STAR, doc 09: Lee, Leonard, Wang, Loguinov, "IRLbot: Scaling to 6 Billion Pages and Beyond," WWW 2008). This is the reputation signal an adversary cannot forge: a spammer can mint hostnames without bound but cannot mint independent domains that vouch for it, so cross-host in-degree is budget that has to be earned. A floor lets a brand-new host be discovered at all; a cap stops any one host claiming the whole partition's budget.
Types ¶
type BudgetSplit ¶
type BudgetSplit struct {
// contains filtered or unexported fields
}
BudgetSplit holds the discovery-versus-refresh ratio at the front-bank feed (doc 09, section "The discovery-versus-refresh budget split"). It is the one knob that decides whether the crawler is growing or maintaining: a discovery-heavy split grows coverage, a refresh-heavy split keeps a known frontier fresh. The split is proportional, not a hard partition, so when one stream has no ready work the other takes the whole budget rather than letting the fetcher idle on a quota it cannot fill.
admit is a deficit-round-robin: it serves whichever stream is furthest behind its share, which holds the long-run ratio at the configured split with two counters and no global accounting.
func NewBudgetSplit ¶
func NewBudgetSplit(p Params) *BudgetSplit
NewBudgetSplit returns a split at the configured shares. Non-positive shares fall back to the params default so the ratio is always well formed.
func (*BudgetSplit) Admit ¶
func (b *BudgetSplit) Admit(discoveryReady, refreshReady bool) StreamKind
Admit decides which stream to pull from next, given which streams currently have ready work, and charges the chosen stream. discoveryReady and refreshReady report whether each stream has an admissible URL right now. It holds the long-run ratio at the configured split while letting either stream borrow the other's idle capacity in the short run.
func (*BudgetSplit) Shares ¶
func (b *BudgetSplit) Shares() (discovery, refresh float64)
Shares returns the running counts admitted to each stream, the way a test or a monitor checks the realized ratio against the configured one.
type CrossHostInDegree ¶
type CrossHostInDegree struct {
// contains filtered or unexported fields
}
CrossHostInDegree tracks, per target host, the set of distinct source hosts that have linked into it (doc 09, section "Budget by cross-host in-degree"). A link from a page on the same host group does not count; only a distinct other host group adds reputation, which is the spam defense. The exact set is resident here for the single-partition gate; at fleet scale this is an approximate distinct counter, the same approximate accumulation D16 sanctions for the cross-partition signal, so a target's in-degree memory stays bounded.
func NewCrossHostInDegree ¶
func NewCrossHostInDegree() *CrossHostInDegree
NewCrossHostInDegree returns an empty tracker.
func (*CrossHostInDegree) Count ¶
func (c *CrossHostInDegree) Count(targetHost uint64) uint32
Count returns the distinct cross-host in-degree recorded for a host.
func (*CrossHostInDegree) Observe ¶
func (c *CrossHostInDegree) Observe(targetHost, srcHost uint64) uint32
Observe records that a link from srcHost reached targetHost and reports the target's new distinct cross-host in-degree. A same-host link (srcHost == targetHost) is ignored and returns the count unchanged: it carries no reputation, which is exactly what stops a spam farm inflating its budget with dense internal links.
type OPIC ¶
type OPIC struct {
// contains filtered or unexported fields
}
OPIC is the online importance estimator of doc 09: Adaptive On-Line Page Importance Computation (Abiteboul, Preda, Cobena, WWW 2003). It models importance as cash flowing through the link graph. Every page holds an amount of cash, the importance it has accumulated but not yet distributed; when a page is crawled it absorbs its cash into a discounted history and splits the cash equally across its out-links, minus a teleport cut. A page's importance is read from its discounted history plus its currently held cash, the forward-looking estimate that lets an uncrawled page a hub points at be prioritized before it is ever fetched.
The estimator stores, per URL, only the two numbers OPIC needs: the held cash and the discounted history. It never materializes the link matrix, which is the whole reason OPIC exists; each event is O(out-degree) and local. The durable importance is the URLRecord.Priority column the frontier sorts on (doc 03): cash and history are resident working state the prioritizer owns, and Priority is the served result recomputed from them. On recovery the working state rebuilds empty and re-converges from the live crawl, which OPIC is built to tolerate, because it is an online estimate that sharpens as cash flows, not a fixed point that must be restored exactly.
func (*OPIC) Credit ¶
Credit adds the cash a single in-link carries to the target URL's held cash (creditCash, doc 09). It is called on the receiving side for each discovered out-link after the seen-set check, whether the target is new or a rediscovery, so a URL many crawled pages point at accumulates cash fast and earns a high forward-looking importance before its own first crawl.
func (*OPIC) Distribute ¶
Distribute implements one OPIC visit for a crawled source page (distributeCash, doc 09): the page absorbs its held cash into its discounted history, then splits the cash equally across its out-links after a teleport cut, writing each Discovery's LinkWeight so the cash travels with the routed link, and resets its own cash to zero. A page with no out-links is a dangling node: all its cash goes to teleport so it is never a sink that traps importance.
The links slice is mutated in place: each LinkWeight is filled with the share this link carries, ready for the frontier to credit locally or route to the owning partition.
func (*OPIC) Known ¶
Known reports how many URLs the estimator tracks, the denominator of the lazy teleport redistribution.
func (*OPIC) Score ¶
Score turns a URL's OPIC state into an importance estimate (opicScore, doc 09). It blends the discounted accumulated history (earned importance, dominant once a URL has been crawled many times) with the currently held cash (forward- looking importance, dominant before the first crawl), plus a uniform teleport floor so a URL no one links to is not exactly zero. The Log1p compresses the heavy tail, the same scaling tsumugi applies to PageRank, so one hub's cash does not swamp the priority range and the score spreads across the front-bank levels. The result lands in a stable range the front bank can quantize.
func (*OPIC) Seed ¶
Seed injects an initial cash endowment for a URL the crawl starts from, the "fixed total cash distributed across the known pages" of the OPIC model. A seed enters with cash equal to its configured importance so the first crawl has flow to distribute; a discovered URL instead accrues its cash from the links that point at it (Credit).
type Params ¶
type Params struct {
// OPIC online importance (doc 09, section "OPIC").
Discount float32 // history decay per visit, gamma slightly below 1
TeleportRate float32 // fraction of distributed cash sent to the teleport node
LogNorm float64 // running normalizer keeping the OPIC score in a stable range
// Import blend weights (doc 09, section "The blend function").
WPageRank float32 // weight on imported per-page PageRank, when present
WOPICWithPage float32 // weight on OPIC when a per-page PageRank is present
WHost float32 // weight on host score when a per-page PageRank is present
WOPICWithHost float32 // weight on OPIC when only a host score is present
WHostOnly float32 // weight on host score when only a host score is present
// STAR per-host budget by cross-host in-degree (doc 09, section "Budget by
// cross-host in-degree").
BaseBudget uint32 // budget floor before any cross-host in-links
PerInLink uint32 // budget added per distinct cross-host in-link
MinBudget uint32 // a brand-new host still gets this, to be discovered at all
MaxBudget uint32 // no single host can claim more than this
// Spam and trap dampeners (doc 09, section "Spam and trap avoidance").
TrapSuspectFactor float32 // priority multiplier for a trap-suspect host, e.g. 0.1
DepthDecay float32 // per-level priority multiplier, e.g. 0.95
// Discovery-versus-refresh budget split (doc 09, section "The one knob"). The
// shares are a ratio; admit holds the long-run split between them.
}
Params is the prioritizer's tunable policy, the M5 counterpart to freshness.Params (doc 09). Every knob the OPIC estimator, the import blend, the STAR budget, the spam penalties, and the discovery-versus-refresh split read lives here, so a campaign tunes ordering without touching code. The defaults are the doc 09 targets, stated as starting points until the benchmark gate (D19) retunes them on real crawl data.
func DefaultParams ¶
func DefaultParams() Params
DefaultParams returns the doc 09 starting policy.
The discount is set for a multi-thousand-crawl half-life, so a page that was important once does not dominate the order forever but a stable hub stays high across a long campaign. The teleport rate is the standard 0.15 PageRank damping complement, so 85 percent of a page's cash follows its links and 15 percent teleports, the same split tsumugi's graph signals use. The blend leans hardest on a real imported PageRank when one exists, keeps a quarter of the weight on OPIC to track links the stale import never saw, and falls all the way back to OPIC alone on the first crawl. The STAR budget is a floor plus a per-cross-host-in-link increment, clamped, so reputation an adversary cannot forge bounds the crawl an adversary can demand. The split starts discovery-heavy, the annealed-campaign default.
type Prioritizer ¶
type Prioritizer struct {
// contains filtered or unexported fields
}
Prioritizer ties the OPIC estimator, the import blend, the cross-host in-degree reputation, and the spam penalties into the one importance the frontier reads. It is the policy object the frontier holds when prioritization is on.
func (*Prioritizer) Credit ¶
func (pr *Prioritizer) Credit(d meguri.Discovery) uint32
Credit folds one discovered out-link into the importance signals: it adds the link's OPIC cash to the target URL's held cash and, when the link crosses host groups, counts it toward the target host's cross-host in-degree. It returns the target host's new distinct cross-host in-degree so the caller can refresh the host's url_budget (UpdateHostBudget). A same-host link credits cash but adds no reputation, the spam defense that stops dense internal links inflating a budget.
func (*Prioritizer) CrossHostInDegree ¶
func (pr *Prioritizer) CrossHostInDegree(hostKey uint64) uint32
CrossHostInDegree returns the distinct cross-host in-degree recorded for a host, the STAR reputation that sets its budget.
func (*Prioritizer) Distribute ¶
func (pr *Prioritizer) Distribute(src meguri.URLKey, links []meguri.Discovery)
Distribute spreads a just-crawled source page's accumulated cash equally across its out-links, filling each Discovery's LinkWeight, and folds the cash into the source's discounted history (one OPIC visit). The frontier then credits the local links and routes the rest.
func (*Prioritizer) ImportPageRank ¶
func (pr *Prioritizer) ImportPageRank(key meguri.URLKey, rank float32)
ImportPageRank loads a per-page PageRank tsumugi computed over a prior crawl. It overwrites rather than accumulates, because a newer computation supersedes an older one (doc 09): the import is a refresh, not a sum.
func (*Prioritizer) Params ¶
func (pr *Prioritizer) Params() Params
Params returns the policy this prioritizer runs.
func (*Prioritizer) Priority ¶
func (pr *Prioritizer) Priority(rec *meguri.URLRecord, h *meguri.HostRecord) float32
Priority computes the final importance for a URL: the OPIC estimate, blended with any imported per-page PageRank and per-host quality, then scaled down by the trap-suspect and depth penalties (doc 09). It reads the record and its host but writes nothing; the caller stores the result in URLRecord.Priority and decides whether the change crosses a front-bank level.
func (*Prioritizer) Score ¶
func (pr *Prioritizer) Score(key meguri.URLKey) float32
Score returns a URL's current OPIC importance estimate, the held cash and discounted history blended into a stable range (doc 09). It reads the accumulated signal without the import or penalty blend Priority applies, so a caller can confirm a routed link's cash actually landed on its target.
type StreamKind ¶
type StreamKind uint8
StreamKind names the two sources that feed the front bank: the discovery stream of new URLs awaiting a first crawl, and the refresh stream of due recrawls the rescheduler has marked ready.
const ( StreamDiscovery StreamKind = iota // a new URL, growing coverage StreamRefresh // a due recrawl, maintaining freshness )
Source Files