Charging the Solver's Clock: Trace-Driven Evaluation of Online Matching Allocators

Many systems hand out discrete resources by solving a bipartite matching problem. Requests sit on one side of a graph, resource slots on the other, edge weights score each pairing, and an exact solver such as the Hungarian method finds the best overall assignment. The online versions come with guarantees: low regret against a hindsight optimum, or a bounded competitive ratio, meaning a guaranteed fraction of the best achievable value. Two things are usually missing from how these methods are tested. The instances are synthetic, with smooth Gaussian, Beta or i.i.d. arrivals. And the solver is treated as free, so the time spent computing a matching never counts against the system. We propose a trace-replay harness built from the Alibaba 2017 production cluster trace. In this harness every allocator pays for its own wall-clock decision time: requests whose deadlines pass while the solver is still running are lost, and a matching computed on old state is applied to the state that exists once the solver finishes.

The claim is narrow and testable. Once solver latency and real arrival jaggedness are both charged, the ranking of online matching allocators changes relative to synthetic, zero-latency evaluation. There is likely a measurable crossover in request rate and deadline tightness below which exact re-optimized matching wins and above which degree-guided or dual-price greedy rules win. The deliverable is that crossover map, together with an ablation that says how much of the change comes from latency and how much from the trace.

Why this gap, and what already exists

The motivating evidence is that the main online-matching allocators in the literature were validated only on generated instances. An Online Learning Approach to Sequential User-Centric Selection Problems pairs an optimistic bandit index with a Hungarian subroutine and shows sub-linear regret on a 15-arm, 30-user simulation. It never measures the cost of re-running the solver inside its loop. Online Learning and Matching for Resource Allocation Problems updates dual "shadow prices" by online gradient descent so that scarce items are throttled. It is tested on synthetic customers and argues that regret cannot be measured on real logs because the true purchase probabilities are unknown. A stochastic algorithm for online bipartite resource allocation problems re-solves a two-stage stochastic program at intervals. Its authors report substantial computational overhead as the number of re-optimizations grows, which motivates our latency charge directly.

Other work constrains the design. (Optimal) Online Bipartite Matching with Degree Information shows that worst-case design is pessimistic on real topologies. Its greedy minimum-predicted-degree rule (MPD) reaches about 0.99 competitive ratio on the Oregon and CAIDA router graphs, while the classic randomized Ranking algorithm reaches 0.95–0.97. However, that study is unweighted and uncapacitated. Bipartite Graph Matching Algorithms for Entity Resolution: An Empirical Evaluation finds that linear-time greedy matchers match or beat assignment solvers, and that the input threshold matters more than the algorithm. That result is for record linkage, not allocation. Together these warn us that greedy may simply win.

NetMoE is the one system in the file that runs Kuhn-Munkres matching on real hardware. It hides solver cost by running the matching on host CPUs while the GPUs compute. We borrow that idea as a "pipelined" variant of each exact allocator.

Our trace substrate comes from Anomaly Analysis for Co-located Datacenter Workloads in the Alibaba Cluster. That study characterizes the trace: about 1,300 machines, bursty batch jobs co-located with long-lived online services, 81 machines flagged as anomalous, and healthy machines left idle.

This proposal differs from all of the above in two ways. It evaluates weighted, capacitated online matching on a production trace. And it treats decision latency as part of the outcome rather than reporting it separately.

Core Claim and Metric

We convert the trace into an online allocation instance. Batch tasks arrive at their logged times with their logged resource requests. Each machine is split into capacity slots, one graph node per slot, following the standard construction where a capacity of $c$ becomes $c$ separate nodes. The available slots change over time as the logged utilization of the co-located online services rises and falls. The anomalous machines identified in the analysis paper are made temporarily unavailable at the flagged times.

Hindsight evaluation works here, contrary to the obstacle raised in the e-commerce paper. Realized arrivals and demands are fully logged, so an offline optimal matching over the whole trace can be computed, even though stochastic pseudo-regret cannot.

The headline metric is latency-charged value:

$$V_{\text{charged}} = \sum_{r \in R} w_r \,\mathbf{1}[\,t^{\text{decide}}_r + d^{\text{solve}}_r \le \tau_r\,],$$

The symbols are defined as follows. $R$ is the set of requests. $w_r$ is the value of request $r$ if it is placed on a feasible slot under the realized state at commit time. $t^{\text{decide}}_r$ is when the allocator begins the decision that covers $r$. $d^{\text{solve}}_r$ is the measured wall-clock solver time for that decision. $\tau_r$ is the request's deadline. We report $V_{\text{charged}}$ divided by the value of the hindsight optimum.

