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

persistant_core/
choose.rs
