oxedyne/fe2o3/fe2o3_ore/src/sync/mod.rs
4.5 KiB, 37 runs
created by r1870400018:19637, which is this file's identity for as long as the history lasts, whatever it is later renamed to
download · who wrote it · its history
| 1 | //! Bringing two logs into agreement, as pure computation. |
| 2 | //! |
| 3 | //! Two replicas that have edited apart hold overlapping histories, and neither |
| 4 | //! knows what the other is missing. This module works that out and says what to |
| 5 | //! send. It is a state machine over typed messages: bytes in, bytes out, and |
| 6 | //! whatever carries them -- a socket, a file, a courier with a memory stick -- |
| 7 | //! is the caller's business. Nothing here opens anything. |
| 8 | //! |
| 9 | //! Both peers run the same code. There is no client and no server, and no |
| 10 | //! message either side may send that the other may not; a relay that carries the |
| 11 | //! bytes learns nothing and decides nothing, which is what makes a server |
| 12 | //! optional rather than authoritative. |
| 13 | //! |
| 14 | //! # Closures, never subsets |
| 15 | //! |
| 16 | //! Everything sent is causally closed against what the receiver already holds: |
| 17 | //! what arrives, plus what was already there, names no parent nobody has. That |
| 18 | //! is not a courtesy. An operation set with a hole in it renders differently |
| 19 | //! from the same set once the hole is filled -- an anchor whose target is absent |
| 20 | //! has to be placed somewhere -- so a peer that absorbed an arbitrary subset |
| 21 | //! would show a state that never existed and was never authored. The receiver |
| 22 | //! checks the property on arrival rather than trusting it: [`arrival_gap`] names |
| 23 | //! the operation and the parent nobody holds, and a batch that fails is refused |
| 24 | //! whole. |
| 25 | //! |
| 26 | //! # Two modes, one message set |
| 27 | //! |
| 28 | //! - The **frontier walk** is the default and is correct at any divergence. The |
| 29 | //! peers exchange their frontiers, and each sends every operation the other's |
| 30 | //! frontier does not cover -- and that it has not already watched the other |
| 31 | //! hand over, which is the half a frontier cannot report and which |
| 32 | //! [`Session::knowing`] is how a carrier remembers. It costs one round trip and |
| 33 | //! never fails. |
| 34 | //! - **Sketch reconciliation** is the optimisation. Each peer sends an |
| 35 | //! invertible Bloom lookup table over the names of the operations it holds; |
| 36 | //! subtracting one from the other yields the difference directly, in bytes |
| 37 | //! proportional to the difference rather than to the history. It is worth it |
| 38 | //! when two large logs differ by a little, which is the steady state of a |
| 39 | //! repository that syncs often. |
| 40 | //! |
| 41 | //! A sketch is sized from an estimate, and an estimate can be wrong. When the |
| 42 | //! peeling decoder stalls the difference is not half taken: the answer is a |
| 43 | //! table of twice the cells -- [`Step::Grew`] -- and, once growth has climbed as |
| 44 | //! far as it is worth climbing, the walk, from the frontier the sketch message |
| 45 | //! carried for exactly that purpose ([`Step::FellBack`]). Nothing is guessed and |
| 46 | //! no round trip is lost. |
| 47 | //! |
| 48 | //! Growing before walking is not a preference between two equally good answers. |
| 49 | //! A peer that has written anything of its own presents a frontier this end |
| 50 | //! cannot subtract, so the walk's owed set is the whole log however much of it |
| 51 | //! that peer already holds; a table twice the size costs a round trip and some |
| 52 | //! hundreds of bytes. |
| 53 | //! |
| 54 | //! # A carrier that keeps nothing |
| 55 | //! |
| 56 | //! A bounded reply cuts an exchange into a run of sessions, and three things |
| 57 | //! would otherwise be thrown away at each boundary: what the far end handed over |
| 58 | //! ([`Session::knowing`]), the table size that was grown to |
| 59 | //! ([`Session::sizing`]), and how far into the owed set the far end was carried |
| 60 | //! ([`Message::Resume`]). The last of those is the one that crosses the wire, |
| 61 | //! because it is the only one the end that keeps nothing cannot work out for |
| 62 | //! itself -- and without it a bounded walk against a peer whose head the carrier |
| 63 | //! does not hold sends the same prefix every session, for ever. |
| 64 | //! |
| 65 | //! # Layout |
| 66 | //! |
| 67 | //! - [`msg`] is the message set, with a daticle form and a version-tagged byte |
| 68 | //! form. |
| 69 | //! - [`walk`] computes what a peer at a given frontier is owed, and the closure |
| 70 | //! checks that hold at both ends. |
| 71 | //! - [`sketch`] is the invertible Bloom lookup table over operation names: how a |
| 72 | //! name is keyed, how the table is sized, and what a decode yields. |
| 73 | //! - [`session`] is the driver: feed it a message, take the messages it hands |
| 74 | //! back, and read the outcome. |
| 75 | //! |
| 76 | //! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\ |
| 77 | //! Anthropic Claude |
| 78 | |
| 79 | pub mod msg; |
| 80 | pub mod session; |
| 81 | pub mod sketch; |
| 82 | pub mod walk; |
| 83 | |
| 84 | #[cfg(test)] |
| 85 | mod tests; |
| 86 | |
| 87 | pub use msg::{ |
| 88 | Message, |
| 89 | Parts, |
| 90 | MAGIC, |
| 91 | VERSION, |
| 92 | VERSION_MIN, |
| 93 | }; |
| 94 | pub use session::{ |
| 95 | Growth, |
| 96 | Mode, |
| 97 | Session, |
| 98 | Step, |
| 99 | Turn, |
| 100 | FANOUT, |
| 101 | }; |
| 102 | pub use sketch::{ |
| 103 | Diff, |
| 104 | Fallback, |
| 105 | }; |
| 106 | pub use walk::{ |
| 107 | arrival_gap, |
| 108 | covered, |
| 109 | owed, |
| 110 | }; |