令牌桶与预热算法

这是英雄联盟中的机械公敌-兰博，一个驾驶着蒸汽朋克风格机甲，可以使用喷火器、鱼叉、燃烧火箭弹的约德尔机械工程师。震惊，工科男竟然站起来了，而且对你造成了成吨的魔法伤害！

兰博有整个LOL中独特的预热机制：兰博的技能都能使其获得热量。当兰博的热量达到50%时，他会处于危险温度状态，所有基础技能都会获得额外效果。当热量达到100，他会进入过热状态， 在过热状态下，兰博将在6秒内无法释放技能。如果兰博长时间不释放技能，那么机甲的温度就会缓慢的下降，兰博将失去危险温度下的技能伤害加成，换句话说，兰博脱离了最佳状态。因此在需要消耗敌人的场景下（比如：嚎哭深渊），要将机甲维持在危险温度，已获得最大的伤害输出。

和兰博的蒸汽机甲类似，“预热”(Warm Up)一词广泛的出现在工科领域和.....健身领域，其基本表现都是：都是运行机器一段时间，已使其达到最大性能的状态。

例如：

1. 在冬天提前发动汽车，让引擎充分被汽油润滑，并且让暖气拯救你冻僵的手指。
2. 在进行大重量的健身运动之前，充分活动关节，避免受伤。
3. 推荐系统中，对于新用户的画像没有历史数据参考，一般先改为推荐热门数据，在用户产生足够的在线行为之后，更换为推荐个人数据。
4. 在阿里云的企业级分布式应用服务（EDAS）中，有个限流降级规则：预热启动。使系统避免被突发的高水平流量搞崩溃。

Sentinel中的流控组件中也有一个预热模式，和EDAS限流规则中的“预热模式”近乎相同。而这个算法又声明是参考了Guava中的算法。那我们就从这个“鼻祖算法”开始看起，接下就是枯燥无味的代码环节了，带上你的老干妈，一起看源码。

令牌桶

额，等下，在开始之前，我们需要先了解一下什么是令牌桶

令牌桶算法可以描述如下：

• 每 1/r1/r1/r 秒向桶中添加一个令牌。
• 该桶最多可以容纳 bbb个令牌。 如果桶满时令牌到达，则将令牌丢弃
• 当一个需要消耗nnn个令牌的请求到达时：
  • 如果桶中至少有nnn个令牌，则从桶中取出nnn个令牌，放行请求。
  • 如果可用的令牌少于nnn个，进行限流处理。

对于请求的限流处理有哪些可能的方式呢：

1. 它们将被丢弃
2. 当桶中积累了足够的令牌时，它们可能会被排入队列以进行后续传输。
3. 它们可能会被传输，但被标记为不合格，如果网络过载，可能随后会被丢弃。

这就是令牌桶。那么之前我们已经介绍了漏桶(Leaky Bucket)，漏桶有两种版本：流量计和队列。那令牌桶和漏桶（流量计和队列版本)有什么关系呢？

漏桶（队列版）是特殊的漏桶（流量计版）。而令牌桶则是形式上倒放版的漏桶（流量计版），哎~就是诺兰电影《信条》那味儿。三者在流量监控、流量整型中可以发挥大同小异的作用。

令牌桶的变化过程

这个时候，聪明的小伙伴就会问了：你不是来讲预热算法的咩？令牌桶很好理解，但是这和预热算法有什么关系。

说的不错，其实Guava的预热算法底层正是基于令牌桶的模型实现的，而实现的关键是"变化的请求等待时间"。现在不明白没有关系，只要记住这个结论就可以了，当你看完令牌桶算法的变化过程，你大概就理解了。

版本0：原始令牌桶

第一：对于一个以每秒产生rrr个令牌的令牌桶，假设每个请求到达时需要获取nnn个令牌，而如果此时令牌桶中剩余mmm个令牌时，怎么办？

