漏桶算法与虚拟队列

算法定义

漏桶算法（Leaky Bucket），描述了一个桶口流入水流，底部开口的桶。是不是很像小时候经常做的一边注水一边放水的数学应用题？ 桶的上部接水，桶的下部以固定的速率漏水，当桶中的水的量超过桶的容量时，后续的水将无法进入桶中，漏桶随即进入溢出状态。在溢出状态时，后续的水将被抛弃，或者在队列中等待，直到桶中的水量低于一个阈值时，才可以继续承接水量。

图-1 漏桶算法示意图

应用场景

漏桶算法有两类主要的作用：流量监控(Traffic Policing)、流量整形(Traffic Sharping)。

流量整形是非常符合直觉的：将流量（或者网络请求）本身比作水，流量（或者网络请求）本身不规律地流入漏桶，漏桶则以固定的速率放行流量，看起来存在突发性或者抖动的流量，在经过漏桶之后，都被削平了；

网络图片，来自：http://www.geeksforgeeks.org/leaky-bucket-algorithm/

假设一个场景，在网络中的路由设备只能接受固定带宽输入数据。如图上所示，一个交换机前十秒的带宽： $$ 总通过量= 12Mbps * 2 +2Mbps *3 = 30Mb $$ 前两秒的突发流量`12Mbps`。很可能超过了该交换机的处理能力。通过漏桶算法的整流能力，可以将这类突发的网络流量，整流成每秒3Mbps的稳定网络流量。 **流量监控**场景中，将流量所代表的带宽、字节、离散事件类型等权重比作水，漏桶本身像一个计数器，当流量或事件经过其检查点时，计数器的数值增加相应的值，同时计数值以固定的速率递减，流量（事件）经过时，算法通过判断漏桶溢出与否，赋予流量合法性。即此场景中，漏桶算法本身无法影响流量的通过速率，而只执行标记的作用。在标记流量（事件）之后，可以配合后续的处理器/过滤器来区别处理，进而实现流量整形的功能。 ##### 流量计 >A technique used in ATM networks at the switch level that applies a sustained cell flow rate to bursty traffic. Incoming data flows into a buffer (the "bucket"), then "leaks" out at a steady rate, which is designated as constant bit rate (CBR) traffic. In the event the in-flow exceeds the negotiated rate for a certain time, the buffer will overflow. At that point, the switch examines the Cell Loss Priority (CLP) bit in each cell, and low-priority cells are discarded and retransmitted by the originating device. See [leaky bucket counter](http://encyclopedia2.thefreedictionary.com/leaky+bucket+counter). 在[ATM网络](http://support.huawei.com/enterprise/zh/doc/EDOC1100055312/437f0712)（一种快速分组的网络通信技术）中，[GCRA](http://en.wikipedia.org/wiki/Generic_cell_rate_algorithm)（通用信元速率算法，存在一种类似漏桶版本的算法实现）起到类似流量计的作用，当ATM中的网络设备检测到网络流量超出**网络合同**（一种开启网络通信时定义的，关于服务质量的参数集合）中规定的**固定速率**时（即通过判断当前信元是否会造成漏桶溢出确定网络拥塞与否），会根据信元中的CLP的取值（一个在信元头中声明的标志位，CLP=0表示优先级高，CLP=1表示优先级低），首先选择CLP=1的信元丢弃并让来源设备尝试重新发送信元，进而缓解拥塞。

简单介绍GCRA算法: 有一个总容量为$L$的漏桶，它当前的计数值为$X$，他的泄露速率为$\frac{1单元}{单位时间}$，当漏桶中的$X < L $时（即漏桶还没有泄露时），每个信元的到达都会为计数值带来 $l$ 的增量。则GCRA算法的漏桶版本的实现流程如下所示：

