Fetch-Once Scheduling Against Stale Cache Indicators

Cluster and edge schedulers try to run each task on a machine that already holds the task's input data, because fetching data from a distant origin store is slow. Today's locality-aware schedulers assume the scheduler knows exactly where data lives. In practice, worker caches insert and evict items constantly and advertise their contents with periodically refreshed Bloom filters, which are compact bit arrays that answer "is this item here?" quickly. Between refreshes these advertisements go stale. An item that was cached a moment ago still reads as "absent", which is called a stale false negative. A scheduler that trusts the advertisement sends the task elsewhere and pays a remote fetch it did not need to pay. The caching literature has shown that a single client gains a lot by treating a "no" as uncertain and probing anyway. That work has never been carried into the scheduler, where thousands of tasks share inputs, machines have capacity limits, and one fetch can serve many tasks.

We propose a scheduler that turns each stale advertisement into a probability that the item is present. It then solves a linear program, an optimization with continuous variables standing in for yes/no decisions, that jointly chooses task placements and which machine–item pairs to "open". Opening a pair means paying the probe and possible fetch once, after which every co-located task that needs the item gets a hit. A dependent rounding step converts the fractional solution into a real schedule. The central claim is about structure, not about using an LP for its own sake. Expected fetch cost under staleness is charged per machine–item pair, not per task. The obvious fix is to plug expected processing times into an existing scheduler, and that fix charges every task the full expected miss. It therefore overpays exactly when tasks share data, and it ignores the load that probes put on the probed machines.

Core Claim

Fix a batch of tasks $j$, machines $i$, and data items $d$, where $d(j)$ is task $j$'s input. Let $q_{id}$ be the scheduler's posterior probability that item $d$ is currently at machine $i$. The posterior is computed from the indicator's answer, its age since last refresh, its false-positive rate, and an online estimate of how often negatives turn out to be hits. The online estimate is the same exponential-moving-average statistic that False Negative Awareness in Indicator-based Caching Systems uses for heterogeneous caches. The relaxation is

$$\min T \quad \text{s.t.} \quad \sum_i x_{ij} = 1,\quad x_{ij} \le y_{i,d(j)},\quad \sum_j x_{ij}\,h_{ij} + \sum_d y_{id}\big(c_i + (1-q_{id})M_{id}\big) \le T,\quad \sum_{i,d} y_{id}(1-q_{id})s_d \le B .$$

The symbols are defined as follows. $x_{ij}\in[0,1]$ is the fraction of task $j$ placed on machine $i$, and $y_{id}\in[0,1]$ is the fraction to which machine $i$ "opens" item $d$. $h_{ij}$ is the task's runtime once its data is local. $c_i$ is the probe cost at machine $i$. $M_{id}$ is the time to fetch $d$ from the origin into $i$. $s_d$ is the item size. $B$ is the batch's budget on bytes over the origin link. The linking constraint $x_{ij} \le y_{i,d(j)}$ makes the expected miss a once-per-pair cost, much like opening a facility in facility location. This is the feature that per-task expected-time models lack.

When every item is used by exactly one task, the program collapses to unrelated-machine makespan with inflated processing times. That collapse is a built-in sanity check and a clean ablation.

Research Program

The work has four parts.

Presence model. We build the presence posterior $q_{id}$ for both kinds of indicator error. Positive answers carry Bloom false positives plus eviction-induced staleness. Negative answers carry insertions by other tenants since the last refresh. The posterior is calibrated online from probe outcomes.

Solver. We solve the relaxation at batch boundaries. The starting point is the multiplicative-weights packing/covering machinery of Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems. That paper gives a $(2+\epsilon)$ makespan algorithm on unrelated machines in time linear in the number of task–machine edges, and it supplies the method we extend. Our program adds the item-level $y$ variables and the origin-budget row, but it keeps the packing/covering form those solvers need. We will check empirically whether the nearly-linear runtime survives at the 100,000-task scale.

