Backpressure in Kademlia

[mxinden]

See #3078 for tracking issue on backpressure in rust-libp2p in general.

Terminology

• Query and request

  rust-libp2p/protocols/kad/src/behaviour.rs

  Lines 2493 to 2495 in 75f967f

  	// Note on the difference between 'request' and 'query': A request is a
  	// single request-response style exchange with a single remote peer. A query
  	// is made of multiple requests across multiple remote peers.

Backpressure

• User -> Kademlia NetworkBehaviour
  • No backpressure on any of the query methods, e.g. Kademlia::get_closest_peers today.
    

    rust-libp2p/protocols/kad/src/behaviour.rs

    Lines 656 to 660 in 75f967f

    	/// Initiates an iterative query for the closest peers to the given key.
    	///
    	/// The result of the query is delivered in a
    	/// [`KademliaEvent::OutboundQueryCompleted{QueryResult::GetClosestPeers}`].
    	pub fn get_closest_peers<K>(&mut self, key: K) -> QueryId

  • 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 Track the accept backlog and add an upper limit rust-yamux#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.