Request acknowledgement (especially Kademlia)

[nazar-pc]

We have a challenge with provider announcements in Kademlia. When requests come in, we basically have to process them right away, there doesn't seem to be any way to tell library that request needs more time to be processed.

Specifically, we need to manage enormous number of announcements and we use disk-based storage, which means no guarantee on how much time it takes to write to disk, so we need to do that in a separate thread. Moreover, we do other time consuming things in addition to that. What this means is that when we get a storm of announcements there is no way for us to tell announcer to wait a little while we're processing previous announcements.

As the result we have a bounded queue that fills up quickly and after that we just ignore majority of announcements simply to avoid running out of memory, which is not ideal because we can't discover the content later due to announcements not being stored.

#3035 is kind of sort of related. While it talks about errors, it was already mentioned by @mxinden that we would likely also want to make those async. I'm wondering if the issue described here is covered by the same task or more tickets need to be created.

This is the next major issue for Subspace and I'm willing to dedicate time implementing/fixing it given some guidance on how to approach it.

[thomaseizinger]

Effectively, what you are asking for is back-pressure, ideally on newly opened streams all the way to the other the peer. See #3078.

There are a lot of moving parts here but I'll try to summarize:

• Our StreamMuxer interface can in theory already do back-pressure: The poll_inbound interface allows us to not accept new inbound streams if we cannot handle them at the moment.
• Kademlia states in its spec that streams can be reused. This should probably go away such that we can piggy back on the back-pressure of new inbound streams: Not being able to handle any more inbound streams will automatically mean that we cannot handle any more inbound kademlia requests.
• The ConnectionHandler interface currently has no ability to signal whether it can handle more streams. It is simply given streams as they come available. This is one of the holes in our back-pressure chain.
• One issue in solving the above is that we need to accept a stream from the remote and run multistream-select on it before we even know which ConnectionHandler to ask whether it can handle more streams.

[thomaseizinger]

The message passing way of solving this would be to introduce a message from the NetworkBehaviour to the ConnectionHandler once a provider is added. The ConnectionHandler could then wait with reading further messages from a stream until it has received this confirmation.

[nazar-pc]

I'd really prefer to not maintain a fork, especially long-term, and rather improve upstream. But I may go that route in the meantime since it sound reasonably straightforward and not too bad to maintain.

The message passing way of solving this would be to introduce a message from the NetworkBehaviour to the ConnectionHandler once a provider is added. The ConnectionHandler could then wait with reading further messages from a stream until it has received this confirmation.

This feels like a more idiomatic solution in rust-libp2p.

[thomaseizinger]

I'd really prefer to not maintain a fork, especially long-term, and rather improve upstream. But I may go that route in the meantime since it sound reasonably straightforward and not too bad to maintain.

I can't promise that we'd accept it upstream but I also wouldn't rule it out, esp. if it turns out significantly simpler and allows to easily backpressure individual streams / connections.

The message passing way of solving this would be to introduce a message from the NetworkBehaviour to the ConnectionHandler once a provider is added. The ConnectionHandler could then wait with reading further messages from a stream until it has received this confirmation.

This feels like a more idiomatic solution in rust-libp2p.

It has definitely historically been the way things get implemented in here (with reason). That doesn't mean we shouldn't experiment with other designs.

[nazar-pc]

Okay, I'll experiment with it and let you know if I have something meaningful to share.
Thanks for suggestions!

[thomaseizinger]

Another idea just came to my mind:

• Use Arc<Mutex<RecordStore>> in ConnectionHandler
• RecordStore interface is not async but has poll functions:
  • RecordStore::poll_ready_add_provider
  • RecordStore::add_provider

This would allow us to use a regular std::sync::Mutex because the lock times would be extremely short:

1. Lock Mutex
2. Call poll
3. If ready, add provider
4. If pending, return pending (i.e. suspend ConnectionHandler)

Predictable lock times and not holding locks across await points make it much less likely that we run into deadlocks which makes the use of a Mutex less bad.

[mxinden]

Sorry for only commenting here now. Difficult topic. Thanks for the elaborate discussion. A couple of thoughts. I will discuss this more synchronously with @thomaseizinger tomorrow.

• I don't think reusing streams is the way to go. Kademlia requests are small. They will most likely not saturate a stream receive window, thus no backpressure. Reusing streams implies head-of-line blocking.
• Async or poll style RecordStore sounds reasonable.
• Arc<Mutex<RecordStore>> I would prefer RecordStore only, having the implementer of RecordStore decide whether they use a Mutex or something else under the hood.
• We should rely on stream-creation backpressure of the underlying Muxer implementation. For libp2p-quic that should give us a concurrency limit of 100, i.e. at most 100 Kademlia requests in-flight at any given point in time. As long as libp2p-kad does not drop an inbound stream (e.g. waiting for RecordStore) libp2p-quic does not allow the remote node a new stream and thus the remote producer (libp2p-kad) is backpressured.
• While ideally we would have a backpressure mechanism for ConnectionHandler to deny new streams, this is tricky. As mentioned above, at first we don't know what protocol a new incoming stream is for, as multistream-select hasn't yet run.