p2panda_core/
logs.rs

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

p2panda_core/
logs.rs
