限流算法介绍，及记录一次遭遇到的恶意攻击

限流算法介绍，及记录一次遭遇到的恶意攻击

32 2019-05-13 16:31:58

## 背景
近期部门业务遭到分布式拒绝服务攻击（Distributed Denial of Service, DDoS），正常情况下单服务峰值qps约为1200，服务异常期间单服务qps约为3500，导致正常用户无法访问服务。

### 现象与原因
- 正常用户访问出现白页
- Tomcat运行正常，AccessLog记录的响应时间提高，Tomcat的Http线程池（最大线程数400）耗尽
- GC频繁

业务层有爬虫识别机制，对访问频率过高的IP进行了限制，但对一些知名爬虫和合作方爬虫白名单放行。知名爬虫包括百度、搜狗、各种主流手机浏览器（他们内部做了一些特殊转化）。
但是攻击者使用了几千个IP，且UA等特征伪造了知名爬虫的特征，因此我们只能做到将其判断为爬虫，但无法与正常爬虫区分开，也就无法做到针对性的屏蔽。
一旦无法针对性屏蔽，放行的爬虫会占用正常用户的资源（比如线程池），导致正常用户访问异常。

### 临时策略
由于无法从来源区分合法与非法的爬虫，只能另辟蹊径，减少爬虫占用的资源。
当爬虫请求过来时，不走任何正常业务逻辑，直接返回异常响应码，减少响应时间。爬虫响应时间减少后，对爬虫请求的处理时间占总的请求处理时间比例下降，Tomcat压力有所减轻。
最终上线的临时策略是对所有爬虫返回403响应，无论是否是知名爬虫。

但是这个策略仍然存在问题：
- 即使不处理任何业务逻辑直接返回403，爬虫仍然到达了业务层，并占用了业务服务总处理能力的一大部分，线程池消耗仍然很高，也就是说服务仍有很多时间在“空转”
- 如果攻击方继续增加请求量，那么爬虫请求处理占比仍然会提高，正常访问仍然有可能资源不足

### 改进策略
针对临时策略存在的不足，部门提出了更完善的解决方案：
1. 接入层限流，保证业务层不会因为DDoS或突发流量而瘫痪
2. 业务层增加分流逻辑，将服务集群划分为普通集群和爬虫（及合作方）集群，保证爬虫或合作方不占用正常用户的资源。这一点类似于给资源池上加以区分，互不影响，还可以施行不同的策略
3. 打通接入层和业务层的屏蔽名单，一旦业务层将IP识别为未知爬虫，上报接入层进行屏蔽或限流

目前几个策略搭配看起来相对合理，具体效果还需要整体上线后观察。

## 限流算法
经典限流算法包括计数器算法、漏桶算法和令牌桶算法。

### 计数器算法
计数器算法非常简单，对每个IP一个时间周期内的请求计数，如果超过阈值则进行屏蔽，下一个周期对计数清零。
比如，限制单个IP在5分钟内对同一URL只允许正常请求100次，超过则判断为爬虫，或直接屏蔽访问，返回403。

**优点**
- 实现简单，计数可参考以前博客到的并发计数工具，或使用Redis

**缺点**
- 不够平滑，可能出现在一个周期前期放行，中后期完全屏蔽，下一个周期又突然放行。这样的反复屏蔽、放行形成流量“突刺”（我觉得可以叫狗牙，hh）
- 具有周期性，除了可能形成“突刺”现象外，还需要额外的处理才能实现持续屏蔽或限流

目前部门业务层使用的爬虫识别及屏蔽策略基于计数器算法。

### 漏桶算法
漏桶算法核心思想类似消息队列，对请求进行削峰填谷。
![](/img/pic/2019051316303390409_png_443_299_41373)
> 其实叫漏斗算法可能更准确

漏桶算法可以很形象地类比：水倒入一个底部开口的桶，桶中的水以恒定的速率从下边的洞流出；如果水倒得太快，超过了桶的容量，那么会从桶上边的口溢出来。
对于请求来说，无论调用方请求频率多高，漏桶通过的频率是恒定的，请求频率超过通过频率时就会出现请求积压；当请求积压超过阈值时，新到达的请求可以屏蔽或是标记爬虫。

**优点**
- 可以削峰填谷，保护下游服务正常运行
- 并非周期性，面对持续的大规模请求可以持续屏蔽或限流，不会出现“突刺”现象

**缺点**
- 由于出桶速度恒定，无法应对短时间内的突发流量
- 部分请求会在桶中排队，响应时间拉长

目前部门接入层使用的限流策略基于漏桶算法，并对溢出的请求IP进行加权屏蔽。

### 令牌桶算法
由于漏桶算法无法应对短时间内的突发流量，出现了令牌桶算法对漏桶算法进行优化。
![](/img/pic/2019051316315036511_jpeg_431_515_18953)
> 令牌桶算法

令牌桶算法的优化点是将桶的限流部分抽离出请求流程：请求到达后需要获得令牌才能继续执行，否则屏蔽该请求或标记爬虫；而令牌由令牌工厂以恒定速度生产出来并保存在仓库。
也就是说，核心思想还是用“漏桶”来限制速度，但并非直接限制请求速度，而是多个请求可以短时间内并发获取之前未消耗完的令牌，为突发流量留了一些余地。

**优点**
- 可以应对突发流量
- 非周期性，仍然可以持续屏蔽或限流
- 获取令牌能比在桶中排队更快速地响应或反馈异常

**缺点**
- 相较于漏桶算法，在一定程度上减少了对下游服务的保护
- 漏桶算法在请求较少时不需要特殊处理，可以很方便地针对IP建立漏桶；但令牌桶算法会持续产出令牌，针对IP创建令牌桶不但会造成资源浪费，还需要防止令牌过多的情况

## 参考资料
[谈谈限流算法的几种实现 - 简书](https://www.jianshu.com/p/76cc8ba5ca91)