nucleation

THEORY-386: When a cached interval of width W is kept valid by its source, which pushes a refresh at cost C_vr whenever the value leaves it, and queries fetch the exact value at cost C_qr whenever it is too wide, and the chances of the two per step go as 1/W² and as W, the expected refresh cost is least at W* = (ρK₁/K₂)^(1/3) with ρ = 2C_vr/C_qr, where ρ times the chance of a pushed refresh equals the chance of a fetch

4 min read

Properties6
StatusActive
Tagsdatabases, operations-research
SourceLIT-1109 — Adaptive Precision Setting for Cached Approximate Values
Extended byTHEORY-377 — In Olston, Loo and Widom's simulations, a rule that multiplies a cached interval's width by 1 + α on a pushed refresh with probability min{ρ, 1}, and divides it by 1 + α on a query's exact fetch with probability min{1/ρ, 1}, settled within 1% of the best fixed width on one random walk and within 5% over eight walk settings; on a 50-host network-traffic trace, restricted to exact copies, it almost matched a tuned adaptive cache-or-not rule, and with a 50-value cache, where queries tolerated imprecision, it cost less; that it converges to the best width is argued, not proved
Bears onQUESTION-114 — Is sorting a collection amortized search, and does physical database design, where a table is stored in one order and every further index is paid for in space and upkeep, give the joint cost model that the question on amortized retrieval lacks?
SupportsCLAIM-303 — Filing an argument moves work across time: it is paid for now, in filing, indexing, tracking dependencies and checking it is still current, against reconstruction later, so it is worth its cost only when expected reuse covers it, and recurrence is evidence of reuse, not the criterion

Graph View

Source

Olston, Loo and Widom (2001), LIT-1109, SIGMOD 2001, pp. 355–366, read in full in NOTE-912 from the camera-ready copy in the University of Pennsylvania’s repository: Section 3, Appendix A, Section 4.2.

What was actually shown

The model. A source validates every cached interval whenever its value changes and pushes a new one if the value has left it (a value-initiated refresh, cost C_vr). A query that finds the interval too wide fetches the exact value (a query-initiated refresh, cost C_qr). Intervals are centred and constant until refreshed, so width W describes one. The objective is network traffic, the expected cost rate per step Ω = C_vr·P_vr + C_qr·P_qr.

The forms. Appendix A takes a random walk of step s, one value per query, a query every T_q steps and precision demands uniform on [0, δ_max]. Then P_qr = W/(T_q·δ_max) for W ≤ δ_max, exactly. For P_vr, Chebyshev gives P ≤ t·(s/k)², and with k = W/2 the paper treats “the upper bound as a rough approximation”, so P_vr ∝ 1/W². In general P_vr = K₁/W² and P_qr = K₂·W.

The optimum. Ω(W) = C_vr·K₁/W² + C_qr·K₂·W has its minimum at W* = (ρ·K₁/K₂)^(1/3), ρ = 2·C_vr/C_qr, where ρ·P_vr = P_qr. With ρ = 1 the best width is where the two refreshes are equally likely.

The check. With one value on a random walk (steps uniform on [0.5, 1.5], T_q = 2, δ_avg = 20, ρ = 1) and W fixed per run, the measured P_vr and P_qr were proportional to 1/W² and W, and the measured cost was least where they crossed (Figure 3). That check could have failed: other drift processes, or precision demands not spread evenly, would change the exponents and move the optimum off the crossing.

What this does not say

  • That the balance holds for other drift. The 1/W² form is a Chebyshev bound used as an estimate, for an unbiased random walk. For trending data the paper found other interval shapes better (Section 4.5), and with other exponents the factor 2 in ρ changes; under Divergence Caching’s update-count staleness the paper’s own analysis gives ρ′ = C_vr/C_qr.
  • That staleness costs anything but messages. Validity is guaranteed, so there is no cost of reusing a wrong value and no cost of an imprecise answer; queries that need more precision simply pay C_qr.
  • That build cost, space or stored answers are priced. Nothing is paid once, the cache limit is a heuristic eviction of the widest intervals, and the cached items are base values.
  • Anything in the worst case. The optimum is of an expected rate under a stationary stochastic model; no competitive bound is given.
  • That the record’s argument has a monitoring source. The model needs one that sees every change and tests every copy.

Connections

  • QUESTION-114: the first model the record holds in which upkeep and tolerated staleness are traded in one objective, with an interior optimum. THEORY-348 forbids stale reads; THEORY-350 budgets upkeep with no staleness; THEORY-332 has upkeep and build cost without staleness.
  • THEORY-364: the query side this model’s P_qr summarizes.
  • THEORY-377: the adaptive rule that seeks this balance without knowing K₁ and K₂.
  • CLAIM-303: its upkeep u and per-use verification c_a become functions of one dial, the tolerance a filed item claims, with a best level between them; usable only where something watches the premises and triggers upkeep.
  • CLAIM-308: once staleness is admitted, the two-state choice of THEORY-348 becomes a continuum of widths, and the best choice is an interior balance; the cache-or-not choice is the endpoint case.
  • THEORY-348: the rent-or-buy rule is the endpoint of this model, with intervals of zero width; the adaptive rule here has no competitive guarantee.

Backlinks