paxakos 0.1.0

Rust implementation of Paxos consensus algorithm
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

use std::ops::RangeInclusive;

use async_trait::async_trait;
use num_traits::{Bounded, Zero};
use thiserror::Error;

use crate::error::BoxError;
use crate::RoundNum;

#[derive(Debug)]
pub struct AppendArgs<R: RoundNum> {
    pub round: RangeInclusive<R>,
    pub importance: Importance,
    pub retry_policy: Box<dyn RetryPolicy>,
}

impl<R: RoundNum> Default for AppendArgs<R> {
    fn default() -> Self {
        Self {
            round: Zero::zero()..=Bounded::max_value(),
            importance: Importance::GainLeadership,
            retry_policy: Box::new(DoNotRetry),
        }
    }
}

/// Describes the importance of an append operation.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Importance {
    /// If necessary, leadership should be gained.
    ///
    /// Note: Just because leadership _should_ be gained does not imply that it
    /// can or will be gained. It merely implies that the node will not
    /// immediately give up when it doesn't have leadership.
    GainLeadership,

    /// Leadership should only be maintained.
    ///
    /// Using this mode implies that the given append is of low importance. We
    /// wish only to go through with it if it does not require an election
    /// cycle.
    MaintainLeadership(Peeryness),
}

/// Whether to inquire with other nodes about the round in question.
///
/// If a node has to abandon an append due to [lack of status][Maintain] it may
/// still wish to inquire with other nodes whether the round in question has
/// converged. This can be achieved by indicating an inquisitiveness of "peery".
///
/// [Maintain]: Importance::MaintainLeadership
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub enum Peeryness {
    /// Inquire with up to a quorum of other nodes.
    ///
    /// By inquiring about a round with (up to) a quorum of other nodes one
    /// learns whether the round has already converged or not. This can be a
    /// convenient mechanism for keeping up with the distributed log without
    /// upsetting the status quo.
    Peery,

    /// Immediately abandon an append if status is insufficient.
    Unpeery,
}

#[derive(Debug, Error)]
#[non_exhaustive]
pub enum AppendError {
    /// Append was aborted.
    #[error("append was aborted")]
    Aborted(BoxError),

    /// The chosen round had already converged.
    #[error("round had already converged")]
    Converged,

    /// Node does not currently know the shared state.
    #[error("node is disoriented")]
    Disoriented,

    /// Node was removed from the cluster.
    #[error("node was removed from the cluster")]
    Exiled,

    /// Node either lost its mandate or failed in acquiring one.
    #[error("node lost its mandate or failed in acquiring one")]
    Lost,

    /// Failed in achieving achieve a quorum.
    ///
    /// This commonly indicates communication errors.
    #[error("node could not achieve a quorum")]
    NoQuorum,

    /// An I/O error was encountered.
    #[error("I/O error")]
    IoError(crate::error::IoError),

    /// Catch-all, this may be refined over time.
    #[error("uncategorized error occured")]
    Other(crate::error::BoxError),

    /// Node is in passive mode.
    #[error("node is passive")]
    Passive,

    /// Node was forced to append a different entry for the chosen round.
    #[error("node was forced to append a different entry")]
    Railroaded,

    /// Node is shut down.
    #[error("node is shut down")]
    ShutDown,

    /// Node is stalled.
    ///
    /// A node is stalled when it failed to write to its obligation log. Once
    /// that happens it can no longer make promises or accept entries. This is
    /// because there is no expectation that they will be remembered after a
    /// potential crash.
    // TODO allow recovery from this state
    #[error("node is stalled")]
    Stalled,
}

#[async_trait]
pub trait RetryPolicy: std::fmt::Debug + Send {
    async fn eval(&mut self, err: AppendError) -> Result<(), BoxError>;
}

#[derive(Clone, Copy, Debug)]
pub struct DoNotRetry;

#[async_trait]
impl RetryPolicy for DoNotRetry {
    async fn eval(&mut self, _err: AppendError) -> Result<(), BoxError> {
        Err(Box::new(AbortedError))
    }
}

#[derive(Clone, Debug, Error)]
#[error("append was aborted")]
pub struct AbortedError;