Support for UnixFS Sharding + support balanced & trickle dag

[daviddias]

When spec is ready

[hackergrrl]

Is there a wip spec? Could you link to it (and/or any other relevant docs)?

[daviddias]

There you go. Gist is that we figured out how to do the Sharding while at NYC, waiting on @jbenet to lay down the spec.

• Sharding - unixfs support for large directories ipfs/specs#32
• Distinguish fanout from non-fanout links ipfs/specs#10
• Sharding IPLD objects ipfs/notes#76
• captain.log - go-ipfs ipfs/kubo#2247 (comment)

[daviddias]

@whyrusleeping can you share how is the 'file wrapping' happening in go-ipfs currently? If I'm not mistaken, it is something like ' each time we reach 174 links in a file dag node, we wrap it in another dagnode and add the chunks to the new one'

[daviddias]

@whyrusleeping is there a spec in progress for the sharding? plus probably some impl details to make it faster? It would also be good to have the trickle dag documented and something saying when we are moving to it so that we can prepare.

[dignifiedquire]

Does it make sense to do this before IPLD, as far as I understood the spec would change with IPLD?

[whyrusleeping]

The changes to the unixfs protobuf are the most relevant.

Beyond that, a few notes:

• using murmur3-64 over the directory entry names
• i'm using the unixfs Data field to hold the bitfield.
• All link names are prefixed with the hex representation of their index within the bitfield. Nested shards link names are just the hex number.
• When creating new directories, we leave them unsharded up until some threshold which is at the moment arbitrarily set to 1000

And after that, it just follows the HAMT algorithms

[jbenet]

• using murmur3-64 over the directory entry names

must be configurable.

@whyrusleeping do you recall where we put the HAMT notes we took on a pad once? it had the construction in IPLD and the mapping form protobuf to IPLD.

[whyrusleeping]

must be configurable.

Yes, of course. Take a look at the linked changes to the protobuf

As for the pad, i'm not finding it in my chrome history... Do you remember if we used a riseup pad for that?

[jbenet]

Yeah riseup most likely :/
On Mon, Aug 8, 2016 at 13:30 Jeromy Johnson notifications@github.com
wrote:

must be configurable.

Yes, of course. Take a look at the linked changes to the protobuf
ipfs/kubo@9dde293#diff-7e6bd2fe376f37f54b3dda741384d37dR10

As for the pad, i'm not finding it in my chrome history... Do you remember
if we used a riseup pad for that?

—
You are receiving this because you were assigned.
Reply to this email directly, view it on GitHub
#45 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAIcocDfWOgHeO_8T0Qb5UnK60uN7jPYks5qd2fFgaJpZM4IoPh9
.

[daviddias]

@whyrusleeping, @pgte just pinged me about the max number of leaves per node and from the diagram we sketched a couple of weeks ago, the impression I got was that it is 172 data leaves + nLayerRepeat (default 4) + 1 link for the next level, total of 177.

However, just to be sure, I tested adding a big file with the TrickleDAG and got 183 Links

ipfs object links QmHash.. | wc -l
     183

Where are the extra 6 coming from?

[whyrusleeping]

the trickledag doesnt have a max width, but you can compute the expected width of a tree of a given depth by taking num_data_leaves + (depth * nLayerRepeat).

Not having a max width is fine because by the time we get to max blocksize, we end up having a file with more bits than there are atoms in the planet, or something

[whyrusleeping]

@diasdavid The key here is that everything about the trickledag is recursive.

[daviddias]

Got it now :)

It keeps repeating itself as it goes, increasing the level of depth each time. @pgte does the graph above help to clarify this last detail?

[pgte]

Yes, thank you @whyrusleeping!
It's a recursive tree limited by maximum depth at each iteration, and unlimited in width at each node.
These caractheristics have made it a quite interesting challenge to implement as a pull stream.. :)

Thanks @daviddias for the diagram, I think this one illustrates this well! 👍

[pgte]

Specially the reduction being asynchronous has made this quite interesting to solve.. :)

[daviddias]

BalancedDAG + TrickleDAG is on #118 thanks to @pgte and Sharding/HAMT is on its way! :D

[daviddias]

@pgte has shipped all of this!! !:D check it out on the last release of js-ipfs :)