Skip to content

Draft: StreamMap: add and use an internal priority queue

Jim Newsome requested to merge jnewsome/arti:peekable-streams into main

Previously, fair usage of hop resources over streams was implemented by pulling a message from every stream that had one ready, if we had the resources (send window capacity) to send any of them. Afterwards, any that couldn't be sent immediately were queued on the reactor's hop's outgoing queue.

This was a bit fragile, and in particular would be difficult to make work well in conjunction with prop340 (packing and fragmentation). e.g. in the previous model:

  • If any stream wanted to send a message that required a relatively large send window (e.g. a large DATAGRAM), it would necessarily block all streams.
  • When looking for data to opportunistically pack into an outgoing cell, we would have only been able to consider the set of DATA messages that had been extracted from the previous or current "round" of processing but that we weren't able to send yet. In many common cases (e.g. a circuit with a single stream that never fully runs out of send windows), we would be able to do little or no such packing.

Here, we:

  • Make stream receiver's "peekable"
  • Update the reactor to peek at each stream being processed, and if an event can't be handled immediately (e.g. because there is unsufficient outgoing send window), leave it in the stream instead of pushing it to a hop-wide queue.
  • Note that the previous change by itself could starve some streams if we keep running out of hop-level send window before processing all
  • We address this by adding and using a persistent priority queue to StreamMap. This allows processing to resume at the stream where we left off when we obtain more hop-level send window.
Edited by Jim Newsome

Merge request reports