关键词：
应用限流
在开发高并发系统时，有三把利器用来保护系统：缓存、降级和限流：
- 缓存：缓存的目的是提升系统访问速度和增大系统处理容量
- 降级：降级是当服务出现问题或者影响到核心流程时，需要暂时屏蔽掉，待高峰或者问题解决后再打开
- 限流：限流的目的是通过对并发访问/请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理
本文仅针对限流做一些简单的说明，那么何为限流呢？顾名思义，限流就是限制流量，就像你宽带包了1个G的流量，用完了就没了。通过限流，我们可以很好地控制系统的qps，从而达到保护系统的目的。本篇文章将会介绍一下常用的限流算法以及他们各自的特点。
限流本质上是控制某段代码在一定时间内执行的次数，例如我们系统每天五点过后都有130w~140w的数据需要插入数据库，若是直接一次性插入这些数据，必将导致数据库连接被占满无法接收其他处理的请求，数据库的负载压力会瞬间飙升，甚至是压垮数据库造成雪崩现象。所以我们需要对此操作进行限流，以一个恒定的速率去插入数据，假设每秒插入400条数据，当然这个数值需要根据实际情况去设定，如此一来就可以有效控制同一时间往数据库插入的数据流不会很大，这样就不会出现上述问题了。如下图：
应用限流的常用算法：
- 计数器法
- 滑动窗口
- 漏桶算法
- 令牌桶算法
计数器法
计数器法是限流算法里最简单也是最容易实现的一种算法。比如我们规定，对于A接口来说，我们1分钟的访问次数不能超过100个。那么我们可以这么做：在一开始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个 请求的间隔时间还在1分钟之内，那么说明请求数过多；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter，具体算法的示意图如下：
具体的伪代码如下：
public class CounterDemo {
public long timeStamp = getNowTime(); // 当前时间
public int reqCount = 0; // 初始化计数器
public final int limit = 100; // 时间窗口内最大请求数
public final long interval = 1000; // 时间窗口ms
public boolean grant() {
long now = getNowTime();
if (now < timeStamp + interval) {
// 在时间窗口内
reqCount++;
// 判断当前时间窗口内是否超过最大请求控制数
return reqCount <= limit;
} else {
timeStamp = now;
// 超时后重置
reqCount = 1;
return true;
}
}
}这个算法虽然简单，但是有一个十分致命的问题，那就是临界问题，如下图：
从上图中我们可以看到，假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求，也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。
聪明的朋友可能已经看出来了，刚才的问题其实是因为我们统计的精度太低。那么如何很好地处理这个问题呢？或者说，如何将临界问题的影响降低呢？我们可以看下面的滑动窗口算法。
滑动窗口
滑动窗口，又称rolling window。为了解决计数器法统计精度太低的问题，引入了滑动窗口算法。如果学过TCP网络协议的话，那么一定对滑动窗口这个名词不会陌生。下面这张图，很好地解释了滑动窗口算法：
在上图中，整个红色的矩形框表示一个时间窗口，在我们的例子中，一个时间窗口就是一分钟。然后我们将时间窗口进行划分，比如图中，我们就将滑动窗口划成了6格，所以每格代表的是10秒钟。每过10秒钟，我们的时间窗口就会往右滑动一格。每一个格子都有自己独立的计数器counter，比如当一个请求 在0:35秒的时候到达，那么0:30~0:39对应的counter就会加1。
那么滑动窗口怎么解决刚才的临界问题的呢？在上图中，0:59到达的100个请求会落在灰色的格子中，而1:00到达的请求会落在橘×××的格子中。当时间到达1:00时，我们的窗口会往右移动一格，那么此时时间窗口内的总请求数量一共是200个，超过了限定的100个，所以此时能够检测出来触发了限流。
我再来回顾一下刚才的计数器算法，我们可以发现，计数器算法其实就是滑动窗口算法。只是它没有对时间窗口做进一步地划分，所以只有1格。
由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。
漏桶算法
漏桶算法，又称leaky bucket。为了理解漏桶算法，我们看一下对于该算法的示意图：
从图中我们可以看到，整个算法其实十分简单。首先，我们有一个固定容量的桶，有水流进来，也有水流出去。对于流进来的水来说，我们无法预计一共有多少水会流进来，也无法预计水流的速度。但是对于流出去的水来说，这个桶可以固定水流出的速率。而且，当桶满了之后，多余的水将会溢出。
我们将算法中的水换成实际应用中的请求，我们可以看到漏桶算法天生就限制了请求的速度。当使用了漏桶算法，我们可以保证接口会以一个常速速率来处理请求。所以漏桶算法天生不会出现临界问题。
具体的伪代码如下：
public class LeakyDemo {
public long timeStamp = getNowTime(); // 当前时间
public int capacity; // 桶的容量
public int rate; // 水漏出的速度
public int water; // 当前水量(当前累积请求数)
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;
}
}
}令牌桶算法
令牌桶算法，又称token bucket。同样为了理解该算法，我们来看一下该算法的示意图：
从图中我们可以看到，令牌桶算法比漏桶算法稍显复杂。首先，我们有一个固定容量的桶，桶里存放着令牌（token）。桶一开始是空的，token以 一个固定的速率r往桶里填充，直到达到桶的容量，多余的令牌将会被丢弃。每当一个请求过来时，就会尝试从桶里移除一个令牌，如果没有令牌的话，请求无法通过。
具体的伪代码如下：
public class TokenBucketDemo {
public long timeStamp = getNowTime(); // 当前时间
public int capacity; // 桶的容量
public int rate; // 令牌放入速度
public int tokens; // 当前令牌数量
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;
}
}
}若仔细研究算法，我们会发现我们默认从桶里移除令牌是不需要耗费时间的。如果给移除令牌设置一个延时时间，那么实际上又采用了漏桶算法的思路。Google的Guava库下的SmoothWarmingUp类就采用了这个思路。
我们再来考虑一下临界问题的场景。在0:59秒的时候，由于桶内积满了100个token，所以这100个请求可以瞬间通过。但是由于token是以较低的速率填充的，所以在1:00的时候，桶内的token数量不可能达到100个，那么此时不可能再有100个请求通过。所以令牌桶算法可以很好地解决临界问题。下图比较了计数器（左）和令牌桶算法（右）在临界点的速率变化。我们可以看到虽然令牌桶算法允许突发速率，但是下一个突发速率必须要等桶内有足够的 token后才能发生：
限流算法小结
计数器 VS 滑动窗口：
计数器算法是最简单的算法，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。
漏桶算法 VS 令牌桶算法：
漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法，取走token是不需要耗费时间的，也就是说，假设桶内有100个token时，那么可以瞬间允许100个请求通过。
令牌桶算法由于实现简单，且允许某些流量的突发，对用户友好，所以被业界采用地较多。当然我们需要具体情况具体分析，只有最合适的算法，没有最优的算法。
RateLimiter使用示例
Google开源工具包Guava提供了限流工具类RateLimiter，该类基于令牌桶算法(Token Bucket)来完成限流，非常易于使用。RateLimiter经常用于限制对一些物理资源或者逻辑资源的访问速率，它支持两种获取permits接口，一种是如果拿不到立刻返回false（tryAcquire()），一种会阻塞等待一段时间看能不能拿到（tryAcquire(long timeout, TimeUnit unit)）。
使用tryAcquire方法获取令牌的示例代码：
@Slf4j
public class RateLimiterExample1 {
/**
* 每秒钟放入5个令牌，相当于每秒只允许执行5个请求
*/
private static final RateLimiter RATE_LIMITER = RateLimiter.create(5);
public static void main(String[] args) {
// 模拟有100个请求
for (int i = 0; i < 100; i++) {
// 尝试从令牌桶中获取令牌，若获取不到则等待300毫秒看能不能获取到
if (RATE_LIMITER.tryAcquire(300, TimeUnit.MILLISECONDS)) {
// 获取成功，执行相应逻辑
handle(i);
}
}
}
private static void handle(int i) {
log.info("{}", i);
}
}若想保证所有的请求都被执行，而不会被抛弃的话，可以选择使用acquire方法：
@Slf4j
public class RateLimiterExample2 {
/**
* 每秒钟放入5个令牌，相当于每秒只允许执行5个请求
*/
private static final RateLimiter RATE_LIMITER = RateLimiter.create(5);
public static void main(String[] args) {
for (int i = 0; i < 100; i++) {
// 从令牌桶中获取一个令牌，若没有获取到会阻塞直到获取到为止，所以所有的请求都会被执行
RATE_LIMITER.acquire();
// 获取成功，执行相应逻辑
handle(i);
}
}
private static void handle(int i) {
log.info("{}", i);
}
}集群限流
前面讨论的几种算法都属于单机限流的范畴，但是业务需求五花八门，简单的单机限流，根本无法满足他们。
比如为了限制某个资源被每个用户或者商户的访问次数，5s只能访问2次，或者一天只能调用1000次，这种需求，单机限流是无法实现的，这时就需要通过集群限流进行实现。
如何实现？为了控制访问次数，肯定需要一个计数器，而且这个计数器只能保存在第三方服务，比如redis。
大概思路：每次有相关操作的时候，就向redis服务器发送一个incr命令，比如需要限制某个用户访问/index接口的次数，只需要拼接用户id和接口名生成redis的key，每次该用户访问此接口时，只需要对这个key执行incr命令，在这个key带上过期时间，就可以实现指定时间的访问频率。
高并发场景下常见的限流算法及方案介绍(代码片段)
...场景，比如秒杀、下单、查询商品详情，最大特点就是高并发，而往往我们的系统不能承受这么大的流量，这时候限流熔断就发挥作用了，限制请求数，快速失败，保证系统满负载又不超限。本文为大家介绍几种常见的限流算法... 查看详情
springboot-优雅的实现流控
...搞AOP用上验证源码概述限流简言之就是当请求达到一定的并发数或速率，就对服务进行等待、排队、降级、拒绝服务等操作。限流算法我们先简单捋一捋限流算法并发编程-25高并发处理手段之消息队列思路+应用拆分思路&#... 查看详情
限流和常见的三种算法
...求也只能排队等待被消费。实际上计算机是具备一定的高并发处理能力的，只要不是一直处于高并发下即可。所以计数器限流和漏洞限流折中的算法，令牌限流成为现在最主流的算法。（Redis结合expire方案可以实现)第一次请求开... 查看详情
三种常见的限流算法(代码片段)
在开发高并发系统时，有三把利器用来保护系统：缓存、降级和限流。那么何为限流呢？顾名思义，限流就是限制流量，就像你宽带包了1个G的流量，用完了就没了。通过限流，我们可以很好地控制系统的qps，从而达到保护系统... 查看详情
高并发三个方案
在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。本文结合作者的一些经验介绍限流的相关概念、算法和常规的实现方式。限流的算法常见的限流算法有：计数器、漏桶和令牌桶算法。计数器计数器是最简... 查看详情
限流及常用算法
适用场景当系统需要应用高并发的冲击时，一个最常用的策略是使用缓存提高系统容量，这通常是效果最好的方式，但如论如何提升系统容量，都会存在一个QPS/TPS的阈值，超过该阈值则认为系统不再稳定，因此需要采取措施屏... 查看详情
常见限流算法原理
限流的目的是通过限制并发访问数或者时间窗口内的请求数，保证系统在流量突增情况下的稳定性，使系统不至于被高流量击垮，一旦达到限制阈值就可以拒绝服务（告知没有资源了或定向到错误页&#x... 查看详情
常见的几种限流算法代码实现（java）(代码片段)
最近在学习Sentinel组件需要了解限流算法相关的知识，正好在微信公众号上看到了一篇不错的文章，在此记录一下以下是原文链接。年轻人，来手撸几种常见的限流算法！限流算法接口publicinterfaceRateLimiter/***判断... 查看详情
常见的几种限流算法代码实现（java）(代码片段)
最近在学习Sentinel组件需要了解限流算法相关的知识，正好在微信公众号上看到了一篇不错的文章，在此记录一下以下是原文链接。年轻人，来手撸几种常见的限流算法！限流算法接口publicinterfaceRateLimiter/***判断... 查看详情
java并发编程：synchronized及其实现原理
Java并发编程系列：Java并发编程：核心理论 Java并发编程：Synchronized及其实现原理Java并发编程：Synchronized底层优化（轻量级锁、偏向锁）Java并发编程：线程间的协作(wait/notify/sleep/yield/join)Java并发编程：volatile的使用及其原理... 查看详情
限流算法介绍（转）(代码片段)
在开发高并发系统时，有三把利器用来保护系统：缓存、降级和限流。服务限流： 流量控制本质上是减小访问量，而服务处理能力不变；而服务降级本质上是降低了部分服务的处理能力，增强另一部分服务处理能力，而访问... 查看详情
限流限流算法
在高并发系统中，我们常常提到的几个词汇“缓存”，“限流”，“降级”等。本文涉及到的是其中“限流”的部分，顾名思义，限流是一种限制流量的手段（我们可以粗粒度地理解为，限制请求的数量或者速度）。在限流特技... 查看详情
day857.高性能限流器guavaratelimiter-java并发编程实战(代码片段)
...能限流器GuavaRateLimiter的内容。GuavaRateLimiter是如何解决高并发场景下的限流问题的。Guava是Google开源的Java类库，提供了一个工具类RateLimiter。先来看看RateLimiter的使用，对限流有个感官的印象。 查看详情
day857.高性能限流器guavaratelimiter-java并发编程实战(代码片段)
...能限流器GuavaRateLimiter的内容。GuavaRateLimiter是如何解决高并发场景下的限流问题的。Guava是Google开源的Java类库，提供了一个工具类RateLimiter。先来看看RateLimiter的使用，对限流有个感官的印象。 查看详情
常见限流算法分析
背景介绍限流的目的是通过对并发访问请求进行限速或者一个时间窗口内的的请求数量进行限速来保护系统，一旦达到阈值则可以拒绝服务、排队或等待。限流，从分布式角度，可以分为分布式限流和单机限流。从算... 查看详情
常用限流算法与guavaratelimiter源码解析(代码片段)
在分布式系统中，应对高并发访问时，缓存、限流、降级是保护系统正常运行的常用方法。当请求量突发暴涨时，如果不加以限制访问，则可能导致整个系统崩溃，服务不可用。同时有一些业务场景，比如短信验证码，或者其它... 查看详情
springboot接口-如何实现接口限流之单实例(代码片段)
...示例源码#准备知识点主要的知识点，请参考架构之高并发：限流,这里小结下。#为什么要限流每个系统都有服务的上线，所以当流量超过服务极限能力时，系统可能会出现卡死、崩溃的情况，所以就有了降级... 查看详情
resilience4j源码解析：限流模块ratelimiter与常见限流算法(代码片段)
...f08;不一定都是外部的恶意攻击，也有可能是内部的高并发量接口访问调用）。在这种情况下 查看详情