Serving Bounded-Staleness Reads with an Explicit Freshness Budget

Problem statement: the read path is “eventually consistent” and everybody assumes that means fast, and nobody can state how old the data a user sees is allowed to be — or how old it actually is.

Bounded staleness means exactly one thing: there is a number, and the system enforces it. This page turns that from a design aspiration into code, with a single budget per read path that each layer decrements. It makes concrete the composition problem described in caching and materialized reads for stale-tolerant workloads.

Symptom Identification

You are serving unbounded staleness, whatever the design document says, if:

  • Nobody can state the maximum age of the data on a given page without reading three config files and adding numbers up.
  • Freshness settings are per-component: a lag threshold in the proxy, a TTL in the cache, an interval in a cron job, each owned by different people.
  • Users occasionally report data much older than any single setting allows, and the reports cannot be reproduced.
  • There is a latency SLI and no freshness SLI, so nothing measures the property that is actually failing.
  • The response payload contains no indication of how old it is, so a stale value is indistinguishable from a current one at every layer above the database.

The last point is why this class of problem persists: staleness is invisible in the data. A latency regression shows up in every dashboard; a freshness regression shows up only when a user notices and complains.

Root Cause Analysis

Every layer contributes an age, and the ages add. A value served from a cache that was populated from a replica that was replaying a materialized view has three ages stacked: replication lag at population time, the view’s age at that moment, and how long it has since sat in the cache. The composition is additive, and the total has no owner because each layer was configured separately.

Per-layer limits are individually conservative and jointly unbounded. This is the central failure. A 2-second lag budget is prudent. A 5-minute view refresh is generous. A 60-second cache TTL is short. Together they permit a value 6 minutes and 2 seconds old, and no review of any single setting would have caught it.

A budget only works if it is decremented. Stating “our budget is 30 seconds” and then setting a 30-second TTL, a 30-second lag threshold and a 30-second refresh interval produces a 90-second worst case. The budget must be spent: the replica lag observed at read time is subtracted before the cache TTL is chosen, and what remains is the allowance for the next layer.

Bounded means enforced, not intended. The distinction between a bounded and an unbounded system is whether something checks. An entry that arrives over budget must be refused, not served with a note. A read path that cannot meet the budget from cheap sources must escalate, degrade, or fail — and which one it does must be a decision made in advance rather than an accident of code structure.

A single budget decremented layer by layer A thirty second budget bar at the top. Below it, each layer's consumption is subtracted in turn: replication lag takes two seconds at read time, the materialized view's current age takes twelve seconds, and the sixteen seconds remaining become the cache time to live for this particular entry. A second row shows the same layers with fixed independent settings, where each layer takes its own thirty seconds and the total reaches ninety. one budget, decremented — total is bounded at 30 s budget 30 s lag 2 view age 12 s (measured, not scheduled) cache TTL = 16 s — what is left, not a fixed number the layers fit inside the budget because each one is told what remains independent settings — total is 90 s and nobody computed it lag threshold 30 s refresh interval 30 s cache TTL 30 s worst case 90 s — three defensible settings, one indefensible total Same three components, same three technologies. The only difference is whether one number owns the total.

Step-by-Step Resolution

Step 1 — State one budget per read path

yaml
# freshness.yml — the budgets, in one place, owned by the product decision
# they encode. Reviewed when the product changes, not when the infra does.
read_paths:
  account_balance:      {budget_s: 0,    on_exhausted: escalate}   # must be current
  order_status:         {budget_s: 5,    on_exhausted: escalate}
  product_listing:      {budget_s: 60,   on_exhausted: degrade}
  follower_count:       {budget_s: 300,  on_exhausted: degrade}
  admin_daily_report:   {budget_s: 3600, on_exhausted: fail}

Derive each number from what a user can tolerate, not from what the system currently achieves. A budget set to the observed p99 is satisfied by construction and constrains nothing.

Inline verification: every read path in the codebase resolves to exactly one entry here; a path with no entry is a path with no bound.

Step 2 — Make each layer report its contribution

python
# Each source returns (value, age_seconds). Nothing may return a value
# without also returning how old it is.
def read_from_replica(sql, *params) -> tuple[object, float]:
    with replica.cursor() as cur:
        cur.execute("""SELECT CASE
                         WHEN pg_last_wal_receive_lsn() = pg_last_wal_replay_lsn()
                         THEN 0 ELSE EXTRACT(EPOCH FROM
                              (now() - pg_last_xact_replay_timestamp())) END""")
        lag_s = float(cur.fetchone()[0] or 0.0)
        cur.execute(sql, params)
        return cur.fetchone(), lag_s

def view_age(view_name: str) -> float:
    """From the refresh log, not from the cron schedule."""
    with primary.cursor() as cur:
        cur.execute("""SELECT EXTRACT(EPOCH FROM (now() - max(finished_at)))
                         FROM mv_refresh_log WHERE view_name = %s""", (view_name,))
        return float(cur.fetchone()[0] or 0.0)

