Switch to sharding based on estimated directory size

[schomatis]

The background and motivation for this is in ipfs/kubo#8106, but this is a self-contained issue.

Add an option similar to UseHAMTSharding that switches from basic to HAMT directory based on an approximated directory size.

Proposed option's name (just for the sake of this issue description; feel free to suggest any other): HAMTShardingSize.

Directory size estimation: aggregate byte length of all of BasicDirectory.ProtoNode's Links (namely their name and CID). This is only an estimation because we don't marshal/encode the underlying ProtoNode to get the exact block size (which is the motivation for the sharding in the first place) but it is close enough given the BasicDirectory doesn't use the ProtoNode's data field.

• Optional: we can cache the estimated size as an internal variable to avoid constant recomputation.

This option will work in tandem with the global UseHAMTSharding; either of the two can trigger the HAMT transition. Any plans for the deprecation of UseHAMTSharding are outside of the scope of this issue.

Known drawbacks (inherited from current design) mentioned here just to make sure stakeholders are in sync:

• We do not transition back from HAMT to a basic directory. Once a HAMTDirectory always a HAMTDirectory. There won't be any system of high and low watermarks: once the estimated directory size grows above HAMTShardingSize we switch and that is it.
• There is no logic to signal to use a HAMT directory for a particular case. If the user knows from the start directory D, and only directory D, will have, say, thousands of entries and would like to make it a HAMT directory from the start to avoid the (relatively expensive) switch down the road it is forced to use the global UseHAMTSharding option for all directories, not just directory D.

---

The switch from basic to HAMT directory logic lives here in the MFS repo. This should actually live in UnixFS, MFS shouldn't need to know what type of directory it is manipulating, it only needs the Directory interface to mount its mutable FS (the sole objective of this layer). This is clearly evidenced by the fact that the UseHAMTSharding option itself is a UnixFS option (that go-ipfs sets directly). If we can fix this in #86 before proceeding here, we will implement the logic described here in UnixFS instead, otherwise the HAMTShardingSize will be added to the MFS layer alongside the global option in addUnixFSChild.

[Stebalien]

The switch from basic to HAMT directory logic lives here in the MFS repo. This should actually live in UnixFS, MFS shouldn't need to know what type of directory it is manipulating, it only needs the Directory interface to mount its mutable FS (the sole objective of this layer). This is clearly evidenced by the fact that the UseHAMTSharding option itself is a UnixFS option (that go-ipfs sets directly). If we can fix this in #86 before proceeding here, we will implement the logic described here in UnixFS instead, otherwise the HAMTShardingSize will be added to the MFS layer alongside the global option in addUnixFSChild.

Yes, I agree. I'd much prefer to push this logic into go-unixfs. I'd expect we'll end up with less code (and less work).

---

Optional: we can cache the estimated size as an internal variable to avoid constant recomputation.

We can also stop enumerating when we reach the limit. This will be especially important when switching from sharded to non-sharded.

We do not transition back from HAMT to a basic directory

Can we not enumerate links till we reach the maximum to determine that we shouldn't "switch back"? This will have a performance impact, but it shouldn't be terrible (especially if we memoize) and is only incurred when deleting files.

This isn't absolutely critical but it would be nice to figure out how viable it is.

This option will work in tandem with the global UseHAMTSharding; either of the two can trigger the HAMT transition.

The goal here is to replace this flag with something that "just works". I wouldn't try to maintain both in tandem. (@aschmahmann?)

There is no logic to signal to use a HAMT directory for a particular case. If the user knows from the start directory D, and only directory D, will have, say, thousands of entries and would like to make it a HAMT directory from the start to avoid the (relatively expensive) switch down the road it is forced to use the global UseHAMTSharding option for all directories, not just directory D.

Why is this a huge performance issue? In practice, I expect starting with a non-sharded directory and sharding late will actually have better performance:

1. When the directory is small, we'll be able to keep everything in one object (which we can cache in memory).
2. When the directory grows large, we can build the sharded directory all at once, avoiding the cost of building it incrementally (i.e., we won't have create "intermediates" just to throw them away).

[schomatis]

The goal here is to replace this flag with something that "just works". I wouldn't try to maintain both in tandem. (@aschmahmann?)

I'm fine dropping it, just not in this issue to maintain as much backward compatibility as possible and make the least amount of possible changes in go-ipfs here. Just trying to scope this and reduce discussion here.

Why is this a huge performance issue?

Maybe it's not, just wanted to flag current behavior, don't really care about performance in this issue.

[Stebalien]

I'm fine dropping it, just not in this issue to maintain as much backward compatibility as possible and make the least amount of possible changes in go-ipfs here. Just trying to scope this and reduce discussion here.

I'm assuming that keeping it will be more work than dropping it but I'm not entirely sure how you're planning on going about it.

[aschmahmann]

I don't think it's worth keeping the current behavior where it's possible for someone to create a directory block of size >1MiB.

In theory we could have some behavior where unless EnableSharding=true we error instead of switching from non-sharded to sharded and refuse to modify sharded directories, but this seems like it'd be a pain to implement.

[schomatis]

This isn't absolutely critical but it would be nice to figure out how viable it is.

Yes, I'm not doing that here. Feel free to submit another issue and discuss potential solutions for that after this one lands.

[achingbrain]

We do not transition back from HAMT to a basic directory

FWIW, the MFS implementation for js-IPFS does transition back to a basic directory if the sharding threshold is crossed, though it's a bit simpler as it just uses an arbitrary directory entry count as the threshold value.

[Stebalien]

FWIW, the MFS implementation for js-IPFS does transition back to a basic directory if the sharding threshold is crossed, though it's a bit simpler as it just uses an arbitrary directory entry count as the threshold value.

ipfs/kubo#8106 (comment)