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 three 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///
29/// The crate provides implementations for flat majority sets, joint quorum sets, hierarchical
30/// [`QuorumTree`] rules, and [`BothQuorums`], which requires both a read and a write quorum.
31/// [`ReadOrBoth`] holds either a read rule alone or a [`BothQuorums`].
32pub trait QuorumSet {
33    /// Node ID type in this quorum set.
34    type Id;
35
36    /// Iterator over every voter ID tracked by this quorum set.
37    ///
38    /// Implementations that combine multiple sub-rules return each ID once.
39    type Iter: Iterator<Item = Self::Id>;
40
41    /// Return `true` if the candidate IDs satisfy this quorum rule.
42    ///
43    /// Repeated IDs count once, and IDs that [`ids()`](Self::ids) does not yield are ignored.
44    fn is_quorum<'a, I>(&self, ids: I) -> bool
45    where
46        Self::Id: 'a,
47        I: Iterator<Item = &'a Self::Id> + Clone;
48
49    /// Return all voter IDs in this quorum set.
50    fn ids(&self) -> Self::Iter;
51}
52
53impl<T> QuorumSet for Arc<T>
54where T: QuorumSet
55{
56    type Id = T::Id;
57
58    type Iter = T::Iter;
59
60    fn is_quorum<'a, I>(&self, ids: I) -> bool
61    where
62        Self::Id: 'a,
63        I: Iterator<Item = &'a Self::Id> + Clone,
64    {
65        self.as_ref().is_quorum(ids)
66    }
67
68    fn ids(&self) -> Self::Iter {
69        self.as_ref().ids()
70    }
71}
quorum_set/quorum/quorum_set.rs

quorum_set/quorum/
quorum_set.rs
