一、简介

限流算法通过限制每个用户的访问频率来保护系统免受无意或恶意的过度访问。

在上图中，最初系统每分钟接收4个请求（绿色方块），当在12:02开启限流后，系统拒绝了其他请求（红色方块）。

  • 限流的应用

    • APIs

      保护API免遭过度使用或滥用。

    • Web Servers

      控制传入的HTTP请求并防止服务器过载。

    • Microservices

      管理服务间通信并防止级联故障。

  • 使用限流的好外

    • 避免资源匮乏，限流可以提高服务的可用性。

    • 限流可以允许多个用户公平共享服务。

    • 可以防御或缓解某些常见攻击，例如：DoS和DDoS（分布式拒绝服务）攻击，暴力破解和撞库攻击，以及网页抓取或网站抓取等。

二、限流算法

常用的限流算法有：

  • Leaky Bucket

漏桶算法：将请求放在桶中，并以固定速率流出；如果请求超出桶的容量则将被拒绝。

  • Token Bucket

令牌桶算法：令牌以固定速率添加到桶中，如果请求能获取到令牌，则处理请求。

  • Fixed Window

固定窗口算法：在固定时间窗口内应用速率限制，超过限制的请求将被拒绝。

  • Sliding Window

滑动窗口算法：基于随时间移动的动态时间窗口，可以更灵活地管理流量突发。

1、漏桶

漏桶(Leaky bucket)算法创建一个容量有限的队列，在给定时间范围内超出队列容量的所有请求都会溢出。

  • 优点

可以平滑处理请求的突发并以恒定的速率处理，无论请求数量如何，都会以恒定的、近乎均匀的流量传输到服务器；此算法很容易在负载均衡器上实现。

  • 缺点

如果出现大量请求可能会填满队列（桶），导致新请求无法处理。它也不保证请求在固定的时间内得到处理。

2、令牌桶

令牌桶(Token bucket)算法中令牌以每次固定的速率添加到令牌桶中存储，应用程序处理的每个请求都会使用令牌桶中的令牌；令牌桶的大小是固定的，因此令牌不能无限堆积；当桶中的令牌用完时，新的请求将被拒绝。

令牌桶算法和漏桶算法的不同之处在于处理瞬时到达的大量请求：令牌桶算法可以在令牌桶里积攒一些令牌，当大量请求到来时可以一次性处理令牌桶中数量的请求，然后按恒定的速度处理请求；而漏桶算法则一直以一个固定的速率处理请求。

3、固定窗口

固定窗口(Fixed Window)算法在给定的持续时间内（n秒的窗口大小）维持一个计数器，并对收到的每个请求递增它；如果计数器超过阈值，将丢弃请求，直到重置持续时间。

例如，服务器允许每分钟最多通过300个请求，那么在8:00~8:01之间不会处理超过300个请求；窗口将在8:01重置，允许另外300个请求，直到8:02。

  • 优点

此算法可以确保处理较新的请求。

  • 缺点

当在窗口边界附近发生的单个流量突发可能会导致处理两倍的请求，因为它允许在短时间内同时请求当前窗口和下一个窗口。而且，如果在窗口重置时请求突然激增，仍然可能导致请求过载。

例如，8:00:50之前没有请求，而8:00:50开始有300个请求，8:01窗口重置后到8:01:20又来了300个请求，那么在8:00:50~8:01:20之间请求有600个。

4、滑动日志

滑动日志(Sliding Log)算法跟踪每个请求的时间戳日志，系统将这些日志存储在按时间排序的哈希集合或哈希表中，它会丢弃时间戳超过指定阈值的所有请求。当有新请求传入时会计算日志的总和以确定请求速率，如果请求超过阈值速率，则将其保持（Hold），否则将处理请求。

  • 优点

不受固定窗口边界条件的影响，将保持精确的速率限制。由于系统跟踪每个请求的滑动日志，因此不会遇到固定窗口的踩踏效应。

  • 缺点

为每个请求存储无限数量的日志成本可能高昂，另外计算成本也很高，因为每个请求都需要计算先前请求的总和，可能跨服务器集群。因此，它不能很好地扩展以处理大量流量爆发和拒绝服务攻击。

5、滑动窗口

滑动窗口(Sliding window)算法结合了固定窗口算法的低处理成本和滑动日志算法改进的边界条件，与固定窗口算法一样在每个固定窗口维持一个计数器。

滑动窗口算法是基于时间的，类似于固定窗口算法，但在每个时间窗口的起点有所不同。滑动窗口时间范围从用户发出新请求时开始，而不是在预定时间开始。例如，如果第一个请求在7:00:30到达（速率限制为每分钟200个），则在7:01:30之前，服务器最多允许200个请求。

滑动窗口算法通过提供更大的灵活性，解决固定窗口算法所面临的问题，它适用于处理大型请求，同时具有轻量级和快速运行的特点。

三、RateLimiter

Guava库中的RateLimiter是基于令牌桶算法实现的，可以用它实现限流。使用前需添加依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>32.0.0-jre</version>
</dependency>

