限流算法-Guava RateLimiter

Java-其他库 架构

TG架构笔记

漏桶算法 vs 令牌桶算法

漏桶算法(Leaky Bucket)：水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.示意图如下:

令牌桶算法(Token Bucket)：与 Leaky Bucket具有相同效果但反方向算法，系统以固定速度派发token，请求取走token后执行实际操作，当没有可领取token时，请求阻塞或拒绝，示意图如下：

两者比较下的特点：

1. 令牌桶：增加令牌速率恒定；漏桶：消费令牌恒定
2. 由于第1点，令牌桶允许一定程度的突发，而漏桶将所有的突发均平滑处理了
3. 两者算法实现可以是一样的，对于相同的参数得到的限流效果是一样的

Guava RateLimiter

api

limiter.acquire(i)：以阻塞的方式获取令牌

tryAcquire(int permits, long timeout, TimeUnit unit)：设置等待超时时间的方式获取令牌，如果超timeout为0，则代表非阻塞，获取不到立即返回

getRate()：返回RateLimiter 配置中的稳定速率，该速率单位是每秒多少令牌数

setRate(double permitsPerSecond)：更新RateLimite的稳定速率，参数permitsPerSecond 由构造RateLimiter的工厂方法提供

平滑突然限流 SmoothBursty

/**
 * 平滑突发限流：SmoothBursty
 */
@Test
public void test1() {
    //每秒允许5个请求，表示桶容量为5且每秒新增5个令牌，即每隔0.2秒新增一个令牌
    RateLimiter limiter = RateLimiter.create(5);
    /**
     * 一次性消费5个令牌，改变一次性的令牌数，会影响下一个acquire的等待时间
     * output : 0.0
     */
    System.out.println(limiter.acquire(5));
    /**
     * limiter.acquire(1)将等待差不多1秒桶中才能有第一个令牌
     * output: 0.995618
     */
    System.out.println(limiter.acquire(1));
    /**
     * 0.2秒后派发新令牌
     * output：0.2
     */
    System.out.println(limiter.acquire(1));
    /**
     * 0.2秒后派发新令牌
     * output：0.2
     */
    System.out.println(limiter.acquire(1));
    /**
     * 0.2秒后派发新令牌
     * output：0.2
     */
    System.out.println(limiter.acquire(1));
}

原理

恒定速率向令牌桶增加令牌的2种实现思路：
1、通过定时器实现，缺点：成本高
2、通过计录增加令牌的时刻，并计算请求执行的当前时间之差，获得令牌结果。类似Guava LoadingCache的缓存过期设计。

关键操作resync(long nowMicros): 通过计录增加令牌的时刻，并计算请求执行的当前时间之差，获得令牌结果

1. nextFreeTicketMicros：最近一个新增令牌到桶的时刻
2. maxPermits：最大令牌数
3. storedPermits：有效令牌书数

code:

void resync(long nowMicros) {
  // if nextFreeTicket is in the past, resync to now
  // 当前【最近一个新增令牌的时刻】已过去，则重新同步计算【nextFreeTicketMicros】与【storedPermits】
  if (nowMicros > nextFreeTicketMicros) {
    // 计算时间差内，可以新增的令牌数
    double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
    // 存量加增量令牌数 与 令牌桶总量 取较小者作为存量令牌数
    storedPermits = min(maxPermits, storedPermits + newPermits);
    // 当前时间设为 【最近一个新增令牌的时刻】
    nextFreeTicketMicros = nowMicros;
  }
}

关键参数