0%

GuavaRateLimiter的理解

Posted on In

一. 介绍

项目中一直在使用RateLimiter进行单机的限流，但是没有去了解他的运作原理，这里就简单记录下，为以后学习Sentinal做铺垫。

这里强烈推荐酷家乐的文章《RateLimiter解析(一) ——设计哲学与快速使用》

把定积分写入技术文档我也是第一次见，实打实的说，核心部分我也没看懂。

本文仅仅讨论SmoothBursty的情况，SmoothWarmingUp先放着，因为不是很理解。

二. 个人困惑点

2.1 放令牌的时间窗口

其实在阅读源码前，自己对单机限流的工具进行了脑补，想单机限流工具的实现方案。

之前了解的方法，基本就两种，一种是漏桶，一种是令牌桶。

我比较疑惑的是令牌桶方式的放令牌的时间窗口，比如说，我设置的QPS是1分钟6000。

放令牌的时候，是每隔一分钟，丢6000个进去吗？

还是把6000个平均的分布在这一分钟的跨度内，每秒放100个进去呢？

个人理解比较合适的方式是每秒放100个进去。

因为如果你每分钟就立即放6000个进去，如果在1S内立马被消耗完了，那就剩余的59S就在那儿干等。

对于服务器而言，比如说Mysql，显然是不太合理的。

这种场景下，Mysql的QPS可能达到6000/S，如果抗过去了这1S，剩余的59S一个请求也就没有。

但是如果设置的QPS是1S6000。

那么这种放令牌的方式是怎么放呢？

每隔1S就放6000个令牌，还是再下降一个计时单位到毫秒进行发放？

如果每次的放置时间窗口都下降一个单位，再小的时间单位对于计算机而言也没有意义。

2.2 放令牌的方式

往令牌桶中放令牌的方式，是单独起一个线程，每隔一段时间醒一次，往令牌桶中放令牌吗？

这种方式看起来有点太消耗内存和CPU了。

不知道RateLimiter是怎么实现的

三. 具体实现

先来看看创建方法：RateLimiter create(double permitsPerSecond)

RateLimiter的创建方法，是个double类型的值，表示1s可以产生的令牌数。

进入doSetRate方法，注意两行代码：

1
2
double stableIntervalMicros = (double)TimeUnit.SECONDS.toMicros(1L) / permitsPerSecond;
this.stableIntervalMicros = stableIntervalMicros;

这里的stableIntervalMicros的值，就是以微秒为时间单位，计算多少微秒可以产生一个令牌。

所以这里基本上可以解答我的第一个疑惑，RateLimiter的时间窗口是微秒。

1s = 1,000millis = 1,000,000micros。

这里为什么是微秒，能不能是毫秒的单位？我其实还不是很懂。

有时间看看其他的限流器的实现

令牌桶与漏桶算法的区别就是在空闲时可以保存一部分的令牌，那么是多少个呢？

这个变量保存在SmoothRateLimiter::maxPermits中，如果看调用的话，根据是SmoothBursty还是SmoothWarmingUp是不同的，

这里我们仅仅讨论SmoothBursty的情况，因为SmoothWarmingUp实在是看不懂。

在SmoothBursty.doSetRate方法中，进行了这个值的设置，maxBurstSeconds的默认值是1s。

1
maxPermits = maxBurstSeconds * permitsPerSecond;

所以这个空闲时最多保留的令牌数就是我们构造参数传入的值。

最后来看看最后一个问题，何时放置令牌以及取令牌的过程。

说到这儿其实已经知道了，RateLimiter并没有单独启一个线程去放令牌，而是使用了取时计算的方式。

而使用这种方式也是有弊端的，就是acquire方法需要加锁：

1
2
3
4
5
6
7
8
9
10
11
12
RateLimter##acquire()
public double acquire(int permits) {
    long microsToWait = reserve(permits);
		...
  }

final long reserve(int permits) {
    checkPermits(permits);
    synchronized (mutex()) {  //加锁
      return reserveAndGetWaitLength(permits, stopwatch.readMicros());
    }
  }

取令牌时，我们要知道目前令牌桶中存有几个令牌。计算方式也比较简单，记录下上一次获取令牌的时间t，

公式：(now - t) / windowTime

就能计算出，空闲的这段时间内，产生了多少空闲的令牌。

同时记得要和maxPermits取个最小值。

这个方法在方法resync中：

方法coolDownIntervalMicros()在SmoothBursty就是上文提到的固定的时间窗口stableIntervalMicros

1
2
3
4
5
6
7
8
9
void resync(long nowMicros) {
	// if nextFreeTicket is in the past, resync to now
  if (nowMicros > nextFreeTicketMicros) {
    storedPermits = min(maxPermits,
        storedPermits
          + (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros());
    nextFreeTicketMicros = nowMicros;
  }
}

得到了获取时，当前令牌桶中有多少令牌，最后看整体的获取逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    resync(nowMicros);
    long returnValue = nextFreeTicketMicros;
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    double freshPermits = requiredPermits - storedPermitsToSpend;           // 1
    long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
        + (long) (freshPermits * stableIntervalMicros);                     // 2

    try {
      this.nextFreeTicketMicros = LongMath.checkedAdd(nextFreeTicketMicros, waitMicros); // 3
    } catch (ArithmeticException e) {
      this.nextFreeTicketMicros = Long.MAX_VALUE;
    }
    this.storedPermits -= storedPermitsToSpend; // 4
    return returnValue;
}

  1. 比较想要获取的令牌数和目前令牌桶中的令牌数量，得到除去令牌桶中的令牌数，有多少令牌还未产生，需要慢慢等待。

    比如令牌桶中只有3个令牌，而需要获取10个令牌，则需要额外的等待7个令牌的获取时间

  2. storedPermitsToWaitTime在SmoothBursty是返回的0。

    所以这里的waitMicors就是freshPermits * timeWindow

  3. 由于下面的freshPermits个令牌都被这个请求拿走了，所以下一次产生令牌的时间需要加上waitMicros

这里假设的是令牌不够的情况，那么如果空闲时间的令牌数足够的情况是呢？

比如令牌桶中有10个令牌，请求3个。

  1. freshPermits = 0
  2. waitMicros = 0
  3. nextFreeTicketMicros 不变
  4. 需要减去使用完的令牌数

四. 总结

看到这儿对RateLimiter有了大概的了解

  1. 对于存放令牌的时间窗口是微秒。
  2. 是完全公平的限流器，来请求的线程按照顺序等待。

并没有可扩展的其他复杂逻辑。比如排队多了，丢弃后续的请求，而不是一直卡在那儿等。