betaFeedback

WorksComputer Science

Predicting, Fast and Slow: SSD Already Knows Which Guess Is Wrong

Abstract

Heimdall, a learned controller, calls slow on 52% of an SSD's reads when 30% are slow. Uncertainty estimators, the remedy prescribed for its wrong guesses, cannot find them: nine of them do no better than a coin. The drive can. On one trace, 2% of the reads of 4 to 8 KiB that found less than 4 KiB outstanding while the drive was answering came back slow, and Heimdall called 96% of them slow. A 4,096-entry table of how the drive's recent reads came back, untrained and 21 ns a decision, ranks the wrong guesses at a median AUROC of 0.68 on 57 held-out traces, where the nine sit at 0.46 to 0.52, and it predicts slow reads better than Heimdall itself.

The estimators flip a coin

Heimdall [1] puts a small neural network in front of each SSD of a replicated pair. Before a read is submitted the network guesses fast or slow, and a slow guess sends the read to the other drive. Gohil et al. [2] add an uncertainty estimator that scores each guess, so that a distrusted read can go to both drives. At microsecond budgets they prescribe distance from the training data: “a distance-based estimator must be selected, as it is the only viable option”. Their evidence is latency: a 56 to 57% cut at p99.9. Whether distance picks out Heimdall’s wrong guesses, they did not measure.

We measured it. Heimdall’s own pipeline trains the network on the first minute of a three-minute replay, as its long-term evaluation deploys it [1 §7], and every read of the next two minutes is scored. A read is slow when its latency exceeds the knee of the replay’s read-latency distribution, found as LinnOS [5] and Heimdall find it. A guess is wrong when the read comes back on the other side of that knee: the task as Gohil et al. state it, “binary latency classification (fast/slow) for each I/O.” An estimator’s score is the AUROC with which it ranks wrong guesses above right ones, in the worst of four 30-second windows.

Nine estimators compete. Three families are those of Gohil et al., rebuilt from their description: distance, conformal scores and a Bayesian network [6]. Four are standard: the network’s margin, an ensemble [7], deep nearest neighbours [8] and trust score [9].

None finds the wrong guesses (Figure 1): on 57 held-out traces their median AUROCs run from 0.46 to 0.52. The traces are the busiest stretches of 38 volumes, nearly all from the UMass collections [10] and the rest from MSR Cambridge [11], at their recorded pace or eight times faster. Each was replayed once on a WD_BLACK SN770, and nothing here was tuned on them. Used as Gohil et al. use it, to flag the inputs beyond the 90th percentile of the training distances, Euclidean distance says little: a guess it flags is wrong a median 4 points more often than one it passes, on traces where a median 42% of Heimdall’s guesses are wrong.

Figure 1. Which of Heimdall’s guesses are wrong? Each dot is one of 57 held-out traces, at the AUROC with which a row ranks wrong guesses above right ones. Bars are medians. Right: only reads Heimdall admits as fast, where knowing that it calls slow too often no longer helps. Red rows learn from completed reads. Grey rows are the nine uncertainty estimators.

The wrong guesses are a bias

Doubt is the wrong thing to look for. Heimdall is biased. Over the 57 traces it calls slow on a median 52% of reads, where a median 30% come back slow, and a median 73% of its wrong guesses are slow calls on reads that come back fast. Figure 2 shows it at its starkest. An estimator that asks how unfamiliar an input is, or how torn the network is, cannot see a bias. One number can: a single running count of how often reads come back slow, blind to the read in front of it, outranks all nine estimators (median 0.60).

Figure 2. The table after three minutes of one held-out trace, an MSR Cambridge media-server volume, for reads submitted with nothing outstanding for longer than TT, the knee of the first minute’s read latencies. Sizes and backlogs are classes one power of two wide, named by their lower edge. Blank cells saw fewer than 20 reads. Slow reads are large reads behind a backlog, more so just after the drive has gone quiet. Heimdall’s twelve inputs carry neither the backlog in bytes nor the quiet.

