最近接了需求，要实现一个优先级限流。但是实现的路上遇到了诸多头大之事，感觉这就是为什么各个大厂的限流器都没有一个优先级限流比较统一的实现的原因。
优先级限流算法的流程挺简单的，就是给出一个系统总容量，再给出不同接口之间的优先级关系，然后通过某个神秘逻辑去判断对于每个不同的优先级请求，应该是通过还是拒绝。
Sentinel
目前在使用上比较常见的框架是 Sentinel。Sentinel 内部实现了一个十分简陋，并且我觉得没什么用的优先级算法，在限流逻辑执行的时候传入一个布尔值，代表这个请求是高优先级还是低优先级。
这个逻辑是直接应用在Sentinel的滑动窗口算法之上的。如果某个请求是高优先级请求，并且在请求到来的时候窗口已满，就会：
- 计算距离下一个窗口的起始时间还有多久;
- Sleep 对应的时间;
- 直接判定为通过，并在统计槽内计算。
也就是说，Sentinel的优先级算法基本依赖Sleep，必定是会引入额外的延迟的。Sentinel内默认的滑动窗口总长度是1秒，内部是两个500ms的子窗口拼到了一起。也就是说一个高优先级请求在最糟糕的情况下需要等待500ms才能被处理。
另外，众所周知，全世界没有人类各种神秘远古老旧无人维护的屎山代码都还在使用Java 8。而Java 8并没有协程这种便利的东西，每个Java 8里面的线程都对应了一个实际的系统线程，因此唤醒和休眠都是一个相对很重的操作，并且会占用线程池里面为数不多的线程资源。而每个经过这个接口的高优请求都会在系统容量告急的时候占用一个休眠线程，老实说感觉不是很行。
作为一个负责任的开发，肯定不能拿这么个东西来糊弄。于是继续去网上看看有没有什么更好的实现。
水位线算法
原理
网上实际并没有太多优先级限流相关的算法设计。简单搜索了一下，有个游戏推荐业务中基于 sentinel 的动态限流实践（我这里简称水位线算法）看起来效果还可以。不过也只是看起来效果还可以，实际实现起来坑是一个接一个。坑什么的先按下不表，这里简单讲讲水位线算法的原理。
水位线算法需要解决的的问题很简单，就是找到一个水位点，使被放过的部分都是比水位线高的优先级，被拒绝的都是比水位线低的优先级。同时保证放过的部分不超过并接近（大部分情况需要是等同于）这个特定系统容量。
这个具体的点就比较复杂了。水位线算法也基于滑动窗口算法，因此需要做的事就是在每个内部时间窗口结束的时候记录一下当前窗口各个优先级的请求的请求总量各自是多少。这个实现方法比较简单，只要保留n+1个窗口的请求总量，通过量，拒绝量的统计值即可。第1个窗口是刚刚过期的时间窗口（窗口结束时间距离当前超过滑动窗口计数时间），第2个到第n个窗口是当前已结束但未过期的时间窗口，第n+1个窗口是当前正在统计且没有结束的时间窗口。把前两个部分加起来，我们就得到了前一时刻的“快照值”。
图里的实际时间窗对应的各个优先级请求量就是我们要找的快照值。通过这个快照值，我们就可以知道前一个时刻，各个优先级都来了多少请求。首先将这些请求按优先级从高到低统计好，再用阈值挨个减去请求数量，一直减到减不够或者所有优先级都减完为止。这个时候水位线就是减不够的那个优先级还余下的阈值量。如果都减完了那就没有水位线。
对于滑动窗口来说，一个总窗口内部会包含n个子滑动窗口。在总时长基本一致，并且请求总量没持续打满系统总量的时候，这个n越大，对于限流效果一般来说会越平缓，资源消耗也会随之以$O(n)$时空复杂度增长。对于水位线算法来说，n的值越大，那么内部时间窗口就越小（内部时间窗口=总计数时间/n），计算出来对请求量的误差值也就越小，那么根据前一个过期窗口预估出来的当前滑动窗口各优先级请求量误差也就越小。这是根据上面的文章得出的结论。
但是我认为这里其实问题很大。考虑一个请求速率持续上升的场景——这个时候我们预测下一个时间窗口的请求量是第一个过期窗口请求量，但是因为请求速率一直在上升，实际请求量最终会明显高出预测值。实际上比较好的方式是用2-2里面每个小格的索引作为x，具体请求量的值作为y，做一个线性或二次拟合来预测当前内部时间窗口各优先级的请求量，并作为当前水位线的判断依据。
在总请求量持续高于系统容量的时候，n的值并不会对系统内请求的通过平缓情况造成很大影响。在这种情况下，每个新到来的窗口的通过量，都和刚刚过期的窗口的通过量保持一致。换句话说，请求速率会在计数时长内呈现周期性波动，波动的大小取决于容量刚刚满的时候，请求通过量在整个计数时长内的分布。
计算出了水位线之后，就要开始对当前窗口的请求进行限流了。可以看图2-2那里，最后一个白色小格就是我们实际在处理的部分。根据水位线，我们可以判断哪些优先级是放过，哪些优先级是拒绝，哪个优先级又是刚刚好卡在水位线上，可以放过之前计算出的还余下的阈值量。
当然这只是第一重判断。在这之后还需要统计放过请求的总量。因为我们实际上没有在当前窗口判断高于水位线的各请求已经放过去了多少个，这样的话如果当前窗口突然来了很多高优先级的请求，还是限不住。所以对所有通过的请求，我们还要进行第二次判断。如果目前的总通过量已经高于了阈值，那么余下的所有请求都应该被拒绝。
坑点
实际上这个水位线算法基本只存在于理想之中。实现起来那叫一个问题重重。u1s1，这个滑动窗口就是最大的问题源。本来我的目标实现是达成无延迟的优先级限流，事实上一开始也实现了无延迟的优先级限流，但是一测试就发现，误限问题相当严重。在我的实现中，内部窗口使用了100ms的长度。听起来并不长，但是我玩游戏按键盘的速度都比这快。不过考虑到性能和效率的平衡，也就这样了。
误限是怎么发生的呢？我在代码实践中观察到了几种情况下的误限。
其一是在限流器刚刚启动的时候，如果总的请求量就超过了阈值，会有大概一个计数时间（在我这里是1秒）长度的随机限流状态。其原因是，在限流器刚刚启动时，内存里面还没有任何历史请求量的数据，需要等待历史请求量被已有的数据填满之后，限流器才可以对接下来的请求量有一个比较准确的预测。这种情况还好，因为不会持续出现，所以一般场景都还可以接受。
其二是不同优先级在单个时间窗口的尺度内存在先后顺序导致请求的误限。考虑这个场景：现在的100ms时间窗口的水位线在优先级3上（优先级数字越大级别越低）。我们有20个阈值余量，这时候这个时间窗口如果来了15个优先级1的请求和15个优先级2的请求，我们自然而然会希望优先级1的15个请求全部都通过，而优先级2的请求拒绝10个，放过5个。但是实际情况和这个完全不一样。之前说过，水位线以上的优先级，我们只会在总的限流请求数上施加限制。所以如果这个时候，在前50ms先来了15个优先级2的请求，那么这些请求会全部都放过。这时候再来的优先级1请求，即使优先级更高，但是因为我们的阈值已经被优先级2占完了，所以顶多再放过5个，剩下的10个优先级1请求都会被拒绝。从逻辑上讲，这个就是正确的，但是从能不能满足需求上讲，就有点糟糕了。
其三是请求速率的上升和下降阶段。前面说过，水位线算法其实是用第一个过期的内部窗口去加上已经过的n个有效窗口来近似统计的。因此，如果总请求量超阈值但水位线上还有多个优先级，且高优先级请求速率持续上升，那么这个时候就会因为新窗口释放的阈值实际上是旧窗口请求量，导致新估出来的水位线其实偏低，导致一些本不应该被放过的低优先级请求也和高优先级请求一起去抢阈值。
这三个情况加在一起，这水位线算法基本上就没法用了。实际上，只要想想也不难发现：立即判断——严格按优先级排序请求——保证放过量和总阈值一致这三者构成了一个不可能三角。想要实现这个优先级限流，我们必须在其中一个方向上做出妥协。
妥协
尽管无法破解这个不可能三角，但是我们还是可以做一些取舍。对于优先级限流来说，保证放过量和总阈值一致是必须的，因此就必须在严格排序和立即判断间二选一。实际的解决方案是，开放一个选项，允许因为总量超额而被限制的请求延后至下个内部窗口的开头处理，并且对同时休眠的线程数进行限制。这样测下来，平均的延迟基本在50ms内。具体要不要开启，就看使用时的取舍了。