假设在t0t_0t0​时刻，这个请求（假设为A）只能等待WaitTime={0m>=nn−mrm<nWaitTime =\begin{cases} 0 & m >= n \\ \frac{n-m}{r} & m<n \end{cases}WaitTime={0rn−m​​m>=nm<n​ 秒，再被处理。 盲生，你发现华点了吗？

当令牌桶中当前令牌数量满足条件m>nm > nm>n时，请求将直接被放行。看起来没什么问题。

我们举一个例子：假设在令牌桶中的令牌数m=5∗n+1m = 5*n + 1m=5∗n+1的时间点t0t_0t0​，同时来了6个请求，会发生什么情况？

6个请求中会有5个请求（不分顺序）被直接放行，还有一个请求需要等待 n−1r\frac{n-1}{r}rn−1​秒。其中，对于"同时通过"的5个请求，就是此时限流器的突发性，我们知道 Max(m)==令牌桶的容量b Max(m) == 令牌桶的容量bMax(m)==令牌桶的容量b，因此bbb就是你查询资料时，经常碰到的**突发容限(burst tolerance)**概念，可以说bbb就是衡量这个令牌桶突发性的指标。

另一方面，只有在令牌桶中的令牌数量mmm在被消耗到一定水平之后，即m∈[0,n) m \in [0,n)m∈[0,n)时，才能对未来的请求实行限流，让它们乖乖等着，可以给此时的流量状态定义为"平均流量水平"。而这个平均流量水平等于多少？考虑一个“一滴也没有了”的消耗过度的令牌桶，即m=0m = 0m=0时，每一个消耗nnn令牌的请求就需要nr\frac{n}{r}rn​秒来等待令牌生产，"平均流量水平"就是它的倒数：rn\frac{r}{n}nr​ （单位：QPS 请求/秒）。

这就是令牌桶怎么限流的：通过令牌生产效率影响请求的等待时间，进而影响流量的QPS。

版本1：突发型令牌桶

进阶版1：平滑突发性限流，就是Guava中的SmoothBursty类，它在原始的令牌桶上做了一些小变动，例如，允许”透支令牌"。

原始版本中提到了到达平均流量水平时，请求都需要等待？说到等待，他怎么实现的，我产生一种看到在平行世界中熊猫馆门口排队的"小T"的既视感？

没错，如果看了Guava中的SmoothRateLimiter类的实现（不要慌，它是SmoothBursty的父类，定义了整个平滑限流的基础功能），你会发现一个类似“检票口”的属性：SmoothRateLimiter#nextFreeTicketMicros。

	abstract class SmoothRateLimiter extends RateLimiter {
       /**
	 * The time when the next request (no matter its size) will be granted. After granting a request,
	 * this is pushed further in the future. Large requests push this further than small requests.
	 * could be either in the past or future
	 */
	private long nextFreeTicketMicros = 0L;
  }

如代码注释所说：这个属性代表了下一个请求被授权通过的时间，当一个请求被授权之后，这个请求会向未来推进。他就像一个定时开放的闸门一样，记录了下一个请求被准许通过的时间。如果小伙伴看过上一篇《漏桶算法与虚拟队列》的话，就会脱口而出：“虚拟队列！原来你搁这藏着呢！换了马甲我就不认识你？”，真相是：是也不是。为什么？

前者功能更加丰富

1. Guava的实现可以计算令牌增量：SmoothRateLimiter 通过计算nextFreeTicketMicros和当前时间的差值来计算这段时间内需要添加令牌。查看SmoothRateLimiter#resync方法：

      void resync(long nowMicros) {
            // if nextFreeTicket is in the past, resync to now
            if (nowMicros > nextFreeTicketMicros) {  // 代码A
                double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros(); // 代码B
                storedPermits = min(maxPermits, storedPermits + newPermits); // 代码C
                nextFreeTicketMicros = nowMicros; // 代码D
            }
      }
   

   • 代码A :  如果请求到达的时间nowMicros 大于 nextFreeTicketMicros，则说明距离上次请求已经过去了一段足够时间，令牌桶在此期间处于闲置状态，应该为令牌桶添加令牌了。
   • 代码B：计算令牌桶在这个时间差内应该产生多少个令牌，coolDownIntervalMicros()方法返回的是令牌桶生产令牌的时间间隔，不论哪种令牌桶（包括当前的"平滑突发型"和还没讲到的"平滑预热型"）。
   • 代码C:  取maxPermits和新增后令牌数量的最小值，防止令牌数溢出。
   • 代码D:  将当前请求的通过时间进行更新，此时的nextFreeTicketMicros的取值就是当前请求的执行时间。

2. 如果请求到达时间(nowMicros) 小于 nextFreeTicketMicros时间，代表当前令牌桶处于平均流量水平，也就是后续请求都需要等待，才会导致nextFreeTicketMicros一直向未来推进。

3. nextFreeTicketMicros的功能和虚拟队列中的记录的时间戳功能类似，都是影响请求被准许通过的时间。但是前者最终记录的是下一个请求赋予通过的时间，而虚拟队列中的时间戳对于每一个请求来说，是自己被允许通过的时间。这个区别也是实现"透支令牌"的关键。

突发容限

虚拟队列是没有“突发容限”的，即使并发的请求一瞬间将虚拟队列填满，也没有请求可以从“贵宾通道”先走，而是需要抢占一个原子性的时间锁，抢到时间锁的线程可以先执行；令牌桶则不同，当令牌充足时，可以不用等待直接通过，只有令牌不足时才会产生等待，像极了和小伙伴们去吃自助餐时等出锅的样子。为什么会这样，前面不是说令牌桶不是和漏桶一样，只有形式不同而已？虚拟队列的本质是漏桶（队列版），而令牌桶的本质是漏桶（计量器）版，他们 的不同，其实也是漏桶的两个版本之间的不同。

溢出处理不同

虚拟队列定义了队列的长度，当并发的请求过多时，请求们会因为等待时间过长而被降级（定义为不合格） ，而令牌桶则没有这样的限制，一些没有获得令牌的“倒霉”请求们可以无限期的沉睡下去。

---

第二：为什么要规定一个请求要消耗nnn个令牌？一个请求不能只消耗一个令牌吗？nnn代表了什么？

nnn代表的其实是请求的权重，或者这个请求需要消耗的资源：在交换机里他可能代表一个信元的字节大小，在服务器上他可能代表一个网络请求的平均耗时，在机械公敌-兰博的实现代码里它可能代表每放一个技能所产生的“热量”值。nnn的取值可以是变化的，而令牌桶的平均流量水平=rn平均流量水平=\frac{r}{n}平均流量水平=nr​，在生产速率不变的情况下，nnn的变化影响平均流量水平。

令牌透支

第三：如果对于一个r=1r =1r=1的令牌桶，在于某一时刻，令牌桶中只有5个令牌，而接踵而至的请求是一个需要消耗100个令牌的请求（比如某个I/O频繁的请求），怎么办？让这个请求等待95秒吗？

这么做也许符合原始令牌桶算法的定义，但是多少有点浪费了（在请求等待的95秒内，系统并没有在处理这个请求，反而要在无所事事95秒后，面临和后续请求并发执行的窘境，虚拟队列的实现就有这个问题）。

Guava中的SmoothRateLimiter允许请求在申请令牌时进行"透支"：不论当前剩余多少令牌，请求就会被放行，而等待令牌桶产生足够令牌的时间则由后面的请求承担。

对于一个请求，假设上一个请求透支的令牌数为ccc，当前请求等待的时间其实满足这个公式: WaitTime={0c=0crc>0WaitTime = \begin{cases} 0 & c = 0 \\ \frac{c}{r} & c > 0 \end{cases}WaitTime={0rc​​c=0c>0​ ，只要上一个请求没有透支令牌，当前请求立刻执行。这个公式或许大变样了，但其实是一个含义：ccc 的取值是上一个请求通过时的 ∥m−n∥ \| m - n \|∥m−n∥（透支令牌数）。SmoothRateLimiter只是将请求到达时需要计算的请求等待时间改为由上一个请求通过时的nnn和mmm决定。

有点意思， 怎么实现的？

查看代码SmoothRateLimiter#reserveEarliestAvailable((int permits, long nowMicros) 如何实现“令牌透支”。

代码1-1 如何实现令牌透支

abstract class SmoothRateLimiter extends RateLimiter {	
  // ....
    @Override
    final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
        resync(nowMicros); // 代码A
        long returnValue = nextFreeTicketMicros; // 代码B
        double storedPermitsToSpend = min(requiredPermits, this.storedPermits); // 代码C 
        double freshPermits = requiredPermits - storedPermitsToSpend;  // 代码D
        long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) // 代码E
                                + (long) (freshPermits * stableIntervalMicros);  // 代码F。
        this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros); // 代码G
        this.storedPermits -= storedPermitsToSpend; // 代码H
        return returnValue; // 代码B-1
    }
  // ....
}

• 代码A: 还记得resync(nowMicros)方法吗？上面讲过resync的作用是当令牌桶处于闲置状态时，他可用来补充令牌。
• 代码B & B-1: 当前请求的执行时间其实是由上一个请求决定的，而这个决定的程度则体现在代码B~代码B-1之间。
• 代码C: 计算本次请求实际消耗的令牌数，取最小值是为了防止请求的令牌数过大，导致桶中令牌数小于0。
• 代码D: 计算当前请求需要透支的令牌数：当requiredPermits > this.storedPermits 时，freshPermits 即等于透支的令牌数。
• 代码E: 计算当前令牌数对等待时间的影响，SmoothBursty固定返回0，只有预热限流器才会计算这个值（这就是预热限流与突发性限流最大的不同）。如下代码所示

static final class SmoothBursty extends SmoothRateLimiter {		
    // ....
    @Override
    long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
        return 0L;
    }
    // ....
}