1、方法介绍

  • acquire()

    从RateLimiter获取一个许可，如果获取不到则阻塞，直到请求被批准。

  • acquire(int permits)

    同acquire()，获取指定数量的许可。

  • create(double permitsPerSecond)

    创建指定吞吐量的RateLimiter，参数为每秒可获得的许可数。

  • create(double permitsPerSecond, long warmupPeriod, TimeUnit unit)

    同create(double permitsPerSecond)，可以指定预热期，在此期间平稳提高其速率，直到在该周期结束时达到最大速率。

  • getRate()

    获取RateLimiter的稳定速率(permitsPerSecond)。

  • setRate(double permitsPerSecond)

    更新RateLimiter的稳定速率(permitsPerSecond)。

  • tryAcquire(long timeout, TimeUnit unit)

    如果可以在不超过指定超时时间内获得许可，则从RateLimiter中获取许可，否则如果在超时到期之前还未获得许可，则直接返回false（不会阻塞）。

  • tryAcquire(int permits, long timeout, TimeUnit unit)

    同tryAcquire(long timeout, TimeUnit unit)，获取指定数量的许可。

2、基础用法

假设方法doSomeLimitedOperation的执行速率限制为每秒2次。

private static void doSomeLimitedOperation(){
	//do something
}

创建每秒2个许可的RateLimiter，在调用doSomeLimitedOperation方法前先获取许可：

public static void main(String[] args) {
	RateLimiter rateLimiter = RateLimiter.create(2);
	int startTime = ZonedDateTime.now().getSecond();
	rateLimiter.acquire();
	doSomeLimitedOperation();
	rateLimiter.acquire();
	doSomeLimitedOperation();
	int elapsedTimeSeconds = ZonedDateTime.now().getSecond() - startTime;
	System.out.println(elapsedTimeSeconds <= 1);//true
}

假设doSomeLimitedOperation方法会立即完成（不耗时），那么上面两次获取许可的方法调用acquire()都不会阻塞，且运行时间会小于1秒（因为每次都可以立即获得许可）。

可以通过带参的方法获取指定数量的许可：

rateLimiter.acquire(100);

3、阻塞

假设方法doSomeLimitedOperation的执行速率限制为每秒100次；而现在有1000个请求需调用此方法，获取不到许可以请求会阻塞，因此至少需要执行10秒执行完成。

public static void main(String[] args) {
	RateLimiter rateLimiter = RateLimiter.create(100);
	int startTime = ZonedDateTime.now().getSecond();
	for(int i = 0; i < 1000; i++){
		rateLimiter.acquire();
		doSomeLimitedOperation();
	}
	int elapsedTimeSeconds = ZonedDateTime.now().getSecond() - startTime;
	System.out.println(elapsedTimeSeconds >= 10);//true
}

4、超时

下面的例子中创建了每秒1个许可的RateLimiter，随后获取许可并执行doSomeLimitedOperation()方法，执行完立即在10毫秒内获取2个许可，由于每秒只有1个许可，因此获取不到，直接返回false（不阻塞），输出abandon。

public static void main(String[] args) {
	RateLimiter rateLimiter = RateLimiter.create(1);
	
	rateLimiter.acquire();
	doSomeLimitedOperation();
	
	boolean ret = rateLimiter.tryAcquire(2, 10, TimeUnit.MILLISECONDS);
	if(ret){
		doSomeLimitedOperation();
	}else{
		System.out.println("abandon");
	}
}

5、预热

下面的例子中每秒发放5个许可（获取每个许可大概0.2秒）；预热时间为2秒，即从开始到2秒的时间内，发放许可的速率会逐渐提升到0.2秒1个许可。

public static void main(String[] args) {
	RateLimiter rateLimiter = RateLimiter.create(5, 2, TimeUnit.SECONDS);
	for (int i = 1; i <= 15; i++) {
		double time = rateLimiter.acquire(1);
		System.out.println(String.format("%s. Acquires a permit take %s second", i, time));
	}
}

输出:

1. Acquires a permit take 0.0 second
2. Acquires a permit take 0.535166 second
3. Acquires a permit take 0.478881 second
4. Acquires a permit take 0.399621 second
5. Acquires a permit take 0.318707 second
6. Acquires a permit take 0.239538 second
7. Acquires a permit take 0.199555 second
8. Acquires a permit take 0.199087 second
9. Acquires a permit take 0.199835 second
10. Acquires a permit take 0.199798 second
11. Acquires a permit take 0.199752 second
12. Acquires a permit take 0.19973 second
13. Acquires a permit take 0.199106 second
14. Acquires a permit take 0.199987 second
15. Acquires a permit take 0.199451 second

如果不使用预热：

RateLimiter rateLimiter = RateLimiter.create(5);
for (int i = 1; i <= 15; i++) {
	double time = rateLimiter.acquire(1);
	System.out.println(String.format("%s. Acquires a permit take %s second", i, time));
}

输出结果可以看到获取一个许可大概0.2秒：

1. Acquires a permit take 0.0 second
2. Acquires a permit take 0.174139 second
3. Acquires a permit take 0.197923 second
4. Acquires a permit take 0.198975 second
5. Acquires a permit take 0.199928 second
6. Acquires a permit take 0.199061 second
7. Acquires a permit take 0.200008 second
8. Acquires a permit take 0.199923 second
9. Acquires a permit take 0.199114 second
10. Acquires a permit take 0.19991 second
11. Acquires a permit take 0.199059 second
12. Acquires a permit take 0.199956 second
13. Acquires a permit take 0.199783 second
14. Acquires a permit take 0.198878 second
15. Acquires a permit take 0.198913 second
参考资料

Rate Limiter: Explained

How to Design an API Rate Limiting Algorithm - Kong Inc

Quick Guide to the Guava RateLimiter

RateLimiter