Inline verification: each function returns a plausible age — the replica’s near zero when caught up, the view’s between zero and its refresh interval.

Step 3 — Decrement as the request descends

python
def read(path: str, key: str, *, view: str | None = None):
    budget = BUDGETS[path]["budget_s"]
    spent  = 0.0

    # 1. Cache — cheapest source. Serve only if its age fits the budget.
    if (e := cache.get(key)) is not None:
        age = time.time() - e["as_of"]
        if age <= budget:
            emit_age(path, age, source="cache")
            return e["value"]
        cache.delete(key)                     # over budget: not usable

    # 2. Materialized view age, if the query reads one.
    if view is not None:
        spent += view_age(view)
        if spent > budget:
            return _exhausted(path, key)      # nothing downstream can recover this

    # 3. Replica, whose lag adds to what the view already spent.
    value, lag = read_from_replica(SQL[path], key)
    spent += lag
    if spent > budget:
        return _exhausted(path, key)

    # 4. Whatever remains is this entry's TTL — never a fixed constant.
    cache.set(key, {"value": value, "as_of": time.time() - spent},
              ttl=max(budget - spent, 1.0))
    emit_age(path, spent, source="replica")
    return value

Inline verification: log spent for a sample of requests; the distribution should sit below the budget with a visible tail approaching it, not a flat line far beneath it (which would mean the budget is too loose to constrain anything).

Step 4 — Define what exhaustion does

python
def _exhausted(path: str, key: str):
    policy = BUDGETS[path]["on_exhausted"]
    BUDGET_EXHAUSTED.labels(path=path, policy=policy).inc()

    if policy == "escalate":
        # Correctness over cost: go to the primary. Bound how often this
        # can happen, or a lagging fleet becomes a primary overload.
        if not escalation_limiter.allow(path):
            raise ReadUnavailable(path)
        return primary.query(SQL[path], key)

    if policy == "degrade":
        # Serve the stale value WITH its age, so the interface can say so.
        e = cache.get(key)
        return Degraded(value=e["value"], age_s=time.time() - e["as_of"]) if e \
               else _exhausted_fail(path)

    raise ReadUnavailable(path)               # policy == "fail"

The rate limiter on escalation is the detail that prevents this from becoming a new outage. Without it, a fleet-wide lag event converts every read on every escalating path into a primary read simultaneously — the scenario covered in graceful degradation when all replicas exceed the lag budget.

Inline verification: with replay paused on every replica, an escalating path returns correct data until the limiter engages and then returns ReadUnavailable — not an unbounded flood of primary queries.

Step 5 — Export the served age as the SLI

python
READ_AGE = Histogram("db_read_served_age_seconds",
                     "Age of the data actually returned",
                     ["path", "source"],
                     buckets=(0.05, 0.25, 1, 2, 5, 15, 60, 300, 3600))

def emit_age(path: str, age_s: float, source: str) -> None:
    READ_AGE.labels(path=path, source=source).observe(age_s)
promql
# The SLI: fraction of reads served inside their own path's budget.
sum by (path) (rate(db_read_served_age_seconds_bucket{le="60"}[5m]))
  / sum by (path) (rate(db_read_served_age_seconds_count[5m]))

Inline verification: the histogram is populated for every read path in the budget file; a path with no observations is a path where the instrumentation was not wired up.

Configuration Snippet

python
# budgets.py — the whole enforcement surface, small on purpose.
from dataclasses import dataclass

@dataclass(frozen=True)
class Budget:
    seconds: float
    on_exhausted: str        # "escalate" | "degrade" | "fail"
    escalation_qps: float = 0.0   # only meaningful for "escalate"

BUDGETS = {
    # Zero budget means "never serve from a replica without a watermark check".
    # It is not the same as "use the primary" — a replica that has replayed
    # your write is still eligible.
    "account_balance":    Budget(0,    "escalate", escalation_qps=500),
    "order_status":       Budget(5,    "escalate", escalation_qps=200),
    "product_listing":    Budget(60,   "degrade"),
    "follower_count":     Budget(300,  "degrade"),
    "admin_daily_report": Budget(3600, "fail"),
}

def budget_for(path: str) -> Budget:
    try:
        return BUDGETS[path]
    except KeyError:
        # Failing closed is deliberate: an unregistered read path must not
        # silently inherit an unbounded default.
        raise RuntimeError(f"read path {path!r} has no freshness budget")

Raising on an unknown path is the load-bearing line. A default budget — even a strict one — lets new read paths ship without anyone deciding what their freshness requirement is, and the whole mechanism decays back into per-layer settings within a few releases. Making registration mandatory keeps the budget file an accurate inventory of every read path in the system.

A zero-second budget deserves a note: it does not mean “always use the primary”. It means the read must reflect everything committed before it, which a replica can satisfy if it has replayed the relevant write — the watermark check described in read-your-writes consistency with read replicas. Conflating the two sends far more traffic to the primary than correctness requires.

