接口限流的几种算法

今天面试遇到一个关于接口限流的问题：设计一个方案，保证每秒只有 10 个请求可以访问接口。不得不说，此问题可以很好的考察面试高级工程师岗位的候选人的过往经验。不过很遗憾，我原来并没有做过这方面的工作。

在自己的知识储备中，首先想到的是：假如保证每秒只有 1 个请求访问接口，如何实现。在这个前提下，首先想到的是直接加锁，加锁后，每次只有一个请求可以访问接口，但是每个请求的处理时间不确定，可能小于 1s（也可能大于 1 s），此种方法不符合问题要求，pass。

接着想到使用 Redis 设置 1 个过期时间为 1s 的互斥 key，key 的命名可根据业务场景设定，每个请求均尝试设置这个 key，设置成功就可以访问接口，否则拒绝。而针对每秒限制 10 个请求，就索性设置 10 个过期时间为 1s 的互斥 key，每个请求使用 for 循环依次尝试设置这 10 个 key，前 10 个请求就将 10 key 设置，当第 1 个 key 没有过期时，第 11 个请求将设置失败，访问拒绝。此种虽然可以变相实现需求，但有一个巨大的问题，假设 QPS 为 1 万，每秒限制 100 个请求，Redis 客户端和服务器通信的网络 IO，将变成 100 万次，不敢想。

面试完成之后（当然挂了），发现思考方向还是太窄了，有很多简单方式就能实现限流。

1、计数器（固定时间窗口算法）

使用一个计数器代表请求数，设置每秒请求限制数为 10（图片为 100） ，当请求间隔大于 1s（图片为 1 minutes） 时，请求通过，重置计数器，当前时间设为间隔开始时间；当间隔时间小于 1 s 时，计数器加 1，如果计数器大于限制数时，此时请求拒绝，小于时，请求通过。因为间隔时间固定，所以这种方式也叫固定时间窗口算法。

伪代码如下：

public class CounterDemo {
    private long timeStamp = getNowTime();
    private volatile int reqCount = 0;
    private final int limit = 10; // 时间窗口内最大请求数
    private final long interval = 1000; // 时间窗口 1000 ms, 1s
    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        }
        else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }
}

线程安全代码：

public class CounterDemo {
    private long timeStamp = System.currentTimeMillis();
    private AtomicInteger reqCount = new AtomicInteger(0);
    private final int limit = 10; // 时间窗口内最大请求数
    private final long interval = 1000; // 时间窗口 1000 ms, 1s

    public boolean grant() {
        long now = System.currentTimeMillis();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount.incrementAndGet();
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount.get() <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount.set(1);
            return true;
        }
    }
}

使用示例：

@Controller
public class UserController {
	@Autowired
	UserService userService;

	@PostMapping("/signin")
	public ModelAndView doSignin(@RequestParam("email") String email, @RequestParam("password") String password,
			HttpSession session) {
        CounterDemo counter = new CounterDemo();
        if (!counter.grant()) {
            return new ModelAndView("signin.html", Map.of("email", email, "error", "Signin failed"));
		}
		try {
			User user = userService.signin(email, password);
			session.setAttribute(KEY_USER, user);
		} catch (RuntimeException e) {
			return new ModelAndView("signin.html", Map.of("email", email, "error", "Signin failed"));
		}
		return new ModelAndView("redirect:/profile");
	}
}

上面是一个接口一个 counter，如果要限制所有接口的每秒请求数，可以在 Filter 中设置。

2、滑动时间窗口算法（Sliding Window）

如果每秒限制请求访问数量为系统临界值时，假设每秒 100 次，如果 1s 内前 800ms 内没有访问，后 200ms 内访问了 100 次，后 1s 的前 200ms 又访问了 100 次，此时这 1s 就访问 200 次，此时可能会造成系统崩溃。但如果限制每秒访问次数是 10 次，那么上面计数器这种方式就足够了，毕竟每秒最多 20 次访问不会出现什么问题。

此时需要使用滑动窗口来保证间隔处不会出现超限制请求的情况。具体需要记录时间窗口每个请求的时间，即在时间窗口内每个接口请求到达的时间点。

滑动窗口记录的时间点 list = (t_1, t_2, …t_k)，起点是 list 中最小的时间点 t_1。模拟：当 t_m 时刻新的请求到来时，如果 t_m 在 t_1 + 1 内，判断 list.size() 是否小于 100，是，t_m 加入 list，通过。如果不在，丢弃第一个时间点 t_1，通过。

伪代码如下：