1. 假设上一个信元的到达时间为$LCT$, 而漏桶的泄露速率为$\frac{1单元}{单位时间}$，所以两个信元之间的时间差既是此期间漏桶中泄露的水量，当前信元到达漏桶检查点时，那么漏桶中的剩余容量：$X^1 = X - (t_a(k) - LCT) $ 2. 如果 $X^1 < 0$，说明两个信元到达的时间差过大，漏桶中的所有水量都已漏光，当前漏桶为空，因此设置$X = 0$。此时跳转到步骤4，更新漏桶状态。 3. 如果 $X^1 > 0 $ 且 $X1 > L $，说明当前信元的到达，超出了漏桶的容量，则标记当前信元不符合要求；在ATM网络中，代表了当前的信元超过了PCR(峰值信元速率)的限制。 4. 否则，则说明当前漏桶上可以接收此信元带来的增量，执行 $ X = X + l $来更新漏桶计数值，通过执行$ LCT = t_a(k)$来重置上次到达时间。 总结来说，如果信元以大于泄露速率的速率（可以理解为峰值速率）经过漏桶的检查点，那么漏桶钟的计数值将很快超过漏桶容量而造成溢出，当溢出出现时，经过的信元会被标记为“不符合要求” 进而被后续的流量管理设备抛弃。反之，如果信元经过检查点的速率并不那么快，那么漏桶总是不满的（或是空的，这取决与信元相对于漏桶的泄露速率）。 ##### 整流工具或缓冲区 上面已经说明使用计数器方式实现的漏桶算法，可以通过标记流量（或事件）的“合规性”配合后续的服务组件达到整流的目的。事实上，也存在一种使用队列这一数据结构实现的漏桶算法。

使用队列实现整流功能，来自wiki百科：Leaky Bucket

