Tracking issue for UnixFS automatic sharding

[aschmahmann]

Update 10/21: All major work has been finished. Full review pending.

The sharding PR has landed and we're working on the reverse transition of "unsharding". We haven't merged it in go-ipfs (#8114) until we finish with the unsharding to have the whole functionality together (and ensure deterministic CIDs for any directory size).

Main unsharding work happening in ipfs/go-unixfs#94.

Minor issues left for last compiled in ipfs/go-unixfs#105 can be addressed after main PRs land.

Potential issue with merkledag.Walk function doing a BFS in ipfs/boxo#392, but this can be address after landing the major work as it's only an optimization.

---

Tracking implementation of #7022

Per the linked issue in order to enable sharded directories by default we want to shard the directories when required.

After some discussion the heuristic we are going to use for now to do determine when to use sharded vs regular directories is option three listed here. That is we will sum the sizes of all the names + CIDs in the map and if they are >256KiB we will use sharded directories and if they are <=256KiB we will use regular directories.

Places where we'll likely have to look at changes include:

• go-unixfs (the importer and directory code as well as potentially the helper code)
• go-mfs (wherever we modify a folder)

Hopefully if we keep the interfaces the same here we won't have to make any changes in go-ipfs itself. We may need to do a scan to see if we do any type casting to a UnixFS basic or sharded directory though just in case.

Once this is done we should be able to drop the global boolean that enables "use sharded directories" from both go-unixfs, go-ipfs, and go-ipfs-config.

[schomatis]

Scoped issue with technical details in ipfs/go-mfs#87 regarding the MFS/UnixFS enhancement to support this. Once that is done go-ipfs should only need to update the dependencies and set the new option with the desired 256KiB value.

[Stebalien]

Now that auto-sharding is implemented, let's try implement auto-unsharding. As far as I can tell, this shouldn't be too difficult and shouldn't be a massive performance problem (TBD). The tricky parts are:

1. We don't want to do any size estimation unless we actually delete something.
2. Ideally, we'd only do size estimations when we serialize.

Potential solution:

1. When making changes in a sharded directory, keep track of the net size change.
2. On serialization, if the net size change is negative, enumerate until we hit the limit.

Additional notes (possible future extensions):

• We may want to try EnumLinksAsync to enumerate in parallel, but this may actually have worse performance because we might try sampling different parts of the graph each time (non-deterministic). It may actually be better to just enumerate links sequentially, especially because we likely only need to fetch maybe ~10 leafs (would need to be computed). Alternatively, it may be worth it to try to make EnumLinksAsync more depth-first instead of breadth-first.
• We may want to count over the limit (e.g., by 2x). We could use this to "offset" our net size change running total to avoid re-computing this. But this probably isn't worth it for a first-pass.

[schomatis]

We still need to integrate this into go-ipfs (draft in #8114), namely fixing sharness and interop tests.

[BigLep]

2021-05-10 discussion:

1. @schomatis is going to do the unsharding work week of 2021-05-17
2. @mburns is going to do a test fix here. @schomatis or @aschmahmann can provide the details.

[schomatis]

More details in the TODO list of the ongoing PR #8114.

[schomatis]

Update 8/13 (@schomatis): I'm leading this effort currently in progress. Not blocked.

• The sharding PR has landed and we're working on the reverse transition of "unsharding". We haven't merged that in go-ipfs (feat: update UnixFS/MFS with auto sharding #8114) until we finish with the unsharding to have the whole functionality together (and ensure deterministic CIDs for any directory size).

• Main unsharding work happening in Size-based unsharding go-unixfs#94. There are several reviews that I need to address next week.The PR is constantly being updated with the main TODO items.

• The tests have been progressing in a separate PR in Tests for unsharding PR go-unixfs#99 which now have a preliminary code for review. After Size-based unsharding go-unixfs#94 is lands will re-focus here.

[schomatis]

Update 8/17 (@schomatis, DRI):

Brief:

• Not blocked.
• Reviews pending for:
  • Remove tiemout and refactor sizeBelowThreshold go-unixfs#102
  • Add unsharding logic for the AddChild case as well go-unixfs#103
  • Tests for unsharding PR go-unixfs#99

[schomatis]

Update 8/17 (corrected) (@schomatis, DRI):

Brief:

• Not blocked. Working on Size-based unsharding go-unixfs#94.
• Reviews pending for:
  • Remove tiemout and refactor sizeBelowThreshold go-unixfs#102
  • Add unsharding logic for the AddChild case as well go-unixfs#103
  • Tests for unsharding PR go-unixfs#99

[schomatis]

Update 8/23 (@schomatis, DRI):

Brief:

• Working on tests in separate branch while Size-based unsharding go-unixfs#94 gets reviewed.
• Reviews pending for:
  • Remove tiemout and refactor sizeBelowThreshold go-unixfs#102
  • Add unsharding logic for the AddChild case as well go-unixfs#103
  • Tests for unsharding PR go-unixfs#99

(See full status in the OP.)

[schomatis]

Update 8/27 (@schomatis, DRI):

Brief:

• Working on tests in Tests for unsharding PR go-unixfs#99.
• We need to decide on how to implement a potential concurrent test for HAMT enumeration: Tests for unsharding PR go-unixfs#99 (comment)
• Reviews pending for:
  • Tests for unsharding PR go-unixfs#99 (Need a more detailed review on io/directory_test.go as explained in PR description.)

(See full status in PR description.)

[schomatis]

Update 9/3 (@schomatis, DRI):

Brief:

• Working on concurrent test in Concurrent walk test go-unixfs#106.
• Reviews pending for:
  • Concurrent walk test go-unixfs#106
  • Potential issue with merkledag.Walk function doing a BFS: ipld/unixfs: concurrent dag.Walk does a BFS when unsharding boxo#392.
  • Tests for unsharding PR go-unixfs#99 (Need a more detailed review on io/directory_test.go as explained in PR description.)

(See full status in PR description.)

[schomatis]

Update 10/21: All major work has been finished. Full review pending.

The sharding PR has landed and we're working on the reverse transition of "unsharding". We haven't merged it in go-ipfs (#8114) until we finish with the unsharding to have the whole functionality together (and ensure deterministic CIDs for any directory size).

Main unsharding work happening in ipfs/go-unixfs#94. Test for this are in a separate PR: ipfs/go-unixfs#99

Minor issues left for last compiled in ipfs/go-unixfs#105 can be addressed after main PRs land.

Potential issue with merkledag.Walk function doing a BFS in ipfs/boxo#392, but this can be address after landing the major work as it's only an optimization.

[aschmahmann]

Closed by #8563