public class SlidingWindowDemo {
    private final int limit = 100; // 时间窗口内最大请求数
    private final long interval = 1000; // 时间窗口 1000 ms, 1s
    private List<Long> reqTimes = new ArrayList<>(){{
        add(getNowTime());
    }}; // 记录请求的时间
    public boolean grant() {
        long t_m = getNowTime();
        // 判断 t_m 是否在时间窗口内
        if (t_m < reqTimes.get(0) + interval) {
            // 判断当前时间窗口内是否超过最大请求控制数
            if (reqTimes.size() < limit) {
            	reqTimes.add(t_m);
                return true;
            } else {
                return false;
            }
        }
        else {
            // 如果不在时间窗口内，丢弃第一个时间点
            requestTimes.remove(0);
            return true;
        }
    }
}

在滑动窗口中，在时间窗口间隔处，如果时间窗口的后 200 毫秒有了 100 次访问，下一个时间窗口前 800 毫秒的请求将被拒绝。

每个时间窗口（1s）list 最多 100 个。

3、漏桶算法（Leaky Bucket)

滑动时间窗口无法应对细时间粒度（某个时间）的突发性请求，示例：当 t_1 = 1ms，来了 50 个请求，窗口有 50 个时间点了，中间没有请求，t_3 = 900 ms，又来了 100 个请求，只能加入 50 个。

漏桶算法在此方面有更好的表现，它以指定速度漏出请求（水），如果可以往桶里加请求，代表请求可以访问。漏出量无需使用额外线程控制，根据时间间隔和速率减少。

假设限制每秒请求数限制为 100，那么设置桶的容量为 100，1 秒漏完，流速为 100 request/s（0.1 request/ms），默认容量为 0。

伪代码：

public class LeakyBucketDemo {
    private long timeStamp = getNowTime();
    private int capacity = 100; // 桶的容量 100
    private float rate = 0.1f; // 水漏出的速度 0.1（浮点型 * 整数结果去除精度）
    private int water = 0; // 当前水量(当前累积请求数) 0
    public boolean grant() {
        long now = getNowTime();
        water = max(0, water - (now - timeStamp) * rate); // 先执行漏水，计算剩余水量
        timeStamp = now;
        if ((water + 1) < capacity) {
            // 尝试加水,并且水还未满
            water += 1;
            return true;
        }
        else {
            // 水满，拒绝加水
            return false;
        }
    }
}

分析临界情况：漏桶算法没有时间窗口的概念，如果 water 还是 0，当 10ms 有 100 个请求过来后，此时 water 容量为 100，10ms 能漏掉的请求 10*0.1 = 1，water = 99。所以请求 101 次时，请求将被拒绝。

分析细时间粒度的突发性请求情况：50 个请求在 899ms 的时间内已经漏完了，所以第 900ms 的 100 个请求可以容纳。

4、令牌桶算法（Token bucket）

上面漏桶算法是往里面塞，这个令牌桶算法是从里面取。以一个固定的速率往桶中加 token（令牌），每次请求均从桶中取一个令牌，没有令牌将不能访问。添加令牌也无需使用额外线程控制，根据时间间隔和速率来添加。

假设限制每秒请求数限制为 100，那么每 1 秒最多取走 100 个 token，桶的容量 100，令牌放入的速度 100 token/s，0.1 token/ms。

伪代码如下：

public class TokenBucketDemo {
    private long timeStamp = getNowTime();
    private int capacity = 100; // 桶的容量
    private float rate = 0.1f; // 令牌放入速度
    private int tokens = 100; // 当前令牌数量
    public boolean grant() {
        long now = getNowTime();
        // 先添加令牌
        tokens = min(capacity, tokens + (now - timeStamp) * rate); 
        timeStamp = now;
        if (tokens < 1) {
            // 若不到 1 个令牌,则拒绝
            return false;
        }
        else {
            // 还有令牌，领取令牌
            tokens -= 1;
            return true;
        }
    }
}

总结

如果限制请求很低，可以直接使用计数器（固定时间窗口算法）。

滑动时间窗口算法需要更多的内存。

令牌桶和漏桶算法当出现峰值后，添加 token 和漏水有速度控制，下一次不能马上达到峰值，所以相比固定时间窗口算法更加平滑。

令牌桶算法，当桶满了，可以一下拿走 100 个令牌。漏桶算法，漏完了，一次可以加 100 个请求。所以相比滑动时间窗口算法可应对突发性请求。

一般来说，也不会直接用代码去实现相应的算法，而是在 ngix 中配置，ngix 限流默认使用的漏桶算法。

参考链接

• 接口限流算法总结
• 微服务接口限流的设计与思考（附 GitHub 框架源码）