advalcache

AdVal-Cache

A cache that knows the difference between a $0.31 recommendation vector and a stock ticker that is worthless two seconds after you store it.

LRU asks when did you last touch this. LFU asks how often. Neither asks the only question a bill cares about: what does losing this actually cost me? In a real service that answer spans four orders of magnitude — a free 4 MB product image against a ten-second, fifty-cent ML inference. AdVal-Cache computes a per-object value score from access pattern, resource footprint, regeneration cost and data volatility, then decides retain / evict / refresh / decline — and separately decides, in dollars, when buying more cache capacity is worth the rent.

Quickstart

python -m venv venv; venv\Scripts\activate; pip install -r requirements.txt
python -m benchmarks.run_all --seed 42          # 80 cells in ~4 min -> results/report.md
streamlit run dashboard/app.py                  # playback dashboard

Everything is a deterministic simulation: no network, no Redis, no Docker, CPU only. Same seed ⇒ byte-identical traces, results and charts.

Results

60 simulated minutes per scenario, seed 42. The problem statement's baselines are LRU, LFU and GDS; exact GDSF ships alongside because it is stronger than the brief requires (D29).

AdVal is cheaper and fresher than the best baseline in 8 of 8 cells.

Read the last two columns before you believe the first ones

The cost model used to bill compute and memory and nothing at all for serving a customer stale data. Nobody decided that; it is what you get by leaving wrong answers unpriced, and it meant a cache-freshness system was scored on everything except the thing it does — gds won on cost by serving 75,526 wrong answers an hour for free.

D31 fixes it on a principle rather than a knob: a stale hit is not a hit, it is a miss you failed to notice, so it is charged the regen_usd of the very object it displaced. The price is read per object out of the catalog, billed by the simulator so every policy pays the same for the same event, and measured at $0.0077–$0.186 per stale serve. That is 7–170x the ~0.11 cent break-even, which is why the ranking flips.

On the old model gds is still cheaper — that is the pre-D31 pair above, kept in summary.csv as total_usd_compute_only in every run, and python -m benchmarks.run_all --stale-mult 0 reproduces it exactly (a test asserts it). The honest caveat: at the shipped price the staleness bill is ~10x compute plus memory, so the ranking now rests mostly on this one priced assumption. The full flat-price sweep, including where AdVal loses, is in results/dominance.md.

Savings are 6.5–11.8% on read_heavy_api and only 0.9–1.5% on compute_heavy_rec, where slow-changing ml_result objects dominate the staleness bill for every arm alike.

The four answers that assume nothing

Separately from the cost model, results/dominance.md:

1. Nothing in the study is both cheaper and fresher than AdVal — 16/16 arm-cells, on either cost model.
2. Capacity cannot buy freshness. gds serves 75,526 stale responses at 100 MB and 75,526 at 500 MB while its hit rate climbs 81.6% → 93.9%. AdVal at 100 MB is cheaper and 12.2 pp fresher than gds at 500 MB.
3. The flat-price sweep: above ~0.11 cents per stale response AdVal is cheapest in all 8 cells, to 4.6–45 cents where LRU takes over. Both bounds published.
4. At 50–60 MB, where memory is actually scarce, AdVal is cheaper and fresher at equal capacity even with staleness free.

Against LRU and LFU, AdVal is 92–99% cheaper on either model. It still loses on tail latency — 158 ms p95 against 55 ms — because refreshing on read is not free. Full tables, timelines, the ablation ladder and an auto-generated "where this result is weakest" section: results/report.md.

The score

score(i) = hotness(i) × pain(i) × freshness(i) / size_units(i)

• hotness — LRFU decayed counter c ← 1 + c·e^(−λΔt), λ = 0.001 (half-life ≈ 693 s); recency at short lags, frequency at long ones, one number.
• pain — regeneration latency and regeneration dollars, each normalised against the catalog's p99 so neither drowns the other. ~200× spread across object classes.
• freshness — exp(−(now − last_sync) / change_interval), which for a Poisson mutation process is exactly P(the cached copy is still valid). Multiplying a value by a probability gives an expected value, which is the right thing to rank by. Exactly 1.0 for immutable objects and anything slower than 1800 s.
• size_units — log1p(bytes / 1 KB), so 5 MB is penalised ~12× rather than ~5000×. Large objects must justify themselves; they are not banned.

Two runtime loops keep it from being a set of hardcoded constants:

• The cache A/B tests its own brain. Every 5000 requests it shadow-replays the window it just served through five candidate weight vectors, seeded from a snapshot of its real state, and adopts whichever delivered the most value. steady picks freq_heavy; chaos picks fresh_heavy. Nobody told it which signal matters.
• Capacity is a dollar decision that checks itself. A shadow zone measures the marginal dollars the next slice of memory would have saved; the controller acts, waits five windows, and reverts the change if realised spend per request did not fall by more than the rent it took on. From a badly-sized 30 MB cache it cuts cost 72–84%.

ARCHITECTURE.md has the decision-engine diagram and the full justification.

Repo layout

models.py            THE CONTRACT: Request, CatalogEntry, object classes, ops, constants
proxy/               FastAPI reverse proxy sidecar · live cache engine · traffic generator
database/            Neon PostgreSQL client · schema · real-world dataset ingestion pipeline
cache/               base (interface, sampling, event sink) · lru · lfu · gdsf · adaptive · controller
generator/           catalog · popularity modes · scenario engine · trace writer · validator
sim/                 simulator (replay + window aggregation) · metrics (the only cost model)
benchmarks/          run_all (the 80-cell matrix) · report (tables, charts, honest caveats)
dashboard/app.py     Streamlit control center: batch replay scrubber & live dynamic proxy mode
web_adval/           React/Vite standalone web control UI mounted on proxy port 8000
traces/              trace samples & Postgres query trace generator
tests/               unit & integration tests: core, live cache, and proxy API
results/             event logs, window CSVs, summary.csv, report.md, charts/

Verify it yourself

python -m generator.validate --minutes 60 --seed 42   # 9 workload checks, ~6 s
python -m pytest -q                                   # 63 tests, ~8 s
python -m benchmarks.run_all --seed 42                # 80 cells, ~4 min

generator/validate.py is the workload referee: it asserts the arrival-rate curve matches the scenario spec within 4σ on all four scenarios, that the top-10 popular keys genuinely rotate during gradual_shift (0 shared keys), that the reuse working set is 4.05× cache capacity (a cache that never fills has no story), that static_asset is 99.4% of bytes but only 30.1% of requests, and that seed 42 reproduces byte-identical files. A cache benchmark is only as honest as its workload.

Reading the docs