Automatic sharding of big directories

[Stebalien]

This is a tracking issue for the sharded directory feature. This feature can be enabled with:

> ipfs config --json Experimental.ShardingEnable true

TODOs:

• Make sure we don't shard too soon. At the moment, the cutoff to start sharding is very low.
• Ideally, avoid creating sharded directories thar are too "deep". However, this may be tricky to do without breaking changes.

Ideally, we'd fix this issue by switching to unixfs 2.0 and a generalized sharded map implementation. However, that's probably not going to happen in the near future and this feature is used widely enough that we'll likely have to stabilize it in its current form.

[achingbrain]

I'd really like to enable sharding by default in js-IPFS to reduce the amount of codepaths and A/B tests.

ipfs.add in js-IPFS takes a shardingSplitThreshold argument that sounds similar to the sharding cutoff above - it's set to 1000 by default when sharding is enabled.

Can go-IPFS take the same option? That should tick off the first item.

cc @aschmahmann

[lidel]

We really should fix this. js-ipfs shards dirs >1k of items out-of-the-box and go-ipfs fails flat.

On top of that, the biggest problem in go-ipfs right now is that when you enable sharding, it shards EVERYTING, so even if you have a small dir under 1k of items, its still sharded, which produces different CIDs.

I believe a lot of work happened in IPLD team since we implemented HAMT-sharding in go-ipfs, would be useful to leverage that work when we make sharding enabled by default in go-ipfs.

@ribasushi @warpfork are there any libs / specs related to improved sharding in IPLD/Filecoin which we should be aware of in planning here?

[warpfork]

Yes!

• We shifted to trying to make sharding "in scope" for IPLD by defining it as something you do with an ADL ("Advanced Data Layout"), which is a plugin-like concept.

• A lot of work was done on HAMTs as a map sharding mechanism. There's a spec in https://github.com/ipld/specs/blob/master/data-structures/hashmap.md ; a golang implementation in https://github.com/ipld/go-ipld-adl-hamt ; and a JS implementation in ((hm, @rvagg, give me the latest link?)).

• We don't have particular work done on the "don't shard below $X entries" problem. The idea was that we'd more or less ignore this during the implementation of the "guts" of something like a HAMT, and then do it with a small piece of logic at the top level of an ADL. The net effect would be that the plugin versioning problem of an ADL would still thus cover the "when do we start sharding" decision (which is good; answers all in one place).

• All in all there's a lot of pieces here. Some assembly still required.

I'll re-tag to @rvagg and @mvdan for more info.

[mvdan]

Doesn't a HAMT already "shard" or split the data among multiple blocks, depending on its parameters like bitWidth and bucketSize? If one were to add sharding at the ADL layer on top of go-ipld-adl-hamt, would you not end up with two layers of sharding?

[warpfork]

iiuc I think the point of the "shardingSplitThreshold" mentioned above is that there's some value below which any sharding should be skipped, and a simple inline map (potentially, not even a single new block) should be used.

So what I meant by "don't shard below $X entries" is like: less than 1000 (or $X) entries, don't invoke a hamt at all and just use a regular plain map in the same block. Or in other words, I'm treating "sharding" as roughly an alias for using a HAMT (or some other ADL that serves a similar purpose to HAMTs).

My statement about this and how it relates to ADLs is: whatever that condition is for whether to invoke the full HAMT (and all its sharding logic) vs just do an inline plain map... is something that I think should be placed within the boundary of what we call ADLs. Doing so means we have a place to identify what that $X condition is: it's the same place we identify the ADL as a whole. This doesn't mean the problem goes away, but it means two problems can solved at once in one place: we already have the "identify the sharding logic needed here" problem; we might as well combine that with the "what is the shard vs inline threshhold and how do we identify that logical conditon" problem.

[mvdan]

Ah, gotcha, that makes sense. I wonder if we could expose that as a generic ADL layer, e.g. "use a basic map if size < N, otherwise use this fancy multi-block map prototype".

[rvagg]

JS implementation is https://github.com/rvagg/js-ipld-hashmap which is algorithmically backed by https://github.com/rvagg/iamap, but we're a little out of sync across our HAMT implementations (and spec) as we've tried to (a) integrate Filecoin's formats into our specs and ideally enable our implementations to speak that format, and (b) improve based on some learnings. It wouldn't be hard, but if we want to put the pedal down on UnixFS v2 and a better directory map->hamt version/implementation then we would need to budget the work and get it all sorted out. Otherwise, if we're not intending to reach for UnixFS v1 it seems like we should be using the HAMT stuff that's supposed to come with MFS. I'm not really over that work or how it might differ from the HAMT work we've done outside of MFS and how standardised it is and whether we can break the layout to do it betterer?
@mvdan - there might be yet another HAMT layout to consider for the ipld-prime ADL work you've done, we haven't even talked about MFS in this context before.

[achingbrain]

we're a little out of sync across our HAMT implementations

Yes - js-IPFS uses hamt-sharding* and not ipld-hashmap (I didn't know about this new package, if it generates the same HAMTs as go-IPFS maybe you could open a PR refactoring the unixfs-importer and mfs internals to use this instead).

We don't have particular work done on the "don't shard below $X entries" problem

Neither did js-IPFS TBH, I think the 1k figure for $X may have been plucked out of thin air but it seems to work well enough and the user can override it if they choose.

if we want to put the pedal down on UnixFS v2

I want UnixFS v2 but I think tying the resolution of this issue to V2 would be a mistake as it's a much bigger job with an unclear end point as mentioned in the OP.

A more expedient path would be for go-IPFS to just add the shardingSplitThreshold option to ipfs.add to let the user specify $X and shard conditionally based on that.

The js-IPFS import logic will use a regular UnixFS directory until it hits the threshold, then converts that to a shard once the threshold is passed.

The MFS implementation then uses this mechanism to convert existing directories to HAMT shards when adding members takes you over the threshold, and also turns shards back into regular directories when removing members takes you below it.

---

* hamt-sharding was extracted from ipfs-unixfs-importer with the aim of reuse but I don't think that's been terribly successful 🤷

[rvagg]

Excuse my ignorance but I'm not quite grokking it from this thread and this thread is already breaking my assumptions about how it currently works - but don't go-ipfs and js-ipfs both implement the same HAMT algorithm and block structure for large directories? Or is this issue actually saying that go-ipfs doesn't have such support and only js-ipfs does, and therefore the use of the HAMT is not actually standardised or specified?