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

quorum_set/quorum/
quorum_intersection_impl.rs
