Shallow snapshot root retreats far below the requested frontier when two peers take turns (since 1.16.2)

Aperta
#1,294 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

@avergin ci sta già lavorando.

Dal 15/11/2026.

  • #1295 di @avergin — aperta

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

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

Apri in Codespaces

Avvia il container di sviluppo del progetto nel browser, con il tuo account GitHub.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di loro-dev/loro

Tutte le issue di loro-dev/loro

Issue simili

Altre issue su Rust

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.