Batch Operations at the Grove Level

GroveOp Variants

At the GroveDB level, operations are represented as GroveOp:

#![allow(unused)]
fn main() {
pub enum GroveOp {
    // User-facing operations:
    InsertOnly { element: Element },
    InsertOrReplace { element: Element },
    Replace { element: Element },
    Patch { element: Element, change_in_bytes: i32 },
    RefreshReference { reference_path_type, max_reference_hop, flags, trust_refresh_reference },
    Delete,
    DeleteTree(TreeType, SubelementsDeletionBehavior),  // Per-op deletion policy
    Move { new_key: Vec<u8> },  // Rename a key, keeping everything under it (V4)

    // Non-Merk tree append operations (user-facing):
    CommitmentTreeInsert { cmx: [u8; 32], rho: [u8; 32], cv_net: [u8; 32], payload: Vec<u8> },
    MmrTreeAppend { value: Vec<u8> },
    BulkAppend { value: Vec<u8> },
    DenseTreeInsert { value: Vec<u8> },

    // Internal operations (created by preprocessing/propagation, rejected by from_ops):
    ReplaceTreeRootKey { hash, root_key, aggregate_data },
    InsertTreeWithRootHash { hash, root_key, flags, aggregate_data },
    ReplaceNonMerkTreeRoot { hash: [u8; 32], meta: NonMerkTreeMeta },
    InsertNonMerkTree { hash, root_key, flags, aggregate_data, meta: NonMerkTreeMeta },
}
}

NonMerkTreeMeta carries tree-type-specific state through batch processing:

#![allow(unused)]
fn main() {
pub enum NonMerkTreeMeta {
    CommitmentTree { total_count: u64, chunk_power: u8 },
    MmrTree { mmr_size: u64 },
    BulkAppendTree { total_count: u64, chunk_power: u8 },
    DenseTree { count: u16, height: u8 },
}
}

SubelementsDeletionBehavior controls how a DeleteTree handles non-empty subtrees:

#![allow(unused)]
fn main() {
pub enum SubelementsDeletionBehavior {
    DontCheckWithNoCleanup, // Skip emptiness check AND post-apply cleanup; caller guarantees tree is empty
    Error,                  // Return Error::DeletingNonEmptyTree if non-empty
    DeleteChildren,         // Skip emptiness check, but perform post-apply storage cleanup
    Skip,                   // Check, and silently skip deletion if non-empty
}
}

Each operation is wrapped in a QualifiedGroveDbOp that includes the path:

#![allow(unused)]
fn main() {
pub struct QualifiedGroveDbOp {
    pub path: KeyInfoPath,           // Where in the grove
    pub key: Option<KeyInfo>,        // Which key (None for append-only tree ops)
    pub op: GroveOp,                 // What to do
}
}

Note: The key field is Option<KeyInfo> — it is None for append-only tree operations (CommitmentTreeInsert, MmrTreeAppend, BulkAppend, DenseTreeInsert) where the tree key is the last segment of path instead.

Two-Phase Processing

Batch operations are processed in two phases:

graph TD
    input["Input: Vec<QualifiedGroveDbOp>"]

    subgraph phase1["PHASE 1: VALIDATION"]
        v1["1. Sort by path + key<br/>(stable sort)"]
        v2["2. Build batch structure<br/>(group ops by subtree)"]
        v3["3. Validate element types<br/>match targets"]
        v4["4. Resolve & validate<br/>references"]
        v1 --> v2 --> v3 --> v4
    end

    v4 -->|"validation OK"| phase2_start
    v4 -->|"validation failed"| abort["Err(Error)<br/>abort, no changes"]

    subgraph phase2["PHASE 2: APPLICATION"]
        phase2_start["Start application"]
        a1["1. Open all affected<br/>subtrees (TreeCache)"]
        a2["2. Apply MerkBatch ops<br/>(deferred propagation)"]
        a3["3. Propagate root hashes<br/>upward (leaf → root)"]
        a4["4. Commit transaction<br/>atomically"]
        phase2_start --> a1 --> a2 --> a3 --> a4
    end

    input --> v1

    style phase1 fill:#fef9e7,stroke:#f39c12,stroke-width:2px
    style phase2 fill:#d5f5e3,stroke:#27ae60,stroke-width:2px
    style abort fill:#fadbd8,stroke:#e74c3c,stroke-width:2px
    style a4 fill:#d4e6f1,stroke:#2980b9,stroke-width:2px