• 代码F: 计算偿还透支令牌所需要等待的时间：stableIntervalMicros是令牌桶在稳定状态下的令牌生产间隔，等于1r\frac{1}{r}r1​。freshPermits*stableIntervalMicros就等于请求偿还透支令牌的时间。
• 代码G: 这是实现令牌透支的关键：将需要等待的时间转嫁到下一个请求上。结合代码B, 下一个请求将直接取当前请求计算出来的nextFreeTicketMicros。
• 代码H: 消耗令牌。

---

第四: 最后一个问题。在任意时刻，令牌桶中的令牌数量代表了什么？

直觉性的想法是，代表了未来流量能被允许的突发性！没错，这正是版本0：原始令牌桶的第一点想要告诉你的，但是，令牌数还有另一个含义，它还可以指明过去流量的闲置的程度：因为只有请求的通过能消耗令牌数，而令牌数则按照稳定生产速率增加。

因而令牌数慢慢累积增加，则说明流量从过去到现正在逐渐减少（Guava源代码中将这个概念称为“underutilization”，用storedPermits属性建模，没有字典翻译，粽子姑且将其称为“闲置度”）。这个闲置度在“平滑突发型令牌桶”中并没有起作用（不论闲置度如何，突发性限流器固定返回等待时间为0，参看第三点的代码E），而在“预热型令牌桶”中，闲置度将直接影响请求的等待时间，进而影响请求的QPS。

