recon_protocols/total_order_log.rs
1//! The total-order log port: what a layer above a totally ordered log may depend on, and the whole
2//! of what it may.
3//!
4//! Built on the model of [`crate::link`] and [`crate::detector`], and for the same reason. An
5//! implementation keeps its own `Cmd` and `Ind` — that vocabulary is the algorithm's, not the
6//! port's — and the port supplies the three translations a layer above actually needs: build an
7//! append, build a read, and classify an indication. Pinning the port to one pair of types would
8//! admit exactly one implementation, which is the failure `link.rs` records: four `session_*`
9//! broadcast modules existed because a layer written against one link's vocabulary could not
10//! compose over another's.
11//!
12//! One suite is written against this port and every implementation behind it is held to it, so that
13//! where two implementations differ is visible rather than asserted. Here the pair is crash-stop
14//! against fail-recovery, and what differs is exactly one thing: whether the ordered sequence
15//! survives a restart.
16//!
17//! # The read is a departure, and this is where it is recorded
18//!
19//! The book's abstraction is *total-order broadcast* — `⟨ tob, Broadcast | m ⟩` and
20//! `⟨ tob, Deliver | p, m ⟩`, with no read at all. Both algorithms behind this port nonetheless
21//! maintain `delivered`, the totally ordered sequence, and a log's clients read it. So
22//! [`TotalOrderLog::read`] exposes what the page keeps and does not offer: a departure of one
23//! method rather than of the algorithm.
24//!
25//! **A read is served from the reading process's own copy.** That is all either algorithm can
26//! honestly do — a read observing every completed append would have to go through consensus or hold
27//! a lease, which is not on the page and would change what is being transcribed. So the claim is a
28//! **total order**, not linearizability: a process whose round has not yet decided has not yet
29//! extended its sequence, and its read says so rather than waiting. What two reads anywhere in a run
30//! do guarantee is that one result is a prefix of the other, because both are prefixes of one agreed
31//! sequence.
32
33use recon_core::{NodeId, Position, Protocol};
34
35/// What a layer above a totally ordered log may depend on, and the whole of what it may.
36///
37/// `V` is the value a client appends. An implementation is free to wrap it — both of the ones here
38/// carry the originator alongside — which is why [`TotalOrderLog::append`] builds the request rather
39/// than the caller constructing one, and why [`TotalOrderLog::classify`] takes the value back out.
40///
41/// Satisfying the port is a decision, not an accident of shape. `link.rs` records an earlier draft
42/// making its port a blanket impl over every protocol with the right associated types, which meant a
43/// protocol became a link by coincidence; a log says so. One that has not is rejected when the
44/// project is built:
45///
46/// ```compile_fail
47/// # struct NotALog;
48/// # #[derive(Debug, Clone, PartialEq, Eq)]
49/// # struct Whatever;
50/// # impl recon_core::Protocol for NotALog {
51/// # type Cmd = Whatever;
52/// # type Ind = Whatever;
53/// # type Msg = Whatever;
54/// # type Scope = core::convert::Infallible;
55/// # type Note = recon_protocols::Note;
56/// # type Meta = core::convert::Infallible;
57/// # type Entry = core::convert::Infallible;
58/// # fn on_cmd(&mut self, _: Whatever, _: &mut recon_core::ProtoCx<'_, Self>) {}
59/// # fn on_msg(&mut self, _: recon_core::NodeId, _: Whatever,
60/// # _: &mut recon_core::ProtoCx<'_, Self>) {}
61/// # fn on_timer(&mut self, _: recon_core::TimerId,
62/// # _: &mut recon_core::ProtoCx<'_, Self>) {}
63/// # }
64/// fn requires_a_log<L: recon_protocols::total_order_log::TotalOrderLog<u32>>() {}
65/// requires_a_log::<NotALog>();
66/// ```
67pub trait TotalOrderLog<V>: Protocol<Note = crate::Note> {
68 /// The request that appends `value` to the log.
69 ///
70 /// A constructor rather than a fixed type, because the request is the implementation's own
71 /// vocabulary.
72 fn append(value: V) -> Self::Cmd;
73
74 /// The request that reads the ordered sequence from `from` onwards.
75 ///
76 /// The departure this module's header records. Served locally, so it may lag an append that has
77 /// completed elsewhere.
78 fn read(from: Position) -> Self::Cmd;
79
80 /// What this indication means to the layer above.
81 ///
82 /// Total, as [`crate::link::Link::classify`] and [`crate::detector::Detector::classify`] are: a
83 /// layer above maps its child's indications with one function, so an implementation that could
84 /// report something unclassifiable would leave that layer with a case it could only drop — and
85 /// silently absorbing something is this project's cardinal sin.
86 fn classify(ind: Self::Ind) -> LogInd<V>;
87}
88
89/// What an indication from any totally ordered log amounts to, in the port's own vocabulary.
90///
91/// A layer above matches on this rather than on the implementation's own indication type, which is
92/// how one suite serves every implementation.
93#[derive(Debug, Clone, PartialEq, Eq)]
94pub enum LogInd<V> {
95 /// An entry took its place in the agreed sequence, at `position`, having been appended by
96 /// `from`.
97 ///
98 /// `from` is the process that *appended* it, which the page carries as `⟨ tob, Deliver | s, m ⟩`
99 /// and which a checker needs in order to say whose operation completed.
100 Ordered { position: Position, from: NodeId, value: V },
101 /// The answer to a read: the entries at `from` and later, in order.
102 Contents { from: Position, entries: Vec<V> },
103 /// A scope that part of this log's guarantee held within has changed.
104 ///
105 /// Reachable only over a link that can observe one. A log composing a reliable broadcast
106 /// inherits that broadcast's inability to bridge an ending — it holds no redundancy outliving
107 /// the scope beyond what consensus gives it — so it propagates rather than absorbing.
108 Boundary(crate::link::Boundary),
109}