RateLimiter with 1 permitsPerSecond does not appear to work properly

[David Hoffer]

I've used RateLimiter before with good success but this time I'm running into a problem. I'm using it to limit my calls to an external API to a max of 1 per second so I created a RateLimiter with 1.0 permitsPerSecond. Then I call acquire right before I call the external API that I need to limit my use of.

The problem is the external API says I am still calling the API more than once per second.  So to see if they are right I added some logging that checks to see if the delta between the current call and the last one is less than 1000 ms and sure enough it is.  So it seems this proves the bug is with RateLimiter and not the external API.

My use case is that I create the single RateLimiter instance in a static context and that instance is passed to all callers of the external API.  E.g. in some cases the RateLimiter instance will be called by a single thread in a loop several times (so I'm using the RateLimiter  instance in this case to slow the loop down to 1/sec.  And it's also passed to other instances in perhaps other threads which will do the same thing.  So in all cases I'm expecting the aggregated calling of the external API to be 1 per second, however my logging is telling me we sometimes call the external API with as little as 125ms gap between calls.

Why would RateLimiter behave this way?  Am I doing something wrong?  I'm assuming I can use the RateLimiter to slow down the current thread (same thread that created the RateLimiter) and to slow down other threads so none can call the external API too fast.

-Dave

 

[Justin Sampson]

RateLimiter is "bursty" -- it aims for an average rate of 1/s, not strictly 1s between permits. There's a lengthy explanation in a non-javadoc comment:

 

https://github.com/google/guava/blob/master/guava/src/com/google/common/util/concurrent/SmoothRateLimiter.java#L27

 

Cheers,

Justin

--
guava-...@googlegroups.com
Project site: https://github.com/google/guava
This group: http://groups.google.com/group/guava-discuss
 
This list is for general discussion.
To report an issue: https://github.com/google/guava/issues/new
To get help: http://stackoverflow.com/questions/ask?tags=guava
---
You received this message because you are subscribed to the Google Groups "guava-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to guava-discus...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/guava-discuss/5ae17980-e2d3-419d-afd1-d043f6b41368%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Joachim Durchholz]

On 05.03.2017 18:47, Justin Sampson wrote:
> RateLimiter is "bursty" -- it aims for an /average/ rate of 1/s, not

> strictly 1s between permits. There's a lengthy explanation in a
> non-javadoc comment:
>
> https://github.com/google/guava/blob/master/guava/src/com/google/common/util/concurrent/SmoothRateLimiter.java#L27

The class name is misleading then - a rate limit is usually understood
to be a hard maximum, not a best effort at achieving a given average.

Maybe RateLimiter should be renamed to RatePolicy (RatePolicer? whatever
fits best).

[David Hoffer]

Yes I agree, if that is the case RateLimiter is not a good name.  But regardless of name it severely limits the use cases where RateLimiter can be used as probably the most common use case is just a simple maximum.  It seems to me all the other cases described are optimizations for specific use cases.  So at a very minimum one needs to be able to adjust the RateLimiter so the optimizations can be turned off and it becomes a standard maximum rate limiter.

In my use case the external API I need to limit use to 1/sec has no allowance for anything other than a simple 1/sec (not average) so I need to limit to this.

Is there a way to turn off the optimizations?

-Dave

--
guava-...@googlegroups.com
Project site: https://github.com/google/guava
This group: http://groups.google.com/group/guava-discuss

This list is for general discussion.
To report an issue: https://github.com/google/guava/issues/new
To get help: http://stackoverflow.com/questions/ask?tags=guava

--- You received this message because you are subscribed to a topic in the Google Groups "guava-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/guava-discuss/UST-DM5BMAo/unsubscribe.
To unsubscribe from this group and all its topics, send an email to guava-discuss+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/guava-discuss/7c1590ae-b50f-406e-b046-a3c3ba1c38e8%40durchholz.org.

[Justin Sampson]

Hi David,

 

I'll let the Guava folks debate the naming, but even if TimeLimiter imposed a simple maximum then it still wouldn't guarantee that no two calls will hit the external service with less than a second between them, due to the inevitable delays between calling acquire(), marshalling the request, and sending it over the wire. If one call starts at 0ms and takes 100ms to go over the wire and then the next call starts at exactly 1000ms but only takes 10ms to go over the wire, the external service will see them with only 910ms between them. If you want to absolutely guarantee that no two calls arrive at the external service with less than 1s between them, you might have to bite the bullet and make all the calls from a single thread with Thread.sleep(1000) between them.

 

By the way, to see the bursty behavior empirically, I just ran the following test:

 

RateLimiter rateLimiter = RateLimiter.create(1.0);

long start = System.currentTimeMillis();

for (int i = 0; i < 10; i++) {

  if (i == 5) Thread.sleep(1500L);

  rateLimiter.acquire();

  System.out.println((System.currentTimeMillis() - start) / 1000.0);

}

 

Here's the output I got:

 

0.001

1.005

2.004

3.004

4.004

5.508

6.004

7.005

8.003

9.005

 

Notice how the limiter is recovering the average rate by only having half a second between 5.5 and 6.0. But also notice that a few of the other time points are slightly less than 1000ms apart, which we can attribute to the inherent delays between calling acquire() and calling currentTimeMillis() as well as the imperfect nature of the system clock. The delays involved in calling an external API will be orders of magnitude larger.

 

Cheers,

Justin

[David Hoffer]

I see what you mean.  I understand your point that network delays in calling my external API are going to vary and there is no way the RateLimiter can account for that. 

The fact that it recovers lost acquire attempts by shorting future ones is going to be a problem for me. I think your example is a good one and really shows the problem of my use case because when the API does get called the length of time it takes can vary dramatically so it might have a delay of 5 seconds...then the RateLimiter might think it can send a bunch out quickly to make up for the lost ones (which is more like the behavior I'm seeing).  That just won't work for my use case.  It has to take the you-snooze-you-loose approach as the API at the other end makes no allowances for lost calls.

However in my case if there is a 5 second delay in one thread I do want the other threads usage to still occur given the 1/sec rule.  But in no case do I want it to 'make up' for lost usage.

Maybe there is another simple way to do this...maybe RateLimiter is not the right tool for this job.  Any ideas?

In summary, I need a tool that allows requests to come in at any rate but come out at a fixed rate.  Then to solve the separate problem of network delays if I get an error from the external API I would need to put that request back in the queue but at the front of the line.  However I was hoping for a much simpler solution so I don't have to manage threads between different callers.  Maybe I'll just leave it as it is but retry with delay when I get the API usage failures.

-Dave

   

[Joachim Durchholz]

On 06.03.2017 02:06, Justin Sampson wrote:
> I'll let the Guava folks debate the naming

FWIW some other suggestions - they're meant as brainstorming input, not
as suggestions what the final name should be:
AveragingRateLimiter, because it tries to averate out the rate;
RateConvergingLimiter, because it tries to converge on a given rate.

> even if TimeLimiter imposed a simple maximum then it still wouldn't
> guarantee that no two calls will hit the external service with less than
> a second between them, due to the inevitable delays between calling
> acquire(), marshalling the request, and sending it over the wire. If one
> call starts at 0ms and takes 100ms to go over the wire and then the next
> call starts at exactly 1000ms but only takes 10ms to go over the wire,
> the external service will see them with only 910ms between them.

Right, there's always the possibility of jitter introduced after the
rate limiter has done its jobs. There are multiple sources of such
jitter: The JVM itself, the operating system, and the network if that is
involved.

I see no 100% reliable way to get beyond that, so David's code will need
a way from having sent messages too quickly.
He can reduce the impact by measuring the jitter, and reducing the rate.
Depending on the nature of the jitter, he could eliminate 90% or 99% of
over-the-rate incidents.

> If you
> want to absolutely guarantee that no two calls arrive at the external
> service with less than 1s between them, you might have to bite the
> bullet and make all the calls from a single thread with
> Thread.sleep(1000) between them.

This will reduce the problem for him since it eliminates the catch-up
behavour of Guava's RateLimiter.

It will not eliminate post-ratelimit jitter, so it will not fully solve it.
It's going to be ugly code with the Thread.sleep() calls and the
associated exception handling.
It will make testing harder because he cannot inject a dummy rate
limiter when he needs to test something unrelated to rate limiting (may
or may not be a problem for him).
If he is generating requests in a multithreaded fashion, he will need a
rate-limiting thread anyway.

So I think there's still a use case for a rate limiter that enforces a
maximum.
It's Javadoc should have a pretty explicit warning about potential
jitter sources and that you cannot rely on the maximum rate arriving
with 100% perfection, and that you need to measure the jitter at the
destination, decide what percentage of fails is acceptable, reduce the
rate appropriately, and have a strategie to deal with fails.

[hbkri...@gmail.com]

Hi,

I happened to notice this discussion after I had observed the stated behaviour - Average Rate Limiting - in one of my tests.

I had to work on a similar use case which required my system to control the rate at which messages are sent to another system. The external system rejects messages when my system violates the agreed threshold (#messages/second). I evaluated RateLimiter for this purpose and saw the detailed explanation pointed out by Toolforger.

I wrote a piece of code to address my use case. Yes it involves some kind of sleep when the rate is exceeded (wait and notify). I used the jmock DeterministicScheduler to unit test my code (http://www.jmock.org/threads.html).

I would like to know whether there is any plan to enhance RateLimiter to support such use cases.

Thanks,

Richards.

[lmir...@gmail.com]

Hi David, what did you do at the end? I'm facing the exact same problem and it'd be interesting to know what did you end up doing.

Luis