Allow for bounding of pending acquisitions?

[jamesmunns]

Hey there!

I'm planning to use leaky-bucket for a reverse proxy rate limiter, and one feature that I would be interested in is to bound the number of waiters to return-early at the acquire stage.

For example, if the number of tokens is 3, the refill interval is 100ms, and the waiter-bound is 5, then we would get a behavior like this if 10 requests arrived at the same time:

• Req 0: Gets token immediately
• Req 1: Gets token immediately
• Req 2: Gets token immediately
• Req 3: Gets token after 100ms
• Req 4: Gets token after 200ms
• Req 5: Gets token after 300ms
• Req 6: Gets token after 400ms
• Req 7: Gets token after 500ms
• Req 8: Gets Err immediately
• Req 9: Gets Err immediately

Right now I can emulate this by adding a timeout of ~600ms to acquire_one, but that means that the tasks for Req 8 and Req 9 will sleep for 600ms, and only error out then, when it could be possible to "know" that there are already too many pending waiters.

Is this something you'd be interested in supporting, and if so, do you have any suggestions on how to implement it?

Thanks!

[udoprog]

It's doable, but we'd have to change the internal architecture.

Rather than bounding on the number of waiters though it would at least to me make more sense to bound on the number of pending tokens. Uses outside of acquiring one token are typically intended to indicate that a task has more "weight" than another, and if you really want to limit the number of waiters then each task would simply specify that it wants one token.

In practice this means that the state of the rate limiter would also have to store the number of pending tokens. I suppose the easiest way to achieve this might be to convert the balance into an isize rather than an usize where negative values means that there are tokens "in debt" for pending waiters. Acquiring tasks that obeys the token bound would then have to look at this balance to decide whether or not to wait.

Another thing I would have to think hard about is whether narrowing the max supported balance to support this change is a breaking change or not. Making the balance a signed value would half its range (one bit is used to determine whether the core task is held).

[jamesmunns]

Rather than bounding on the number of waiters though it would at least to me make more sense to bound on the number of pending tokens.

Ah, that makes sense to me! I am mapping "one waiter = one token", but I agree "max pending tokens" is generally reasonable.

Regarding breaking changes: I would say that it is likely this would require a breaking change, as acquire operations need to become failable, either at the non-blocking acquire call, or having the future return Result<()> instead of ().

Would it make sense to have a separate BoundedRateLimiter then instead, which acts in the way you proposed?

[udoprog]

My expectation was that if the internals were changed to support this, then you could have functions which do yield by a pending token limit that are fallible, and the existing suit of functions just ignores them. So the added functions could be:

impl RateLimiter {
    fn acquire_bounded(&self) -> AcquireBounded<'_>;

    fn try_acquire_bounded(&self) -> Result<(), TryAcquireBoundedError>;
}

pub struct AcquireBounded<'a> {
     /* .. */
}

impl<'a> Future for AcquireBounded<'a> {
    type Output = Result<(), AcquireBoundedError>;
}

It depends a bit on whether you think the ability to "bypass" the configured bound is a feature or a bug that should be avoided on the type level (with a BoundedRateLimiter).

[jamesmunns]

@udoprog if you are asking for my opinion, I'd probably prefer a separate type, in order to avoid confusion when bounding does/doesn't apply! However you know your library best, and I'm open to either approach, so take it only as a weak opinion.