限制方法在N秒内调用M个请求

Question

我需要一个组件/类来限制某些方法的执行到N秒内的最大M次调用(或ms或nanos,无关紧要).

换句话说,我需要确保我的方法在N秒的滑动窗口中执行不超过M次.

如果您不知道现有的课程,请随时发布您的解决方案/想法如何实现这一点.

Answer 1

我使用固定大小为M的时间戳的环形缓冲区.每次调用该方法时,检查最旧的条目,如果它在过去的时间内小于N秒,则执行并添加另一个条目,否则您将睡眠为时差.

Answer 2

对我来说开箱即用的是Google Guava RateLimiter.

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

private void someMethod() {
    throttle.acquire();
    // Do something
}

Answer 3

具体而言,您应该能够使用a实现此功能DelayQueue.使用M Delayed最初设置为零的实例初始化队列.当对方法的请求进入时,会出现take一个令牌,导致该方法阻塞,直到满足限制要求为止.当一个令牌被占用时,add一个新的令牌延迟到队列N.

Answer 4

阅读令牌桶算法.基本上,你有一个带有令牌的桶.每次执行该方法时,都会获取一个令牌.如果没有更多令牌,则阻止直到获得一个令牌.同时,有一些外部演员以固定的间隔补充令牌.

我不知道有一个库(或类似的东西).您可以将此逻辑写入代码或使用AspectJ添加行为.

Answer 5

如果您需要在分布式系统上运行的基于Java的滑动窗口速率限制器，则可能需要查看https://github.com/mokies/ratelimitj项目。

Redis支持的配置，将IP请求限制为每分钟50个，如下所示：

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");

有关Redis配置的更多详细信息，请参见https://github.com/mokies/ratelimitj/tree/master/ratelimitj-redis。

Answer 6

这取决于应用程序.

想象一下这样的情况:多个线程希望令牌执行某些全局速率限制操作而不允许突发(即您希望每10秒限制10个操作,但您不希望在第一秒内发生10个操作然后保留停了9秒).

DelayedQueue有一个缺点:线程请求令牌的顺序可能不是它们获得请求的顺序.如果多个线程被阻塞等待令牌,则不清楚哪个线程将使用下一个可用令牌.在我看来,你甚至可以让线程永远等待.

一种解决方案是在两个连续动作之间具有最小时间间隔,并且按照它们所请求的相同顺序采取动作.

这是一个实现:

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);
        }
    }
}

Answer 7

我下面的实现可以处理任意请求时间精度，它对每个请求都有 O(1) 时间复杂度，不需要任何额外的缓冲区，例如 O(1) 空间复杂度，此外它不需要后台线程释放令牌，而是令牌根据自上次请求以来经过的时间释放。

class RateLimiter {
    int limit;
    double available;
    long interval;

    long lastTimeStamp;

    RateLimiter(int limit, long interval) {
        this.limit = limit;
        this.interval = interval;

        available = 0;
        lastTimeStamp = System.currentTimeMillis();
    }

    synchronized boolean canAdd() {
        long now = System.currentTimeMillis();
        // more token are released since last request
        available += (now-lastTimeStamp)*1.0/interval*limit; 
        if (available>limit)
            available = limit;

        lastTimeStamp = now;
        if (available<1)
            return false;
        else {
            available--;
            return true;
        }
    }
}