Rounding. Rounding proceeds in two stages.

  1. For each item, the open fractions $y_{\cdot d}$ are rounded across machines with a dependent rounding scheme. The pairwise mass-shifting used for knapsack and cardinality constraints in A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint and in Planning to Fairly Allocate preserves each marginal and the number of opened replicas. As a result, expected fetch cost and expected origin bytes match the LP.
  2. Tasks are then assigned among opened machines with the unrelated-machine rounding of the nearly-linear LP paper.

The target guarantee is bicriteria: expected fetch cost no worse than the LP's, and makespan within a constant factor of $T$ plus one additive maximum-fetch term. We state this as a conjecture to prove. It is not yet a result.

Feedback. After dispatch, the scheduler folds its own dispatches into $q_{id}$. Only foreign insertions remain uncertain. This keeps the method honest against the shadow-index alternative discussed below.

The regime that makes the problem real is a shared cache fleet with several independent schedulers or tenants. Examples are multi-tenant analytics clusters and CDN-adjacent compute. In that regime no scheduler sees all insertions, and the indicator refresh rate is capped by a bandwidth budget, as studied by Self-adjusting Advertisement of Cache Indicators with Bandwidth Constraints.

That paper and the two false-negative-awareness papers, False Negative Awareness and On the Power of False Negative Awareness, motivate this work. They show that staleness is costly and that probing on negatives pays off. All of them decide per request, against caches whose capacity is never stressed by the probes themselves. On the scheduling side, Data-Locality-Aware Task Assignment and Scheduling and Delay scheduling supply the locality objective and the baselines. Both treat locality as a known, static replica map, and our proposal removes exactly that assumption.

Baselines

The naive reference is the indicator-oblivious locality scheduler. We run Water-Filling and Replica-Deletion from Data-Locality-Aware Task Assignment and Scheduling with the stale Bloom filter treated as the true replica map. A second reference has no locality at all: least-loaded placement. These two bound the problem from below.

The strongest existing competitor is the "false-negative-aware transformation" of a good locality scheduler. In False Negative Awareness in Indicator-based Caching Systems the authors prove that any oblivious algorithm can be made false-negative-aware while keeping its approximation guarantee. The direct analogue here runs two versions on identical inputs:

  1. Water-Filling and OBTA with each task's processing time replaced by its expected value under $q_{id}$.
  2. The unrelated-machine LP of Nearly-Linear Time LP Solvers with the same expected times.

It is the strongest competitor because it already uses the same posterior and the same LP solver. Any gain we show must therefore come from fetch-once coupling and probe-load accounting, not from better information.

The reported numbers available for this baseline family are thin.

  • The false-negative-aware caching papers report access-cost reductions of up to 25%. They also report that a false-negative-aware system refreshed every 8,000 insertions matched an oblivious one refreshed every 512 on the Wiki trace.
  • For OBTA, Zhao et al. report reaching optimal results with roughly 50% less solver overhead. They also report that Water-Filling runs two orders of magnitude faster than OBTA on cluster-trace-v2017.
  • No reported result was found on Lacuna for makespan of OBTA or Water-Filling under stale indicators. No reported result was found on Lacuna for any scheduler in this combined setting.

The baselines therefore have to be run by us, not quoted.

We also run Delay Scheduling in two versions: as published, and with the per-request false-negative-aware probe threshold applied to each candidate node. We run greedy per-task false-negative-aware probing, which is HeCSFNA applied at dispatch. Finally, we run a shadow-index scheduler that updates its own copy of the filters with its own dispatches.

All methods share the same simulator, traces, posterior estimator, indicator refresh schedule, and per-batch wall-clock budget. Any method with tunable parameters gets the same tuning grid on a held-out week of trace. These are the delay window for Delay Scheduling and the smoothing constant for the moving-average estimators.

Our ablation keeps everything in our method but deletes the linking constraint, so the fetch cost is charged per task. This isolates the key ingredient. A second ablation replaces dependent rounding with independent rounding.

