openraft 0.10.0-alpha.18

Advanced Raft consensus
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

use std::cmp::Ordering;

use crate::vote::RaftLeaderId;

/// Provide comparison functions for [`RaftLeaderId`] implementations.
pub struct LeaderIdCompare;

impl LeaderIdCompare {
    /// Implements [`PartialOrd`] for LeaderId to enforce the standard Raft behavior of at most one
    /// leader per term.
    ///
    /// In standard Raft, each term can have at most one leader. This is enforced by making leader
    /// IDs with the same term incomparable (returning None), unless they refer to the same
    /// node.
    pub fn std<LID>(a: &LID, b: &LID) -> Option<Ordering>
    where LID: RaftLeaderId {
        match a.term().cmp(&b.term()) {
            Ordering::Equal => {
                if a.node_id() == b.node_id() {
                    Some(Ordering::Equal)
                } else {
                    None
                }
            }
            cmp => Some(cmp),
        }
    }

    /// Implements [`PartialOrd`] for LeaderId to allow multiple leaders per term.
    pub fn adv<LID>(a: &LID, b: &LID) -> Option<Ordering>
    where LID: RaftLeaderId {
        let res = (a.term(), a.node_id()).cmp(&(b.term(), b.node_id()));
        Some(res)
    }
}

#[cfg(test)]
mod tests {
    use std::cmp::Ordering;

    use crate::vote::RaftLeaderId;

    #[derive(Debug, PartialEq, Eq, Clone, PartialOrd, derive_more::Display)]
    #[display("T{}-N{}", _0, _1)]
    #[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
    struct LeaderId(u64, u64);

    impl PartialEq<u64> for LeaderId {
        fn eq(&self, _other: &u64) -> bool {
            false
        }
    }

    impl PartialOrd<u64> for LeaderId {
        fn partial_cmp(&self, other: &u64) -> Option<Ordering> {
            self.0.partial_cmp(other)
        }
    }

    impl RaftLeaderId for LeaderId {
        type Term = u64;
        type NodeId = u64;
        type Committed = u64;

        fn new(term: u64, node_id: u64) -> Self {
            Self(term, node_id)
        }

        fn term(&self) -> u64 {
            self.0
        }

        fn node_id(&self) -> &u64 {
            &self.1
        }

        fn to_committed(&self) -> Self::Committed {
            self.0
        }
    }

    #[test]
    fn test_std_cmp() {
        use Ordering::*;

        use super::LeaderIdCompare as Cmp;

        let lid = |term, node_id| LeaderId(term, node_id);

        // Compare term first
        assert_eq!(Cmp::std(&lid(2, 2), &lid(1, 2)), Some(Greater));
        assert_eq!(Cmp::std(&lid(1, 2), &lid(2, 2)), Some(Less));

        // Equal
        assert_eq!(Cmp::std(&lid(2, 2), &lid(2, 2)), Some(Equal));

        // Incomparable
        assert_eq!(Cmp::std(&lid(2, 2), &lid(2, 1)), None);
        assert_eq!(Cmp::std(&lid(2, 1), &lid(2, 2)), None);
        assert_eq!(Cmp::std(&lid(2, 2), &lid(2, 3)), None);
    }

    #[test]
    fn test_adv_cmp() {
        use Ordering::*;

        use super::LeaderIdCompare as Cmp;

        let lid = |term, node_id| LeaderId(term, node_id);

        // Compare term first
        assert_eq!(Cmp::adv(&lid(2, 2), &lid(1, 2)), Some(Greater));
        assert_eq!(Cmp::adv(&lid(1, 2), &lid(2, 2)), Some(Less));

        // Equal term
        assert_eq!(Cmp::adv(&lid(2, 2), &lid(2, 1)), Some(Greater));
        assert_eq!(Cmp::adv(&lid(2, 1), &lid(2, 2)), Some(Less));

        // Equal term, node_id
        assert_eq!(Cmp::adv(&lid(2, 2), &lid(2, 2)), Some(Equal));
    }
}