漏桶的队列版本的描述： >[Andrew S. Tanenbaum](http://en.wikipedia.org/wiki/Andrew_S._Tanenbaum)："The leaky bucket consists of a finite queue. When a packet arrives, if there is room on the queue it is appended to the queue; otherwise it is discarded. At every clock tick one packet is transmitted (unless the queue is empty) 漏桶由一个**有限队列**组成。当一个数据包到达时，如果队列上有空间，它就会被附加到队列尾部；否则将被丢弃。除非队列为空，否则在每个固定时间点传输一个数据包。队列版本的漏桶，被漏桶管理的"水"，不再是流量计版本中的"数据包的大小"、"信元的大小"、"事件的权重"等等信息属性，而是数据包、信元、事件本身。 ### 虚拟队列 根据队列版本的漏桶描述，实现一个漏桶需要指定两个参数：队列长度、处理时间间隔。 在Sentinel中，有一个匀速限流效果控制器`RateLimiterController`，它正是基于队列版本的漏桶算法来实现：对一个资源的访问线程在队列中排队等待，直到合适的时间点到达时，才被允许执行，而超出队列长度的线程则被禁止执行业务代码，进而达成限制一个资源访问QPS的限流效果。 和前面讲到的管理流量、信元等等的漏桶例子不同，Sentinel的匀速限流效果控制器（可以视为漏桶）管理的是访问资源的线程本身，它不太可能在一个并发环境下再引入一个同步的队列：假设，Sentinel真的引入了线程间同步的队列，考虑一下每个访问资源的线程并发地确认队列长度，自己的放行时间等等操作对业务性能造成的影响？ `RateLimiterController`使用虚拟队列来实现，其并不需要维护真正的队列信息。虽然虚拟队列也存在一定的局限：并不能实现访问请求先入先出的顺序保证，但在Sentinel的限流场景下，都是对同一个资源的并行访问，因为线程通过顺序并不是第一要务，重要的是漏桶的整流能力。

#### 线程角度 理解虚拟队列的过程并不简单，可以从线程本身和整体角度两个视角来入手说明。首先用将线程比作"架空世界"中一个到动物园游玩的游客“小T”，从它的角度来看看会发生什么。 ##### 场景一：空空荡荡的熊猫馆排队大厅 上午十点整，"小T"进入空空荡荡的熊猫场馆排队大厅，辛勤的小T发现此时排队大厅里一个人都没有。另外大厅的尽头有一个闸机让游客们依次通过，而后小T就看到闸机上方巨大的时钟，小T知道这个时钟不是记录时间的时钟，而是记录着当前最后一次闸机开放的时间：`9:51`。在正常情况下，闸机最快只会每隔**5分钟**开启一次。这代表着已经9分钟没有人通过闸机了，所以当小T走到闸机口时，检票员并没有阻拦，就让小T通过了闸机口。在通过闸机的时候，时钟“叮”的一声被设置成了"10:00"。 ##### 场景二：热闹的熊猫馆排队大厅 第二天上午十点整，“小T"又来到了排队厅，这次他发现大厅里很热闹：很多和他一样的线程们站在大厅中，拿着手机在点击屏幕。小T知道，这是他们在线上排队，原来是今天等候访问熊猫馆的人太多了，而闸机口最快只能5分钟通过一人，大家只能通过抢购的形式确定自己的通过时间。 平时时空No.0: 不幸的小T 现在时钟显示`10:27`分，糟糕了，小T只能立即放弃排队，因为时钟显示`10:27`，而此时时间是:`10:00`,意味着小T即使立即加入抢购大军，在运气非常好的的情况下，最快也要到`10:32`才能通过闸机，他仍需要等待32分钟，这超过了场馆的规定：为了防止拥挤，任何人都不要排队超过30分钟。 平行时空No.1: 幸运的小T 平行时空的小T的运气则非常好，时钟显示时间是：`10:17`，说明最近一个抢到通过权的幸运儿排在`10:17`。小T还有两次机会，如果抢到下次(`10:22`)，和下下次(`10:27`)两次排队资格，那么小T就能在不超时的情况下顺利参观熊猫馆。于是小T打开了排队APP开始排队，等了一会儿之后，系统返回了一个时间: `10:27`。‘Yeah!' 小T欢呼一声，躺在了自己的座位上，调用自己的sleep()方法休息个27分钟等候进入场馆。 平时时空No.2: 幸运的又有那么点倒霉的小T 在No.2号平时时空里，时钟显示`10:17`分，于是小T开始排队，等了一会儿之后，系统返回了一个时间: `10:37`。‘焯！’，小T怒摔手机，超时了！！！小T点击了确定，离开场馆的排队大厅，代表小T放弃了本次访问场馆的资格，过一会儿闸机口上方的时钟，默默回调了**五分钟**，等待下一个“有缘人抢到通过资格。 上面的场景再现，讲了一个小T访问熊猫馆的故事。其实这个故事对应着Sentinel中允许限流控制器中的各个元素，整理到一个表格中： 故事举例 | Sentinel世界 | 说明 | | --------- | ------------------------------------------------------------------------------------ | -------------------------------------------------------------------------------------------------------------------------------------------------------------------- | | 小T | 线程 | | | 熊猫馆 | 线程访问的资源 | Sentinel世界好比是一个动物园，而动物园里的场馆，则是Sentinel中的资源 | | 场馆前的排队大厅 | `RateLimiterController`类(匀速限流效果控制器) | `FlowSolt`将对资源访问线程的校验工作委托给`FlowRuleChecker`, `FlowRuleChecker`完成集群限流和本地限流方式的区分 如果是本地限流，则将具体的限流工作委托给`TrafficShapingController`（`RateLimiterController`的父接口）实现不同的限流效果。 | | 闸机口上方的时钟 | `RateLimiterController.latestPassedTime`属性，类型是`AtomicLong`，记录匀速限流效果控制器最后一次允许线程通过的时间戳 | 对于正在通过效果控制器的线程们而言，他有以下作用:
1. 让线程们知道自己能否在超时之前等到下一次队列开放
2. 利用`AtomicLong`的自旋和原子性，让线程们争夺队列开放的时间点
3. 让线程们知道自己需要等待多久才能继续执行 | | 闸机5分钟放行一次 | `FlowRule.Count`属性，即QPS，在实现过程中，代表了换成每次等待队列放行的通过间隔 | 例如设置count的值为200QPS， 那么虚拟队列的放行的频率就是: $\frac{1000}{200QPS}=5ms$ | | 超时时间30分钟 | `RateLimiterController.maxQueueingTimeMs` | 记录了线程们的最大等待时间，如果超过这个时间的Sentinel会直接以 `FlowException`的形式中断线程对资源的访问。 ### 整体角度 正所谓“不识庐山真面目，只缘身在此山中”，之前的角度锁定在一个虚拟队列中的线程角度阐述其行为，现在换一个说明问题的角度，让我们从整体的角度看看对同一个资源的访问线程们都在什么状态吧。 

图1-1 从整体角度查看线程经过虚拟队列的并发情况

#### 整流功能 在示意图中，线程2、3、4、5、6都在**第8毫秒**并发进入队列，但是通过对`RatelimiterController.LaterPassedTime`这个“时间锁”的抢占更新，他们获得了不同的执行时间: - 线程3被允许在第17毫秒执行业务逻辑 - 线程4被允许在第22毫秒执行业务逻辑 - 线程5被允许在第12毫秒执行业务逻辑 - 线程6被循序在第27毫秒执行业务逻辑 在系统时间到达线程本身被允许执行时间点之前，线程调用sleep()，等待被系统唤醒。看起来是不是就像是并发的线程们进入了一个队列等待，然后按照固定的频率被放行，不同的是， 特别注意的是**线程2**： 1. 就像平行时空No.2号那个幸运的又有点倒霉的小T一样，线程2虽然参与了排队，但是被它允许执行性的时间点（第32毫秒），距离当前的时间差又超过了20ms(假设超时时间是20ms)。线程2只能返回一个`BlockException`，相当于说明当前虚拟队列的长度就是，一旦当前并行的线程超过4，其余的线程将直接溢出。 1. 线程2在返回异常之前，还有一个工作要做，将最近更新时间**回拨**一个时间间隔（5ms）。相当于释放自己所占用的时间锁，让其他线程有可能重新占用第32ms的这个执行时间点。如下图所示：\ 第①步：【线程2】执行Update Lock Time = 32 - 5 = 27 ms\ 第②步：【线程8】执行Update Lock Time = 27 + 5 = 32 ms\ 第③步：【线程9】执行Update Lock Time = 32 + 5 = 37 ms 1. 其他的并发线程可能永远也占用不到32ms的这个执行时间点了，它们可能在第37ms的这个时间点相遇：\ \ 与上一点不同的是，如果第①步和第②步的执行顺序正好相反，也就是线程8执行的新增5ms操作先于线程2的回调5ms操作:\ 第①步：【线程8】执行Update Lock Time = 32 + 5 = 37 ms\ 第②步：【线程2】执行Update Lock Time = 37 - 5 = 32 ms\ 第③步：【线程9】执行Update Lock Time = 32 + 5 = 37 ms\ 在这个场景下，线程8和线程9最后都在第37ms这个时间点并发执行，这看起来是个场景似乎是个问题：在第32毫秒，没有线程开始执行自己的业务代码，而在第37毫秒，线程8和线程9一起执行了自己的并发代码。整体来说，这个虚拟队列的实现，还是能保证“**平均QPS**”的承诺的。 **线程7**则是平行时空No.0的那个倒霉的小T，线程7在第12ms开始，通过计算 32+5 - 12 = 25ms > 20 ms（此时线程2还没来的及将时间回调5ms到27，不然的话线程7不会超时） 就可以知道当前队列必然已满，因此将直接触发Sentinel对自己的限流，并返回阻塞异常。 总结一下，只需要三个参数：超时时间、通过频率、最后通过时间。就可以实现一个虚拟队列： $ 通过间隔 = \frac{1000}{QPS} = \frac{1000}{200} = 5ms$ $ 队列长度 = \frac{超时时间}{通过间隔} = \frac{QPS超时时间}{1000} = \frac{200 20ms}{1000} = 4$ $最后通过时间_n=\begin{cases} 当前时间 & if 队列为空 \\ 最后通过时间_{n-1} + 通过间隔 & if 线程排队中 \end{cases}$ ### 实现流程  #### 代码实现 ```java import java.util.concurrent.CountDownLatch; import java.util.concurrent.atomic.AtomicLong; import java.util.concurrent.atomic.LongAdder; /** * 虚拟队列 * 1. 连续创建多个线程，线程创建之后就执行 * 2. 让线程通过虚拟队列 * @author zongzi */ public class VirtualQueue { /** * 统计放行的线程数 */ static final LongAdder PASS_COUNT = new LongAdder(); /** * 统计阻塞的线程数 */ static final LongAdder BLOCK_COUNT = new LongAdder(); /** * 统计总的线程数 */ static final LongAdder DONE_COUNT = new LongAdder(); /** * 最大的测试线程数 */ private static final int TEST_MAX_THREAD = 50; /** * 等待所有的线程执行结束标志 */ private static final CountDownLatch COUNT_DOWN = new CountDownLatch(1); /** * 允许通过的最大并发线程数 */ private static final int QPS = 10; /** * 最大的等待时间 */ private static final Long MAX_QUEUEING_TIME_MS = 1000L; private static final AtomicLong LATEST_PASSED_TIME = new AtomicLong(-1); public static void main(String[] args) throws InterruptedException { int i = 0; // 声明测试线程并启动 while (i < TEST_MAX_THREAD) { Runnable andStartThread = createAndStartThread(); new Thread(andStartThread, String.format("ThreadName:%d", i)).start(); i++; } // 阻塞等待 COUNT_DOWN.await(); System.out.println("pass:\t" + PASS_COUNT.longValue()); System.out.println("block:\t" + BLOCK_COUNT.longValue()); System.out.println("done:\t" + DONE_COUNT.longValue()); } public static Runnable createAndStartThread() { return () -> { // 进入虚拟队列， boolean pass = queueWait(); if (pass) { PASS_COUNT.add(1); } else { BLOCK_COUNT.add(1); } DONE_COUNT.add(1); // 让主线程继续运行 if (DONE_COUNT.longValue() >= TEST_MAX_THREAD) { COUNT_DOWN.countDown(); } }; } /** * 进入虚拟队列等待 * @return true 线程可以放行， false 线程被阻塞 */ static boolean queueWait() { long currentTime = System.currentTimeMillis(); // passedInterval 是一个请求通过的时间间隔，根据我们设置的QPS有关，如果QPS等于200，那么每个请求平均需要的时间是costTime=1000/200=5ms. long passedInterval = Math.round(1.0 * (1000) / QPS ); // 下次开放通过的时间 long expectedPassedTime = passedInterval + LATEST_PASSED_TIME.get(); // 如果期望的时间小于当前时间，说明上一个请求在很早之前就已经被放行了，当前队列应该是空的 if (expectedPassedTime <= currentTime) { // 这里可能仍会存在并发，但是只影响最开始进入队列的几个线程，是可以接受的 LATEST_PASSED_TIME.set(currentTime); return true; } else { // 计算从当前系统开始，期望的等待时间 long expectWaitTime = passedInterval + LATEST_PASSED_TIME.get() - System.currentTimeMillis(); // 在未开始排队前，线程就知道等待的时间超过了最大等待时间，说明当前虚拟队列已经满了，当前线程不再进入排队 if (expectWaitTime > MAX_QUEUEING_TIME_MS) { return false; } // 和其他线程一起并发竞争时间锁的更新，获得自己的通过时间。 long expectPassedTime = LATEST_PASSED_TIME.addAndGet(passedInterval); try { expectWaitTime = expectPassedTime - System.currentTimeMillis(); // 如果期望的排队时间超过了超时时间，说明当前线程虽然参与了排队，但是已经在队列长度之外， if (expectWaitTime > MAX_QUEUEING_TIME_MS) { // 回调自己占用的放行时间点，给可能的其他线程 LATEST_PASSED_TIME.addAndGet(-passedInterval); return false; } // 运行到这里，说明线程已经正确的派上到了虚拟队列中，休眠等待 if (expectWaitTime > 0) { Thread.sleep(expectWaitTime); } // 返回true, 代表请求业务被放行，后面可以正常执行业务代码了 return true; } catch (InterruptedException e) { } } return false; } } ``` #### 代码说明 在代码实现中，已经添加了足够的代码注释，相信理解这个问题，已经不是难事了，现在我们来看看虚拟队列的两个主要参数：QPS、MAX_QUEUEING_TIME_MS 两个参数对虚拟队列的整流效果的影响吧。 在代码中，我们首先创建了500个并发线程，然后创建了一个QPS为10，超时时间为1000ms的，由此我们可以得到:，因而50个并发线程中应该只有10个线程通过。其余的线程都因为队列已满而被阻塞（`queueWait()`方法返回`false`)。 如果你运行这个示例代码的话，应该会得到类似的结果。 ```shell pass: 11 block: 39 done: 50 ``` “通过的线程”是11个情况和`图1-1`的类似，在队列能正常工作之前，需要一个额外的线程来启动时间锁（作用和图1-1中的线程1类似）。