quorum_set/quorum/
quorum_set.rs

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

quorum_set/quorum/
quorum_set.rs
