架构师必备：限流方案选型（原理篇）

大家好，我是Java烘焙师。上一篇文章介绍了限流方案的使用和选型，本文接着讲限流算法的原理。
常见的限流算法有：令牌桶、窗口计数、漏桶，前两种在实际使用中最常见，因此重点介绍。限流算法是通用的，既可以在单机上实现，也可以借助redis来实现分布式限流。
首先，定义一下限流算法需实现的基本功能：

• tryAquire尝试获取通行许可：立刻返回结果，true代表允许、false代表被限流
  
• aquire阻塞式获取通行许可：如果能获取到则返回，否则阻塞等待（指定超时时间，或一直等待）。当触发限流时借助java.util.concurrent.locks.Condition的await方法来阻塞等待，当恢复时通过signalAll来唤醒阻塞的线程
  

令牌桶算法

概念

• 令牌：相当于通行许可，需要多少qps或资源消耗速率，就需要获取到多少令牌
  
• 桶：决定了令牌个数上限，即处理能力上限
  
• 令牌生成速率：每秒往桶里补充多少令牌
  
• 可用令牌大小：不超过桶大小
  

令牌桶算法，类似于生产者/消费者模式。桶相当于队列，令牌相当于任务，往桶里补充令牌相当于生产者，获取令牌相当于消费者。但不用真的生成线程、队列等实体，而是通过比较请求与可用令牌的大小、以及计算下一个令牌的发放时间，来实现的。
特点

• 场景通用，允许突发流量
  
• 理解起来不够直观，但代码实现相对简单
  

关键流程

不用定时补充令牌，而是类似于懒加载的方式，在调用时重新计算可用的令牌数。
<ul>tryAquire方法：

• 先补充令牌：重新计算可用令牌数
  
• 比较可用令牌数、与请求许可数：如果前者大则扣减请求许可数、更新可用令牌数，并返回成功，否则返回失败
  

aquire方法：<ul>
如果请求许可数  0) {                condition.signalAll();            }        }    }}[/code]窗口计数算法

概念

• 时间窗口：一段时间范围，可以是秒，也可以是分钟、小时、天等。窗口限流值，就代表该时间窗口最大允许的请求数
  
• 格子：把时间窗口拆分到更细粒度，比如把1秒拆成10个100毫秒，每个格子有开始时间、结束时间
  
• 格子计数，就是格子对应时间范围的请求计数
  
• 窗口总计数，就是所有格子计数的总和
  
• 固定窗口计数：时间窗口固定，在临界情况下可能出现qps尖刺。例如：每秒限流100，在第一个1秒格子的第900毫秒请求许可80次（通过），在第二个1秒格子的第200毫秒请求许可70次（通过），但是整体看900毫秒到1200毫秒，这300毫秒内已经请求了150次，超过了限流100的阈值、存在qps尖刺
  
• 滑动窗口计数：滑动窗口有起始时间点、终止时间点，随着时间流逝一起动态往后推移，滑动窗口限流就是统计该时间范围内的请求许可是否超过阈值
  

一般用环形数组实现，数组的每个元素就是格子计数器，循环复用。
因为滑动窗口使用了更细粒度的格子，所以限流qps相对于固定窗口，会更平滑。
特点

• 追求严格的限流，不允许突发流量
  
• 理解起来容易，但是代码实现较复杂，需要维护更新格子计数
  

关键流程：

以滑动窗口计数为例，下面的关键流程是阅读代码后提炼出来的。

• tryAquire方法：
  
  
  
  • 首先更新过期的格子：把过期格子的计数清零，同时更新格子的开始、结束时间
    
  • 检查当前窗口总计数是否超过限制，是则返回false，代表被限流；否则更新当前格子的计数、以及窗口总计数，返回成功
    
  
  
• aquire方法：
  
  
  
  • 首先更新过期的格子，然后检查当前窗口总计数是否超过限制，是则计算需要等待的时间，否则更新当前格子的计数、以及窗口总计数，返回成功
    
  • 其中，计算需要等待的时间：
    
    
    
    • 至少等待的时间：当前窗口中最早的格子多久后过期，则需要至少等待多久
      
    • 至多等待的时间：如果窗口总计数减掉最早格子计数，仍然小于请求许可，说明即使最早格子过期，仍然会限流，则至多等待一个格子的时间，待下一轮循环再判断
      
    • 使用condition.awaitNanos方法，来实现阻塞等待
      
    
    
  • 上述步骤循环往复，直到满足条件
    
  
  
• 清理过期的格子时，如果发现窗口总计数小于限流值，则通知唤醒等待的线程，通过condition.signalAll()实现。
  

以下是带注释的代码示例。
[code]import java.util.concurrent.TimeUnit;import java.util.concurrent.locks.Condition;import java.util.concurrent.locks.ReentrantLock;import java.util.concurrent.atomic.AtomicInteger;import java.util.Arrays;/** * 滑动窗口限流器 - 支持非阻塞和阻塞获取 */public class SlidingWindowRateLimiter {    // 时间窗口大小（毫秒）    private final long windowSizeMs;    // 窗口内允许的最大请求数    private final int maxRequests;    // 格子数量    private final int slotCount;    // 每个格子的时间长度（毫秒）    private final long slotSizeMs;        // 滑动窗口数组，每个元素代表一个时间格子的请求计数    private final AtomicInteger[] slots;    // 每个格子对应的开始时间（毫秒）    private final long[] slotStartTimes;    // 当前窗口的总请求数    private final AtomicInteger totalRequests;        // 锁和条件变量，用于阻塞等待    private final ReentrantLock lock;    private final Condition condition;        /**     * 构造函数     * @param maxRequests 时间窗口内允许的最大请求数     * @param windowSizeMs 时间窗口大小（毫秒）     * @param slotCount 窗口分割的格子数量     */    public SlidingWindowRateLimiter(int maxRequests, long windowSizeMs, int slotCount) {        if (maxRequests