版本2：预热型令牌桶

他来了他来了，预热算法走来了，前面讲了这么多？不知道你理解了多少呢，下面的知识将在这个基础上涉及到：积分（幼儿版），准备好了吗。

先总结一下前面所说的两个版本：

1. 版本0: 原始令牌桶告诉我们：通过令牌生产效率影响请求的等待时间，进而影响流量的QPS。扩展一下：限流的基本实现方式，是通过控制请求的等待时间，进而控制QPS。
2. 版本1: 突发型令牌桶的实现将闲置度对请求等待时间的影响设置为0，但是如果遵循”系统闲置越久，越需要从低QPS的水平处理请求，并慢慢提升QPS，直到稳定水平"的算法需求，即得出：闲置度越高，请求的等待时间越高，一旦闲置度低于某个阈值，则请求等待的时间不再变化，系统处于平稳水平。

有了上面两点，就可以尝试理解Guava的SmoothWarmingUp 限流算法了！

首先，Guava算法将请求的通过间隔和令牌数之间的关系符合下图:

          ^ throttling
          |
     cold +                  /
 interval |                 /.
          |                / .
          |               /  .   
          |              /   .      ← "warmup period" is the area of the trapezoid between threshold and max
          |             /    .
          |            /     .
          |           /      .
   stable +----------/  WARM .
 interval |          .   UP  .
          |          . PERIOD.
          |          .       .
        0 +----------+-------+--------------→ storedPermits
          0     threshold   max

解释模型

纵坐标：throttling(限制)，代表令牌桶对流量的放行间隔（单位:秒/令牌），即一个令牌桶将以多大的时间间隔发放一个令牌（注意，他的倒数就是QPS）。有些资料认为纵坐标是令牌的生产间隔，其实令牌的生产间隔不变：查看SmoothRateLimiter#coolDownIntervalMicros()可知。当然，在throtting达到稳定水平stable intervale时，这个值在数值上等于令牌的生产间隔，但含义完全不同。

横坐标：storedPermits(桶中当前令牌数)，当storedPermits∈[threshold,max]storedPermits \in [threshold, max] storedPermits∈[threshold,max]时，令牌桶被定义为处于预热状态。随着令牌的消耗，令牌桶对请求的限制逐渐放宽，当storedPermits∈[0,threshold]storedPermits \in [0, threshold]storedPermits∈[0,threshold] 时, 令牌桶达到稳定水平，将按照stable interval的固定间隔（也就是最大允许QPS）放行一个令牌。在令牌桶处于稳定水平时，如果后续请求逐渐减少，那么桶中令牌又会逐渐累积，又返回到预热状态，如此循环往复。

突发容限

预热型令牌桶的突发容限呢？当桶中令牌数到达max的时候，throttling 最大，允许通过的QPS最小，怎么和你前面讲到的令牌桶容量越大，突发容限越大相矛盾呢？

没错，以这种根据当前令牌数调整请求等待时间的方式，所实现限流的预热型令牌桶是没有突发容限的。我们参看代码1-1的代码E和代码F，一个请求到达时，需要计算的 等待时间 = 受令牌数影响的时间 + 生产透支令牌数的时间 。 如果是SmoothBursty的话，受令牌数影响的时间（也就是storedPermitsToWaitTime方法的返回值）固定是0，所以对于SmoothBursty而言，只要令牌桶中尚有足够的令牌（此时，生产透支令牌数的时间也是0），请求通过的等待时间就是0，也就存在突发性。而对于SmoothWarmingUp， 受令牌数影响的时间永远不会为0，所以每一个请求到达时，都会计算出一个等待时间，只不过这个等待时间被转嫁到下一个请求了，就整体来看，通过SmoothWarmingUp的请求是没有并发通过请求的能力的。

等待时间

这个模型很好，是某种阶梯函数，代表桶中有x个令牌时，令牌桶将间隔y秒放行一个令牌 ，看出了。那么请问，一个请求的等待时间在哪里？你明白我的意思吗？例如当桶中的令牌数 = max 时，一个需要消耗3个令牌的请求需要等待多久？

首先：预热型令牌桶桶也是支持令牌透支的（所有令牌透支的逻辑都在SmoothWarmingUp和SmoothBursty的父类SmoothRateLimiter中定义），严谨来说，应该是需要下一个请求等待多久，为了方便，可以直接说当前请求等待多久，这样比较符合直觉。

第二：这是一个很好的问题，纵坐标throttling的单位是：时间/令牌，横坐标storedPermits的单位是令牌，他们相乘的结果就是时间。所以呢？假设用一个函数表示throttling=f(storedPermits)throttling = f(storedPermits)throttling=f(storedPermits)， 那么storedPermits从max到max - 3所需要等待时间就等于定积分 ∫max−3maxf(x) dx\int_{max-3}^{max} {f(x)} \,{\rm d}x∫max−3max​f(x)dx 。你不要被积分吓到，可以举一个不是很恰当的例子来类比：假设有小鸟的速度-时间函数，按时间求定积分即两个时间点小鸟飞过的距离，两者是一个道理: 积分的含义来源于单位的运算。

