Thoughts on the next level of content routing for ipfs

[whyrusleeping]

Currently ipfs uses a DHT for all content routing. This works quite well for
many use cases and is generally reliable, fast, and durable. The problem we are
now facing is that it does not scale well. Sending out provider records for
every single block of every file to the DHT uses an obscene amount of
bandwidth, not to mention the increased CPU and memory load. To continue
improving ipfs, we need to find a better solution.

Delegated routing

The idea of delegated routing is fairly simple. Select another node in the
network to perform all of your content routing for you. This is a good
solution, but it assumes a few things: There are other nodes in the network
willing to do this for you, you trust those nodes, and you can reach those
nodes. This sort of routing is going to be just about required for mobile
applications of ipfs.

Advantages

If you have a low latency connection to your selected delegate, and the
delegate is well connected in the network, routing queries should complete
very fast. From the users perspective, all that is involved is a single RPC
between them and the delegate. The resources required here are very minimal.

Another nice feature is that if a single delegate is shared across multiple
clients, results could be cached to further reduce the resource usage.

Disadvantages

In order for this to work, you have to have a node on the network willing to be
your delegate. This means that you either have to control your own node out in
the wild, or convince someone else to let you use theirs. This isn't always
easy, especially for the casual or mobile users. One solution here is to allow
the ipfs gateway nodes to be open routing delegates, but that may end up
putting an extreme level of stress on the gateways and also makes the whole
system just a bit more centralized (which happens to be something we're opposed
to).

Trackers

The idea of trackers is quite similar to delegated routing. The primary
difference here is that while the idea of delegated routing is agnostic to
how the routing is performed, the intention was still that the delegates were
DHT nodes on the main network. Using the idea of trackers would mean that the
delegate just stores all routing information it deals with locally. This is
what bittorrent uses (in addition to Mainline DHT).

Advantages

Compared to delegated routing in general, the only main advantage is that all
routing queries will be resolved by the tracker, and not require extra work in
the background to find the data. This, in an ideal world, is the fastest
content routing system.

Disadvantages

Trackers have a limited knowledge of what all is available in the network. To
find content using a tracker, other users who have the content you want must
also be using that tracker. Trackers also don't scale well to larger scale
systems, too much load on a single point of failure.

Hybrid Delegates

The idea of a 'hybrid' delegate system is something i've been thinking of for a
little while now. The basic concept is to use multiple delegates, as well as
falling back to the dht in certain cases. First, nodes can mark themselves as
'supernodes' and announce through some medium that they are willing to fulfill
routing queries. Other peers can discover these through some mechanism, mdns,
the dht, a preconfigured list, or randomly discover them when connecting for
other purposes. Once discovered, if a node is configured to use this system,
they can select the 'best' set of discovered supernodes to use and send all
routing queries to those nodes. Depending on how much you trust each of those
nodes you can select more or less of them to query and optionally fall back to
making DHT queries. You should also be able to mark certain supernodes as
trusted in your configuration so you remember them and can use 'just them' to
fullfil queries.

This idea is really a few different things mashed together. Tiered routing, the
ability to query multiple content routing providers intelligently, Delegated
routing as discussed above, and integrated ways to discover these delegates.

One scenario i'm imagining with this system is that you could run a 'supernode'
on your LAN or in your datacenter for all the other ipfs nodes around you to
automatically discover (via MDNS) and use.

TODO: make this section more coherent.

Other things that could help

Batched Providing

Currently, the content routing interface only allows for a single object to be
provided or have providers looked up for at a time. Changing this interface to
allow multiple requests to be batched together should improve resource
consumption significantly.

Multicast

The DHT sends the same message to a large number of different peers throughout
the network, requiring it to form individaul connections to each of them and
send out the message many times. If a multicast system were to be implemented
in libp2p, it could be used to reduce the outgoing bandwidth required by the
DHT.

[slothbag]

I'm writing these thoughts here from a very naive point of view, I don't have a deep understanding of the libp2p protocol, and you guys have obviously thought a lot more about this than me.

