quorum_set/quorum/
read_or_both.rs

1use std::collections::BTreeSet;
2use std::collections::btree_set;
3
4use crate::quorum::BothQuorums;
5use crate::quorum::QuorumSet;
6
7/// A quorum rule that is either a read rule alone or a [`BothQuorums`].
8///
9/// A consensus election picks the variant by how it orders leaders:
10///
11/// - With totally ordered ballots, as in Paxos, use [`Read`](Self::Read). Two leaders always differ
12///   in ballot, and a voter rejects entries from a ballot smaller than one it granted. So read
13///   quorums need to intersect only write quorums.
14/// - When two leaders of one term are not ordered, as in Raft, use [`Both`](Self::Both). Any two
15///   winning vote sets must then intersect, but two read quorums may be disjoint.
16///
17/// [`ids()`](QuorumSet::ids) returns the read IDs for `Read`, and the union of the read and write
18/// IDs for `Both`, each ID once.
19#[derive(Clone, Debug)]
20pub enum ReadOrBoth<R, W> {
21    /// Accepts an ID set when the read rule accepts it.
22    Read(R),
23
24    /// Accepts an ID set when both the read rule and the write rule accept it.
25    Both(BothQuorums<R, W>),
26}
27
28impl<R, W> QuorumSet for ReadOrBoth<R, W>
29where
30    R: QuorumSet,
31    W: QuorumSet<Id = R::Id>,
32    R::Id: Ord,
33{
34    type Id = R::Id;
35    type Iter = btree_set::IntoIter<R::Id>;
36
37    fn is_quorum<'a, I>(&self, ids: I) -> bool
38    where
39        Self::Id: 'a,
40        I: Iterator<Item = &'a Self::Id> + Clone,
41    {
42        match self {
43            Self::Read(read) => read.is_quorum(ids),
44            Self::Both(both) => both.is_quorum(ids),
45        }
46    }
47
48    fn ids(&self) -> Self::Iter {
49        match self {
50            Self::Read(read) => {
51                let ids = read.ids().collect::<BTreeSet<_>>();
52                ids.into_iter()
53            }
54            Self::Both(both) => both.ids(),
55        }
56    }
57}
58
59#[cfg(test)]
60mod tests {
61    use std::collections::BTreeSet;
62
63    use maplit::btreeset;
64
65    use super::ReadOrBoth;
66    use crate::Node;
67    use crate::QuorumTree;
68    use crate::quorum::BothQuorums;
69    use crate::quorum::QuorumSet;
70    use crate::quorum::verify_intersection;
71
72    /// Nodes form a 2x2 grid, `1 2` over `3 4`. A read quorum holds a row and a write quorum holds
73    /// a column, so the read quorums `{1,2}` and `{3,4}` are disjoint.
74    #[test]
75    fn test_grid_rows_and_columns() -> anyhow::Result<()> {
76        let read = QuorumTree::new(1, [
77            Node::Subtree(QuorumTree::new(2, [Node::Id(1), Node::Id(2)])?),
78            Node::Subtree(QuorumTree::new(2, [Node::Id(3), Node::Id(4)])?),
79        ])?;
80        let write = QuorumTree::new(1, [
81            Node::Subtree(QuorumTree::new(2, [Node::Id(1), Node::Id(3)])?),
82            Node::Subtree(QuorumTree::new(2, [Node::Id(2), Node::Id(4)])?),
83        ])?;
84        let read_only = ReadOrBoth::<_, QuorumTree<u64>>::Read(read.clone());
85        let both = ReadOrBoth::Both(BothQuorums::new(read, write));
86
87        let mut read_only_accepted = vec![];
88        let mut both_accepted = vec![];
89        for mask in 0..16_u64 {
90            let ids = (1..=4).filter(|id| mask & (1 << (id - 1)) != 0);
91            let ids = ids.collect::<BTreeSet<u64>>();
92            if read_only.is_quorum(ids.iter()) {
93                read_only_accepted.push(ids.clone());
94            }
95            if both.is_quorum(ids.iter()) {
96                both_accepted.push(ids);
97            }
98        }
99
100        let want = vec![
101            btreeset! {1,2},
102            btreeset! {1,2,3},
103            btreeset! {1,2,4},
104            btreeset! {3,4},
105            btreeset! {1,3,4},
106            btreeset! {2,3,4},
107            btreeset! {1,2,3,4},
108        ];
109        assert_eq!(want, read_only_accepted);
110
111        let want = vec![
112            btreeset! {1,2,3},
113            btreeset! {1,2,4},
114            btreeset! {1,3,4},
115            btreeset! {2,3,4},
116            btreeset! {1,2,3,4},
117        ];
118        assert_eq!(want, both_accepted);
119
120        assert!(!verify_intersection(&read_only, &read_only));
121        assert!(verify_intersection(&both, &both));
122
123        Ok(())
124    }
125
126    /// `Read` yields only the read IDs, even when the write rule holds other IDs.
127    #[test]
128    fn test_ids_of_each_variant() -> anyhow::Result<()> {
129        let read = btreeset! {1u64, 2, 3};
130        let write = QuorumTree::new(2, [Node::Id(3), Node::Id(4), Node::Id(5)])?;
131        let read_only = ReadOrBoth::<_, QuorumTree<u64>>::Read(read.clone());
132        let both = ReadOrBoth::Both(BothQuorums::new(read, write));
133
134        let read_only_ids = read_only.ids().collect::<Vec<_>>();
135        assert_eq!(vec![1, 2, 3], read_only_ids);
136
137        let both_ids = both.ids().collect::<Vec<_>>();
138        assert_eq!(vec![1, 2, 3, 4, 5], both_ids);
139
140        Ok(())
141    }
142}
quorum_set/quorum/read_or_both.rs

quorum_set/quorum/
read_or_both.rs