为什么要使用积分表示？

根据SmoothRateLimiter类中的设计注释：

Using integrals guarantees that the effect of a single acquire(3) is equivalent to {acquire(1); acquire(1); acquire(1); }, or { acquire(2); acquire(1); }, etc, since the integral of the function in [7.0, 10.0] is equivalent to the sum of the integrals of [7.0, 8.0], [8.0,9.0], [9.0, 10.0] (and so on), no matter what the function is. This guarantees that we handle correctly requests of varying weight (permits), /no matter/ what the actual function is - so we can tweak the latter freely. (The only requirement, obviously, is that we can compute its integrals).

使用积分可以保证一个消耗3令牌（acquire(3)）的请求的影响和 3个消耗1令牌的请求（或1个消耗2令牌请求 + 1个消耗3令牌的请求）的效果相同。换句话说，使用积分的设计可以保证，在与具体关系函数解耦的前提下，将不同权重（消耗的令牌数）的请求所导致请求等待时间的差异抹平。即，不论具体的令牌-放行间隔函数关系是什么（水平线，上斜线，下斜线，曲线），在相同初始条件下，一个大权重的请求所导致的等待，与通过多个小权重请求的总体等待时间相等，整体来看，或许请求数量不满足流量控制条件，但是令牌的消耗却是在控制范围之内。

再返回Guava给出的模型，看到标记着“WARM UP PERIOD” 的梯形了吗？这个梯形的面积，就是令牌桶的“预热时长”，也就是定积分∫thresholdmaxf(x) dx\int_{threshold}^{max} {f(x)} \,{\rm d}x∫thresholdmax​f(x)dx的值。

看实现代码

很好，现在来看代码SmoothWarmingUp#storedPermitsToWaitTime来怎么计算这个积分（a.k.a如何根据闲置度计算等待时间）

代码1-2.如何根据闲置度计算等待时间

static final class SmoothWarmingUp extends SmoothRateLimiter{
  	// .....
        @Override
        long storedPermitsToWaitTime(double storedPermits, double permitsToTake) {
            double availablePermitsAboveThreshold = storedPermits - thresholdPermits; // 代码A
            long micros = 0;
            // measuring the integral on the right part of the function (the climbing line)
            if (availablePermitsAboveThreshold > 0.0) { // 代码B
                double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake); // 代码C
                double length = permitsToTime(availablePermitsAboveThreshold) + 
                    permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake); // 代码D
                micros = (long) (permitsAboveThresholdToTake * length / 2.0); // 代码E
                permitsToTake -= permitsAboveThresholdToTake; // 代码C-1
            }
            // measuring the integral on the left part of the function (the horizontal line)
            micros += (long) (stableIntervalMicros * permitsToTake); // 代码F
            return micros; // 代码G
        }
	  // .....
  	private double permitsToTime(double permits) {
            return stableIntervalMicros + permits * slope;
        }
}

SmoothWarmingUp中此方法返回的等待时间受storedPermits和permitsToTake两个值影响。

• 代码A: 计算阈值之上的令牌数，也就是模型中threshold右侧的部分。
• 代码B: availablePermitsAboveThreshold > 0.0 代表的是当前令牌桶处于预热状态。因而需要计算梯形面积。
• 代码C & 代码C-1: 保证当前的积分属于阈值右侧部分，如果一次性获取的令牌数会导致storedPermits小于阈值，则分段计算梯形和矩形的面积，可以参看代码F。
• 代码D、代码E: 计算梯形面积。假设当前令牌数为a， permitsToTime(availablePermitsAboveThreshold)方法返回的就是梯形的下底，permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake); 返回的则是梯形的上底。 permitsToTime方法可以将超出阈值的令牌转换成时间间隔：stableIntervalMicros+横坐标∗斜线斜率stableIntervalMicros + 横坐标 * 斜线斜率stableIntervalMicros+横坐标∗斜线斜率 。如下图蓝色区域所示：

• 代码F、代码G：处理一次性获取令牌数量过多的场景，导致令牌数低于threshold的场景，即下图所示中的绿色部分，不再赘述。代码G返回等待时间在代码1-1中被添加到nextFreeTicketMicros属性中，等待时间转嫁到下一个请求中。

现在，让我们在返回代码1-1中的代码E，你理解了咩？预热算法根据令牌桶中剩余的令牌数量和请求动态调整nextFreeTicketMicros的推进步长，进而实现了对流量QPS的控制。

算法初始化

我发现你这个人真的很奇怪，算法讲完了再讲初始化？