One problem I have concluded with the current libp2p/ipfs stack is that peer connections are long lived, they stay connected for a long time, I assume to facilitate some bitswap session of sorts, but the protocol also expects every peer to have direct access to a peer who has the content. This makes it impossible to limit the connections because others cant connect.

If your going to have long lived connections then the peers need to relay the blocks between each other to cater for peers that are unreachable by others.

My preference would be for short lived connections, < a second or two, that way a single node could service hundreds of thousands of requests and always be accessible. But obviously bitswap accounting gets more tricky.

In your notes you also mention the DHT struggling to keep up with block provider records? Would it not be possible to use summarised provider records? i.e instead of sending 1000 records for a 500MB file you just send the one provider record indicating you have the whole file? Then during a session if the provider dissappears or lied he gets flagged as such and we move onto the next provider.

If you have any more notes that already cover all these questions i'm happy to be pointed in that direction :)

[whyrusleeping]

If your going to have long lived connections then the peers need to relay the blocks between each other to cater for peers that are unreachable by others.

Yeah, we're working on getting relays implemented and setup, but its tricky. You'll be essentially donating your bandwidth to other peers, which could get weird.

Would it not be possible to use summarised provider

The problem here is that you still want to have random access to the subblocks. This is the hard part. If i want hash QmCCC that is a sub-block of QmAAA, and I don't know that QmCCC is a subblock of QmAAA, i won't be able to find it because i don't know to ask for QmAAA. One thing that would help here is a way to do backlinks, but that gets really expensive and complex as well (and ends up not really solving the problem). What would be interesting would be to have an efficient way to do backlinks, or some other way to do random access into subgraphs without explicitly announcing everything.

[mildred]

An idea would be to add an indirection level and split the merkle-dag into limited trees that could be considered as a single unit. A record in the DHT would contain the list of all the peers interested in any node from that tree. This record would be the logical root of the tree. When a peer wants to access a block knowing it is below that record, it would fetch the record and use a separate, smaller DHT that is only shared between the nodes interested in that limited merkle-tree.

Advantages: The main DHT is smaller and consumes less bandwidth because individual blocks are not referenced in it. When connecting to a sub-DHT, your peer is closer to other peers interested in closest data you are probably interested in. This leverages the principle of data locality.

Disadvantages: Not all blocks are accessible directly, you must first know the record identifier.

Variant to still reference all the individual blocks in the main DHT: Instead of associating the block id with the list of peers that can provide this (dynamic information that is subject to frequent changes, this more bandwidth), the main DHT only makes an association from the block id to the record id tracking the tree the block is included in. This information is much more static, or barely changes at all, and will require less bandwidth to keep up to date.

Disadvantages: An extra level of indirection.

[whyrusleeping]

@mildred Thanks for the input!

I do really like the idea of essentially 'sharding' the dht. One hard part here is deciding how these record groups are formed. Ideally this would be a deterministic process so that it would not require any consensus or messaging to other peers for discovery.

Your second proposal is essentially something we've discussed in the past and called "Backlinks", that discussion was about using the dht to store which hashes are children of which other hashes. Our conclusion there was essentially that the scaling here actually tends to be either exactly the same, or worse in terms of messaging complexity due to the cost of having to announce blocks into each of the 'groups' they might be in.

I'll have to put more thought into dht subgroup formation. Perhaps theres something cool here involving probabilistic sets... (maybe treat the whole network as a bloom filter somehow?)

[zeta0134]

Here's a stray thought: instead of sharding based on parent / child relationships between nodes, why not shard based on the hash itself? Would it be feasible to subdivide the DHT networks by a hash prefix? Say, in an extremely simplified example, an IPFS node elects to route for hashes beginning with 'Q' and only announces itself as a provider to other nodes that are interested in that prefix? I feel like basing it on the hash of the data itself makes it deterministic, and would naturally result in a fairly balanced distribution of resources, but I dunno.

When I proposed this idea to a friend, he suggested that this approach may weaken the network overall, and make it susceptible to Sybil attacks, but I feel like that's true of any sharding scheme. There will need to be a balance between redundancy and performance.