TreeCache and Deferred Propagation

During batch application, GroveDB uses a TreeCache to defer root hash propagation until all operations in a subtree are complete:

graph TD
    subgraph without["WITHOUT TreeCache (naive)"]
        w1["Op 1: Insert A in X"]
        w1p["Propagate X → parent → root"]
        w2["Op 2: Insert B in X"]
        w2p["Propagate X → parent → root"]
        w3["Op 3: Insert C in X"]
        w3p["Propagate X → parent → root"]
        w1 --> w1p --> w2 --> w2p --> w3 --> w3p
    end

    subgraph with_tc["WITH TreeCache (deferred)"]
        t1["Op 1: Insert A in X<br/>→ buffered"]
        t2["Op 2: Insert B in X<br/>→ buffered"]
        t3["Op 3: Insert C in X<br/>→ buffered"]
        tp["Propagate X → parent → root<br/>(walk up ONCE)"]
        t1 --> t2 --> t3 --> tp
    end

    style without fill:#fadbd8,stroke:#e74c3c,stroke-width:2px
    style with_tc fill:#d5f5e3,stroke:#27ae60,stroke-width:2px
    style w1p fill:#fadbd8,stroke:#e74c3c
    style w2p fill:#fadbd8,stroke:#e74c3c
    style w3p fill:#fadbd8,stroke:#e74c3c
    style tp fill:#d5f5e3,stroke:#27ae60,stroke-width:2px

3 propagations × O(depth) vs 1 propagation × O(depth) = 3x faster for this subtree.

This is a significant optimization when many operations target the same subtree.

Atomic Cross-Subtree Operations

A key property of GroveDB batches is atomicity across subtrees. A single batch can modify elements in multiple subtrees, and either all changes commit or none do:

    Batch:
    1. Delete ["balances", "alice"]       (remove balance)
    2. Insert ["balances", "bob"] = 100   (add balance)
    3. Update ["identities", "bob", "rev"] = 2  (update revision)

    Three subtrees affected: balances, identities, identities/bob

    If ANY operation fails → ALL operations are rolled back
    If ALL succeed → ALL are committed atomically

The batch processor handles this by:

1. Collecting all affected paths
2. Opening all needed subtrees
3. Applying all operations
4. Propagating all root hashes in dependency order
5. Committing the entire transaction

Batch Preprocessing for Non-Merk Trees

CommitmentTree, MmrTree, BulkAppendTree, and DenseAppendOnlyFixedSizeTree operations require access to storage contexts outside the Merk, which is not available inside the standard execute_ops_on_path method (it only has access to the Merk). These operations use a preprocessing pattern: before the main apply_body phase, the entry points scan for non-Merk tree ops and convert them to standard internal ops.

#![allow(unused)]
fn main() {
pub enum GroveOp {
    // ... standard ops ...

    // Non-Merk tree operations (user-facing):
    CommitmentTreeInsert { cmx: [u8; 32], rho: [u8; 32], cv_net: [u8; 32], payload: Vec<u8> },
    MmrTreeAppend { value: Vec<u8> },
    BulkAppend { value: Vec<u8> },
    DenseTreeInsert { value: Vec<u8> },

    // Internal ops (produced by preprocessing):
    ReplaceNonMerkTreeRoot { hash: [u8; 32], meta: NonMerkTreeMeta },
}
}

