ocaml-h2 icon indicating copy to clipboard operation
ocaml-h2 copied to clipboard

Scheduling algorithm starves streams

Open quernd opened this issue 4 years ago • 0 comments

The recent question about gRPC on Discord reminded me that I still hadn't reported this issue I've encountered with scheduling.

We have a gRPC use case with many streams over a single connection and the scheduler starves some streams. I know it’s not your algorithm, but my intuition is there is a flaw in the scheduling algorithm. The issue is that the scheduler allocates "quota to send data" based on how much data a given stream already sent, so that streams that send a lot have to wait for other streams to "catch up" before they get a chance to send more data.

Here's a basic reproduction, using just two streaming requests in parallel (expected and actual output at the end). The second request starts a few seconds after the first and causes the first stream to queue up because it doesn't get a chance to send. It's even more dramatic if you replace "FOO" by "FOOO" (simulating a faster stream), it spirals into longer and longer queues.

https://github.com/dialohq/ocaml-h2/blob/two-streams/examples/lwt/two_streams.ml

Our workaround for this is to use simple round-robin scheduling to alternate between parallel streams, not taking their throughput into account. This works well in our use case (we don't use advanced features like stream priority), but it's not entirely satisfactory. Here's the changes: https://github.com/dialohq/ocaml-h2/compare/fa0c8a4...1800282

quernd avatar Mar 13 '22 08:03 quernd