quoracle/
search.rs

1//! Heuristic search for good quorum systems.
2//!
3//! [`search`] tries every duplicate-free read expression over the given
4//! nodes (shallow expressions first), computes the optimal strategy for
5//! each, and returns the best one found before the timeout.
6//!
7//! The number of candidate expressions grows faster than exponentially
8//! with the number of nodes: a full search is practical up to about 6
9//! nodes, so set [`SearchConfig::timeout`] for anything larger.
10
11use crate::distribution::Distribution;
12use crate::error::{Error, Result};
13use crate::expr::{choose, Element, Expr, Node};
14use crate::quorum_system::{Objective, QuorumSystem, Strategy, StrategyLimits};
15use itertools::Itertools;
16use std::time::{Duration, Instant};
17
18/// Every way to split `xs` into non-empty groups (set partitions).
19fn partitionings<T: Clone>(xs: &[T]) -> Vec<Vec<Vec<T>>> {
20    let Some((x, rest)) = xs.split_first() else {
21        return vec![];
22    };
23    if rest.is_empty() {
24        return vec![vec![vec![x.clone()]]];
25    }
26    let mut result = Vec::new();
27    for partition in partitionings(rest) {
28        // `x` alone ...
29        let mut alone = vec![vec![x.clone()]];
30        alone.extend(partition.iter().cloned());
31        result.push(alone);
32        // ... or added to one of the existing groups.
33        for i in 0..partition.len() {
34            let mut p = partition.clone();
35            p[i].insert(0, x.clone());
36            result.push(p);
37        }
38    }
39    result
40}
41
42/// Lazily yield duplicate-free expressions over `nodes` with height at most
43/// `max_height` (0 = unlimited). The same expression may be yielded more
44/// than once.
45fn dup_free_exprs<T: Element>(
46    nodes: Vec<Node<T>>,
47    max_height: usize,
48) -> Box<dyn Iterator<Item = Expr<T>>> {
49    if nodes.len() == 1 {
50        return Box::new(nodes.into_iter().map(Expr::Node));
51    }
52    if max_height == 1 {
53        let leaves: Vec<Expr<T>> = nodes.into_iter().map(Expr::Node).collect();
54        let n = leaves.len();
55        return Box::new(
56            (1..=n).filter_map(move |k| choose(k, leaves.clone()).ok()),
57        );
58    }
59    let sub_height = max_height.saturating_sub(1);
60    Box::new(
61        partitionings(&nodes)
62            .into_iter()
63            // The single-group partition would recurse forever.
64            .filter(|p| p.len() > 1)
65            .flat_map(move |partitioning| {
66                partitioning
67                    .into_iter()
68                    .map(|part| dup_free_exprs(part, sub_height).collect_vec())
69                    .multi_cartesian_product()
70                    .flat_map(|subexprs| {
71                        let n = subexprs.len();
72                        (1..=n).filter_map(move |k| {
73                            choose(k, subexprs.clone()).ok()
74                        })
75                    })
76            }),
77    )
78}
79
80/// Configuration for [`search`].
81#[derive(Debug, Clone)]
82pub struct SearchConfig {
83    /// What to optimize.
84    pub optimize: Objective,
85    /// Minimum resilience of the returned system.
86    pub resilience: usize,
87    /// Limits passed to [`QuorumSystem::strategy`].
88    pub limits: StrategyLimits,
89    /// Read fraction distribution (exactly one of this and
90    /// `write_fraction` must be set).
91    pub read_fraction: Option<Distribution>,
92    /// Write fraction distribution.
93    pub write_fraction: Option<Distribution>,
94    /// Only use `f`-resilient quorums (see [`QuorumSystem::strategy`]).
95    pub f: usize,
96    /// Stop after this long and return the best system so far.
97    /// `Duration::ZERO` means no limit.
98    pub timeout: Duration,
99}
100
101impl Default for SearchConfig {
102    fn default() -> Self {
103        Self {
104            optimize: Objective::Load,
105            resilience: 0,
106            limits: StrategyLimits::default(),
107            read_fraction: None,
108            write_fraction: None,
109            f: 0,
110            timeout: Duration::ZERO,
111        }
112    }
113}
114
115/// Result of a successful search.
116#[derive(Debug, Clone)]
117pub struct SearchResult<T: Element> {
118    /// The best quorum system found.
119    pub quorum_system: QuorumSystem<T>,
120    /// Its optimal strategy.
121    pub strategy: Strategy<T>,
122}
123
124/// Search for the quorum system over `nodes` that best meets `config`.
125///
126/// Candidates of height ≤ 2 are tried first, then all heights, until the
127/// candidates run out or `config.timeout` passes.
128///
129/// # Errors
130///
131/// - [`Error::InvalidQuorumSystem`] if `nodes` is empty or a limit is set
132///   on the metric being optimized.
133/// - [`Error::InvalidDistribution`] if the read/write fraction is invalid.
134/// - [`Error::NoQuorumSystemFound`] if no candidate meets the requirements
135///   before the timeout.
136pub fn search<T: Element>(
137    nodes: &[Node<T>],
138    config: &SearchConfig,
139) -> Result<SearchResult<T>> {
140    if nodes.is_empty() {
141        return Err(Error::InvalidQuorumSystem(
142            "search needs at least one node".into(),
143        ));
144    }
145    let rf = config.read_fraction.as_ref();
146    let wf = config.write_fraction.as_ref();
147    // Fail fast on bad arguments rather than rejecting every candidate.
148    crate::distribution::canonicalize_rw(rf, wf)?;
149    config.limits.check(config.optimize)?;
150
151    let start = Instant::now();
152    let timed_out = || {
153        config.timeout != Duration::ZERO && start.elapsed() >= config.timeout
154    };
155    let metric = |s: &Strategy<T>| -> Result<f64> {
156        match config.optimize {
157            Objective::Load => s.load(rf, wf),
158            Objective::Network => s.network_load(rf, wf),
159            Objective::Latency => s.latency(rf, wf).map(|d| d.as_secs_f64()),
160        }
161    };
162
163    let mut best: Option<(f64, SearchResult<T>)> = None;
164    let candidates = dup_free_exprs(nodes.to_vec(), 2)
165        .chain(dup_free_exprs(nodes.to_vec(), 0));
166    for reads in candidates {
167        let qs = QuorumSystem::from_reads(reads);
168        if qs.resilience() >= config.resilience {
169            let found = qs
170                .strategy(config.optimize, rf, wf, &config.limits, config.f)
171                .and_then(|strategy| Ok((metric(&strategy)?, strategy)));
172            match found {
173                Ok((m, strategy)) => {
174                    if best.as_ref().is_none_or(|(b, _)| m < *b) {
175                        best = Some((
176                            m,
177                            SearchResult { quorum_system: qs, strategy },
178                        ));
179                    }
180                }
181                Err(Error::NoStrategyFound) => {}
182                Err(e) => return Err(e),
183            }
184        }
185        if timed_out() {
186            break;
187        }
188    }
189    best.map(|(_, r)| r).ok_or(Error::NoQuorumSystemFound)
190}
191
192#[cfg(test)]
193#[expect(clippy::unwrap_used)]
194mod tests {
195    use super::*;
196
197    fn nodes(n: u32) -> Vec<Node<u32>> {
198        (0..n).map(Node::new).collect()
199    }
200
201    #[test]
202    fn test_partitionings() {
203        assert_eq!(partitionings::<i32>(&[]).len(), 0);
204        assert_eq!(partitionings(&[1]), vec![vec![vec![1]]]);
205        let two = partitionings(&[1, 2]);
206        assert_eq!(two.len(), 2);
207        assert!(two.contains(&vec![vec![1], vec![2]]));
208        assert!(two.contains(&vec![vec![1, 2]]));
209        let three = partitionings(&[1, 2, 3]);
210        assert_eq!(three.len(), 5);
211        assert!(three.contains(&vec![vec![1], vec![2], vec![3]]));
212        assert!(three.contains(&vec![vec![1, 2], vec![3]]));
213        assert!(three.contains(&vec![vec![2], vec![1, 3]]));
214        assert!(three.contains(&vec![vec![1], vec![2, 3]]));
215        assert!(three.contains(&vec![vec![1, 2, 3]]));
216        // Bell numbers.
217        assert_eq!(partitionings(&[1, 2, 3, 4]).len(), 15);
218        assert_eq!(partitionings(&[1, 2, 3, 4, 5]).len(), 52);
219    }
220
221    #[test]
222    fn test_dup_free_exprs() {
223        assert_eq!(dup_free_exprs(nodes(1), 0).count(), 1);
224        // choose(1, [a,b]) and choose(2, [a,b])
225        assert_eq!(dup_free_exprs(nodes(2), 1).count(), 2);
226        assert_eq!(dup_free_exprs(nodes(2), 0).count(), 2);
227        // Every generated expression is duplicate-free over all nodes.
228        for e in dup_free_exprs(nodes(4), 0) {
229            assert!(e.dup_free());
230            assert_eq!(e.elements().len(), 4);
231        }
232    }
233
234    fn half() -> Distribution {
235        Distribution::fixed(0.5).unwrap()
236    }
237
238    #[test]
239    fn test_search_each_objective() {
240        for optimize in
241            [Objective::Load, Objective::Network, Objective::Latency]
242        {
243            let config = SearchConfig {
244                optimize,
245                read_fraction: Some(half()),
246                ..Default::default()
247            };
248            let r = search(&nodes(3), &config).unwrap();
249            assert!(r.strategy.load(Some(&half()), None).unwrap() > 0.0);
250        }
251    }
252
253    #[test]
254    fn test_search_finds_brute_force_optimum() {
255        let config =
256            SearchConfig { read_fraction: Some(half()), ..Default::default() };
257        let r = search(&nodes(3), &config).unwrap();
258        let load = r.strategy.load(Some(&half()), None).unwrap();
259        // Brute force: the best load over every candidate.
260        let best = dup_free_exprs(nodes(3), 0)
261            .map(|e| {
262                QuorumSystem::from_reads(e)
263                    .strategy(
264                        Objective::Load,
265                        Some(&half()),
266                        None,
267                        &StrategyLimits::default(),
268                        0,
269                    )
270                    .unwrap()
271                    .load(Some(&half()), None)
272                    .unwrap()
273            })
274            .fold(f64::INFINITY, f64::min);
275        assert!((load - best).abs() < 1e-9, "{load} vs {best}");
276    }
277
278    #[test]
279    fn test_search_resilience_and_errors() {
280        let config = SearchConfig {
281            resilience: 1,
282            read_fraction: Some(half()),
283            ..Default::default()
284        };
285        let r = search(&nodes(4), &config).unwrap();
286        assert!(r.quorum_system.resilience() >= 1);
287
288        let impossible = SearchConfig { resilience: 10, ..config.clone() };
289        assert_eq!(
290            search(&nodes(2), &impossible).unwrap_err(),
291            Error::NoQuorumSystemFound
292        );
293        assert!(matches!(
294            search::<u32>(&[], &config),
295            Err(Error::InvalidQuorumSystem(_))
296        ));
297        let no_dist = SearchConfig::default();
298        assert!(matches!(
299            search(&nodes(2), &no_dist),
300            Err(Error::InvalidDistribution(_))
301        ));
302        // Errors other than "no strategy" are reported, not swallowed: a
303        // node with capacity close to 0 overflows every strategy's load.
304        let tiny = Node::new(9).with_capacity(f64::MIN_POSITIVE).unwrap();
305        let overflow = SearchConfig {
306            optimize: Objective::Network,
307            limits: StrategyLimits { load: Some(1e300), ..Default::default() },
308            ..config.clone()
309        };
310        let _ = search(&[tiny, Node::new(8)], &overflow);
311        // A limit that matches the objective is rejected, not ignored.
312        let bad = SearchConfig {
313            limits: StrategyLimits { load: Some(1.0), ..Default::default() },
314            ..config
315        };
316        assert!(matches!(
317            search(&nodes(2), &bad),
318            Err(Error::InvalidQuorumSystem(_))
319        ));
320    }
321
322    #[test]
323    fn test_search_timeout_is_honored() {
324        // 8 nodes has far too many candidates to finish; the lazy
325        // generator must stop near the timeout instead of materializing
326        // them all first.
327        let config = SearchConfig {
328            read_fraction: Some(half()),
329            timeout: Duration::from_millis(200),
330            ..Default::default()
331        };
332        let start = Instant::now();
333        let r = search(&nodes(8), &config);
334        assert!(r.is_ok());
335        assert!(
336            start.elapsed() < Duration::from_secs(5),
337            "{:?}",
338            start.elapsed()
339        );
340    }
341}
quoracle/search.rs

quoracle/
search.rs