Beating the strongest baseline means one of two outcomes at equal or lower makespan, with confidence intervals over seeds excluding zero:

  1. Fewer origin bytes, at the same bandwidth budget.
  2. The same origin bytes at a lower indicator refresh rate.

Why not just…?

Why not just plug expected processing times into an existing scheduler, as the false-negative-aware transformation theorem suggests? This is the most serious alternative, and in one regime it is provably equivalent to our method. When each item feeds a single task, our LP is exactly the plug-in LP. The difference appears when tasks share inputs. Per-task expected costs then add up $k$ expected misses for $k$ co-located sharers, when only one fetch can occur. This biases the scheduler toward scattering sharers across machines. We test this directly by sweeping the number of tasks per input item. If the plug-in baseline matches us at high sharing, the coupling is not worth its cost and we will say so.

Why not just let each task greedily probe when the false-negative probability exceeds probe cost over miss penalty? The threshold is exactly right for an isolated request, as shown in On the Power of False Negative Awareness. It has no notion of the probed machine's queue, though. Thousands of tasks that see the same moderately likely, cheap-to-probe node will all choose it. We measure the maximum per-node probe and queue load directly. Our method wins on this axis only if greedy probing actually concentrates load on the traces, so this experiment can also fail.

Why not just have the scheduler track its own dispatches, so its view is never stale? If the scheduler is the only source of cache insertions, this shadow index removes insertion-side false negatives entirely, and our posterior adds little. The case for our method rests on foreign insertions from other tenants or schedulers. We therefore sweep the fraction of insertions the scheduler does not observe from 0 to 0.9. We expect our advantage to be zero at 0 and to grow with the foreign share. A flat curve would falsify the motivation.

Why not just refresh the indicators more often? Refresh bandwidth is the binding constraint that Self-adjusting Advertisement of Cache Indicators budgets explicitly. The 16x refresh-rate equivalence reported in the false-negative-aware caching paper shows how expensive matching awareness with freshness is. We report every method's makespan as a function of refresh bandwidth, so this trade-off appears as a curve rather than an argument.

Why not just round independently? The worry is variance against capacity and budget rows, documented in Bidder Selection Problem in Position Auctions and Planning to Fairly Allocate. The rounding ablation measures how often independent rounding breaks the origin-byte budget or the makespan target in this setting.

Proposed Experiments

No public trace contains both task-to-data mappings and live cache contents, so we combine two sources.

Scheduling side. We start from the cluster-trace-v2017 setup of Data-Locality-Aware Task Assignment and Scheduling: 250 jobs, over 113,000 tasks, and 100 servers. We replace its static replica map with per-server LRU caches sized as a fraction of the working set. A sensitivity run uses runtime predictions from the ATLAS LightGBM pipeline instead of true durations, because tail metrics there are known to be fragile under misprediction.

Cache side. Foreign tenants insert into the same caches using the Wiki and Gradle request traces from the false-negative-aware caching papers. Wiki is frequency-biased and Gradle is recency-biased, and the false-negative-awareness gains were larger under recency bias. Indicators refresh every $T$ insertions or under a byte budget, using the CAB policy.

Metrics. We measure batch makespan, total completion time, max-stretch, origin bytes fetched, probes issued, and maximum per-node probe load. We also measure posterior calibration, defined as the predicted versus realized hit rate on probes, and solver wall-clock time per batch.

Decisive checks. Each of four sweeps carries a falsifiable prediction.

  1. The sharing-degree sweep should show our method tied with the plug-in LP at one task per item and pulling ahead as sharing grows.
  2. The foreign-insertion sweep should show zero advantage over the shadow index when all insertions are observed.
  3. The bits-per-element sweep tests the paradox from False Negative Awareness at the scheduling level. We expect oblivious schedulers to get worse as filters grow at fixed refresh bandwidth, and ours to improve monotonically or stay flat.
  4. The scaling run checks whether the coupled LP stays within a per-batch budget comparable to OBTA's at 100,000+ tasks. If it does not, the method needs the controlled-fractionality tricks of Ene et al. to be practical.