【面试真题拆解16】5秒内限10次HTTP接口访问,结合数据结构和算法说说你的思路

面试官问：

做Web项目的时候，会暴露出一些HTTP接口，我现在想对它进行限流，限制5秒内只能访问10次，结合数据结构和算法，看如何实现，说说你的思路

当时只说了个滑动窗口就没说其他的，然后就没有然后了。。。

首先，为什么要限流？

主要有以下三个原因：

1. 1. 防止恶意刷接口，比如爬虫爬数据、黑客DDoS攻击。
2. 2. 保护服务器不被压垮，比如一个接口挂了，拖垮整个服务。
3. 3. 保证核心业务的可用性，比如大促场景下，支付接口优先，对普通接口进行限流。

技术选型

滑动窗口计数器

滑动窗口的核心，是窗口不再是静止分段的，而是随当前时间连续移动、互相重叠的：

比如固定窗口，窗口是死的，0-5秒、5-10秒，边界固定不变。

而滑动窗口，窗口的右边界永远是当前请求的时间，左边界永远是当前时间 - 窗口大小，窗口会跟着每一次请求一直往前滑。

数据结构选型

本地：LinkedList（双向链表）

选择双向链表是因为我们需要频繁删除链表头部的过期时间戳，并且还需要频繁在链表尾部新增新的请求时间戳，而双向链表的删头、加尾操作时间复杂度都是O(1)，效率极高。

分布式：Redis ZSet（有序集合）

Web项目基本都是集群部署，本地计数器无法多实例同步，考虑用Redis实现。

选择Redis中的ZSet数据结构，ZSet的score字段可以存请求的时间戳，天然支持按时间范围排序。

实现逻辑

每次请求进来，执行 3 步：

1. 1. 删掉所有早于当前时间 - 窗口大小的请求
2. 2. 统计当前窗口内的请求数，超过 10 次直接拒绝
3. 3. 把当前请求的时间戳加入数据结构，放行请求

小贴士

1. 1. 令牌桶的令牌生成速度要合理

不能太快（等于没限流），也不能太慢（很多请求被拒），要根据业务场景调整。

1. 2. Redis ZSet的过期时间要设置对

要设置成窗口大小+一点缓冲（比如1秒），防止数据提前过期，导致计数不准确。