前文介绍的是预热算法的概念，至于一些初始化参数，只要你指定了模型中的 stable interval / cold interval / threshold / max 四个值，你在理解核心的基础上，完全可以用自己的方式实现初始化。最后才开始说明，这里主要就是阐明一下Guava中的思路，如果你想自己在源码中遨游一下，可以参照我指出的顺序查看。

另外此处也有我学习时查看的源码解析资料，都写的非常好，可以一起查看(代码版本略有不同，注意分辨):

1. 理解Guava Ratelimiter SmoothWarmingUp实现原理
2. 谷歌Guava限流工具RateLimiter

实例化

static final class SmoothWarmingUp extends SmoothRateLimiter {
    private final long warmupPeriodMicros;
        /**
         * The slope of the line from the stable interval (when permits == 0), to the cold interval
         * (when permits == maxPermits)
         */
        private double slope;

        private double thresholdPermits;

        private double coldFactor;

        SmoothWarmingUp(SleepingStopwatch stopwatch, long warmupPeriod, TimeUnit timeUnit, double coldFactor) {
                super(stopwatch);
                this.warmupPeriodMicros = timeUnit.toMicros(warmupPeriod);
                this.coldFactor = coldFactor;
        }
    // ...
}

• 代码A: 初始化令牌数。
• 代码B: 设置令牌生产间隔，permitsPerSecond代表每秒生产多少令牌，取倒数，求出令牌的生产间隔
• 代码C: 设置子类的特性参数。我们聚焦到子类SmoothWarmingUp的实现。

static final class SmoothWarmingUp extends SmoothRateLimiter {
    // ....
    void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
        double oldMaxPermits = maxPermits; // 代码A
        double coldIntervalMicros = stableIntervalMicros * coldFactor; // 代码B
        thresholdPermits = 0.5 * warmupPeriodMicros / stableIntervalMicros; // 代码C 
        maxPermits = thresholdPermits + 2.0 * warmupPeriodMicros / 
            (stableIntervalMicros + coldIntervalMicros); // 代码E
        slope = (coldIntervalMicros - stableIntervalMicros) / 
            (maxPermits - thresholdPermits); // 代码F
        if (oldMaxPermits == Double.POSITIVE_INFINITY) {
            // if we don't special-case this, we would get storedPermits == NaN, below
            storedPermits = 0.0;
        }
        else {
            storedPermits = (oldMaxPermits == 0.0) ? maxPermits // initial state is cold  // 代码G
                : storedPermits * maxPermits / oldMaxPermits;
        } 
        //...
    }
}

• 代码A & 代码G ：代码A中maxPermits尚未赋值，配合代码F~代码G 将预热型限流器的初始化令牌数设置为代码E中计算出来的最大值。

• 代码B: 通过冷却系数和 stableIntervalMicros，计算出冷却时（storedPermits = max )时的最大通过间隔 coldIntervalMicros。

• 代码C: 计算storedPermits 中预热状态到平稳状态阈值thresholdPermits，因为模型中左侧矩形的面积满足thresholdPermits∗stableIntervalMicrosthresholdPermits * stableIntervalMicrosthresholdPermits∗stableIntervalMicros。注意！从代码中可以看出，Guava中强行规定左侧矩形面积是右侧梯形面积的0.5倍，与coldFactor的取值无关。这可能与查找资料时看到的说明会有不同，注意分辨。另外在Sentinel中实现预热模式时，coldFactor参与了thresholdPermits的计算，后面我们将会看到。

• 代码E: 计算令牌桶中最大的令牌数量:2.0∗warmupPeriodMicros(stableIntervalMicros+coldIntervalMicros)\frac{2.0 * warmupPeriodMicros}{ (stableIntervalMicros + coldIntervalMicros)}(stableIntervalMicros+coldIntervalMicros)2.0∗warmupPeriodMicros​ 代表是在知道：

  1. 梯形面积(warmupPeriodMicros)
  2. 上底+下底的和(stableIntervalMicros + coldIntervalMicros)

  的情况下，计算梯形的高。也就是threshold ~ max之间的距离。

• 代码F: 计算右侧上斜线的斜率。

至此，Guava中的SmoothWarmingUp的预热算法已经介绍完毕。更多的细节可以参看给出的两个链接，里面有更详细的介绍。

Sentinel的预热限流

Sentinel在实现预热限流时参考了Guava的实现，但是在此基础上，又做了一定程度上的变更。

Guava有两个参数需要处理并发：

1. storedPermits（令牌桶中当前令牌数）
2. nextFreeTicketMicros（下一个请求的通过时间）

如果Sentinel每次放行请求都对这两个参数进行CAS操作的话，会对应用程序带来性能上的影响。

Sentinel怎么做的：

1. Sentinel将对令牌数量的控制频率限制在一秒一次；
2. Sentinel完全去除了nextFreeTicketMicros属性：Guava是通过控制时间间隔（单位: 时间/令牌数）实现限流，Sentinel预热算法则是通过控制QPS（单位：令牌数/时间）

总的来说，Sentinel的实现方案比Guava更加直观易懂。并不是“踩一捧一”，产生这种差异，主要是因为Sentinel对请求的数据结构设计而带来的便利性，而Gauva作为一个工具类框架侧重于使用便利性。