The bias is taught. Heimdall trains on period labels, which mark whole stretches of a trace slow: a median 53% of the scored reads, where a median 30% come back slow.

None of this is a weak copy of Heimdall. Its artefact reports 81 to 90% accuracy on its twelve traces, and our reimplementation of its pipeline reproduces that to within 0.5 points, labels and features identical row for row. But that test filters 5 to 18% of a trace’s rows as noise, splits the rest at random into training and test halves, and describes each I/O by the three submitted before it, finished or not. Deployed, the network sees the last three I/Os that completed, and a future it was not trained on. On those traces it is then wrong on 29 to 43% of reads by its own period labels and 27 to 67% by each read’s latency. Heimdall’s long-term evaluation reports 63 to 82% accuracy after one training session [1] [87].

The drive already knows

The table keeps one number per situation: how often reads submitted like this one have lately come back slow (Figure 2). A situation is four things known when a read is submitted: its size, the bytes already outstanding on the drive, the age of the oldest outstanding request, and whether the drive has just been quiet. With 32, 16, 4 and 2 classes of each, that makes 4,096 entries, each starting at 1/2. When a read completes, the entry qq it was submitted under moves 1/64 of the way to 1 if the read took longer than TT, and 1/64 of the way:

q←q+(1{ℓ>T}−q)/64.q \leftarrow q + (1\{\ell> T\} - q)/64.

TT is that knee taken from the first minute alone, without hindsight, so the table needs no training and no label but each read’s own latency. A fast guess is suspect in proportion to qq, a slow guess to 1−q1-q. The table keeps learning from every completion. The network and the nine estimators are fitted to the first minute and then frozen. None of the machinery is new: branch predictors have kept such confidence counters since 1996 [4].

The table was shaped on traces from Heimdall’s artefact, and no held-out trace took part in its design. On the 57 held-out traces it ranks Heimdall’s wrong guesses at a median AUROC of 0.68 and beats the best of the nine, picked per trace with hindsight, on 50 of the 57. The level is modest: 16 traces reach 0.80. And most of the lead is the bias. Among reads Heimdall admits as fast, where knowing the bias no longer helps, the table scores 0.61 against 0.47 to 0.55 for the nine, level with the best of them picked in hindsight.

Judged by Heimdall’s period labels instead of each read’s latency, the table is a coin (0.52) and the best of the nine reaches 0.62: the table learns what reads did, not what the labeller says. The two distances fail under both (0.47 and 0.51). Nor does the lead carry to two other hedging decisions [12, 13], with controllers we trained on each request’s own outcome: there the table trails the network’s margin on one and leads it narrowly on the other.

It costs what distance costs. Timed alone on one core of an Intel i9-13900KF, the table takes 21 ns a decision and Euclidean distance 19 ns, against 1.7 µs for a fixed-point copy of Heimdall’s inference. The microsecond budget that left distance as “the only viable option” admits the drive’s own outcomes too.

And it predicts slow reads better than the network it checks. Take qq itself as the forecast that a read will be slow: its median AUROC is 0.63 against 0.55 for Heimdall’s output, and it is ahead on 47 of the 57 traces. On the artefact’s own twelve traces Heimdall’s output has a median AUROC of 0.43, below a coin, and the table 0.83. The fault is not the architecture: trained on each read’s own latency, with the inputs it sees when deployed, the same network draws level with the table. The table gets there untrained.

The tail cannot referee

The evidence offered for the estimators was latency, above all the tail, and the tail does not care who picks the reads (Figure 3). We replayed the six trace pairs of Heimdall’s artefact on two identical enterprise NVMe drives, for five rounds, keeping only replays during which the drives were otherwise idle. The comparison is made with hedging on [3]: a read still unanswered after the 98th percentile of the first minute’s read latencies gets a copy on the other drive. At the median round, the better of the two distances leaves p99.9 within 9% of where the table leaves it, on every pair, and even an oracle, told which guesses were wrong in an earlier replay, gains at most

