quorum_set/quorum/
quorum_intersection_impl.rs

1use std::collections::BTreeSet;
2
3use crate::quorum::QuorumIntersection;
4
5/// Two joint configs are treated as having quorum intersection when some config of one intersects
6/// some config of the other: every quorum of a joint is also a quorum of each of its configs, so
7/// every quorum of one joint then intersects every quorum of the other. This is sufficient but not
8/// necessary for that property, so this check answers `None` for some pairs of joints whose
9/// quorums do in fact all intersect.
10impl<ID> QuorumIntersection<Vec<BTreeSet<ID>>> for Vec<BTreeSet<ID>>
11where ID: Ord + Clone
12{
13    /// Return the exact answer of the flat [`BTreeSet`] check when each joint holds one config.
14    /// For other joints, return `Some(true)` when some config of `self` intersects some config of
15    /// `other`.
16    ///
17    /// When either joint is empty, return `Some(true)` exactly when the other joint holds an empty
18    /// config. An empty joint accepts the empty set as a quorum, and the empty set misses every
19    /// quorum of the other joint. A joint that holds an empty config has no quorum to miss.
20    ///
21    /// Return `None` for every other pair: two configs that do not intersect prove nothing about
22    /// two joints that contain them.
23    ///
24    /// Read more about extended membership change in OpenRaft:
25    /// <https://docs.rs/openraft/latest/openraft/docs/data/extended_membership/index.html>
26    fn intersects_with(&self, other: &Vec<BTreeSet<ID>>) -> Option<bool> {
27        let either_is_empty = self.is_empty() || other.is_empty();
28        if either_is_empty {
29            let empty_config = BTreeSet::new();
30            let holds_empty_config = self.contains(&empty_config) || other.contains(&empty_config);
31            return Some(holds_empty_config);
32        }
33
34        let both_uniform = self.len() == 1 && other.len() == 1;
35        if both_uniform {
36            return self[0].intersects_with(&other[0]);
37        }
38
39        for a in self {
40            for b in other {
41                let intersects = a.intersects_with(b);
42                if intersects == Some(true) {
43                    return Some(true);
44                }
45            }
46        }
47        None
48    }
49}
50
51/// Exact quorum intersection for two flat majority configs.
52///
53/// A smallest majority of `self` first takes the IDs that `other` lacks, and then takes shared IDs
54/// only as needed. A smallest majority of `other` does the same. Two disjoint majorities exist
55/// exactly when the shared IDs are enough for both, so the check is exact and runs in O(n).
56impl<ID> QuorumIntersection<BTreeSet<ID>> for BTreeSet<ID>
57where ID: Ord + Clone
58{
59    /// Return `Some(true)` when every majority of `self` intersects every majority of `other`,
60    /// and `Some(false)` otherwise. This check never returns `None`.
61    ///
62    /// An empty [`BTreeSet`] has no quorum, so it has quorum intersection with every config.
63    fn intersects_with(&self, other: &BTreeSet<ID>) -> Option<bool> {
64        let majority_self = self.len() / 2 + 1;
65        let majority_other = other.len() / 2 + 1;
66
67        let only_self = self.difference(other).count();
68        let only_other = other.difference(self).count();
69        let shared = self.intersection(other).count();
70
71        let need_self = majority_self.saturating_sub(only_self);
72        let need_other = majority_other.saturating_sub(only_other);
73
74        Some(need_self + need_other > shared)
75    }
76}
77
78/// A joint config and a flat config are treated as having quorum intersection when some config of
79/// the joint intersects the flat config: every quorum of the joint is also a quorum of that config.
80/// This is sufficient but not necessary for that property, so this check answers `None` for some
81/// pairs whose quorums do in fact all intersect.
82impl<ID> QuorumIntersection<BTreeSet<ID>> for Vec<BTreeSet<ID>>
83where ID: Ord + Clone
84{
85    /// Return the exact answer of the flat [`BTreeSet`] check when `self` holds one config. For
86    /// other joints, return `Some(true)` when some config of `self` intersects `other`.
87    ///
88    /// Return `Some(other.is_empty())` when `self` is empty: an empty joint accepts the empty set
89    /// as a quorum, and the empty set misses every quorum of a non-empty `other`. An empty `other`
90    /// has no quorum to miss.
91    ///
92    /// Return `None` for every other pair.
93    fn intersects_with(&self, other: &BTreeSet<ID>) -> Option<bool> {
94        if self.is_empty() {
95            return Some(other.is_empty());
96        }
97
98        let uniform = self.len() == 1;
99        if uniform {
100            return self[0].intersects_with(other);
101        }
102
103        for config in self {
104            let intersects = config.intersects_with(other);
105            if intersects == Some(true) {
106                return Some(true);
107            }
108        }
109        None
110    }
111}
112
113/// Quorum intersection is symmetric, so this check returns the answer of the joint config's check.
114impl<ID> QuorumIntersection<Vec<BTreeSet<ID>>> for BTreeSet<ID>
115where ID: Ord + Clone
116{
117    fn intersects_with(&self, other: &Vec<BTreeSet<ID>>) -> Option<bool> {
118        other.intersects_with(self)
119    }
120}
quorum_set/quorum/quorum_intersection_impl.rs

quorum_set/quorum/
quorum_intersection_impl.rs
