scaling to indefinite and changing groups of files

[okdistribute]

Hey all,

I've been in conversations with Internet Archive to integrate Dat into their dweb portal. One of their requirements is to serve data from Dat over the peer-to-peer network without having to scan all of the files ahead of time (upwards of 50 petabytes of archives...). Opening this on behalf of @mitra42 who is project lead on the Archive's dweb portal.

The way they have approached this with other protocols such as IPFS, Gun, and Webtorrent is to have a peer that pretends that it contains everything, and then once an archive is requested, to go fetch it from Internet Archive storage and serve it on the network.

For example, they want to be able to handle requests for the string /foo/bar/baz.mp3 over the network. Quoting @mitra42:

Looking at that doc [How dat works by vtduncan], I'm struggling a bit with the route from a path.
dat://12334/foo/bar/baz.mp3 to the data.

It seems, if I read it correctly, that this requires all the files to
have previously been put into the metadata "file", so doesn't scale to
indefinite and changing groups of files, i.e. there doesn't appear to be
point (unlike in GUN for example) where the string /foo/bar/baz.mp3 is
sent from one peer to the other, for that peer to then figure out what
to send back.

Wondering if this is a use case that this WG think is interested to support directly in the protocol (e.g., file-aware transfers vs. only block transfers)?

Thanks,

[pfrazee]

Well let's see...

The wire protocol exchanges hypercore blocks, not files. As a result, peers don't explain what files they're trying to fetch when they communicate with each other. They only explain which data-chunks they want. That doesn't help.

One option might be to update the hyperdrive data structure so that it can have "placeholder" entries. These would be empty files with a "is_placeholder" flag set. A wire-protocol extension message could ask the owning peer to "hydrate" the file, in which case it would overwrite the placeholder entry with a real entry. Then replication could happen as usual.

Another option might be to leverage one-way mounts, once they're implemented. In that scenario, the owning peer would be sharding their file-set into a tree of dats. They would optimistically create and share the dats, but not populate them -- when a peer first connects, they would then populate the dats.

Let me step through the one-way mount solution. Let's say we have the following file tree:

/alice/fun/stuff
/alice/work/emails
/alice/work/backups
/bob/fun/games
/bob/fun/pics
/bob/work/
/carla/

The top level has three folders:

/alice
/bob
/carla

At initialization, a top-level dat would be created, and then 3 more dats: one for each folder. They would remain empty. The top-level dat would mount each of them.

# toplevel dat:
/alice -> dat://alice
/bob -> dat://bob
/carla -> dat://carla

# dat://alice
(empty)

# dat://bob
(empty)

# dat://carla
(empty)

All 4 dats are swarmed. Let's suppose a reading client wants to pull down the 'bob' folder. It would request a block from the 'bob' hyperdrive. When this happens, the owning peer would immediately mint 2 more dats, the 'bob-fun' dat and the 'bob-work' dat, and mount them to the bob dat:

# dat://bob
/fun -> dat://bob-fun
/work -> dat://bob-work

# dat://bob-fun
(empty)

# dat://bob-work
(empty)

These 2 new dats would then also be swarmed. This continues recursively. Basically, we're using entire dats as placeholders, and using the request of any block as a trigger to "hydrate" it.

The good news is that one-way mounts will not require additional hits to the DHT. The replication connection for the top-level dat can multiplex all of the child mounts, making this design relatively efficient over the network. It also would not require any unplanned changes to the protocol.

[martinheidegger]

This is now theory land: Another way to go about this would be more "lowlevel". Every DAT consists of 2 hypercores, metadata & content. What if it were to contain X hypercores? One per folder and one per file. The special hypercore dir/ will contain a list of operations.

For a file, it might contain an entry

{ "op": "add", "file": "Readme.md", "time":12312313, "hash": "YI8Qx5b/Tpbu5Hiw72RoSduT3qL3ZgYWZEMx5QwTPZ4=", "type": "file" }

... which means that for the latest version of the Readme.md you would need to ask the server for the hypercore file/YI8Qx5b/Tpbu5Hiw72RoSduT3qL3ZgYWZEMx5QwTPZ4= to receive the files.

For a folder, it might contain en entry:

{ "op": "add", "file": "css", "time":12312313, "hash": "85FydCC60+APHJsgWHJBOISXnITmtx9dwRUC4wi+pak=", "type": "dir" }

... which means that folder the history of this folder you would need to ask the server for the hypercore: dir/85FydCC60+APHJsgWHJBOISXnITmtx9dwRUC4wi+pak= which would contain the version history for this folder.

The server would need to lookup all files in a folder and just generate the hashes and upon request of a hypercore would start creating those hypercores (like a stream placeholder).