Escalate, degrade or fail: the three exhausted-budget policies Three branches from an exhausted budget. Escalate sends the read to the primary, protecting correctness but adding primary load, and needs a rate limit so a fleet-wide lag event does not overload the primary. Degrade serves the stale value together with its age so the interface can display it, protecting the primary at the cost of showing old data. Fail returns an error, which is correct only for paths where wrong data is worse than no data. budget exhausted spent > budget escalate read from the primary + correct data − primary load; needs a rate limit default for most user-facing paths degrade serve stale + its age + primary protected − user sees old data, told so needs UI support for the age indicator fail return an error + never wrong − unavailable right where wrong data is worse than none Choose per path, in the budget file, before the incident — not in the code path during one.

Verification and Rollback

Confirm the budget is actually binding:

promql
# Distribution of served age against the budget, per path.
histogram_quantile(0.99, sum by (le, path) (rate(db_read_served_age_seconds_bucket[5m])))

# Exhaustion rate — how often the cheap path could not meet the budget.
sum by (path, policy) (rate(db_budget_exhausted_total[5m]))

A p99 far below the budget with a zero exhaustion rate means the budget is too loose to be doing anything. A p99 pressed against the budget with a high exhaustion rate means it is too tight for the infrastructure, and either the budget or the infrastructure has to change. Both are useful findings; a budget that is never approached is not.

Confirm the escalation limiter works:

bash
# Pause replay on every replica, then watch what an escalating path does.
for h in r1 r2 r3; do psql -h $h -c "SELECT pg_wal_replay_pause()"; done
hey -n 5000 -c 50 http://app/order/12345/status
for h in r1 r2 r3; do psql -h $h -c "SELECT pg_wal_replay_resume()"; done

Primary query rate should rise to the configured escalation_qps and stop there, with the excess returning ReadUnavailable. If it rises without bound, the limiter is not in the path.

Rollback. The budget mechanism is additive to an existing read path, so removing it returns to the previous behaviour:

python
ENFORCE_BUDGETS = False     # serve from the cheapest source regardless of age

Keep the measurement on even when disabling enforcement — db_read_served_age_seconds costs nothing and is the only way to know what the unenforced system is actually doing. In practice most teams that disable enforcement after an incident re-enable it once the metric shows how old the served data becomes without it.

Edge Cases and Gotchas

Clock skew corrupts every age calculation

Ages computed as now() - as_of across machines are only as good as the clocks. A host 3 seconds ahead computes negative ages for fresh data and under-reports for stale data; a host behind does the reverse. Where the budget is tight (under about 5 seconds), derive age from LSN positions rather than timestamps, and monitor clock offset explicitly — node_timex_offset_seconds above about 100 ms makes second-level budgets unreliable.

The budget must cover the client too

A browser or mobile client that caches the response for 60 seconds adds 60 seconds to whatever the server computed, and the server-side histogram will never see it. If clients cache, either subtract their cache duration from the server-side budget or send the computed age in the response so the client can enforce the remainder:

http
Cache-Control: max-age=14
X-Data-Age-Seconds: 16

A zero budget is not the same as “use the primary”

A read path with a zero-second budget must reflect everything committed before it — but a replica that has replayed the relevant write satisfies that perfectly. Treating a zero budget as “route to primary” sends far more traffic to the primary than correctness requires. Implement it as a watermark check against replica replay position, with the primary as the fallback when no replica has caught up.

FAQ

How do I choose the budget number?

From the product behaviour the read supports, not from what the current system achieves. Ask how long a user can see the previous value before it is wrong — a follower count can be a minute stale, a shopping cart cannot be a second stale, a balance shown before a transfer must be current. Deriving the budget from measured performance produces a number that is unfalsifiable by construction and therefore useless as a constraint.

Why one budget instead of a limit per layer?

Because staleness composes. Per-layer limits are each individually defensible and sum to something nobody has calculated: a two-second lag budget plus a five-minute view interval plus a sixty-second cache TTL is a six-minute worst case, from three settings that all look conservative. One budget decremented by each layer makes the total the thing you control and the layers the thing that fit inside it.

What should happen when the budget is exhausted?

One of three things, chosen per read path in advance: escalate to the primary, which protects freshness at the cost of primary load; degrade, by serving the stale value with an explicit age the interface can show; or fail, returning an error rather than wrong data. Failing is right for a small number of paths, escalation for most, and degradation for anything where showing a timestamp is acceptable to users.

Does this require distributed tracing?

No. Tracing makes the per-layer breakdown much easier to investigate, but the budget itself only needs each layer to return the age of what it produced, plus a single histogram of the final served age. That is a few lines of code and one metric. Add tracing when you need to know which layer consumed the budget on a particular request; add the budget first regardless.

← Back to Caching & Materialized Reads for Stale-Tolerant Workloads