graph TD
    subgraph preprocess["PREPROCESSING PHASE"]
        scan["Scan ops for<br/>CommitmentTreeInsert<br/>MmrTreeAppend<br/>BulkAppend<br/>DenseTreeInsert"]
        load["Load current state<br/>from storage"]
        mutate["Apply append to<br/>in-memory structure"]
        save["Write updated state<br/>back to storage"]
        convert["Convert to<br/>ReplaceNonMerkTreeRoot<br/>with new root hash + meta"]

        scan --> load --> mutate --> save --> convert
    end

    subgraph apply["STANDARD APPLY_BODY"]
        body["execute_ops_on_path<br/>sees ReplaceNonMerkTreeRoot<br/>(non-Merk tree update)"]
        prop["Propagate root hash<br/>upward through grove"]

        body --> prop
    end

    convert --> body

    style preprocess fill:#fef9e7,stroke:#f39c12,stroke-width:2px
    style apply fill:#d5f5e3,stroke:#27ae60,stroke-width:2px

Why preprocessing? The execute_ops_on_path function operates on a single Merk subtree and has no access to self.db or broader storage contexts. Preprocessing in the entry points (apply_batch_with_element_flags_update, apply_partial_batch_with_element_flags_update) has full access to the database, so it can load/save data and then hand off a simple ReplaceNonMerkTreeRoot to the standard batch machinery.

Each preprocessing method follows the same pattern:

1. preprocess_commitment_tree_ops — Loads frontier and BulkAppendTree from data storage, appends to both, saves back, converts to ReplaceNonMerkTreeRoot with updated combined root and CommitmentTree { total_count, chunk_power } meta
2. preprocess_mmr_tree_ops — Loads MMR from data storage, appends values, saves back, converts to ReplaceNonMerkTreeRoot with updated MMR root and MmrTree { mmr_size } meta
3. preprocess_bulk_append_ops — Loads BulkAppendTree from data storage, appends values (may trigger chunk compaction), saves back, converts to ReplaceNonMerkTreeRoot with updated state root and BulkAppendTree { total_count, chunk_power } meta
4. preprocess_dense_tree_ops — Loads DenseFixedSizedMerkleTree from data storage, inserts values sequentially, recomputes root hash, saves back, converts to ReplaceNonMerkTreeRoot with updated root hash and DenseTree { count, height } meta

The ReplaceNonMerkTreeRoot op carries the new root hash and a NonMerkTreeMeta enum so the element can be fully reconstructed after processing.

Automatic backward-reference maintenance (V4)

Full batches maintain backward references by default, including when a plain replacement or delete displaces a registered element. Preparation observes old values and retains their Merk nodes for execution and storage accounting. The existing consent and batch-conflict rules still apply.

Every displacing op declares what it displaces through its variant: the checked op (Delete, DeleteTree, InsertOrReplace, Replace, Patch) maintains a participant the write lands on, its DontCheckForBackwardsReferences twin (DeleteDontCheckForBackwardsReferences, DeleteTreeDontCheckForBackwardsReferences, InsertOrReplaceDontCheckForBackwardsReferences, ReplaceDontCheckForBackwardsReferences, PatchDontCheckForBackwardsReferences) declares the stored value takes no part in backward references and is refused if that turns out to be false wherever the batch reads the value. The check reads nothing extra, since the batch reads the value for the write anyway. A flat drop (DeleteTreeDontCheckForBackwardsReferences with DropFlat) reads nothing and trusts the declaration. Convert a checked op with QualifiedGroveDbOp::dont_check_for_backwards_references at positions known to hold no participants. Partial batches refuse participant mutations; use a full batch for reference maintenance. Recursive removal of a subtree containing participants is supported by live delete; see the bidirectional references ADR for scope.

