unixfs/io: HAMTDirectory.AddChild re-enumerates 256 KiB of links on every in-place replacement (size delta compares a named link with an unnamed one)

Open Beginner friendly
#1,226 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
2/5
Estimated time
1-3 hours
Newbie friendliness
70/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
go

Research direction

Start with ipld/unixfs/io/directory.go, especially needsToSwitchToBasicDir, sizeBelowThreshold, and HAMTDirectory.AddChild; trace how replacement link names affect size estimates. Check the existing tests for HAMT directory replacement and add a case showing a same-size replacement skips shard enumeration. Done when replacement size changes are measured consistently and the regression case passes.

Written by the indexing model from the issue text.

Description

Summary

Replacing an existing entry of a sharded (HAMT) directory with HAMTDirectory.AddChild (the path MFS files write takes for an existing file) enumerates the directory's shards from the blockstore on every call, even though the directory size does not change. needsToSwitchToBasicDir computes the size delta of the operation by comparing the existing entry's link, which carries its name, against a link for the new node built with ipld.MakeLink, which has an empty Name. In SizeEstimationLinks mode that makes every same-CID-length replacement look like a shrink of len(name) bytes, so the d.sizeChange+operationSizeChange < 0 branch runs sizeBelowThreshold, which walks shards until it has seen HAMTShardingSize (256 KiB) worth of links before it can stop.

Code (boxo v0.43.0, the same on main today):

For a directory whose links are about 80 bytes (CIDv0 name + CIDv0), that is roughly 3,300 entries read and decoded from the blockstore per AddChild, independent of how large the directory is. SizeEstimationBlock has the same asymmetry, since the name is part of the serialized link size.

Measurements

kubo 0.43.1 (boxo v0.43.0), linux/amd64, flatfs, offline daemon, warm repo. One MFS directory holding 17,857 entries named by CIDv0 (each entry a one-file subdirectory, 16 KB file), written through /api/v0/files/write with 50 writes in flight. "rewrite" replaces every existing entry; "create" writes the same entries into an empty directory.

operation wall daemon CPU
create 17,857 entries, flush=false, files flush every 250 5.9 s 14 s
rewrite 17,857 entries, flush=false, files flush every 50 66 s 290 s
rewrite 17,857 entries, flush=false, one files flush at the end 41 s 127 s
rewrite 17,857 entries, flush=true 222 s 1,009 s

The same rewrite of a 1,786-entry directory (below the sharding threshold, so a basic directory) costs 0.6 s / 1.6 s with flush=false.

A 30 s CPU profile of the daemon during the flush=false rewrite: 25 to 35% of samples under hamt.parallelShardWalk.func1 (spawned from Shard.EnumLinksAsync, reached through HAMTDirectory.sizeBelowThreshold and needsToSwitchToBasicDir from DynamicDirectory.AddChild), 11 to 15% in blockstore.Get / flatfs.Datastore.Get reading shard blocks, and 17 to 37% in runtime.gcBgMarkWorker from the decoded shards. With flush=true Shard.Node re-serialization adds another 5%.

Expected

A replacement whose link size does not change should be a zero delta and skip the enumeration. Giving the new link its name before measuring (link.Name = name, or a linkSizeFor(name, cid) helper used for both sides) fixes the comparison. Independently, sizeBelowThreshold could skip the walk when d.totalLinks * minLinkSize already exceeds the threshold.

Impact

Anything that rewrites files in large MFS directories pays this on every write: kubo ipfs files write into a directory with more than a few thousand entries, and applications that keep per-item files under one directory. In our case (pkc-js, 17,857 files rewritten per publish cycle) this was most of the daemon's CPU for the cycle.

Dominant language
Go
Stars
326
Forks
165
PR merge metrics
No merged PRs in 30d

Getting set up

  • No Dockerfile or Docker Compose file
  • Has a pull request template
  • No contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from ipfs/boxo

All issues in ipfs/boxo

Similar issues

More Go issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.