Add method to decrement permits in RateLimiter

[GoogleCodeExporter]

We need a new, non-blocking method added to RateLimiter class:

   void forceDecrementPermits(int permits, long timeInThePast);

This method should never block. It shall decrement permits and serve next 
acquire() accordingly.

We need this method for distributed rate limiting. After collecting fresh 
statistics from other nodes, every node can synchronize their local RateLimiter 
to the expected rate.

I mingled around RateLimiter code, and this request seems non-trivial. Any 
design ideas to use current RateLimiter distributedly are welcome.

Original issue reported on code.google.com by bahri.ge...@gmail.com on 8 Apr 2013 at 11:10

[GoogleCodeExporter]

Original comment by kak@google.com on 8 Apr 2013 at 2:04

[GoogleCodeExporter]

Can you elaborate a bit on what this forceDecrementPermits would do? What is 
the "timeInThePast" parameter? I thought you were asking for a non-blocking 
version of

rateLimiter.acquire(permitsToBeWasted)

but the second argument confuses me.

Original comment by andr...@google.com on 8 Apr 2013 at 4:31

[GoogleCodeExporter]

I am not sure that the time parameter is necessary, I would use it to hint the 
RateLimiter that this action actually occured in the past.

Let's say rate is 2.0 tps, and we are using 1.0 tps of it constantly. At time 
10 we would be able to acquire 10 permits non blockingly. If we tell 
RateLimiter someone out of our context, acquired 4 permits 5 seconds ago, we 
would still be able to acquire 6 permits at time 10, 7 permits at time 12 etc...

If timeInThePast parameter was discarded, say 10 permits was acquired 15 
seconds ago, we would pay for the blocking price for a longer time then 
necessary.

Sorry for the late answer.

Original comment by bahri.ge...@gmail.com on 17 Apr 2013 at 7:18

[GoogleCodeExporter]

It's a little trickier than that: an invocation of acquire(P) doesn't itself 
pay (by waiting) for the P permits - the next invocation of acquire(X) pays the 
it. This can be thought as "the permits can go negative (borrowed from the 
future), once".

Regarding the "timeInThePast" parameter, currently the default RateLimiter (not 
the warming-up one, the one you get by RateLimiter.create(qps)) only keeps 
state for the last 1 second. It doesn't remember longer than that, e.g. if it 
was idle for 10 minutes, or 1 second, it looks the same.

In your example, if the RateLimiter was allowed to accumulate permits for 10 
seconds, then it would work pretty much as you describe. The RateLimiter, at 
time 10, would know that it has 10 unused permits (which correspond to a state 
of being completely idle for 5 seconds). Then, to say that "someone acquired 4 
permits 5 seconds ago", you just do acquire(4), because you would know that the 
RateLimiter remembers that far back so it will do the right thing.

If the request was "someone acquired 4 permits 15 seconds ago", then we're back 
at the same problem, the RateLimiter wouldn't remember that much, and wouldn't 
know what to do about it.

Actually I hope that we'll be able to offer an API like this, where you would 
be able to control the past memory of RateLimiter, i.e. how many permits it can 
accumulate due to idleness.

Original comment by andr...@google.com on 17 Apr 2013 at 6:20

[GoogleCodeExporter]

This issue has been migrated to GitHub.

It can be found at https://github.com/google/guava/issues/<issue id>

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:12

• Added labels: MigratedToGitHub

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 1 Nov 2014 at 4:18

• Changed state: Migrated

[GoogleCodeExporter]

Original comment by cgdecker@google.com on 3 Nov 2014 at 9:08

• Added labels: Restrict-AddIssueComment-Commit