Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Inconsistent ordering in select APIs #2135

Open
betamos opened this issue Apr 23, 2020 · 5 comments · May be fixed by #2641
Open

Inconsistent ordering in select APIs #2135

betamos opened this issue Apr 23, 2020 · 5 comments · May be fixed by #2641
Labels
A-future Area: futures::future A-macro Area: macro related A-stream Area: futures::stream docs S-needs-api-design Status: Before implementing this, a discussion or decision on the new API is needed. S-needs-decision Status: A decision on whether or not to do this is needed.
Milestone
futures-0.4, futu...

Comments

@betamos
Copy link

betamos commented Apr 23, 2020

Selecting over >=2 futures has subtle fairness issues when more than one future is ready. The current offering has a few inconsistencies in docs and naming:

  1. futures::select!: pseudo-random, documented
  2. futures::select_biased!: in-order, documented
  3. futures::future::{select, try_select, select_ok}: in-order, undocumented
  4. futures::future::select_all: in-order, documented that one should not rely on order
  5. futures::stream::select: round-robin, documented
  6. futures::stream::select_all: (based on FuturesUnordered - not sure), undocumented

Golang uses random order for select to prevent starvation, which is a hard-to-detect and problematic pitfall. IMO, any select API with a starvation risk should be explicitly documented as such. Even "don't rely on order" is too benign of a statement.

For user-facing behavior, I'd divide the behavior of the current offering into three classes:

  • Order specified in the API. (2)
  • Order not specified, but has mitigations against starvation. (1, 5, 6?)
  • Order not specified, but can cause starvation. (3, 4)
    • Ideally I'd suggest eliminating this class entirely in favor of either of the other two

Initially, adding coverage of these behaviors to the existing API docstrings would be nice. Happy to create a PR upon endorsement from a maintainer.

Regarding naming, I like the precedent set by the macros: select! is starvation-protected by default, and select_biased! has explicit ordering. Following the principle of least surprise, ideally that convention could be applied to the other APIs as well. Now, going down this road would introduce breaking changes. Maybe a maintainer can chime in?
@Nemo157
Copy link
Member

Nemo157 commented May 14, 2020 •
edited

From my reading of SelectAll and FuturesUnordered I believe it will guarantee a form of round-robin. Namely that the streams will be polled round-robin if they are always ready, but a stream that is not ready will be skipped, and added to the end of the round-robin queue when it next wakes. This playground agrees with my base case that always ready streams will be polled round-robin, and this playground seems to agree that there's no starvation.

I think it would be good to add a guarantee around this to the documentation and tests that ensure it will not result in starvation when a stream is always ready.

This was referenced May 14, 2020
Open
Open
@taiki-e taiki-e added A-future Area: futures::future A-macro Area: macro related A-stream Area: futures::stream and removed futures-util labels Dec 17, 2020
@taiki-e taiki-e added this to the futures-0.4, futures-core-1.0 milestone Feb 26, 2021
@Xaeroxe
Copy link
Contributor

Xaeroxe commented Mar 14, 2022

This is a pretty major footgun and had me and my coworker confused for several days about why we were getting inconsistent behavior in our code. I think it's important to get this situation sorted out.

Xaeroxe added a commit to Xaeroxe/futures-rs that referenced this issue Sep 7, 2022
@Xaeroxe
Add fairness to futures_util::{select, try_select, select_ok}, fixes r…
5824a90 
…ust-lang#2135
Xaeroxe added a commit to Xaeroxe/futures-rs that referenced this issue Sep 7, 2022
@Xaeroxe
Add fairness to futures_util::{select, try_select, select_ok}, fixes r…
9d85633 
…ust-lang#2135
@Xaeroxe Xaeroxe linked a pull request Sep 7, 2022 that will close this issue
Open
Xaeroxe added a commit to Xaeroxe/futures-rs that referenced this issue Sep 7, 2022
@Xaeroxe
Add fairness to futures_util::{select, try_select, select_ok}, fixes r…
984689e 
…ust-lang#2135
Xaeroxe added a commit to Xaeroxe/futures-rs that referenced this issue Sep 7, 2022
@Xaeroxe
Add fairness to futures_util::{select, try_select, select_ok}, fixes r…
ceb1595 
…ust-lang#2135
@Demindiro
Copy link

IMO select! should be renamed to select_random! to emphasize that the ordering is random.

I too spent a few days figuring out why my tests weren't reproducible until I read the documentation of select! carefully.

Xaeroxe added a commit to Xaeroxe/futures-rs that referenced this issue May 14, 2023
@Xaeroxe
Add fairness to futures_util::{select, try_select, select_ok}, fixes r…
97b4218 
…ust-lang#2135
@taiki-e taiki-e added S-needs-api-design Status: Before implementing this, a discussion or decision on the new API is needed. S-needs-decision Status: A decision on whether or not to do this is needed. docs labels Jul 19, 2023
@taiki-e taiki-e mentioned this issue Jul 20, 2023
Closed
Xaeroxe added a commit to Xaeroxe/futures-rs that referenced this issue Aug 14, 2023
@Xaeroxe
Add fairness to futures_util::{select, try_select, select_ok}, fixes r…
1be1a61 
…ust-lang#2135
@Xaeroxe
Copy link
Contributor

Xaeroxe commented Aug 17, 2023 •
edited

@Demindiro Hey so I realized my comment wasn't clear and we were actually saying the exact opposite things. I want the behavior to be random by default, with bias being opt-in behavior. I was confused because bias was present, and in your case you were confused because the selection strategy was fair. That happened because we were using different APIs.

Can you tell me more about how random selection caused a problem for you? Was starvation of the later futures desirable?

@Demindiro
Copy link

Demindiro commented Aug 17, 2023 •
edited

Can you tell me more about how random selection caused a problem for you? Was starvation of the later futures desirable?

In my case it made a specific test hard to reproduce, as the order and amount of tests run influenced the behavior of that test.

Starvation is not an issue for my usecase.

Xaeroxe added a commit to Xaeroxe/futures-rs that referenced this issue Apr 29, 2024
@Xaeroxe
Add fairness to futures_util::{select, try_select, select_ok}, fixes r…
ce5eaa3 
…ust-lang#2135
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-future Area: futures::future A-macro Area: macro related A-stream Area: futures::stream docs S-needs-api-design Status: Before implementing this, a discussion or decision on the new API is needed. S-needs-decision Status: A decision on whether or not to do this is needed.
Projects
None yet
Milestone
futures-0.4, futures-core-1.0
Development

Successfully merging a pull request may close this issue.

Add fairness to futures_util::{select, try_select, select_ok} Xaeroxe/futures-rs
5 participants
@Nemo157 @betamos @Xaeroxe @Demindiro @taiki-e