Ordinary batches retain their executor semantics when no old or new value participates in backward references. Reference planner conflict rules apply only to batches that touch participants. A Delete of a populated tree or a tree replacement declared Check inspects the descendants and incurs additional read costs. A DeleteTree is never pre-scanned: DontCheckWithNoCleanup declares that the batch's own deletes emptied the subtree, Error and Skip verify that at apply time, and DeleteChildren checks the declaration on the cleanup walk it already makes, refusing a participant the batch does not explicitly delete. A delete-up-tree chain and a recursive removal therefore cost the plain removal.

Cost estimation follows the same split: an op declared Check charges the displaced-participant fan-out for its plain write or delete, an op declared DontCheck estimates the plain write alone, and ops that write a participant themselves are always charged.

SubelementsDeletionBehavior::DropFlat requires the DeleteTreeDontCheckForBackwardsReferences twin; the checked DeleteTree is refused before reading anything, preserving the O(1) contract. Partial batches refuse participant mutations in either segment; their inspection of tree replacements occurs before commit and can also incur recursive read costs.

Moving an element to a new key (V4)

QualifiedGroveDbOp::move_op(path, key, new_key) renames a key within its parent: the element at path/key ends up at path/new_key with the same bytes, and for a tree everything under it stays exactly as stored. Batches accept it from GROVE_V4 (apply_batch.move_element).

A move is applied in two steps:

1. At the parent's level it becomes two Merk ops. Op::DeleteMoved removes the node at the old key, and Op::PutMoved writes the same value with the same value hash at the new key. A tree element's value hash already commits to its subtree's root, and nothing it commits to depends on the key, so the parent's new root hash comes out right without opening the subtree. Aggregates are unchanged and propagate up as usual. A moved reference is the one element whose value hash can be recomputed: the level follows it from the new key, as it follows a reference the batch writes, and when its path reaches something the batch writes, commits it to the value it reaches there after the batch; otherwise it keeps its stored hash.
2. After the apply, every record of a moved tree is copied from the storage prefixes under the old path to the ones under the new path (a prefix is the blake3 hash of a path, so every nested subtree gets a new one), and the old prefixes are cleared. This covers nested Merk trees, non-Merk trees' data and indexed trees' secondary Merks; namespaces the element shows empty are skipped. Records stream into the storage batch, and a Merk record is classified by its element's type byte, decoded only where its contents matter. A nested tree is copied when its record is met, so besides the storage batch the copy holds one scan per level of depth. A read error stops the batch rather than commit a partial copy. Root hashes, aggregates and Merk shapes below the moved key do not change.

The copy reads the state from before the batch, and within the storage batch a put wins over a delete of the same key, so moves can trade places:

References are copied as stored and resolve from where they now are. One inside the moved subtree whose path stays inside it (any relative reference that does not climb above the moved element) still reaches the element it did. One whose path names the old key, such as an absolute path into the subtree or a reference from outside, keeps its stored value hash but reaches whatever is at the old key after the batch: nothing after a plain move, as after a delete, or the element another move brings there in a swap or a chain. That element can be the reference itself, or one leading back to it: reads of the reference, proofs through it, verify_grovedb with verify_references and state-sync finalization then fail with CyclicReference, as they fail for a dangling one. GroveDB does not follow those; keeping them valid is the caller's job. A moved reference itself is followed: when its path reaches something the batch writes, it commits to the value it reaches from its new key after the batch, so a batch that replaces its target and moves it leaves it valid. Its target is checked where it lies, though: one under a tree the same batch deletes or replaces is not refused, keeps its stored hash and dangles afterwards, as a reference to it the batch writes would.

A move is billed as storage that stays where it is. The moved element's node counts as replaced at the size it had under the old key, plus added bytes if the new key is longer, or removed bytes if it is shorter; only an element without flags may change key length. Every record copied below it counts as replaced at its stored size, and clearing the old prefixes bills nothing. A moved reference also pays for resolving its path, and for re-hashing its value when it is recommitted. The flags-update callback is not called for anything the move carries, so no storage is charged or refunded beyond the change in key length; ancestors updated by propagation go through it as in any batch.