I need a component/class that throttles execution of some method to maximum M calls in N seconds (or ms or nanos, does not matter).

In other words I need to make sure that my method is executed no more than M times in a sliding window of N seconds.

If you don't know existing class feel free to post your solutions/ideas how you would implement this.

15 Answers 15

up vote 72 down vote accepted

I'd use a ring buffer of timestamps with a fixed size of M. Each time the method is called, you check the oldest entry, and if it's less than N seconds in the past, you execute and add another entry, otherwise you sleep for the time difference.

  • 3
    Lovely. Just what I need. Quick attempts shows ~10 lines to implement this and minimal memory footprint. Just need to think about thread safety and queuing of incoming requests. – vtrubnikov Sep 10 '09 at 20:17
  • 5
    That's why you use the DelayQueue from java.util.concurrent. It prevents the problem of multiple threads acting on the same entry. – erickson Sep 10 '09 at 20:22
  • 5
    For a multi threaded case, the token bucket approach may be a better choice, I think. – Michael Borgwardt Sep 10 '09 at 20:44
  • 1
    Do you know how this algorithm is called if it's has any name at all? – Vlado Pandžić Mar 6 at 16:34

What worked out of the box for me was Google Guava RateLimiter.

// Allow one request per second
private RateLimiter throttle = RateLimiter.create(1.0);

private void someMethod() {
    throttle.acquire();
    // Do something
}
  • 14
    I wouldn't recommend this solution as the Guava RateLimiter will block the thread and that will exhaust the thread pool easily. – kaviddiss Oct 22 '14 at 19:35
  • 10
    @kaviddiss if you don't want to block then use tryAquire() – slf Mar 10 '15 at 19:33
  • 4
    The issue with the currently implementation of RateLimiter (at least for me) is that it does not allow for time periods of greater than 1 second and therefore rates of for example 1 per minute. – John B May 21 '15 at 19:17
  • 2
    @John B As far as I understand, you can achieve 1 request per minute with RateLimiter by using RateLimiter.create(60.0)+rateLimiter.acquire(60) – divideByZero Sep 18 '15 at 12:41
  • 1
    @divideByZero - Interesting thought. More accurate would be RateLimiter.create(1.0) to get one permit per second. Then each acquire would use acquire(60) to only allow one per minute. – John B Sep 21 '15 at 12:26

In concrete terms, you should be able to implement this with a DelayQueue. Initialize the queue with M Delayed instances with their delay initially set to zero. As requests to the method come in, take a token, which causes the method to block until the throttling requirement has been met. When a token has been taken, add a new token to the queue with a delay of N.

  • Yes, this would do the trick. But I don't particularly like DelayQueue because it is using (via PriortyQueue) a balanced binary hash (which means lots of comparisons on offer and possible array growth), and its all kinda heavy for me. I guess for others this might be perfectly okay. – vtrubnikov Sep 10 '09 at 20:25
  • 4
    Actually, in this application, since the new element added to the heap will almost always be the maximum element in the heap (i.e., have the longest delay), usually one comparison per add is required. Also, the array will never grow if the algorithm is implemented correctly, since one element is added only after taking one element. – erickson Sep 10 '09 at 20:59
  • 3
    I found this helpful also in cases where you dont want requests to happen in big bursts by keeping the size M and delay N relatively small in order of handful millis. eg. M = 5, N = 20ms would provide a through put of 250/sec kepping burst to happen in size of 5. – FUD Sep 22 '12 at 10:51

Read up on the Token bucket algorithm. Basically, you have a bucket with tokens in it. Every time you execute the method, you take a token. If there are no more tokens, you block until you get one. Meanwhile, there is some external actor that replenishes the tokens at a fixed interval.