算法描述

Sentinel记录了一个资源一秒内请求的数量，即当前秒的QPS。所以Sentinel在实现预热限流时，只需要满足如下条件：

1. 当通过请求时，比较当前秒内的QPS是否小于当前令牌数所限定的最大允许QPS，
2. 如果小于，直接放行请求。
3. 否则进行降级。

看到不同点了吗？Sentinel不需要对满足条件2的请求做时间间隔上的限制，这意味着Sentinel不需要维护一个类似于nextFreeTicketMicros一样的“闸机口”的属性，它在使用预热算法的基础上竟然还允许秒级内的突发请求！

怎么会这样？你前面讲预热算法不存在突发性的呢！你这个骗子！

没关系，我还没讲到Sentinel中预热限流的“本命桶”，你以为Sentinel中预热限流的本质是上面讲到版本2：预热型令牌桶？事实上：

它是按照桶中令牌数量，以一秒一次的频率动态调整容量的版本0：原始令牌桶。在特定的一秒内，Sentinel中的令牌数不会改变，Sentinel根据计算前一秒的令牌消耗之后，再定出当前秒的最大允许通过QPS，相当于同步生成一个容量 = 最大允许通过QPS的虚拟令牌桶。 每当通过一个请求时，就只需要比较虚拟令牌桶中的令牌是否足够，如果足够就放行请求。在下一秒来临后的第一个请求，又将当前秒的虚拟令牌桶中消耗的令牌数，反馈到下一秒的“母桶”上，同时生成一个新容量的虚拟令牌桶。突发性的来源就是这个。

令人印象深刻！那么，代价是什么？

代价是第三点：在任意一秒内，超出最大允许QPS（虚拟令牌桶容量）的请求将被降级，也就是说一部分的请求被抛弃了，  而Guava则不会抛弃任何一个请求，任劳任怨地安排请求们排排坐，食果果，多久都等下去。这两种策略并没有好坏之分，只是场景使然。

实现代码

Sentinel中的预热限流的实现类是WarmUpController（又是源码环节！没关系，你只需要在前面所讲的基础上将时间间隔的概念转换成倒数QPS 就会很好理解）。

初始化

public class WarmUpController implements TrafficShapingController {
    //....
    private void construct(double count, int warmUpPeriodInSec, int coldFactor) {
        if (coldFactor <= 1) {
            throw new IllegalArgumentException("Cold factor should be larger than 1");
        }
        this.count = count; // 代码A
        this.coldFactor = coldFactor; 
        warningToken = (int)(warmUpPeriodInSec * count) / (coldFactor - 1); // 代码B
        maxToken = warningToken + (int)(2 * warmUpPeriodInSec * count / (1.0 + coldFactor)); // 代码C
        slope = (coldFactor - 1.0) / count / (maxToken - warningToken); // 代码D
    }
    //....
}

• 代码A: count代表限流控制器在稳定运行状态时的QPS，倒数1QPS\frac{1}{QPS}QPS1​和版本2:预热型令牌桶中模型中的纵坐标（throttling）中的stable interval的值相同。
• 代码B: 计算阈值的令牌数。warmUpPeriodInSec 代表规定的预热时长，也等于模型侧梯形面积。而warmUpPeriodInSec(coldFactor−1)\frac{warmUpPeriodInSec}{(coldFactor - 1)}(coldFactor−1)warmUpPeriodInSec​代表模型中左侧矩形面积。可以看到，Sentinel和Guava的不同，Guava是硬编码矩形面积是梯形面积的1/2，而在Sentinel中这个面积的比值由coldFactor决定，当coldFactor = 3时，在Sentinel中才构成两倍关系。在Guava中，面积除以1count\frac{1}{count}count1​，就是稳定状态下的阈值数。
• 代码C: 计算最大令牌数，最大令牌数等于梯形的底边+梯形的高，这里不在赘述。
• 代码D: 计算梯形斜边的斜率，和Guava中相同，只不过从时间间隔换成了QPS，注意分辨。

限流校验

public boolean canPass(Node node, int acquireCount, boolean prioritized) {
    long passQps = (long) node.passQps(); // 代码A
    long previousQps = (long) node.previousPassQps(); // 代码B
    syncToken(previousQps); // 代码C
    long restToken = storedTokens.get(); //代码D      
    if (restToken >= warningToken) { // 代码E
        long aboveToken = restToken - warningToken;
        double warningQps = Math.nextUp(1.0 / (aboveToken * slope + 1.0 / count)); // 代码F
        if (passQps + acquireCount <= warningQps) { // 代码G
            return true;
        }
    } else { // 代码H
        if (passQps + acquireCount <= count) {
            return true;
        }
    }
    return false;
}

