persistant_core/
choose.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//! Stage 4 of backend benchmarking, kind-agnostic: **"best backend for X"**, as a ranked list *with its
3//! evidence*. The kinds (`persistant_kv::choose`, `persistant_blob::choose`) supply their contract leaf
4//! ids, their workload ids and a table of what their backends declare about durability; the logic is
5//! here, once.
6//!
7//! The consumer states what it needs; nothing is chosen for it:
8//!
9//! - the contract leaves it relies on ([`Need::leaves`]),
10//! - the **minimum durability class** it will accept ([`Need::min_durability`]),
11//! - the one workload it ranks by ([`Need::rank_by`]), and
12//! - the environment the ranking is for ([`Need::environment`], an
13//!   [`Environment::comparable_key`](crate::bench::Environment::comparable_key)).
14//!
15//! [`choose`] returns a [`Choice`]: the eligible backends fastest first, each with the measurement it
16//! was ranked on (date, re-run command, image digest), the eligible ones that were not measured in that
17//! environment, and every backend that was **excluded, with the reason**. If nothing is eligible it is
18//! an error ([`NoneEligible`]) that carries the exclusions: no silent fallback, no "closest match".
19//! Every decision is written as lines ([`Choice::log_lines`]) the caller logs.
20//!
21//! **Durability is declared; `Process` and `Machine` are verified only where a test ran** (the kind's
22//! process-kill test; the guest power-cut harness in `scripts/machine-durability`). A backend with no
23//! declaration is excluded as unknown once the need asks for more than `Volatile`. `Machine` is marked
24//! verified only for what that harness exercised, and never for host power loss or NTFS.
25
26use crate::bench::{Outcome, SpeedTable, Stats};
27use crate::{Config, Reason};
28use std::fmt;
29
30/// A required leaf the backend did not pass.
31#[derive(Debug, Clone, PartialEq, Eq)]
32pub struct LeafFailure {
33    /// The leaf id (`kv.get`).
34    pub leaf: String,
35    /// `Missing`, `Wrong` or `Untested`.
36    pub reason: Reason,
37    /// The test's own words.
38    pub note: String,
39}
40
41/// Whether a backend passed the contract for the leaves a need names.
42#[derive(Debug, Clone, PartialEq, Eq)]
43pub enum Eligibility {
44    /// Every needed leaf passed.
45    Eligible,
46    /// At least one did not. Never empty.
47    Excluded(Vec<LeafFailure>),
48}
49
50/// How much a stored value survives. Ordered: a higher class includes the lower ones.
51#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
52#[non_exhaustive]
53pub enum Durability {
54    /// Lost when the process exits.
55    Volatile,
56    /// Survives the process exiting or crashing; not claimed to survive the machine losing power.
57    Process,
58    /// Documented to survive an operating-system crash or power loss (the write is flushed to stable
59    /// storage before it is acknowledged).
60    Machine,
61}
62
63impl Durability {
64    /// The word used in logs.
65    pub fn as_str(self) -> &'static str {
66        match self {
67            Durability::Volatile => "volatile",
68            Durability::Process => "process",
69            Durability::Machine => "machine",
70        }
71    }
72}
73
74/// A durability class, where it comes from, and how much of it a test has checked.
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub struct Declared {
77    /// The class the backend documents. Eligibility uses this.
78    pub class: Durability,
79    /// Why it is believed.
80    pub basis: &'static str,
81    /// The highest class a test has actually verified, if any. `Process` is verified by
82    /// [`durability`](crate::durability) (`kv.durability.process`: a writer killed after
83    /// acknowledged writes, the store opened again). `Machine` is verified by `kv.durability.machine`
84    /// (`scripts/machine-durability`: a Hyper-V guest powered off after acknowledged writes, booted, every
85    /// acknowledged key checked), which says nothing about host power loss, NTFS or the disk's own cache.
86    pub verified: Option<Durability>,
87}
88
89/// What the consumer needs. Every field is the consumer's to state.
90#[derive(Debug, Clone, PartialEq, Eq)]
91pub struct Need {
92    /// The contract leaves the consumer relies on. A backend failing any is excluded.
93    pub leaves: Vec<String>,
94    /// The lowest durability class acceptable.
95    pub min_durability: Durability,
96    /// The workload to order eligible backends by (median time, smaller first).
97    pub rank_by: String,
98    /// [`Environment::comparable_key`](crate::bench::Environment::comparable_key) of the
99    /// machine the ranking is for. Measurements from any other environment are not used.
100    pub environment: String,
101}
102
103/// One backend, with the evidence gathered about it. `eligibility` comes from the kind's contract
104/// check on the needed leaves.
105#[derive(Debug, Clone, PartialEq, Eq)]
106pub struct Candidate {
107    /// Backend name, as in the matrix and the speed files.
108    pub backend: String,
109    /// Backend version.
110    pub version: String,
111    /// Backend configuration.
112    pub config: Config,
113    /// The result of the contract check for the needed leaves.
114    pub eligibility: Eligibility,
115}
116
117/// Why a backend is not in the ranking.
118#[derive(Debug, Clone, PartialEq, Eq)]
119pub enum Why {
120    /// Failed (or was never tested on) a needed leaf.
121    Contract(Vec<LeafFailure>),
122    /// Its declared durability is below the minimum.
123    Durability {
124        /// What it declares.
125        declared: Durability,
126        /// What was asked for.
127        wanted: Durability,
128    },
129    /// No durability declaration exists, and the need asks for more than `Volatile`.
130    DurabilityUnknown {
131        /// What was asked for.
132        wanted: Durability,
133    },
134}
135
136/// A backend left out, with the reason.
137#[derive(Debug, Clone, PartialEq, Eq)]
138pub struct Excluded {
139    /// Backend name.
140    pub backend: String,
141    /// Backend version.
142    pub version: String,
143    /// Why.
144    pub why: Why,
145}
146
147/// A backend in the ranking, with what it was ranked on.
148#[derive(Debug, Clone, PartialEq, Eq)]
149pub struct Entry {
150    /// Backend name.
151    pub backend: String,
152    /// Backend version.
153    pub version: String,
154    /// Backend configuration.
155    pub config: Config,
156    /// The measurement it was ranked by.
157    pub stats: Stats,
158    /// When it was measured.
159    pub date: String,
160    /// The image digest of the server, if it ran in a container.
161    pub digest: Option<String>,
162    /// The command that reproduces the measurement.
163    pub rerun: String,
164    /// Its declared durability and the basis.
165    pub durability: Option<Declared>,
166}
167
168/// An eligible backend with no measurement of the ranking workload in the needed environment.
169#[derive(Debug, Clone, PartialEq, Eq)]
170pub struct Unmeasured {
171    /// Backend name.
172    pub backend: String,
173    /// Backend version.
174    pub version: String,
175}
176
177/// The answer: ranked, with evidence, and everything left out with its reason.
178#[derive(Debug, Clone, PartialEq, Eq)]
179pub struct Choice {
180    /// The need this answers, so the log line is self-contained.
181    pub need: Need,
182    /// Eligible and measured, fastest median first (ties by name, then version).
183    pub ranked: Vec<Entry>,
184    /// Eligible but not measured in this environment: not ranked, not hidden.
185    pub unmeasured: Vec<Unmeasured>,
186    /// Left out, with the reason.
187    pub excluded: Vec<Excluded>,
188}
189
190/// Nothing satisfied the need. Carries what was excluded and why, so the caller can see which
191/// requirement ruled the field out.
192#[derive(Debug, Clone, PartialEq, Eq)]
193pub struct NoneEligible {
194    /// Everything that was considered.
195    pub excluded: Vec<Excluded>,
196    /// Eligible backends that had no measurement here (empty if none were eligible).
197    pub unmeasured: Vec<Unmeasured>,
198}
199
200impl fmt::Display for NoneEligible {
201    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
202        write!(
203            f,
204            "no backend satisfies the need: {} excluded, {} eligible but not measured in this environment",
205            self.excluded.len(),
206            self.unmeasured.len()
207        )
208    }
209}
210
211impl std::error::Error for NoneEligible {}
212
213/// Order the candidates for `need` using `speed`. Pure: it reads the evidence it is given and
214/// invents none.
215///
216/// A candidate is excluded if it failed a needed leaf, or its declared durability is below the
217/// minimum (or undeclared when the minimum is above `Volatile`). The rest are ranked by the median
218/// of `need.rank_by` measured in `need.environment`. An eligible candidate with no such measurement
219/// is listed as unmeasured. If nothing can be ranked the result is an error (carrying the
220/// exclusions and the unmeasured): a caller that got `Ok` has a first entry it can use.
221pub fn choose(
222    candidates: &[Candidate],
223    need: &Need,
224    speed: &SpeedTable,
225    declared: &dyn Fn(&str) -> Option<Declared>,
226) -> Result<Choice, NoneEligible> {
227    let mut ranked = Vec::new();
228    let mut unmeasured = Vec::new();
229    let mut excluded = Vec::new();
230    for c in candidates {
231        if let Eligibility::Excluded(ex) = &c.eligibility {
232            excluded.push(Excluded {
233                backend: c.backend.clone(),
234                version: c.version.clone(),
235                why: Why::Contract(ex.clone()),
236            });
237            continue;
238        }
239        let dur = declared(&c.backend);
240        match dur {
241            Some(d) if d.class < need.min_durability => {
242                excluded.push(Excluded {
243                    backend: c.backend.clone(),
244                    version: c.version.clone(),
245                    why: Why::Durability {
246                        declared: d.class,
247                        wanted: need.min_durability,
248                    },
249                });
250                continue;
251            }
252            None if need.min_durability > Durability::Volatile => {
253                excluded.push(Excluded {
254                    backend: c.backend.clone(),
255                    version: c.version.clone(),
256                    why: Why::DurabilityUnknown {
257                        wanted: need.min_durability,
258                    },
259                });
260                continue;
261            }
262            _ => {}
263        }
264        let row = speed.rows().iter().find(|r| {
265            r.workload == need.rank_by
266                && r.backend == c.backend
267                && r.version == c.version
268                && r.config == c.config
269                && r.env.comparable_key() == need.environment
270                && matches!(r.outcome, Outcome::Measured(_))
271        });
272        match row {
273            Some(r) => {
274                let Outcome::Measured(stats) = r.outcome else {
275                    continue;
276                };
277                ranked.push(Entry {
278                    backend: c.backend.clone(),
279                    version: c.version.clone(),
280                    config: c.config.clone(),
281                    stats,
282                    date: r.env.date.clone(),
283                    digest: r.env.digest.clone(),
284                    rerun: r.env.rerun.clone(),
285                    durability: dur,
286                });
287            }
288            None => unmeasured.push(Unmeasured {
289                backend: c.backend.clone(),
290                version: c.version.clone(),
291            }),
292        }
293    }
294    ranked.sort_by(|a, b| {
295        (a.stats.p50_ns, &a.backend, &a.version).cmp(&(b.stats.p50_ns, &b.backend, &b.version))
296    });
297    if ranked.is_empty() {
298        return Err(NoneEligible {
299            excluded,
300            unmeasured,
301        });
302    }
303    Ok(Choice {
304        need: need.clone(),
305        ranked,
306        unmeasured,
307        excluded,
308    })
309}
310
311impl Choice {
312    /// The backend ranked first. A convenience over `ranked[0]`; the whole list is the answer.
313    pub fn first(&self) -> &Entry {
314        &self.ranked[0]
315    }
316
317    /// The decision as plain lines for the caller's log: the need, then each ranked backend with its
318    /// evidence, then the unmeasured and the excluded with their reasons.
319    pub fn log_lines(&self) -> Vec<String> {
320        let n = &self.need;
321        let leaves: Vec<_> = n.leaves.iter().map(String::as_str).collect();
322        let mut out = vec![format!(
323            "choose: need leaves=[{}] min_durability={} rank_by={} environment=[{}]",
324            leaves.join(","),
325            n.min_durability.as_str(),
326            n.rank_by,
327            n.environment
328        )];
329        for (i, e) in self.ranked.iter().enumerate() {
330            out.push(format!(
331                "choose: #{} {} {} {}  p50={}ns p95={}ns ops/s={}  measured {}{}  durability={}  re-run: {}",
332                i + 1,
333                e.backend,
334                e.version,
335                e.config,
336                e.stats.p50_ns,
337                e.stats.p95_ns,
338                e.stats.ops_per_sec,
339                e.date,
340                e.digest
341                    .as_ref()
342                    .map(|d| format!(" image {d}"))
343                    .unwrap_or_default(),
344                e.durability.map_or_else(
345                    || "undeclared".to_string(),
346                    |d| format!(
347                        "{} (declared: {}; verified: {})",
348                        d.class.as_str(),
349                        d.basis,
350                        d.verified.map_or_else(
351                            || "no".to_string(),
352                            |v| format!(
353                                "up to {} by {}",
354                                v.as_str(),
355                                if v >= Durability::Machine {
356                                    "kv.durability.machine"
357                                } else {
358                                    "kv.durability.process"
359                                }
360                            )
361                        )
362                    )
363                ),
364                e.rerun
365            ));
366        }
367        for u in &self.unmeasured {
368            out.push(format!(
369                "choose: eligible, not ranked (no measurement of {} here): {} {}",
370                n.rank_by, u.backend, u.version
371            ));
372        }
373        for x in &self.excluded {
374            out.push(format!(
375                "choose: excluded {} {}: {}",
376                x.backend, x.version, x.why
377            ));
378        }
379        out
380    }
381}
382
383impl fmt::Display for Why {
384    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
385        match self {
386            Why::Contract(ex) => {
387                let parts: Vec<_> = ex
388                    .iter()
389                    .map(|e| format!("{} {}", e.leaf, e.reason.as_str()))
390                    .collect();
391                write!(f, "failed the contract ({})", parts.join(", "))
392            }
393            Why::Durability { declared, wanted } => write!(
394                f,
395                "declares durability {} but {} is required",
396                declared.as_str(),
397                wanted.as_str()
398            ),
399            Why::DurabilityUnknown { wanted } => write!(
400                f,
401                "no durability declaration and {} is required",
402                wanted.as_str()
403            ),
404        }
405    }
406}
407
408#[cfg(test)]
409mod tests {
410    use super::*;
411    use crate::bench::{Environment, SpeedRow};
412
413    fn env(machine: &str) -> Environment {
414        Environment {
415            machine: machine.to_string(),
416            os: "linux".to_string(),
417            arch: "x86_64".to_string(),
418            date: "2026-10-16".to_string(),
419            digest: None,
420            rerun: "re-run".to_string(),
421        }
422    }
423
424    fn row(backend: &str, machine: &str, p50: u64) -> SpeedRow {
425        SpeedRow {
426            workload: "speed.x.get".to_string(),
427            backend: backend.to_string(),
428            version: "1".to_string(),
429            config: Config::new(),
430            env: env(machine),
431            outcome: Outcome::Measured(Stats::from_samples(vec![p50; 10]).unwrap()),
432        }
433    }
434
435    fn cand(backend: &str, ok: bool) -> Candidate {
436        Candidate {
437            backend: backend.to_string(),
438            version: "1".to_string(),
439            config: Config::new(),
440            eligibility: if ok {
441                Eligibility::Eligible
442            } else {
443                Eligibility::Excluded(vec![LeafFailure {
444                    leaf: "x.get".to_string(),
445                    reason: Reason::Wrong,
446                    note: "lost a write".to_string(),
447                }])
448            },
449        }
450    }
451
452    fn need(min: Durability) -> Need {
453        Need {
454            leaves: vec!["x.get".to_string()],
455            min_durability: min,
456            rank_by: "speed.x.get".to_string(),
457            environment: env("laptop").comparable_key(),
458        }
459    }
460
461    fn table(b: &str) -> Option<Declared> {
462        let class = match b {
463            "file" => Durability::Process,
464            "server" => Durability::Machine,
465            "memory" => Durability::Volatile,
466            _ => return None,
467        };
468        Some(Declared {
469            class,
470            basis: "test table",
471            verified: (class >= Durability::Process).then_some(Durability::Process),
472        })
473    }
474
475    #[test]
476    fn a_machine_verified_backend_names_the_machine_test_in_the_log() {
477        fn machine(b: &str) -> Option<Declared> {
478            let mut d = table(b)?;
479            d.verified = Some(Durability::Machine);
480            Some(d)
481        }
482        let speed = SpeedTable::from_rows(vec![row("server", "laptop", 2000)]);
483        let c = choose(
484            &[cand("server", true)],
485            &need(Durability::Machine),
486            &speed,
487            &machine,
488        )
489        .unwrap();
490        let log = c.log_lines().join("\n");
491        assert!(
492            log.contains("verified: up to machine by kv.durability.machine"),
493            "{log}"
494        );
495        // The control: a Process verification still names the process test.
496        let c = choose(
497            &[cand("file", true)],
498            &need(Durability::Process),
499            &SpeedTable::from_rows(vec![row("file", "laptop", 300)]),
500            &table,
501        )
502        .unwrap();
503        assert!(
504            c.log_lines()
505                .join("\n")
506                .contains("by kv.durability.process")
507        );
508    }
509
510    #[test]
511    fn the_fastest_eligible_backend_is_first_and_carries_its_evidence() {
512        let speed = SpeedTable::from_rows(vec![
513            row("file", "laptop", 300),
514            row("server", "laptop", 2000),
515        ]);
516        let cands = [cand("server", true), cand("file", true)];
517        let c = choose(&cands, &need(Durability::Process), &speed, &table).unwrap();
518        assert_eq!(c.first().backend, "file");
519        assert_eq!(c.first().stats.p50_ns, 300);
520        assert_eq!(c.first().rerun, "re-run");
521        let log = c.log_lines().join("\n");
522        assert!(
523            log.contains("min_durability=process") && log.contains("re-run: re-run"),
524            "{log}"
525        );
526        assert!(log.contains("verified: up to process"), "{log}");
527    }
528
529    #[test]
530    fn a_minimum_durability_excludes_a_faster_backend_and_says_so() {
531        let speed = SpeedTable::from_rows(vec![
532            row("file", "laptop", 300),
533            row("server", "laptop", 2000),
534        ]);
535        let cands = [cand("file", true), cand("server", true)];
536        let c = choose(&cands, &need(Durability::Machine), &speed, &table).unwrap();
537        assert_eq!(c.ranked.len(), 1);
538        assert_eq!(c.first().backend, "server");
539        assert!(matches!(
540            c.excluded[0].why,
541            Why::Durability {
542                declared: Durability::Process,
543                wanted: Durability::Machine
544            }
545        ));
546        assert!(
547            c.log_lines()
548                .join("\n")
549                .contains("declares durability process but machine is required")
550        );
551    }
552
553    #[test]
554    fn an_undeclared_backend_is_unknown_not_volatile() {
555        let speed = SpeedTable::from_rows(vec![row("mystery", "laptop", 1)]);
556        let one = [cand("mystery", true)];
557        let c = choose(&one, &need(Durability::Volatile), &speed, &table).unwrap();
558        assert_eq!(
559            c.first().backend,
560            "mystery",
561            "volatile needs no declaration"
562        );
563        let e = choose(&one, &need(Durability::Process), &speed, &table).unwrap_err();
564        assert!(matches!(e.excluded[0].why, Why::DurabilityUnknown { .. }));
565    }
566
567    #[test]
568    fn a_contract_failure_is_excluded_however_fast() {
569        let speed =
570            SpeedTable::from_rows(vec![row("memory", "laptop", 1), row("file", "laptop", 300)]);
571        let cands = [cand("memory", false), cand("file", true)];
572        let c = choose(&cands, &need(Durability::Volatile), &speed, &table).unwrap();
573        assert_eq!(c.first().backend, "file");
574        assert!(matches!(&c.excluded[0].why, Why::Contract(ex) if ex[0].reason == Reason::Wrong));
575    }
576
577    #[test]
578    fn measurements_from_another_machine_are_not_used() {
579        let speed = SpeedTable::from_rows(vec![row("memory", "server", 1)]);
580        let one = [cand("memory", true)];
581        let e = choose(&one, &need(Durability::Volatile), &speed, &table).unwrap_err();
582        assert!(e.excluded.is_empty());
583        assert_eq!(
584            e.unmeasured.len(),
585            1,
586            "eligible, but nothing measured on this machine"
587        );
588    }
589
590    #[test]
591    fn nothing_eligible_is_an_error_with_the_reasons_not_a_fallback() {
592        let speed = SpeedTable::from_rows(vec![row("memory", "laptop", 1)]);
593        let one = [cand("memory", false)];
594        let e = choose(&one, &need(Durability::Volatile), &speed, &table).unwrap_err();
595        assert_eq!(e.excluded.len(), 1);
596        assert!(e.to_string().contains("no backend satisfies"));
597    }
598}
persistant_core/choose.rs

persistant_core/
choose.rs
