quorum_set/quorum/
quorum_set.rs

1use std::sync::Arc;
2
3#[cfg(doc)]
4use crate::BothQuorums;
5#[cfg(doc)]
6use crate::QuorumTree;
7#[cfg(doc)]
8use crate::ReadOrBoth;
9#[cfg(doc)]
10use crate::VecProgress;
11#[cfg(doc)]
12use crate::verify_intersection;
13
14/// Common interface for every quorum rule supported by this crate.
15///
16/// A quorum is a collection of nodes that a read or write operation in a distributed system has to
17/// contact. See: <http://web.mit.edu/6.033/2005/wwwdocs/quorum_note.html>
18///
19/// Every implementation must follow four rules:
20///
21/// - Upward-closed: adding IDs to an accepted quorum keeps it accepted. [`VecProgress`] and
22///   [`verify_intersection`] rely on this rule.
23/// - Closed over [`ids()`](Self::ids): an ID that `ids()` does not yield never changes the result
24///   of [`is_quorum()`](Self::is_quorum). [`verify_intersection`] enumerates only the IDs that
25///   `ids()` yields, so it relies on this rule.
26/// - Duplicate-safe: an ID that appears more than once in the `is_quorum()` input counts once, so
27///   callers may pass an iterator with repeats.
28/// - No empty quorum: an input that holds no ID from `ids()`, such as an empty input, is never a
29///   quorum. An upward-closed rule that accepted the empty input would accept every input, so a
30///   read or write operation would succeed without contacting any node.
31///
32/// The crate provides implementations for flat majority sets, joint quorum sets, hierarchical
33/// [`QuorumTree`] rules, and [`BothQuorums`], which requires both a read and a write quorum.
34/// [`ReadOrBoth`] holds either a read rule alone or a [`BothQuorums`].
35pub trait QuorumSet {
36    /// Node ID type in this quorum set.
37    type Id;
38
39    /// Iterator over every voter ID tracked by this quorum set.
40    ///
41    /// Implementations that combine multiple sub-rules return each ID once.
42    type Iter: Iterator<Item = Self::Id>;
43
44    /// Return `true` if the candidate IDs satisfy this quorum rule.
45    ///
46    /// Repeated IDs count once, and IDs that [`ids()`](Self::ids) does not yield are ignored.
47    /// An empty input is never a quorum.
48    fn is_quorum<'a, I>(&self, ids: I) -> bool
49    where
50        Self::Id: 'a,
51        I: Iterator<Item = &'a Self::Id> + Clone;
52
53    /// Return all voter IDs in this quorum set.
54    fn ids(&self) -> Self::Iter;
55}
56
57impl<T> QuorumSet for Arc<T>
58where T: QuorumSet
59{
60    type Id = T::Id;
61
62    type Iter = T::Iter;
63
64    fn is_quorum<'a, I>(&self, ids: I) -> bool
65    where
66        Self::Id: 'a,
67        I: Iterator<Item = &'a Self::Id> + Clone,
68    {
69        self.as_ref().is_quorum(ids)
70    }
71
72    fn ids(&self) -> Self::Iter {
73        self.as_ref().ids()
74    }
75}
quorum_set/quorum/quorum_set.rs

quorum_set/quorum/
quorum_set.rs
