Futures-rs: FuturesUnordered can block the executor

[jonhoo]

The implementation of FuturesUnordered::poll_next never yields as long as at least one future inside of it is ready. This is problematic if it manages a sufficient number of futures that the time it takes to poll all the ready futures is larger than the time it takes between when any given future it manages becomes ready. FuturesUnordered::poll_next will then enter what is effectively an infinite loop, holding up the executor and starving other tasks in the system.

For a simple example of this, consider a FuturesUnordered that manages futures that run on retry timers. If polling all the ready futures takes longer than the retry time of any one future, then by the time it finishes polling all the futures, the first future it polled will be ready again since its retry timer expired.

The easiest way to fix this is to place a limit on how many calls to Future::poll a given call to FuturesUnordered::poll_next can make. If the limit is exceeded, yield by calling cx.waker().wake_by_ref() and return Poll::Pending.

It is not inherently an issue to yield Some many times in a row, so only counting the calls inside of poll_next should be sufficient. It _does_ place the burden on the caller to implement this kind of limiting themselves too though, so there is an argument for doing a "forced yield" every N calls to Future::poll, resetting the counter whenever we return Poll::Pending (but not when we return Poll::Ready(Some(_))). This would help other Future implementors that _wrap_ FuturesUnordered, since they will get the protection from accidentally blocking the executor by no yielding for too long "for free".

[jonhoo]

One other option, which may not be sufficient I'm not sure, is to do a "forced yield" if we detect that we are about to poll a future that _already_ returned Pending in this call to FuturesUnordered::poll_next (but has _become_ ready again since we first polled it). That would at least fix the retry timer case above, but I'm not sure it solves the more general case of poll_next potentially never yielding in degenerate cases.

[jonhoo]

This is related to #869 and #1957. I think the problem is particularly bad for FuturesUnordered though, because it manages potentially thousands of child futures, and so it runs into the issue _even_ if the underlying futures return Pending.

[cramertj]

I think the only real solution to this, as per @carllerche's comment in #2049, is to prevent leaf futures from surfacing an unbounded amount of work before yielding. I don't think it's reasonable or practical to have every future, stream, async fn etc. keep a counter around every loop to trigger a yield, especially when such loop counters stack exponentially and therefore become basically useless in a large chain of nested futures.

I'll leave this issue open for discussion, but I consider this "working as intended" from the futures-rs perspective.

[jonhoo]

Hmm, I may have phrased the above poorly. Preventing leaf futures from surfacing unbounded work (e.g., through a mechanism as proposed in https://github.com/tokio-rs/tokio/pull/2160), does help immensely, but there is one way in which FuturesUnordered it "special" — it will continue to poll futures _even after they return Pending_.

Consider a "perfect" implementation of the leaf-tracking scheme that @carllerche proposed (and that is partially implemented in https://github.com/tokio-rs/tokio/pull/2160), where after some number of polls, all leaf futures begin returning Poll::Pending. In order to do so, they _must_ wake the current task since nothing else will wake it. That is why the code for that kind of "volunteer yielding" looks like

if volunteer {
    cx.waker().wake_by_ref();
    return Poll::Pending
}

Now consider what happens if you have a FuturesUnordered in such a system. When FuturesUnordered::poll_next is called, it calls poll on any child futures that have been awoken. Imagine that those child futures all return Pending. Some of them because they genuinely aren't finished yet, and some because they are "volunteering" like above. Since they immediately wake themselves, they will immediately be added back onto the FuturesUnordered's run queue. Since FuturesUnordered::poll_next does not return Poll::Pending until the run queue is empty, it will poll all of those futures that volunteered a second time. They will volunteer again, and wake themselves. Leading to an infinite loop.

One option here is for FuturesUnordered to _also_ integrate with the "volunteering" mechanism offered by the executor (if it has one). If it did, then it would volunteer (and return) the moment any of its child futures volunteered, and all would be well. Since we don't yet have a "common" volunteering mechanism across the ecosystem though, there is no such thing for FuturesUnordered to integrate with. That means we have to have some (hopefully temporary) stand-in.

One option for that is what https://github.com/rust-lang/futures-rs/pull/2049 implements. Another is to keep a "generation" counter for each future, increment the generation on each poll_next, update the generation for a future whenever we poll it, and then yield if we are ever about to poll a future that we have already polled this generation.

[cramertj]

Ah, that makes a lot more sense to me, thanks for clarifying! It's still unfortunate in that multiple nested FuturesUnordereds will stack multiplicative-ly. However, that use case is certainly more rare and targeted than the "limit looping in literally every combinator" case, so I'm much more amenable to #2049. I've merged that PR, and I've opened #2053 to discuss more.