I'm not aware of a library to do this (or anything similar). You could write this logic into your code or use AspectJ to add the behavior.

  • 3
    Thanks for suggestion, interesting algo. But its not exactly what I need. For example, I need to limit execution to 5 call per second. If I use Token bucket and 10 requests come in at the same time, first 5 calls would take all available tokens and execute momentarily, while remaining 5 calls will be executed at fixed interval of 1/5 s. In such situation I need remaining 5 call to be executed in single burst only after 1 second passes. – vtrubnikov Sep 10 '09 at 20:37
  • 5
    What if you added 5 tokens to the bucket every second (or 5 - (5-remaining) instead of 1 every 1/5 second? – Kevin Sep 10 '09 at 20:43
  • @Kevin no this still would not give me 'sliding window' effect – vtrubnikov Sep 10 '09 at 20:53
  • 2
    @valery yes it would. (Remember to cap the tokens at M though) – nos Oct 9 '13 at 23:43
  • 1
    Library on GitHub - github.com/bbeck/token-bucket – kervin Aug 9 '15 at 16:52

This depends in the application.

Imagine the case in which multiple threads want a token to do some globally rate-limited action with no burst allowed (i.e. you want to limit 10 actions per 10 seconds but you don't want 10 actions to happen in the first second and then remain 9 seconds stopped).

The DelayedQueue has a disadvantage: the order at which threads request tokens might not be the order at which they get their request fulfilled. If multiple threads are blocked waiting for a token, it is not clear which one will take the next available token. You could even have threads waiting forever, in my point of view.

One solution is to have a minimum interval of time between two consecutive actions, and take actions in the same order as they were requested.

Here is an implementation:

public class LeakyBucket {
    protected float maxRate;
    protected long minTime;
    //holds time of last action (past or future!)
    protected long lastSchedAction = System.currentTimeMillis();

    public LeakyBucket(float maxRate) throws Exception {
        if(maxRate <= 0.0f) {
            throw new Exception("Invalid rate");
        }
        this.maxRate = maxRate;
        this.minTime = (long)(1000.0f / maxRate);
    }

    public void consume() throws InterruptedException {
        long curTime = System.currentTimeMillis();
        long timeLeft;

        //calculate when can we do the action
        synchronized(this) {
            timeLeft = lastSchedAction + minTime - curTime;
            if(timeLeft > 0) {
                lastSchedAction += minTime;
            }
            else {
                lastSchedAction = curTime;
            }
        }

        //If needed, wait for our time
        if(timeLeft <= 0) {
            return;
        }
        else {
            Thread.sleep(timeLeft);
        }
    }
}

If you need a Java based sliding window rate limiter that will operate across a distributed system you might want to take a look at the https://github.com/mokies/ratelimitj project.

A Redis backed configuration, to limit requests by IP to 50 per minute would look like this:

import com.lambdaworks.redis.RedisClient;
import es.moki.ratelimitj.core.LimitRule;

RedisClient client = RedisClient.create("redis://localhost");
Set<LimitRule> rules = Collections.singleton(LimitRule.of(1, TimeUnit.MINUTES, 50)); // 50 request per minute, per key
RedisRateLimit requestRateLimiter = new RedisRateLimit(client, rules);

boolean overLimit = requestRateLimiter.overLimit("ip:127.0.0.2");

See https://github.com/mokies/ratelimitj/tree/master/ratelimitj-redis fore further details on Redis configuration.

Although it's not what you asked, ThreadPoolExecutor, which is designed to cap to M simultaneous requests instead of M requests in N seconds, could also be useful.

The original question sounds a lot like the problem solved in this blog post: Java Multi-Channel Asynchronous Throttler.

For a rate of M calls in N seconds, the throttler discussed in this blog guarantees that any interval of length N on the timeline will not contain more than M calls.

I have implemented a simple throttling algorithm.Try this link, http://krishnaprasadas.blogspot.in/2012/05/throttling-algorithm.html

A brief about the Algorithm,

This algorithm utilizes the capability of Java Delayed Queue. Create a delayed object with the expected delay (here 1000/M for millisecond TimeUnit). Put the same object into the delayed queue which will intern provides the moving window for us. Then before each method call take the object form the queue, take is a blocking call which will return only after the specified delay, and after the method call don't forget to put the object into the queue with updated time(here current milliseconds).

Here we can also have multiple delayed objects with different delay. This approach will also provide high throughput.

  • 6
    You should post a summary of your algorithm. If your link goes away then your answer becomes useless. – j.w.r Oct 20 '12 at 1:01
  • Thanks, I have added the brief. – Krishas Sep 30 '16 at 12:42

I need to make sure that my method is executed no more than M times in a sliding window of N seconds.

I recently wrote a blog post about how to do this in .NET. You might be able to create something similar in Java.

Better Rate Limiting in .NET

  • The link seems wrong. – rozon Feb 13 at 8:44

Try to use this simple approach:

public class SimpleThrottler {

private static final int T = 1; // min
private static final int N = 345;

private Lock lock = new ReentrantLock();
private Condition newFrame = lock.newCondition();
private volatile boolean currentFrame = true;

public SimpleThrottler() {
    handleForGate();
}

/**
 * Payload
 */
private void job() {
    try {
        Thread.sleep(Math.abs(ThreadLocalRandom.current().nextLong(12, 98)));
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.err.print(" J. ");
}

public void doJob() throws InterruptedException {
    lock.lock();
    try {

        while (true) {

            int count = 0;

            while (count < N && currentFrame) {
                job();
                count++;
            }

            newFrame.await();
            currentFrame = true;
        }

    } finally {
        lock.unlock();
    }
}

public void handleForGate() {
    Thread handler = new Thread(() -> {
        while (true) {
            try {
                Thread.sleep(1 * 900);
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                currentFrame = false;

                lock.lock();
                try {
                    newFrame.signal();
                } finally {
                    lock.unlock();
                }
            }
        }
    });
    handler.start();
}

}

Apache Camel also supports comes with Throttler mechanism as follows:

from("seda:a").throttle(100).asyncDelayed().to("seda:b");

You can use redis for this when locking is needed in distributed system. Second algorithm in https://redis.io/commands/incr

This is an update to the LeakyBucket code above. This works for a more that 1000 requests per sec.

import lombok.SneakyThrows;
import java.util.concurrent.TimeUnit;

class LeakyBucket {
  private long minTimeNano; // sec / billion
  private long sched = System.nanoTime();

  /**
   * Create a rate limiter using the leakybucket alg.
   * @param perSec the number of requests per second
   */
  public LeakyBucket(double perSec) {
    if (perSec <= 0.0) {
      throw new RuntimeException("Invalid rate " + perSec);
    }
    this.minTimeNano = (long) (1_000_000_000.0 / perSec);
  }

  @SneakyThrows public void consume() {
    long curr = System.nanoTime();
    long timeLeft;

    synchronized (this) {
      timeLeft = sched - curr + minTimeNano;
      sched += minTimeNano;
    }
    if (timeLeft <= minTimeNano) {
      return;
    }
    TimeUnit.NANOSECONDS.sleep(timeLeft);
  }
}

and the unittest for above:

import com.google.common.base.Stopwatch;
import org.junit.Ignore;
import org.junit.Test;

import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;

public class LeakyBucketTest {
  @Test @Ignore public void t() {
    double numberPerSec = 10000;
    LeakyBucket b = new LeakyBucket(numberPerSec);
    Stopwatch w = Stopwatch.createStarted();
    IntStream.range(0, (int) (numberPerSec * 5)).parallel().forEach(
        x -> b.consume());
    System.out.printf("%,d ms%n", w.elapsed(TimeUnit.MILLISECONDS));
  }
}

Check out the [TimerTask1 class. Or the ScheduledExecutor.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.