Shallow snapshot root retreats far below the requested frontier when two peers take turns (since 1.16.2)
I maintainer di solito rispondono entro 1 giorno
Valutazione
- Difficoltà
- 5/5
- Tempo stimato
- Più di una settimana
- Idoneità per principianti
- 15/100
- Tipo di issue
- Bug
- Chiarezza
- Specificata chiaramente
- Stato di attività
- Attiva
- Stack tecnologico
- javascript, rust
- Ambito
- distributed-systems
Direzione di ricerca
Deep CRDT-internals bug with a fix already proposed in #1295, so read that first rather than starting fresh. Start with crates/loro-internal/docs/critical-version-spec.md §1.4 (redundant implicit-predecessor trap), then calc_shallow_doc_start in crates/loro-internal/src/encoding/shallow_snapshot.rs and the L11 fallback scan's use of deps_to_ord_id_spans in crates/loro-internal/src/dag.rs. Done means the reproduction in the report (and its Rust form) returns the asked frontier as shallow_since_frontiers() for every turn, plus a regression test; the same scan's use as an import replay-base fallback in oplog.rs is unmeasured and worth checking.
Scritto dal modello di indicizzazione a partire dal testo della issue.
Descrizione
What happens
export({ mode: 'shallow-snapshot', frontiers }) (and state_only) should keep frontiers as the shallow root whenever it is a critical version of the retained history. docs/encoding.md §3.3 says the root is "the latest single-head critical version" of ancestry(F) ∪ ancestry(E).
In a plain linear history where two peers take turns (each imports the other's changes, then writes), every version is critical: nothing is concurrent with anything. Yet the root retreats to the end of the first peer's first turn, so the snapshot keeps almost the whole history. In general, a single-head target v is only kept as the root if no peer other than v's author wrote both before and after v.
Reproduction (loro-crdt 1.16.3, Node)
const { LoroDoc } = require('loro-crdt');
const a = new LoroDoc(); a.setPeerId(1n);
const b = new LoroDoc(); b.setPeerId(2n);
const marks = [];
for (let turn = 0; turn < 6; turn++) {
const [w, r] = turn % 2 === 0 ? [a, b] : [b, a];
w.import(r.export({ mode: 'update', from: w.oplogVersion() }));
for (let i = 0; i < 3; i++) { w.getText('t').insert(0, String(i)); w.commit(); }
r.import(w.export({ mode: 'update', from: r.oplogVersion() }));
marks.push(a.frontiers());
}
for (const [turn, target] of marks.entries()) {
const fresh = new LoroDoc();
fresh.import(a.export({ mode: 'shallow-snapshot', frontiers: target }));
console.log(`turn ${turn}: asked ${JSON.stringify(target)}, root ${JSON.stringify(fresh.shallowSinceFrontiers())}`);
}
Output:
turn 0: asked [{"peer":"1","counter":2}], root [{"peer":"1","counter":2}]
turn 1: asked [{"peer":"2","counter":2}], root [{"peer":"1","counter":2}]
turn 2: asked [{"peer":"1","counter":5}], root [{"peer":"1","counter":2}]
turn 3: asked [{"peer":"2","counter":5}], root [{"peer":"1","counter":2}]
turn 4: asked [{"peer":"1","counter":8}], root [{"peer":"1","counter":2}]
turn 5: asked [{"peer":"2","counter":8}], root [{"peer":"2","counter":8}]
Expected: the root equals the asked frontier for every turn. (Only the latest version is kept, because the scan stops at once when there is nothing above it.)
The same in Rust on current main (98465472), shortened from the regression test in the PR:
use loro::{ExportMode, LoroDoc};
let (a, b) = (LoroDoc::new(), LoroDoc::new());
a.set_peer_id(1).unwrap();
b.set_peer_id(2).unwrap();
let mut marks = vec![];
for turn in 0..8 {
let (w, r) = if turn % 2 == 0 { (&a, &b) } else { (&b, &a) };
w.import(&r.export(ExportMode::updates(&w.oplog_vv())).unwrap()).unwrap();
for i in 0..3 { w.get_text("t").insert(0, &i.to_string()).unwrap(); w.commit(); }
r.import(&w.export(ExportMode::updates(&r.oplog_vv())).unwrap()).unwrap();
marks.push(a.oplog_frontiers());
}
let fresh = LoroDoc::new();
fresh.import(&a.export(ExportMode::shallow_snapshot(&marks[4])).unwrap()).unwrap();
assert_eq!(fresh.shallow_since_frontiers(), marks[4]); // fails: root is 2@1, asked 8@1
Cause
Since #1104 (released in 1.16.2, fixing #1095), calc_shallow_doc_start takes the root from latest_single_head_critical_version:
https://github.com/loro-dev/loro/blob/loro-crdt%401.16.3/crates/loro-internal/src/encoding/shallow_snapshot.rs#L804-L817
The scan expands each change through deps_to_ord_id_spans, which pushes the explicit deps and also the same peer's previous op, unless an explicit dep's span directly contains it:
https://github.com/loro-dev/loro/blob/loro-crdt%401.16.3/crates/loro-internal/src/dag.rs#L556-L572
https://github.com/loro-dev/loro/blob/loro-crdt%401.16.3/crates/loro-internal/src/dag.rs#L588-L645 (the call at L634)
When peer 1 writes, peer 2 writes, and peer 1 writes again having seen peer 2's change, peer 1's previous op is in the causal past of its explicit dep (peer 2's op), but not inside that dep's span. It is pushed as a second heap entry, so the heap never narrows to one span until the scan gets below the first turn. This is trap one of crates/loro-internal/docs/critical-version-spec.md §1.4 (the redundant implicit-predecessor path, fixed for the main walk in #1058), here in the L11 fallback scan.
Before 1.16.2, a single-head target was returned as is (pairwise-meet reduction in calc_shallow_doc_start at [email protected]), so this shape kept its root; #1104 fixed real non-critical roots (#1095) and brought this in. The same scan is the import replay-base fallback in oplog.rs (after the multi-head search), so that path can also retreat further than needed; I have not measured the impact there.
A fix with regression tests is in #1295.
Disclosure: this issue was found, and a first fix prototyped, by Claude Fable 5.2; the report and PR were prepared by Claude Opus 5.5 (Anthropic models) and are submitted from my account at my request.
- Lingua principale
- Rust
- Stelle
- 6.3k
- Fork
- 205
- Merge medio
- 3g 18h
- PR unite (30g)
- 45
Preparare l'ambiente
Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.
- Nessun Dockerfile né file Docker Compose
- Nessun modello di pull request
- Leggi la guida per i contributori
Come iniziare
- Leggi tutta la issue e poi la guida ai contributi del progetto.
- Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
- Fai un fork del repository e lavora su un branch.
- Apri una pull request che faccia riferimento al numero della issue.
Altre issue di loro-dev/loro
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 75/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 3/5 1-2 giorni Idoneità per principianti 62/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 4/5 3-5 giorni Idoneità per principianti 42/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 4/5 3-5 giorni Idoneità per principianti 30/100
I maintainer di solito rispondono entro 1 giorno
Tutte le issue di loro-dev/loro
Issue simili
-
Selected chart highlights only its values, not its series names and category labelsForse già presa @Higgs32584 l’ha presa oggi. Apertabug priority: low ui
Difficoltà 2/5 1-3 ore Idoneità per principianti 82/100
storytold/gridcraft#4390 · 2 commenti ·
I maintainer di solito rispondono entro 1 giorno
-
bug
Difficoltà 2/5 1-3 ore Idoneità per principianti 65/100
I maintainer di solito rispondono entro 1 giorno
-
bug bugfix priority: medium
Difficoltà 2/5 1-3 ore Idoneità per principianti 66/100
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 78/100
quarto-dev/q2#1219 ·
I maintainer di solito rispondono entro 1 giorno
-
Difficoltà 2/5 1-3 ore Idoneità per principianti 68/100