Unexpected Behaviour for Batched Cells

[BenD0G]

Hello,

I'm looking for a crate to implement HTTP rate limiting (similar to #39 (comment) I believe), in particular rules of the form "Cannot send more than X requests per Y units of time."

From my dabbling it looks like this crate isn't the one for me (it seems more focused on cells replenishing at a constant rate than on limiting with a time window - would love to hear if you know of a way to implement that behaviour using this crate???).

Anyway, as part of my testing I came across some unexpected behaviour, so I made a test to demonstrate it below, and thought I'd share 😄

Would be very happy to hear your thoughts, but regardless keep up the great work!

use std::num::NonZeroU32;
use std::time::Duration;

use governor::clock::Clock;
use governor::NegativeMultiDecision;

/// When you send cells in bursts (as is the case for weighted API calls), you seem able
/// to fire more cells than you might expect.
///
/// In this test, cells replenish at a rate of 1200 / minute, but we're mostly sending them in bursts of 5.
/// `one_unit` is the time taken for 5 cells to replenish.
///
/// We use up capacity at the start, then elapse 2 units of time, and we're somehow able to fire 1.2 units,
/// instead of the expected 1.0.
#[test]
fn demonstrate_extra_capacity() {
    let one_minute: u64 = Duration::from_secs(60).as_nanos().try_into().unwrap();
    let one_unit = one_minute / 1200 * 5;

    let clock = governor::clock::FakeRelativeClock::default();
    let quota = governor::Quota::per_minute(NonZeroU32::new(1200).unwrap())
        .allow_burst(NonZeroU32::new(5).unwrap());
    let rate_limiter = governor::RateLimiter::direct_with_clock(quota, &clock);

    // We can fire five out straight away.
    assert!(rate_limiter.check_n(NonZeroU32::new(5).unwrap()).is_ok());

    // Check that we can't fire another 5 again before a unit has passed
    clock.advance(Duration::from_nanos(one_unit - 1));
    assert!(rate_limiter.check_n(NonZeroU32::new(5).unwrap()).is_err());

    // Advance one more nanosecond - now we have replenished one unit so can fire
    clock.advance(Duration::from_nanos(1));
    assert!(rate_limiter.check_n(NonZeroU32::new(5).unwrap()).is_ok());

    // Now that we've fired, back to not having any capacity - we can't even fire 1 cell.
    // We would need to wait for a fifth of a unit to pass
    let res = rate_limiter.check_n(NonZeroU32::new(1).unwrap());
    match res.err().unwrap() {
        NegativeMultiDecision::BatchNonConforming(num, until) => {
            assert_eq!(num, 1);
            assert_eq!(
                until.earliest_possible().as_u64() - clock.now().as_u64(),
                one_unit / 5
            );
        }
        _ => panic!(),
    }

    // Now the interesting bit: we advance two units of time.
    clock.advance(Duration::from_nanos(2 * one_unit));

    // We can fire one unit (our maximum burst) just fine
    assert!(rate_limiter.check_n(NonZeroU32::new(5).unwrap()).is_ok());

    // BUT we now have some magical extra capacity to fire one cell???
    assert!(rate_limiter.check_n(NonZeroU32::new(1).unwrap()).is_ok());

    // Not another one though.
    assert!(rate_limiter.check_n(NonZeroU32::new(1).unwrap()).is_err());
}