• 代码A: 返回Sentinel记录的当前秒内通过的请求数（Sentinel对资源的统计用Node对象承接，内部的数据结构设计也非常精妙，有机会会详细介绍）
• 代码B: 返回上一秒通过的请求数。
• 代码C: 将上一秒通过的请求数同步到母桶，更改它的令牌数，这个方法在一秒内只会执行一次。因此代码D的restToken在一秒内都不会变化。
• 代码D: 返回母桶中的令牌数。
• 代码E: 如果母桶令牌数大于阈值，系统处于预热阶段。
• 代码E~F: 根据母桶超出阈值的令牌数，计算此时应该创建的虚拟令牌桶的容量：aboveToke * slop + 1.0 / count 就是此时限流器应该放行请求的最小间隔，求倒数就是当前秒内虚拟令牌桶的容量。
• 代码G: 判断已经通过的请求数量是否足够消耗虚拟令牌桶中的令牌数量，如果足够，放行请求。
• 代码H: 如果没有超出阈值，就虚拟化出一个最大允许QPS的令牌桶，判断通过当前请求后是否超出此虚拟令牌桶，如果足够，放行请求。

秒级令牌更新

public class WarmUpController implements TrafficShapingController	{
    //...
    protected void syncToken(long passQps){
        long currentTime = TimeUtil.currentTimeMillis(); // 代码A
        currentTime = currentTime - currentTime % 1000;
        long oldLastFillTime = lastFilledTime.get();
        if (currentTime <= oldLastFillTime) {
            return;
        } // 代码B
        long oldValue = storedTokens.get(); 
        long newValue = coolDownTokens(currentTime, passQps); // 代码C
        if (storedTokens.compareAndSet(oldValue, newValue)) { // 代码D
            long currentValue = storedTokens.addAndGet(0 - passQps); // 代码E
            if (currentValue < 0) {
                storedTokens.set(0L);
            }
            lastFilledTime.set(currentTime); // 代码F
        }
    }
    //..
}

• 代码A~代码B: 保证下方更新令牌桶的算法一秒内只执行一次，因为每次更新令牌桶中的令牌数后，lastFilledTime就会记录当时的时间戳(到秒级)，一旦判断当前秒相同或更晚，方法就会返回，令牌桶中的令牌数量不会变化。
• 代码C & 代码D : 根据上一秒通过的请求数，以及当前时间差，补充令牌。
• 代码E : 根据上一秒的QPS，扣除出上一秒的令牌数消耗，同时保证令牌数大于0。
• 代码F: 更新令牌数更新的时间戳。

根据时间差更新令牌数

public class WarmUpController implements TrafficShapingController	{
    private long coolDownTokens(long currentTime, long passQps) {
        long oldValue = storedTokens.get();
        long newValue = oldValue;
        if (oldValue < warningToken) { // 代码A
            newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
        } else if (oldValue > warningToken) {
            if (passQps < (int)count / coldFactor) { //代码B
                newValue = (long)(oldValue + (currentTime - lastFilledTime.get()) * count / 1000);
            }
        }
        return Math.min(newValue, maxToken);
    }
}

• 代码A：当母桶中的令牌数小于阈值时，根据当前的秒与上一次更新的时间差，补充令牌数，以每秒count令牌数的频率更新。

• 代码B：当前母桶中令牌数量大于阈值时，只有当passQps < (int)count / coldFactor这个条件满足时再补充令牌，一开始这里也困扰了我许久，为什么要加这个条件，而不是像Guava一样只根据 时间差 * QPS  来计算令牌的增量呢？后来我明白了，根本原因在于更新的时机不同：

  • Guava只在请求的QPS很低时（即系统彻底冷却之后）来再补充令牌（因为令牌透支的特性允许Guava这么做）
  • Sentinel则需要在每秒的第一请求就更新令牌的增量，相比之下，Sentinel更新令牌的频率更高，假如没有代码B的判断条件，而是固定按照每秒count所指定的数量更新，那么系统永远无法预热完毕：假设在处于预热阶段时这么做，那么令牌的增加速度永远会比消耗速度快。

总结

1. 本文从机械公敌的技能特性入手，直觉性的介绍了预热算法的场景，相当于做了一个预热，笑。
2. 然后讲到预热算法使用的重要模型：令牌桶。并粗略的将令牌桶和虚拟队列做了一个比较。
3. 实现预热算法的核心思路：构建一个消耗令牌的速率受桶中已有令牌数影响的负反馈系统。
4. 实现的方式有很多，针对溢出的处理方式不同，可以分为不抛弃请求的Guava式的实现方案（通过维护令牌数和请求预定通过时间实现）和关注QPS限制，可以抛弃请求的Sentinel式实现方案（通过维护令牌数、每秒QPS和令牌更新时间实现）。
5. 本文详细的介绍了Sentinel的实现方案的代码，但是它需要理解前面讲到的令牌桶和Guava方案的设计思路。

参考资料

实战Alibaba Sentinel：深度解析微服务高并发流量治理

理解Guava Ratelimiter SmoothWarmingUp实现原理

常见限流原理探秘

Guava官方文档-RateLimiter类

谷歌Guava限流工具RateLimiter

Token bucket