In-Memory Rate Limiter allows twice as much requests when using default precision

[asafmor]

Hi,

I may be confused with the 'precision' but I don't get the expected results when I use the default precision.

When using default precision (i.e. precision = duration)

When I set a single rule for a limit of X requests per Y seconds, the rate limiter actually allows 2X requests per Y seconds to pass through. More interesting, it seems like this problem decays and disappears when we wait enough time or there are enough requests - i'm not sure.

When using precision = 1

When I use precision = 1, the results I get are much more what I'm looking for but it feels like a "fixed window" algorithm rather than a sliding one.
Also,

I've created a very simple test application for testing this issue and made a CSV output of the results.
I also made a scatter chart in Excel to visualize the problem very clearly.

You can download these Excel files from here:

Test 1: duration = 5 seconds, limit = 1, precision = 3 (default)
https://www.dropbox.com/s/llk479gbq5e3c4t/out1.xlsx?dl=0

Test 2: duration = 3 seconds, limit = 3, precision = 3 (default)
https://www.dropbox.com/s/yi88xd6e9zp9m46/out2.xlsx?dl=0

Test 3: duration = 3 seconds, limit = 3, precision = 1
https://www.dropbox.com/s/ag61g3osuteor9v/out3.xlsx?dl=0

Here is the test application code:

public class Application {

  private final static long TEST_DURATION_MILLIS = 120000;

  public static void main(String[] args) throws InterruptedException, IOException {
    Set<RequestLimitRule> rules = Collections
        .singleton(RequestLimitRule.of(Duration.ofSeconds(3), 3).withPrecision(1));
    RequestRateLimiter requestRateLimiter = new InMemorySlidingWindowRequestRateLimiter(rules);

    try (PrintWriter writer = new PrintWriter(new FileWriter("out.csv"))) {
      writer.write("timestamp,delta time,time from last 'under limit',under limit\r\n");

      long startTime = time();
      long currentTime = 0;
      long previousTime = time();
      long previousUnderLimitTime = time();
      while ((currentTime - startTime) < TEST_DURATION_MILLIS) {
        currentTime = time();
        Timestamp timestamp = new Timestamp(currentTime);

        boolean underLimit = !requestRateLimiter.overLimitWhenIncremented("x");

        writer.write(timestamp
            + ","
            + (currentTime - previousTime)
            + ","
            + (currentTime - previousUnderLimitTime)
            + ","
            + underLimit
            + "\r\n");

        if (underLimit) {
          previousUnderLimitTime = currentTime;
        }
        previousTime = currentTime;

        Thread.sleep(100);
      }
    }

  }

  private static long time() {
    return System.currentTimeMillis();
  }

}

And one more probably related question

Why when I set the 2 following rules I get only 2 requests under-limit per each 10 seconds (and not 4)?

RequestLimitRule.of(Duration.ofSeconds(10), 4).withPrecision(1)
RequestLimitRule.of(Duration.ofSeconds(2), 2).withPrecision(1)

Thank you very much!
Asaf

[mokies]

Hi @asafmor,

Apologies for the defect in the in-memory rate limiter. It seems the test suite was too simplistic to pick up the issue. The critical defect has been patched in v0.6.0 and is now available on maven central.

I've also made some changes to the precision API and documentation as it was previously rather confusing.

I will leave the issue open until I've had a chance two look at your last question.

[asafmor]

Thank you @mokies,
I've tested the fix the same way as above and now I get exactly the same plots but mirrored, so the problem is quite still there and even gets stronger as the time passes.