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            host: None,
422        }
423    }
424
425    fn row(backend: &str, machine: &str, p50: u64) -> SpeedRow {
426        SpeedRow {
427            workload: "speed.x.get".to_string(),
428            backend: backend.to_string(),
429            version: "1".to_string(),
430            config: Config::new(),
431            env: env(machine),
432            outcome: Outcome::Measured(Stats::from_samples(vec![p50; 10]).unwrap()),
433        }
434    }
435
436    fn cand(backend: &str, ok: bool) -> Candidate {
437        Candidate {
438            backend: backend.to_string(),
439            version: "1".to_string(),
440            config: Config::new(),
441            eligibility: if ok {
442                Eligibility::Eligible
443            } else {
444                Eligibility::Excluded(vec![LeafFailure {
445                    leaf: "x.get".to_string(),
446                    reason: Reason::Wrong,
447                    note: "lost a write".to_string(),
448                }])
449            },
450        }
451    }
452
453    fn need(min: Durability) -> Need {
454        Need {
455            leaves: vec!["x.get".to_string()],
456            min_durability: min,
457            rank_by: "speed.x.get".to_string(),
458            environment: env("laptop").comparable_key(),
459        }
460    }
461
462    fn table(b: &str) -> Option<Declared> {
463        let class = match b {
464            "file" => Durability::Process,
465            "server" => Durability::Machine,
466            "memory" => Durability::Volatile,
467            _ => return None,
468        };
469        Some(Declared {
470            class,
471            basis: "test table",
472            verified: (class >= Durability::Process).then_some(Durability::Process),
473        })
474    }
475
476    #[test]
477    fn a_machine_verified_backend_names_the_machine_test_in_the_log() {
478        fn machine(b: &str) -> Option<Declared> {
479            let mut d = table(b)?;
480            d.verified = Some(Durability::Machine);
481            Some(d)
482        }
483        let speed = SpeedTable::from_rows(vec![row("server", "laptop", 2000)]);
484        let c = choose(
485            &[cand("server", true)],
486            &need(Durability::Machine),
487            &speed,
488            &machine,
489        )
490        .unwrap();
491        let log = c.log_lines().join("\n");
492        assert!(
493            log.contains("verified: up to machine by kv.durability.machine"),
494            "{log}"
495        );
496        // The control: a Process verification still names the process test.
497        let c = choose(
498            &[cand("file", true)],
499            &need(Durability::Process),
500            &SpeedTable::from_rows(vec![row("file", "laptop", 300)]),
501            &table,
502        )
503        .unwrap();
504        assert!(
505            c.log_lines()
506                .join("\n")
507                .contains("by kv.durability.process")
508        );
509    }
510
511    #[test]
512    fn the_fastest_eligible_backend_is_first_and_carries_its_evidence() {
513        let speed = SpeedTable::from_rows(vec![
514            row("file", "laptop", 300),
515            row("server", "laptop", 2000),
516        ]);
517        let cands = [cand("server", true), cand("file", true)];
518        let c = choose(&cands, &need(Durability::Process), &speed, &table).unwrap();
519        assert_eq!(c.first().backend, "file");
520        assert_eq!(c.first().stats.p50_ns, 300);
521        assert_eq!(c.first().rerun, "re-run");
522        let log = c.log_lines().join("\n");
523        assert!(
524            log.contains("min_durability=process") && log.contains("re-run: re-run"),
525            "{log}"
526        );
527        assert!(log.contains("verified: up to process"), "{log}");
528    }
529
530    #[test]
531    fn a_minimum_durability_excludes_a_faster_backend_and_says_so() {
532        let speed = SpeedTable::from_rows(vec![
533            row("file", "laptop", 300),
534            row("server", "laptop", 2000),
535        ]);
536        let cands = [cand("file", true), cand("server", true)];
537        let c = choose(&cands, &need(Durability::Machine), &speed, &table).unwrap();
538        assert_eq!(c.ranked.len(), 1);
539        assert_eq!(c.first().backend, "server");
540        assert!(matches!(
541            c.excluded[0].why,
542            Why::Durability {
543                declared: Durability::Process,
544                wanted: Durability::Machine
545            }
546        ));
547        assert!(
548            c.log_lines()
549                .join("\n")
550                .contains("declares durability process but machine is required")
551        );
552    }
553
554    #[test]
555    fn an_undeclared_backend_is_unknown_not_volatile() {
556        let speed = SpeedTable::from_rows(vec![row("mystery", "laptop", 1)]);
557        let one = [cand("mystery", true)];
558        let c = choose(&one, &need(Durability::Volatile), &speed, &table).unwrap();
559        assert_eq!(
560            c.first().backend,
561            "mystery",
562            "volatile needs no declaration"
563        );
564        let e = choose(&one, &need(Durability::Process), &speed, &table).unwrap_err();
565        assert!(matches!(e.excluded[0].why, Why::DurabilityUnknown { .. }));
566    }
567
568    #[test]
569    fn a_contract_failure_is_excluded_however_fast() {
570        let speed =
571            SpeedTable::from_rows(vec![row("memory", "laptop", 1), row("file", "laptop", 300)]);
572        let cands = [cand("memory", false), cand("file", true)];
573        let c = choose(&cands, &need(Durability::Volatile), &speed, &table).unwrap();
574        assert_eq!(c.first().backend, "file");
575        assert!(matches!(&c.excluded[0].why, Why::Contract(ex) if ex[0].reason == Reason::Wrong));
576    }
577
578    #[test]
579    fn measurements_from_another_machine_are_not_used() {
580        let speed = SpeedTable::from_rows(vec![row("memory", "server", 1)]);
581        let one = [cand("memory", true)];
582        let e = choose(&one, &need(Durability::Volatile), &speed, &table).unwrap_err();
583        assert!(e.excluded.is_empty());
584        assert_eq!(
585            e.unmeasured.len(),
586            1,
587            "eligible, but nothing measured on this machine"
588        );
589    }
590
591    #[test]
592    fn nothing_eligible_is_an_error_with_the_reasons_not_a_fallback() {
593        let speed = SpeedTable::from_rows(vec![row("memory", "laptop", 1)]);
594        let one = [cand("memory", false)];
595        let e = choose(&one, &need(Durability::Volatile), &speed, &table).unwrap_err();
596        assert_eq!(e.excluded.len(), 1);
597        assert!(e.to_string().contains("no backend satisfies"));
598    }
599}
persistant_core/choose.rs

persistant_core/
choose.rs
