Should we profile CIDs?

Protocol
38

Adding some additional context as I’ve been diving into this

The state of UnixFS in JavaScript/TypeScript

Most developers use higher-level libraries that depend on these, and have slightly different defaults

Defaults and naming profiles

Naming things is hard. Moreover, understanding the trade-offs in different UnixFS options is far from obvious to newcomers sold on content addressing.

In thinking about this for users not familiar with internals, the conclusion I came to is that we should lean more heavily on defaults to guide users to the happy path, which ensures CID equivalency given the same inputs.

As for naming, my initial suggestion was to name the profile unixfs-v1-2025 denoting the year it was ratified. This is grounded in the insight that consensus around conventions can change over time, though not that often.However, I realise the shortcomings of this approach, it carries no information about the specifics of the profile, so the actual parameters will likely need to live in the spec. Finally, with time, this might feel “outdated”.

I should also note that I don’t think CIDv2 packing this information is pragmatic. This will be a breaking change that I don’t think the ecosystem will embrace, leading to more fragmentation and confusion.

Another approach could be to name profiles based on the key UnixFS/CID parameters:

  • CID version
  • hash function
  • layout, e.g. balanced, trickle
  • chunk-size
  • dag width
  • raw blocks
  • HAMT threshold (I’d need to dive deeper into whether there’s that much variance around this)

For example v1-sha256-balanced-1mib-1024w-raw.

Long and convoluted, but encapsulates the information.

HAMTs and auto-sharding

HAMTs are used to chunk UnixFS directories blocks that contain so many links that result in the block being above the a certain chunk size.

Almost all implementations use HAMT fanout of 256. This refers to the number “sub-shards” or “ShardWidth”

Implementations vary in how determine whether to use a HAMT. Some support auto-sharding, where they automatically shard based on an estimate of the block size (counting the size of PNNode.Links).

  • Kubo/Boxo uses a size based parameter (HAMTShardingSize) of 256KiB, where 256KiB is an estimate of the blocksize based on the size of all links/names. An estimate is used (rather than the actual blocksize) to avoid needing to serialise the Protobuf just to measure size while constructing the DAG.
    • go-unixfsnode (used by go-car and extensively by filecoin ecosystem) also autoshards like Boxo/Kubo
  • Helia and ipfs/js-ipfs-unixfs use the same approach as Kubo (discussion, and this comment). The config is shardSplitThresholdBytes which defaults to 256KiB
  • ipld/js-unixfs which the Storacha tools: ipfs-car and w3up depend on, doesn’t implement autosharding (open issue. Consumers of the library like ipfs-car and w3up trigger HAMT sharding once a directory has 1000 links.

Trade-offs in DAG Widths

@mosh brought up the question of whether 1024 or 174 width is preferred.

  1. Discuss whether 1024 or 174 width is preferred, or if it’s worth having both.

As far as I understand:

  • Wide DAGs are better for retrieval speed: more blocks can be downloaded in parallel as you know about more of the DAG without having to traverse to lower layers. In other words: wider dags result in fewer hops from the root of the DAG (just metadata) to the leaf nodes (containing the actual data).
  • Wide DAGs, on the other hand, are less optimal for structural sharing (which enables caching) when updated (like in Git). So changes result in fewer nodes that need to be updated, but at a higher computational (more data to hash) and i/o (more blocks to read) cost of rehashing.
Factor Wide DAG Narrow DAG
Tree depth Shallow Deep
Verification speed Faster (parallelizable) but more CPU heavy Slower (sequential)
Node size Larger (more links) Smaller
Update cost higher (more children, i.e. bytes to hash) lower cost but more steps since updates cascade up many levels
Parallelism High Low
Deduplication Low (bad) High (good)

Addendum: @rvagg has brought to my attention the following:

Mutation cost is very significant for thicker/wider DAGs, especially if you count the storage cost of historical data - if you update a single leaf at the bottom of a DAG that has a high branching factor, then each of those huge intermediate nodes need to be replaced entirely. This is why Filecoin tends to opt for more slender structures, because we have to care about state cost and state churn. The HAMT that Filecoin uses is only ever used with a bitwidth of 5 - a branching factor of 32. There’s another structure, the AMT, used as an array, and the branching factor varies from fairly high for structures that don’t change very much all the way down to 4! So they get tall and slender. Then when you mutate at the bottom, you’re mutating all the way up but you’re not involving CIDs of many other branches in that process.

Important to consider mutation in all of these, it doesn’t tend to be something you think about once you have a static graph, but there are plenty of places where it matters. Wikipedia has always been my favourite unixfs example, consider how it would go if you were to keep the wikipedia-on-ipfs project going and update it daily. I think if that were done, you’d want to get some stats on % of churn and then model the impact on the graph. I suspect a branching factor of 256 would definitely not be ideal for that, you’d essentially poison the “dedupe” potential of IPFS in the process because almost all of the intermediate graph section would need to mutate each day thanks to the random distribution of leaves in a HAMT. Pages may not change much, but the entire structure above the leaves probably would. I can’t recall how big it is, but it’s more than a few levels deep, 256256256… heavy blobs being replaced each time.

DAG width for IPFS use-cases

IPFS’ main value proposition is resilience and verifiability for data distribution. This is often at the cost of latency (or time to first byte). Retrieving data by CID is much more involved than normal HTTP retrieval: you have to go through content and peer routing before you even to connect to someone providing the data.

All else being equal, wider DAG widths allow for reduced latency and higher parallelism which seems desired if you accept the costs: wider DAGs undermine the potential deduplication across versions thereby increasing the storage cost of historical data. A good example for this is the IPFS Wikipedia mirror, where a full snapshot can be up to 650GB. A while back the topic of deduplication for Wikipedia mirrors was discussed and including systematically measuring and improving deduplication, however, it seems that most of that work was never concluded.

Wikipedia isn’t the typical IPFS use-case. And for such use-cases, it’s totally fine to deviate from the defaults and use specialised chunking techniques and DAG layouts that are better fit for deduplication.

IPFS today isn’t really optimised or has enough tooling for versioning datasets – which would hypothetically benefit from narrower DAGs. And while storage keeps on getting cheaper, networking is still constrained by geographical distances and the speed of light.

So let’s embrace wider DAGs as the default and make sure we communicate these trade-offs!

Other sources of CID divergence

Empty folders

  • Kubo’s ipfs add command and Helia’s unixfs.addAll (with globSource) add empty folders.
  • w3 and ipfs-car both ignore empty folders (they both depend on storacha/files-from-path which only returns files and ignores empty folders).

This means that if your input contains empty folders that resulting CID will be different, even if all other settings are the same.

This brings up the question of why you would even include empty directories in the DAG.

My suggestion would be to account for this as we define the profile settings whether empty directories are included

6 Likes