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)
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
- Domain
- backend, performance
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):
- https://github.com/ipfs/boxo/blob/v0.43.0/ipld/unixfs/io/directory.go#L1127-L1195 (
needsToSwitchToBasicDir):operationSizeChange -= d.linkSizeFor(entryToRemove)whereentryToRemovecomes fromshard.Findand has its name; thenlink, _ := ipld.MakeLink(nodeToAdd); operationSizeChange += d.linkSizeFor(link)wherelink.Name == "". - https://github.com/ipfs/boxo/blob/v0.43.0/ipld/unixfs/io/directory.go#L1203 (
sizeBelowThreshold): enumerates viaEnumLinksAsyncuntilpartialSize+sizeChange > shardingSize. - https://github.com/ipfs/boxo/blob/v0.43.0/ipld/unixfs/io/directory.go#L1017-L1030 (
HAMTDirectory.AddChild): the real bookkeeping removes the old link's size with its name and adds the new one withname, sod.sizeChangestays 0 after a replacement and the branch is taken again on the next one.
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
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from ipfs/boxo
-
Difficulty 4/5 3-5 days Newbie friendliness 46/100
-
Difficulty 3/5 1-2 days Newbie friendliness 55/100
-
need/triage
Difficulty 5/5 Over a week Newbie friendliness 38/100
-
dif/medium effort/hours kind/enhancement P3 topic/devexp
Difficulty 5/5 Over a week Newbie friendliness 35/100
-
dif/expert effort/weeks kind/enhancement P2
Difficulty 5/5 Over a week Newbie friendliness 25/100
Similar issues
-
affects-8.5 component/session severity/moderate sig/transaction type/bug
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
Maintainers usually reply within 1 day
-
enhancement good first issue
Difficulty 2/5 1-3 hours Newbie friendliness 85/100
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 72/100
harvester/harvester#12311 · 1 comment ·
Maintainers usually reply within 1 day
-
verifyrun --bracket-digest --credit: relative --witness is could-not-check, absolute path creditsOpenbug effort:s impact:low raised-by:desk risk:low
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
medici-finance/assay#6580 · 1 comment ·
Maintainers usually reply within 1 day
-
Difficulty 2/5 1-3 hours Newbie friendliness 80/100
blinklabs-io/gouroboros#3026 ·
Maintainers usually reply within 1 day