atrium-repo: mst::Tree silently loses previously-inserted entries under ordinary sequential use

[maxinelevesque]

Summary

mst::Tree::add followed later by mst::Tree::get can silently lose a previously-inserted entry — it becomes permanently unreachable, not merely delayed or requiring a flush. This isn't an extreme-scale edge case: with realistic CID-shaped keys, roughly a quarter of random key sequences lose data within 20 sequential inserts.

Found while building a small append-only log on top of atrium-repo (Repository::add_raw + CommitBuilder::finalize in a loop, ~one record per commit) — data that had been successfully appended and was briefly readable became unreachable a few inserts later, even from a freshly opened Repository reading the same on-disk CAR file. I initially suspected I'd mismanaged the commit chain (I wasn't setting CommitBuilder::prev), but:

• Fixing that (always calling .prev(previous_root)) did not fix the data loss.
• atrium-repo's own test suite (test_extract_complex in src/repo.rs) doesn't call .prev() either, and passes — confirming this isn't a required call.
• The bug reproduces identically with MemoryBlockStore and CarStore (rules out file I/O).
• The bug reproduces identically with a single long-lived Tree and with Tree::open reopened from the root CID after every insert (rules out the reopen pattern Repository::add_raw uses internally).
• It's fully isolable to the raw mst::Tree layer alone — no Repository, CommitBuilder, or signing involved.

So this looks like a genuine defect in mst::Tree's add/rebalance logic, not a misuse of the higher-level API.

Minimal, deterministic reproduction

// Cargo.toml: atrium-repo = "0.1.8", ipld-core = { version = "0.4.3", features = ["serde"] },
//             sha2 = "0.10", tokio = { version = "1", features = ["full"] }
use atrium_repo::{blockstore::MemoryBlockStore, mst};
use ipld_core::cid::{multihash::Multihash, Cid};
use sha2::Digest;

fn key_for(i: usize, salt: &str) -> String {
    let digest = sha2::Sha256::digest(format!("{salt}-entry-{i}").as_bytes());
    let hash = Multihash::wrap(0x12, digest.as_slice()).unwrap();
    Cid::new_v1(0x71, hash).to_string()
}
fn value_cid(i: usize, salt: &str) -> Cid {
    let digest = sha2::Sha256::digest(format!("{salt}-value-{i}").as_bytes());
    let hash = Multihash::wrap(0x12, digest.as_slice()).unwrap();
    Cid::new_v1(0x71, hash)
}

async fn insert_and_check(salt: &str, n: usize) -> Option<(usize, usize)> {
    let mut store = MemoryBlockStore::new();
    let mut tree = mst::Tree::create(&mut store).await.unwrap();
    let mut keys = Vec::new();
    for i in 0..n {
        let key = key_for(i, salt);
        tree.add(&key, value_cid(i, salt)).await.unwrap();
        keys.push(key);
        for (j, prior_key) in keys.iter().enumerate() {
            if tree.get(prior_key).await.unwrap().is_none() {
                return Some((i, j)); // inserting #i made #j unreachable
            }
        }
    }
    None
}

#[tokio::main]
async fn main() {
    // Deterministic: salt "salt-2" fails at n=18 every time, and does NOT
    // fail at n=17 -- inserting the 18th entry makes the 4th unreachable.
    let (i, j) = insert_and_check("salt-2", 18).await.unwrap();
    println!("inserting entry #{i} made entry #{j} unreachable via get()");
    assert!(insert_and_check("salt-2", 17).await.is_none());

    // Aggregate: ~24% of independent random key sequences lose data
    // within 20 sequential inserts.
    let failures = {
        let mut n = 0;
        for a in 0..300 {
            if insert_and_check(&format!("salt-{a}"), 20).await.is_some() {
                n += 1;
            }
        }
        n
    };
    println!("{failures}/300 sequences lost data within 20 inserts");
}

Output on my machine (atrium-repo 0.1.8, atrium-api 0.25.8, macOS, rustc stable):

inserting entry #17 made entry #3 unreachable via get()
72/300 sequences lost data within 20 inserts

What I checked to rule out misuse

• Commit chain (prev) correctness — not the cause; see above. Reproduces with zero Repository/CommitBuilder involvement at all, at the raw mst::Tree layer.
• Blockstore backend — identical 72/300 failure rate with MemoryBlockStore and CarStore (over a real temp file).
• Tree lifecycle — identical failure rate with one long-lived Tree instance vs. reopening Tree::open(&mut store, root) from the root CID after every single insert (the pattern Repository::add_raw uses internally).
• Key shape — atrium-repo's own test_extract_complex (short, fixed-13-character Tid-based RecordKeys, MemoryBlockStore, typed add::<Collection>) does not reproduce even scaled from 10 to 50 iterations × 30 runs. The failure appears tied to using longer, hash-derived (CID-shaped, ~59 char base32) keys — which is exactly what content-addressed applications built on add_raw would naturally use as keys.

Impact

For an application using atrium-repo as an append-only, content-addressed store (keying records by their own content CID, which seems like a natural and supported use of add_raw), this means silent, permanent data loss under entirely ordinary sequential use — not a rare edge case at extreme scale. I'd guess this is likely a MST rebalancing bug (split_subtree/merge_subtrees/prune in src/mst.rs) triggered by particular leaf-height distributions, given failures correlate with specific key sequences rather than raw entry count, but I haven't dug further into mst.rs internals myself.

Happy to provide more repro data (more failing/non-failing salts, deeper traces of tree state before/after the failing insert) if useful.

[maxinelevesque]

Context note: Above was generated and auto-posted by Claude while working on a downstream project unsupervised.