Skip to content

HAMT: collapse under-full subtrees on delete so tree shape is canonical #421

Description

@rmanibus

Context

The HAMT in internal/hamt produces a tree shape that depends on how the tree
was built, but only via deletion. Measured directly against Txn.Insert and
Txn.Delete:

  • Pure insertion is already history-independent. Inserting the same 64 keys
    in forward and reverse order yields byte-identical roots. Entries within a
    leaf are sorted by sortEntries, and buildNode is deterministic on the
    entry set and level.
  • Deletion is not. Building 2048 entries and deleting down to 4 yields a
    different root than building those 4 directly.

The cause is in Txn.delete (internal/hamt/hamt.go). It collapses an internal
node back into a leaf only when a single leaf child remains:

// Collapse: if a single leaf remains, promote it in place of this node.
if len(owned.children) == 1 {
    if only, err := tx.resolve(ctx, owned.children[0]); err == nil && only.leaf {
        return owned.children[0], true, nil
    }
}

It never re-merges several under-full leaves whose combined entry count has
dropped back to maxLeafSize (32). A subtree that split under load and then
shrank stays split.

Note that sorting children is not the fix — children are already canonical,
indexed by hash bits through the node bitmap, and insertion order already does
not matter.

Structural bloat left behind, deleting from a 2048-entry tree:

entries kept nodes after deletion nodes if built fresh ratio
4 5 1 5.0x
64 65 26 2.5x
256 133 29 4.6x

Goal

Make a HAMT's shape a function of its contents alone, so that equal content
yields an equal root regardless of the insertion and deletion history that
produced it.

Scope

  • Add a canonical collapse rule to Txn.delete: when a subtree's total entry
    count drops to maxLeafSize or below, re-merge it into a single leaf.
  • Confirm the rule composes with the existing single-leaf promotion rather than
    duplicating it.
  • Keep the cost of the check proportional to the subtree actually being
    collapsed; counting the whole tree on every delete would trade one problem for
    a worse one.
  • Regenerate TestRootHashGolden. Root hashes change for delete-heavy trees,
    which is a golden-file update, not a compatibility break: nodes are
    content-addressed and trees written by earlier builds stay readable.
  • No repository format version bump. Older builds read a canonically collapsed
    tree exactly as they read any other; this changes which shapes get written,
    not how a shape is encoded.

Impact and priority

There is no correctness impact. Lookup, walk and diff behave identically on
a drifted tree. The costs are node-count bloat in delete-heavy repositories and
weaker node-level dedup between repositories that converge on the same content
through different histories. Bulk data is unaffected — chunk, content and
filemeta refs are pure functions of content and dedup regardless.

The numbers above come from a synthetic 97%-deletion workload. A measurement
on a realistic delete-heavy history is worth taking before committing to this
,
since it is a subtle change to a core data structure.

Found while performance-checking copy (RFC 0017), which is unaffected: it no
longer compares roots across histories.

Acceptance Criteria

  • Building a tree by insert-then-delete and building it directly from the
    surviving entries yield the same root, asserted for several sizes spanning the
    maxLeafSize boundary.
  • Existing HAMT behaviour is unchanged for insert-only workloads.
  • Node counts for the table above match the freshly-built column.
  • go test ./internal/hamt ./internal/engine passes
  • golangci-lint run ./internal/hamt/... ./internal/engine/... passes

Metadata

Metadata

Assignees

No one assigned

    Labels

    area/coreCore backup engine, repository model, and restore semanticstech debt

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions