A Resource-centric Analysis and Optimization of NoSQL Workloads using Distressed Resource Volume Metric
Gunika Verma, Aashutosh A, Pooja Srinivas, Yogesh Simmhan, Ayush Choure, Harshit Shah, Mayukh Das, Prashant Sasatte, Chetan Bansal, Abhijit Pai, Suraj Dixit, Achint Agrawal
cs.DC, cs.DB, eess.SY
2026-08-10
Luna forecasts plus Orbit placement beat Cosmos DB's Simulated Annealing: 163B vs 145B RU at 10 mERU, 47 vs 34k migrations in 6 days, same load on 65% of nodes.
Azure Cosmos DB runs in 60+ regions on hundreds of thousands of nodes, hosting tens of millions of shard replicas. A shard usually has four replicas: one primary that takes the first write and no reads, three secondaries that take all reads and federated writes. The placement unit is a replica on a VM. Resources are billed and capped in Requested Units (RU), a unitless blend of CPU, memory, and IO; one RU is roughly one key-value lookup per second.
Production packing uses Simulated Annealing inside Azure Service Fabric. A node that blows a capacity cap, or a cluster whose max/min energy ratio crosses a threshold, triggers a time-boxed neighborhood search that can move hundreds of replicas in parallel. A global CPU cap such as 80% does not kill tail errors. On a 213-node cluster pushed to 6.3M RU per node and sampled every 5 minutes, error rates stay well below 0.001% (five nines) up to 3.46M RU. In the fourth load bin, 1.2% of samples exceed 0.001%; in the top bin, 39.6% do. All three real clusters have nodes above 3M RU even though average density is modest. Skew, not mean load, is what piles errors onto the tail.
Public cloud-scale NoSQL traces with error codes barely exist. The paper releases three production Cosmos DB traces, defines a user-facing reliability profile, and ships a simulator plus a forecast-aware placer.
Traces come from North American regions covering LLM infrastructure, commerce, finance, and productivity software, and are anonymized. Nodes are homogeneous, with a 380GB memory cap and 5.2TB of storage:
| Cluster | Days | Nodes | Replicas | Peak RU |
| C1a | 60 | 196 | 32k | 3.7M |
| C1b | 13 | 196 | 35,408 | 3.7M |
| C2 | 54 | 196 | 31,207 | 4.3M |
| C3 | 54 | 190 | 42,876 | 8.5M |
C1a and C1b are the same cluster in different windows. C1b is the short slice used for ablations and train/test splits.
Distressed Resource Volume (DRV) does not count raw errors. At this scale, error codes fire in steady state. DRV first computes ERU (errors per RU), bins ERU, and records how many RU were actually delivered in each bin. Area under the curve is total served load. A better policy shifts that area left, toward low-error bins.
LoadStar is the open-source policy simulator. It normalizes logs into timestamp, replica, node, resources, and errors, replays a Packing and Migration (PAM) policy, then maps node-level RU to ERU with a non-parametric model. RU is split into 2,000 percentile bins; dense bins use kernel density estimation, sparse bins use frequency bootstrap. Mean ERU matches closely (C1a 0.0069 vs 0.0068 predicted; C1b 0.0086 vs 0.0087), but RMS is 0.1138 and 0.1254, so the high-ERU boundary is noisy. Overflow bins are unbounded: once a sample is an SLA fail, finer distinctions do not matter.
Scheduling splits into forecast and placement.
Luna (Load Utilization prediction for NoSQL workload Analytics) is LightGBM quantile regression on 30-minute peak replica load. Whittaker-Eilers smoothing, then calendar features, rolling stats, skewness, and kurtosis. On C1b, 6 days train / 6 days test, pinball loss beats ARIMA and exponential smoothing at every percentile: median 1420 vs 2531 vs 2968; 0.001 percentile 58 vs 3069 / 3751. Coverage plots show systematic over-prediction. The model would rather leave a node empty than pack it full.
Orbit has three phases:
Head-to-head is 6 days of C1b against production SA and a multi-dimensional worst-fit online packer (WFO) built on Google OR-Tools. Orbit uses α=4, 2h, P50.
Uniformity is P80/P20, utilization of the 80th-percentile node over the 20th. Perfect balance is 1.0. Orbit's median P80/P20 across four resources sits at 1.34-1.73, tighter than WFO, with SA the most spread. On C2 and C3 the medians are 1.33-1.69 and 1.34-1.64. WFO did not finish those longer traces.
| Policy | RU delivered at 10 mERU | 6-day migrations | Peak single move burst |
| Orbit | 163B | 47 | 7 |
| SA | 145B | 34k | 18.7k |
| WFO | 137B | 19.3k | 19.3k (one full repack) |
Total load is the same, so extra RU in the 10 mERU bin came out of worse bins. WFO needs 30-60s when fewer than 500 replicas arrive in a 5-minute window, 5-8 minutes at 3,000+, and about an hour for a full repack. Orbit decides in under 30s and has tens of minutes to hours of lead time from Luna.
Shrinking C1b from 100% of nodes to 65% in 5% steps is the floor; below that, replicas do not fit. At 65%, RU P80/P20 moves from 1.73 to 1.60. Load at 10 mERU is 151.2B vs 147.5B; at 100 mERU, 1.47B vs 1.65B. That is the 35% resource cut. The policy is in production; the paper claims on the order of $100M per year.
Ablations: DRV is similar for α in 1.0-4.0 and worse at 0.1 and 10. A 0-hour (no forecast) window wrecks uniformity by orders of magnitude in the first days; 0.5-24h look alike, so 2h is the default. P10 and P90 trigger thousands of moves; P25 and P50 trigger the fewest. Default is P50.
For anyone who packs cloud databases, the reusable piece is the eval pipeline: real NoSQL traces, an error-aware DRV profile, and a simulator that maps RU onto user-visible errors. Public traces have been VMs, Hadoop, and GPUs. NoSQL database traces stalled a decade ago and almost never include fault codes.
For a managed store that already chose its shard and replica factor and only moves replicas inside a cluster, the gain is concrete: 35% fewer machines at the same SLA, migrations from tens of thousands down to dozens. Luna is not a deep sequence model. Gradient boosting plus quantiles is enough to drive placement. Orbit without a forecast collapses; 30 minutes of lookahead is already enough.
The placer is worst-fit plus skew and the forecast is GBDT. That is an engineering increment. The traces and LoadStar are the part outsiders can actually use. The $100M production number cannot be audited from outside.
There is no standalone limitations section. The authors note that LoadStar's l1 and l2 errors diverge, so high-ERU bins are unreliable; Luna over-predicts; hyperparameters were swept only on C1b then applied to C2 and C3; WFO never finished the large clusters, so that baseline is incomplete. Future work flags other NoSQL and cloud traces, the cost of the migrations themselves, and online correction of forecast overestimates.
The study is a simulator replay, not an online A/B test. ERU is sampled from the historical RU-ERU relationship. Whether that relationship still holds after the placer changes the mix is untested. Nodes are homogeneous, moves stay inside a cluster, and partitioning is given. That is a different problem from mixed instance types or cross-AZ moves. The abstract calls $100M/yr potential; the introduction writes it as deployed savings. The traces are three North American clusters.