The crux of the issue, and the reason why the webarchive can not really do what they mean to is the problem that you can't quite know how big the entire archive is (something that is prominently displayed in DAT right now).

[pfrazee]

@martinheidegger Correct me if I'm wrong, but I think, for the most part, that's how my one-way-mounts solution works.

[martinheidegger]

@pfrazee It is similar, but on a lower level. Hyperdrive → Hypercore. Also it uses hashes instead of direct file lookups for deletions.

[pfrazee]

@martinheidegger What's the upside of introducing a different hypercore datastructure than hyperdrive? If you stick with hyperdrive, you avoid having to create a niche solution.

[martinheidegger]

Codename for this thing: hyperfs. If you build hyperfs, the way to lookup files will be vastly different from how it currently works in hyperdrive (pre multi-writer). You need to add some structure on top of hyperdrive to do that. It seems to me that having the hyperdrive structure (and overhead) doesn't give any benefit to this: What use is they metadata core if its always the same structure? (one node in metadata declares if its a file or directory, with the content stream only in use when its a file). As the linked DAT's mean that they could be theoretically by different owners, we need to create separate replication streams for all those DATs, If they are but "subcores" we can assume (guarantee?) that they have been generated with the same write key.

[mitra42]

Thanks for the thinking .. I'm hoping we can use this exercise as an example of how DAT might work with a large and changing site like the Archive. IMHO (and from prior experience with how the Web built on legacy Gopher and FTP data), how well a protocol gets adopted depends in part on how well it integrates with legacy data systems, and its great to be able ot use the Archive to test out some of these ideas.

I could be wrong, but I don't think either of those scenarios work for large data sets with an unknown (and changeable) set of items. For example, the obvious structure to me would be dat://// , in @martinheidegger 's suggestion this has two issues
a) one DAT at the top level, pointing at the others and one dat for each directory (what we call an ) - will fail because i) the files are added to all the time (approx once per second) and ii) There would be roughly 50million item ids to keep track of. and iii) practically we can't run any process ahead of time over all the ids.

Of course - we could do this in a different way - similar to how we work around IPFS's inherent weaknesses - where we created a DAT for each item the first time a user requested it, and then shared the address of the DAT out of band (via GUN or HTTP), but with that solution, Wort, Gun or WebTorrent are always going to work better than DAT.

[pfrazee]

@martinheidegger You're free to build any data structure you want on hypercore, but you're going to have to get that structure adopted widely if you want it solve the problem.

@mitra42 Sharding the dataset into multiple mounted dats is going to give you a couple benefits:

1. You can do just-in-time construction of each folder's dat, and avoid constructing dats which have no demand
2. You can retire & swap out a folder's dat if the folder's history ever gets too large (effectively garbage collecting the history)

Are you certain that sharding the dataset to one-dat-per-folder, and only updating folder-dats that have peers, is not enough for you to scale?

[okdistribute]

I wonder how we might use something like kappa-db/multifeed for this 'hyperfs' implementation.. any thoughts @noffle?

[martinheidegger]

@pfrazee That issue persists with both a hyperdrive and a hypercore solution. Pulling it one abstraction level higher doesn't make it quicker to be used.

@mitra42 I am seconding @pfrazee here: but I have some issues comprehending all you wrote (some formatting issues here). The only bottle-neck that I see with my example is that / can not be entirely cleared quickly (which is something worth considering to add). Since each directory/core only keeps track of is children any change operation would be influencing a disconnected part of the structure. Like IPFS I used a "hash" to specify the content hypercore, but this could also "just" be a random key to behave more like DAT does today (more direction of hyperdrive approach). The protocol of dat is built to be quicker and more efficiently than HTTP for larger files (lower overhead).

[okdistribute]

@pfrazee i disagree that it has to be adopted widely for the archive's case, because most of the peers would be served from the client side webrtc (watching the same video at the same time, for example)

[pfrazee]

@Karissa you're just losing wider ecosystem compatibility. If the situation really is niche, then you can do that, but I think you're losing some of the benefits of dat. In the case of cabal the custom data structure makes total sense, but in this case hyperdrive + the upcoming one-way-mounts feature has a good chance to solve the issue.

[okdistribute]

Yeah, this is why I was sort of hoping it could be something at the hypercore level -- being able to expose the filename (if known, optionally) in the request

[okdistribute]

or rather, any payload for extra request content needed

[pfrazee]

@Karissa You could probably do that via a wire-protocol extension message. It's got some extra overhead but if it was only turned on for dats doing this style of on-demand hydration, it's not super crazy. You'll just need the peers to support the extension.