Backpressure in Kademlia

[mxinden]

See https://github.com/libp2p/rust-libp2p/issues/3078 for tracking issue on backpressure in rust-libp2p in general.

Terminology

• Query and request

  https://github.com/libp2p/rust-libp2p/blob/75f967f4da2bb023d8ad2594e63dd887672151cc/protocols/kad/src/behaviour.rs#L2493-L2495

Backpressure

• User -> Kademlia NetworkBehaviour
  • No backpressure on any of the query methods, e.g. Kademlia::get_closest_peers today. https://github.com/libp2p/rust-libp2p/blob/75f967f4da2bb023d8ad2594e63dd887672151cc/protocols/kad/src/behaviour.rs#L656-L660
  • Kademlia has no way to signal to the user that it is not yet ready to accept a new query.
  • Could change the method signature to a futures::Sink style signature with poll_get_closest_peers_ready and a get_closest_peers.
  • Kademlia needs some criteria to decide when to return Poll::Pending in poll_get_closest_peers_ready.
  • Ideally no magic maximum of concurrent queries, but instead dynamic limit, e.g. based on capacity to ConnectionHandlers, or only accept new queries in case existing ones can not make progress.
• Kademlia -> ConnectionHandler
  • Mechansim through ToSwarm::GenerateEvent does not enforce backpressure (yet).
  • Create an futures::channel::mpsc::channel between behaviour and handler at handler creation time.
  • Give query engines access to the channels to each handler, thus being able to make informed decisions where to send which request to.
  • On the handler side, use a new stream per request, have at most one OutboundStreamRequest in-flight, read from the channel from the NetworkBehaviour only on ConnectionEvent::FullyNegotiatedOutbound.
• local ConnectionHandler to remote ConnectionHandler
  • Backpressure through muxers stream creation backpressure mechanism (exists in QUIC, tracked in https://github.com/libp2p/rust-yamux/issues/150 for yamux)

[thomaseizinger]

Removing decision-pending because I think we agree that there should be backpressure. It is still open on how to solve that.

[sirandreww-starkware]

Is this up to date?