[whyrusleeping]

Hrm... I don't know if that would save too much bandwidth. A large put of many different hashes ( from adding a large file) would end up having to interact with pretty much every shard.

…

On Mon, May 29, 2017, 20:31 zeta0134 ***@***.***> wrote: Here's a stray thought: instead of sharding based on parent / child relationships between nodes, why not shard based on the hash itself? Would it be feasible to subdivide the DHT networks by a hash prefix? Say, in an extremely simplified example, an IPFS node elects to route for hashes beginning with 'Q' and only announces itself as a provider to other nodes that are interested in that prefix? I feel like basing it on the hash of the data itself makes it deterministic, and would naturally result in a fairly balanced distribution of resources, but I dunno. When I proposed this idea to a friend, he suggested that this approach may weaken the network overall, and make it susceptible to Sybil attacks, but I feel like that's true of any sharding scheme. There will need to be a balance between redundancy and performance. — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#162 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABL4HIHuZUGhnA-1S1ELhiABvOSsFC5qks5r-414gaJpZM4JuixA> .

[tolikzinovyev]

Hi. I’m new here and might misunderstand something. Would this kind of summarized provider records work?

The idea is, if a node has a whole sub-tree, it makes sense to only publish a provider record for that sub-tree to DHT, without publishing individual nodes in it.

Let’s say we have a file represented by the DAG

        A
    /   |   \
  B     C     D
/ | \ / | \ /
E F G H I J K

A publisher of the file only publishes A (the list of links to B,C,D) and the fact that it has the whole tree.

A node that wants to download the file finds the record of A and nodes that have the whole file. It can start downloading directly from them, but to avoid bottlenecks when a file has just been published, it traverses the tree and prioritizes downloads from nodes that have smallest individual parts. Once it has E, it publishes a provider record for E. Same goes for F. Once it also has G, it publishes a provider record that says it has the whole sub-tree B and never again publishes records for E, F or G. And so on.

Thus, nodes that have the whole file send out one provider record (or two). A node that starts up and that has only downloaded a file partially, typically publishes C*log(filesize) records.

At the same time, a node can start downloading a file only after one DHT request. The speed might be slow because of the bottleneck mentioned above, but it could do a simultaneous download of the same blob from nodes discovered through the tree traversal. (download blob E from node1 from left to right, blob E from node2 from right to left, blob E from node3 starting in the middle and going in both directions and so on).

As for the disadvantages, it is not possible to access an individual block without knowing its ancestor. So, an address to E would probably look like “hashof(A)/hashof(B)/hashof(E)”, or even “hashof(A)/hashof(B)/hashof(E);hashof(X)/hashof(Y)/hashof(E)” if E is part of two files. If someone decides that E is an important piece on its own though, he can pin E separately and that would maintain a provider record for E in the DHT.

Another drawback is that if an address for an individual object is given in the form of “hashof(A)/hashof(B)/hashof(E)”, a node might need to send lengthof(“hashof(A)/hashof(B)/hashof(E)”) requests to the DHT, which is C*log(filesize). It is still a good compromise.

Thank you for reading.

[whyrusleeping]

@aszinovyev summarized provider records arent a bad idea, and it might be something we move forward with, but the drawback is that you lose out on random access. If most nodes only say they provide A, but some node is trying to find B directly, and doesnt know that B is a child of A, it will be very difficult for them to figure out who to ask for data.

I think that this compromise is probably okay on a per file basis, where you can announce the roots of each file and say you have the entire thing, since requesting sub-pieces of files without the context of the root may be a very small usecase (though i really don't know how true that is)

[ingokeck]

Stupid question maybe, did you have a look at the work done on the topic around Gnutella, for example http://rfc-gnutella.sourceforge.net/src/qrp.html ? I know DHT was developed to avoid the problems of the gnutella routing, but maybe it is good to look back. Delegation, sharding and routing search data for others seems to be the only way how to solve this problem in my opinion.

[whyrusleeping]

@ingokeck thanks for the link! I'll read into it and report back.