Placements that turn out infeasible because the state changed while the solver ran get zero value. This is how staleness enters the metric.

Research Program

We will build the harness, implement every allocator against one common interface, and run all of them on a single fixed reference CPU, so that solve times can be compared across methods.

The study varies two knobs. The first is load, by replaying the trace at 1x up to compressed time-scales. The second is deadline tightness, using deadline multiples of the median task duration. For each cell we record charged value, uncharged value, and the full distribution of solve times.

A secondary analysis tests the modularity assumption, which says a pairing's value does not depend on the other pairings. We estimate an interference proxy from co-location utilization in the trace. We then score each matching with and without that proxy, to see whether exact matching's advantage survives when edge values are not independent. Because the 2017 trace logs utilization rather than task slowdown, this proxy is an assumption, and we will state it as one.

Baselines

The naive reference point is first-come-first-served placement onto the least-loaded feasible machine. It approximates what a simple cluster scheduler does, and it sets the floor every method must clear.

The strongest greedy competitor is MPD from (Optimal) Online Bipartite Matching with Degree Information, extended to capacitated slots by using remaining slot counts as degrees. Its reported result is about 0.99 competitive ratio on Oregon and CAIDA, against 0.95–0.97 for Ranking. Before using our capacitated extension, we will first reproduce that unweighted result on those two graphs, to check our implementation. Ranking runs alongside it as the worst-case-guaranteed reference.

The strongest dual-price competitor is the online-gradient shadow-price method of Online Learning and Matching for Resource Allocation Problems. It reports about 315k versus 203k revenue over greedy on 1M synthetic customers. The strongest exact competitor is the re-optimized primal-dual method of A stochastic algorithm for online bipartite resource allocation problems. It reports empirical competitive ratios often above 0.9 on generated instances, with re-optimization interval $\Delta=10$ and smoothing $\rho=0.2$. We add a batched Hungarian allocator that re-solves every $k$ arrivals.

For the Alibaba replay itself, no reported result was found on Lacuna for any of these methods.

Every method gets the same tuning budget, a fixed grid search, run on the first two trace hours and frozen for the remaining ten. All methods share the same machine and the same edge-value function.

The key ablation runs every method with the solve time set to zero. Comparing that run with the charged run isolates how much the latency charge contributes. A second ablation replays a synthetic instance fitted to the trace's marginals, with Poisson arrivals at the trace's mean rates, to isolate how much the trace's jaggedness contributes.

An exact method "beats" MPD in a cell only if its charged value exceeds MPD's by more than the seed-to-seed spread across five replay offsets. We count wins by cell, not on average.

Why not just…?

Why not just benchmark on heavier-tailed synthetic arrivals instead of a real trace? This is a real threat, and our synthetic-fit ablation answers it directly. If a generator matched to the trace's marginals reproduces the same algorithm rankings across the load and deadline grid, then the trace adds nothing. That would be a useful negative result, because it would license cheaper synthetic evaluation for future work. We expect differences from the bursty batch-job behavior and the idle and anomalous machines the analysis paper documents, but we do not assume them.

Why not just microbenchmark Hungarian runtime separately? A standalone timing says how long a solve takes. It does not say what that delay costs. The cost depends on how fast slot availability changes during the solve and how many deadlines expire meanwhile, and both depend on the trace. The zero-latency ablation measures exactly this interaction. The NetMoE result also shows that solve time can sometimes be hidden entirely, so we include pipelined variants rather than assuming a fixed penalty.

Why not just use greedy and stop? The MPD results and the entity-resolution results both suggest greedy may be enough. If MPD wins in every cell, that is the finding: exact online matching would then be unjustified for cluster allocation at these scales. Our hypothesis is narrower. We expect exact matching to win at low load with loose deadlines and with scarce capacity, the regime where the e-commerce paper's greedy rule ran out of inventory. The crossover map will show which hypothesis holds.

Decisive Checks

Three outcomes settle the question. The first is whether the latency charge reorders any pair of methods relative to the zero-latency ablation in at least one realistic load cell. The second is whether trace replay and the fitted synthetic instance produce different rankings. The third is whether the advantage of exact matching over MPD disappears once the interference proxy is applied. If none of the three changes anything, current synthetic practice is vindicated, and we will report that plainly.