Figure 3. Whoever picks the reads, the tail barely moves. Each line is one of six trace pairs on two identical NVMe drives, with hedging on: its p99.9 read latency, the median over rounds, when the guesses to distrust are chosen by a distance, by the table, or by an oracle told which were wrong in an earlier replay.

13% on whichever of them does best.

Nor is the reported cut reproduced. Rebuilt from their description and run without hedging, the better of the two distances cuts Heimdall’s p99.9 by 3 to 24% on these drives, pair by pair at the median round, where Gohil et al. report 56 and 57% on theirs. We cannot say which difference of drives, traces or training accounts for the gap.

And part of any cut needs no model. In the replay logs that Heimdall’s artefact ships, its own hedging baseline, with no model, has the lower p99.9 on all six pairs, by 1.4 to 2.9 times, and Heimdall the lower mean on all six. Heimdall’s paper says as much: hedging “delivers shorter tail latencies above p99” [1].

What to take away. Heimdall’s wrong guesses are a bias, and doubt cannot see a bias. Before bolting an uncertainty estimator onto a learned controller, check that it finds the wrong guesses, read by read, because the tail will not say. And ask the device first. Every completed read says how it came back, and a 16 KiB table of those answers, at 21 ns a decision, knows more about Heimdall’s next guess than nine estimators do, and more about the next read than Heimdall does.

Supplement. One script recomputes every number here and every measurement left out: github.com/philippbogdan/predicting-fast-and-slow

References

References

  1. [1]D. H. Kurniawan, R. A. Putri, P. Qin, K. S. Zulkifli, R. A. O. Sinurat, J. Bhimani, S. Madireddy, A. I. Kistijantoro, and H. S. Gunawi. Heimdall: Optimizing storage I/O admission with extensive machine learning pipeline. In EuroSys, 2025.DOI
  2. [2]V. Gohil, N. Stojkovic, N. Bashir, S. Dev, G. Upasani, D. Lo, P. Ranganathan, and C. Delimitrou. When machine learning isn’t sure: Building resilient ML-based computer systems by embracing uncertainty. In MLSys, 2026.
  3. [3]J. Dean and L. A. Barroso. The tail at scale. Communications of the ACM, 56(2), 2013.
  4. [4]E. Jacobsen, E. Rotenberg, and J. E. Smith. Assigning confidence to conditional branch predictions. In MICRO, 1996.
  5. [5]M. Hao, L. Toksoz, N. Li, E. E. Halim, H. Hoffmann, and H. S. Gunawi. Predictability on unpredictable flash storage with a light neural network. In OSDI, 2020.
  6. [6]C. Blundell, J. Cornebise, K. Kavukcuoglu, and D. Wierstra. Weight uncertainty in neural network. In ICML, 2015.
  7. [7]B. Lakshminarayanan, A. Pritzel, and C. Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. In NeurIPS, 2017.arxiv.org/abs/1612.01474
  8. [8]Y. Sun, Y. Ming, X. Zhu, and Y. Li. Out-of-distribution detection with deep nearest neighbors. In ICML, 2022.arxiv.org/abs/2204.06507
  9. [9]H. Jiang, B. Kim, M. Gupta, and M. Gupta. To trust or not to trust a classifier. In NeurIPS, 2018.arxiv.org/abs/1805.11783
  10. [10]UMass Trace Repository. Storage traces: Financial and Web-Search. https://traces.cs.umass.edu/docs/traces/storage/.
  11. [11]D. Narayanan, A. Donnelly, and A. Rowstron. Write off-loading: Practical power management for enterprise storage. In FAST, 2008.
  12. [12]S. Luo, H. Xu, K. Ye, G. Xu, L. Zhang, G. Yang, and C. Xu. The power of prediction: Microservice auto scaling via workload learning. In SoCC, 2022.DOI
  13. [13]P. M. Phothilimthana, S. Kadekodi, S. Ghodrati, S. Moon, and M. Maas. Thesis: Synthesizing accurate counterfactual I/O traces from I/O samples. In ASPLOS, 2024.DOI

Paper details

vlnc:W_gw53u7pt
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents