基本算法-令牌桶

原始算法

令牌桶（Token-Bucket）是目前最常采用的一种流量测量方法，我们可以想象一个存放令牌的容器，预先设定一定的容量。系统按设定的速度向桶中放置令牌，当桶中令牌满时，多余的令牌将被丢弃，当请求流量进入服务时，需要从桶内获取令牌才可被服务处理，否则将执行拒绝策略。

优化

我们可以将该算法优化，记录下最后一次获取令牌的时间戳和令牌数量，在下一次取令牌的时候根据两次时间戳的间隔计算出应该维护的令牌数后再取令牌，算法时间复杂度和空间复杂度均为O(1)，且不需要额外线程开销。

货币化改造

对于不同的接口，我们可以配置不同的消耗，对于轻量接口我们可以配置较少令牌数量，对于较重接口我们可以配置较多令牌数量，比如对于A接口系统满载可以承受1000TPS，而对于B接口系统满载可以承受2000TPS，那么只需要将A与B接口消耗的令牌数比例设为2:1即可在一定程度上更充分利用系统的性能。

同时，我们新增了窃取令牌数接口和补偿令牌数接口，其中窃取接口可以强行减去当前桶的令牌数量（可将当前桶的数量扣为负数，但是不小于负的桶容量，区别于普通的流控接口），补偿令牌数接口可以强行增加当前桶的令牌数（不得大于桶容量）

算法性能

加锁后每次调用大约需要花费40纳秒（多线程涉及锁竞争，可能会导致延迟增大，但对于大部分服务可以忽略不计）。

分级流控算法

原理

在货币化改造的基础上，我们还可以对不同的功能接口设置不同的等级，同时将设置多个不同等级的令牌桶，不同等级的接口应该在不同等级的令牌桶中获取执行令牌，当获取成功后，我们将所有低于该等级的令牌桶的令牌窃取相应的数量（为保证模型简单，该数量与该接口设置的消耗数量一致）。

服务降级

当高级接口调用频繁的时候，低级令牌桶的令牌总是会被窃取走（因为窃取可以窃取为负数，而流控接口若扣除失败则不会扣除任何令牌，可以理解为窃取优先级高于流控），低级接口获取不到令牌，只能执行事先设定的拒绝策略，从而达到服务降级逻辑

多节点同步

我们可以通过一定的同步机制将节点的消耗传递给其他节点，并在其他节点窃取令牌以达到分布式全局流控的效果。