p2panda_core/
logs.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3use std::collections::BTreeMap;
4use std::hash::Hash as StdHash;
5
6use serde::{Deserialize, Serialize};
7
8use crate::identity::Author;
9
10/// Uniquely identify a single-author log.
11///
12/// The `LogId` exists purely to group a set of operations and is intended to be implemented for
13/// any type which meets the design requirements of a particular application.
14///
15/// A blanket implementation is provided for any type meeting the required trait bounds.
16///
17/// Here we briefly outline several implementation scenarios:
18///
19/// An application relying on a one-log-per-author design might choose to implement `LogId` for a
20/// thin wrapper around an Ed25519 public key; this effectively ties the log to the public key of
21/// the author. Secure Scuttlebutt (SSB) is an example of a protocol which relies on this model.
22///
23/// In an application where one author may produce operations grouped into multiple logs, `LogId`
24/// might be represented a unique number for each log instance.
25///
26/// Some applications might require semantic grouping of operations. For example, a chat
27/// application may choose to create a separate log for each author-channel pairing. In such a
28/// scenario, `LogId` might be implemented for a `struct` containing a `String` representation of
29/// the channel name.
30///
31/// Finally, please note that implementers of `LogId` must take steps to ensure their log design
32/// is fit for purpose and that all operations have been thoroughly validated before being
33/// persisted. No such validation checks are provided by `p2panda-store`.
34pub trait LogId: Clone + Eq + Ord + StdHash + Serialize + for<'de> Deserialize<'de> {}
35
36impl<T> LogId for T where T: Clone + Eq + Ord + StdHash + Serialize + for<'de> Deserialize<'de> {}
37
38/// Sequence number of an entry in an append-only log.
39pub type SeqNum = u64;
40
41/// Map of log heights grouped by author.
42pub type LogHeights<A, L> = BTreeMap<A, BTreeMap<L, SeqNum>>;
43
44/// Map of log ranges grouped by author.
45pub type LogRanges<A, L> = BTreeMap<A, BTreeMap<L, (Option<SeqNum>, Option<SeqNum>)>>;
46
47/// Compare two sets of logs (local and remote) and calculate the "diff" representing ranges of
48/// entries that should be sent to the remote.
49///
50/// Local and remote states are represented by a map of authors to logs, where the logs are
51/// represented by their unique identifier and current log height. If the remote is not aware of a
52/// log, then the range containing all entries in the local log will be contained in the diff, if
53/// the remote knows of some entries in a log, then the range representing only the entries they
54/// need will be included.
55///
56/// Log ranges are represented by `(Option<u64>, Option<u64>)` tuples where the first value is an
57/// exclusive "from" sequence number and the later is an inclusive "until" sequence number. If
58/// either values are `None` that signifies that all entries from the start, or to the end, are
59/// required.
60///
61/// The returned ranges can be used in a sync protocol to then fetch entries from a store and send
62/// them to the remote. If both local and remote replicas do this then they will arrive at the
63/// same state. If pruned logs are being replicated and a range has been returned from this
64/// method, then it is expected only the remaining "frontier" will be replicated for each log.
65pub fn compare<A, L>(local: &LogHeights<A, L>, remote: &LogHeights<A, L>) -> LogRanges<A, L>
66where
67    A: Author,
68    L: LogId,
69{
70    let mut remote_needs: LogRanges<A, L> = BTreeMap::default();
71
72    // Iterate over all authors.
73    for (verifying_key, local_logs) in local {
74        let Some(remote_logs) = remote.get(verifying_key) else {
75            // If the remote did not know of this author, then they need all entries in all of
76            // their logs that the local knows of.
77            let needs = local_logs
78                .iter()
79                .map(|(log_id, log_height)| (log_id.clone(), (None, Some(*log_height))))
80                .collect();
81            remote_needs.insert(verifying_key.to_owned(), needs);
82            continue;
83        };
84
85        // If the local and remote logs are equal then nothing needs to be sent.
86        if local_logs == remote_logs {
87            continue;
88        }
89
90        // Iterate over all local logs for this author.
91        for (log_id, local_log_height) in local_logs {
92            let Some(remote_log_height) = remote_logs.get(log_id) else {
93                // If the remote did not know of this log, then they need all entries from the
94                // local.
95                remote_needs
96                    .entry(verifying_key.to_owned())
97                    .or_default()
98                    .insert(log_id.clone(), (None, Some(*local_log_height)));
99                continue;
100            };
101
102            // If the remote log height is less than the local, then include the exact range they
103            // need in the diff.
104            if remote_log_height < local_log_height {
105                remote_needs
106                    .entry(verifying_key.to_owned())
107                    .or_default()
108                    .insert(
109                        log_id.clone(),
110                        (Some(*remote_log_height), Some(*local_log_height)),
111                    );
112            }
113        }
114    }
115
116    remote_needs
117}
118
119#[cfg(test)]
120mod tests {
121    use std::collections::BTreeMap;
122
123    use crate::logs::compare;
124
125    type Author = u8;
126
127    impl crate::identity::Author for Author {}
128
129    const ALICE: Author = 0;
130    const BOB: Author = 1;
131
132    #[test]
133    fn both_empty() {
134        let local: BTreeMap<Author, BTreeMap<u64, u64>> = BTreeMap::new();
135        let remote: BTreeMap<Author, BTreeMap<u64, u64>> = BTreeMap::new();
136        let result = compare(&local, &remote);
137        assert!(result.is_empty());
138    }
139
140    #[test]
141    fn remote_empty() {
142        let mut local: BTreeMap<Author, BTreeMap<u64, u64>> = BTreeMap::new();
143        let logs = BTreeMap::from([(1, 5), (2, 10)]);
144        local.insert(ALICE, logs);
145
146        let remote: BTreeMap<Author, BTreeMap<u64, u64>> = BTreeMap::new();
147
148        let result = compare(&local, &remote);
149        let needs = result.get(&ALICE).unwrap();
150
151        assert_eq!(needs.get(&1), Some(&(None, Some(5))));
152        assert_eq!(needs.get(&2), Some(&(None, Some(10))));
153    }
154
155    #[test]
156    fn remote_missing_single_log() {
157        let mut local = BTreeMap::new();
158        local.insert(ALICE, BTreeMap::from([(1, 5), (2, 10)]));
159
160        let mut remote = BTreeMap::new();
161        remote.insert(ALICE, BTreeMap::from([(1, 5)]));
162
163        let result = compare(&local, &remote);
164        let needs = result.get(&ALICE).unwrap();
165
166        assert_eq!(needs.get(&2), Some(&(None, Some(10))));
167        assert!(!needs.contains_key(&1));
168    }
169
170    #[test]
171    fn remote_behind() {
172        let mut local = BTreeMap::new();
173        local.insert(ALICE, BTreeMap::from([(1, 20)]));
174
175        let mut remote = BTreeMap::new();
176        remote.insert(ALICE, BTreeMap::from([(1, 10)]));
177
178        let result = compare(&local, &remote);
179        let needs = result.get(&ALICE).unwrap();
180
181        assert_eq!(needs.get(&1), Some(&(Some(10), Some(20))));
182    }
183
184    #[test]
185    fn remote_ahead() {
186        let mut local = BTreeMap::new();
187        local.insert(ALICE, BTreeMap::from([(1, 20)]));
188
189        let mut remote = BTreeMap::new();
190        remote.insert(ALICE, BTreeMap::from([(1, 30)]));
191
192        let result = compare(&local, &remote);
193        assert!(result.is_empty());
194    }
195
196    #[test]
197    fn equal() {
198        let mut local = BTreeMap::new();
199        local.insert(ALICE, BTreeMap::from([(1, 20)]));
200
201        let mut remote = BTreeMap::new();
202        remote.insert(ALICE, BTreeMap::from([(1, 20)]));
203
204        let result = compare(&local, &remote);
205        assert!(result.is_empty());
206    }
207
208    #[test]
209    fn remote_missing_multiple_logs() {
210        let mut local = BTreeMap::new();
211        local.insert(ALICE, BTreeMap::from([(1, 5), (2, 10), (3, 15)]));
212
213        let mut remote = BTreeMap::new();
214        remote.insert(ALICE, BTreeMap::from([(1, 5)]));
215
216        let result = compare(&local, &remote);
217        let needs = result.get(&ALICE).unwrap();
218
219        assert_eq!(needs.get(&2), Some(&(None, Some(10))));
220        assert_eq!(needs.get(&3), Some(&(None, Some(15))));
221        assert!(!needs.contains_key(&1));
222    }
223
224    #[test]
225    fn remote_missing_author() {
226        let mut local = BTreeMap::new();
227        local.insert(ALICE, BTreeMap::from([(1, 5)]));
228        local.insert(BOB, BTreeMap::from([(1, 5)]));
229
230        let mut remote = BTreeMap::new();
231        remote.insert(ALICE, BTreeMap::from([(1, 5)]));
232
233        let result = compare(&local, &remote);
234        let needs = result.get(&BOB).unwrap();
235
236        assert_eq!(needs.get(&1), Some(&(None, Some(5))));
237    }
238}
p2panda_core/logs.rs

p2panda_core/
logs.rs
