限流的定义是什么
- 限流就是对请求的速率进行限制，即限制到达系统的并发请求数，避免瞬时的大量请求击垮软件系统
限流算法有哪些？
- 计数限流
- 固定窗口限流
- 滑动窗口限流
- 漏桶算法
- 令牌桶算法
计数限流算法原理、代码、优缺点
- 原理
- 根据系统能同时处理的请求数，保存一个计数器，处理一个请求加一，处理完后减一，若超过阈值拒绝请求
- 代码
boolean tryAcquire() {
if (counter < threshold) {
counter++;
return true;
}
return false;
}
boolean tryRelease() {
if (counter > 0) {
counter--;
return true;
}
return false;
}
- 优点
- 简单粗暴，单机在 java 可用 Atomic 等原子类、分布式就 Redis incr
- 缺点
- 假设单机设的 1 万阈值，计数器为 0，若在 1 秒内收到 1 万个突发请求，可能超过机器的处理上限而导致机器崩溃
固定窗口限流算法的原理、代码、问题
- 原理
- 相比于计数限流主要是多了个时间窗口的概念，计数器每过一个时间窗口就重置，规则为：
- 1.请求次数小于阈值，允许访问并且计数器 +1
- 2.请求次数大于阈值，拒绝访问
- 3.这个时间窗口过了之后，计数器清零
- 代码
boolean tryAcquire() {
bool now = currentTimeMillis();
if (now - lastAcquireTime > TimeWindow) {
counter = 0;
lastAcquireTime = now;
}
if (counter < threshold) {
counter++;
return true;
}
return false;
}
- 问题
- 无法保证限流速率，因而无法保证突然激增的流量，会遇到固定窗口临界问题，即这个算法有时会让通过请求量允许为限制的两倍
- 如图，限制 1 秒内最多通过 5 个请求，在第一个窗口的最后半秒内通过了 5 个请求，第二个窗口的前半秒内又通过了 5 个请求。这样看来就是在 1 秒内通过了 10 个请求
滑动窗口限流算法的原理、代码
- 原理
- 1.将时间划分为多个区间
- 2.在每个区间内每有一次请求就将计数器加一维持一个时间窗口，占据多个区间
- 3.每经过一个区间的时间，则抛弃最老的一个区间，并纳入最新的一个区间
- 4.如果当前窗口内的请求计数总和超过了限制数量，则本窗口内所有的请求都被丢弃
- 代码
- 实现：记录每次请求的时间，统计每次请求的时间至往前一个时间窗口的请求数，如果小于阈值就记录这个请求的时间，反之拒绝
boolean tryAcquire() {
long now = currentTimeMillis();
long counter = getCounterInTimeWindow(now);
if (counter < threshold) {
addToTimeWindow(now);
return true;
}
return false;
}
- 优点
- 缺点
- 时间区间的精度越高，算法所需的空间容量就越大
- 无法解决短时间集中流量的突击，到流量处理不够平滑
桶漏算法的原理、实现、优缺点
- 原理
- 水滴持续漏到桶中，底部定速流出，如果桶空了则停止漏水，如果满了多余的水会被直接抛弃
- 实现
- 使用队列，服务的请求会存在队列中，服务的提供方按照固定的速率从队列中取出请求并执行，过多的请求则放在队列中排队或直接拒绝
- 优点
- 宽进严出，无论请求数量和速率多大，都能按照固定速率流出，流量处理非常平滑
- 缺点
- 当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应
令牌桶算法的原理、优缺点
- 原理
- 以固定速率生成令牌存入到令牌桶中
- 如果令牌数量超过桶的限制则直接丢弃
- 当请求到达是，会先从令牌桶中取令牌，取到了令牌的请求可以执行，如果桶空了，那么取令牌的请求会被直接丢弃
- 优点
- 能够将所有的请求平均分布到时间区间内，又能接受服务器能够承受范围内的突发请求
参考
