场景及问题

随着云计算的不断快速演进，业务在成本、性能、安全和稳定性高要求下，全栈上云就是个不可逆转的大趋势。对公有云厂商而言，资源超卖是缩减成本的通用方案，那么支持多租户资源共享就是一个关键能力，要保障业务透明而又弹性的资源伸缩是个挑战，这里就有个QoS服务模块做资源管控。实现一个QoS，Quota as a service是解决资源隔离和业务请求文档的一项关键技术，针对不用压力下的业务请求QPS、流量吞吐能自适应的做到弹性限制，总体目标就是在brust请求和流量到来时要保障当前业务的高可用同时还不能影响到其他租户。

一个通用的高性能分布式架构设计就是基于事件驱动的react线程模型，它负责接受用户的请求并做处理回调。往往这个模块被设计成无状态的、可弹性伸缩的组件，这里就面临几个问题：

• 如何甄别一个业务的多客户端连接（保证单间的FD不被打满）
• 如何管控一个节点的请求量（多客户端多业务的并发访问，保证CPU不被打满）
• 如何管控总的收发流量？（保障带宽不被打满）

解决方案

从上面的三个问题来看，CPU不被打满比较好解决，即在系统启动的时候可以根据机器的资源信息配置合理的并发数就可以控制利用率了。至于请求压力和吞吐就必须要相应的算法保障了。下面就总结下常用的流控算法：

1. 固定窗口

原理：在固定时间间隔内维护一个计数器，有请求到来时增加计数器值。当计数器值超过设置的最大值，拒绝请求。

缺点：瞬时流量可能会很高；在两个窗口临界处，流量有可能达到2n。

2. 滑动窗口

原理：为了防止瞬时流量发生，可以把固定窗口划分成多个小窗口，每次向后移动一小格。比如设置一分钟内请求数为100， 划分6个小格， 每个小格维护一个计数器。每次有请求到来时，只要6个小格子中请求总数不超过阈值即可。

原理：

类似固定窗口算法，不过记录前一个窗口的请求数。

比如设置固定窗口为1s，[00:00:00, 00:01:00) 内有9个请求，[00:00:00, 00:02:00) 内有5个请求。 在00:01:15时有一个请求到达， 该请求在当前窗口的 25%处， 当前时间点窗口大小： 9 x (1 - 25%) + 5 = 11.75 > 10， 请求需要拒绝。

缺点：算法假设前一个时间窗口的请求都是均匀的，如果请求不均匀，会导致算法不准确。

3. Sliding Window Log

原理：维护一个按请求时间排序的队列，队列的大小为每个时间窗口内限制的请求数量。当有请求到来时，从队列尾部去掉不在当前时间窗口内的集合，然后计算队列长度，如果长度超过限定值，则拒绝请求，否则接收请求，并将请求加入队列中。

缺点：需要维护一个队列， 占用内存。

4. 漏桶算法

原理：

类似于漏桶， 漏桶有一定容量，漏桶上方接收水滴，下方以恒定速率流出水滴。当漏桶中的水滴量超过漏桶容量时，水滴就无法再加入漏桶。

使用漏桶算法做限流：

1. 定义桶的大小
2. 定义水滴流出的速率

应用：

• https://github.com/uber-go/ratelimit/
• nginx 限流

漏桶算法存在目的主要是用来平滑突发的流量，提供一种机制来确保网络中的突发流量被整合成平滑稳定的流量。

不过由于漏桶对流量的控制过于严格，在有些场景下不能充分使用系统资源，因为漏桶的漏出速率是固定的，即使在某一时刻下游能够处理更大的流量，漏桶也不允许突发流量通过。

5. 令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，等待

• A token is added to the bucket every 1/r seconds.
• The bucket can hold at the most b tokens. If a token arrives when the bucket is full, it is discarded.
• When a packet (network layer PDU) of n bytes arrives, if at least n tokens are in the bucket, n tokens are removed from the bucket, and the packet is sent to the network.if fewer than n tokens are available, no tokens are removed from the bucket, and the packet is considered to be non-conformant.

实现方法：

1. 后台线程每隔1/n秒更新bucket中token数量，直至达到 bucket 容量
2. 主线程检查限速时，查看bucket中token数量，如果小于需要的token数量，则当前请求被限制。否则，token数量减去请求的token数量。

应用：

• rocksdb rate limiter
• Guava中的RateLimiter，RateLimiter实现原理如下：

0. startTick记录RateLimiter初始化时的时间戳（单位ns），后续nowMicros(当前时间点)都是取(System.nanoTime()-startTick)/1000；
1. nextFreeTicketMicros记录下次可获取令牌的开始时间点，在RateLimiter初始化和获取到令牌之后会进行更新；
2. 如果nowMicros大于等于nextFreeTicketMicros，表示可以获取令牌；如果nowMicros大于nextFreeTicketMicros，会计算二者差值并除以放一个令牌的周期，然后赋值给storedPermits字段（表示当前桶中令牌数，注意不能超过桶容量）；
3. 然后storedPermits减去当前需要令牌数，如果此时要获取令牌数大于storedPermits，那么会将nextFreeTicketMicros再往后推进(要获取令牌 - storedPermits) * 放一个令牌的周期 的时间。

6. 基于Redis限流

基于Redis做限流操作，使用lua脚本保证命令原子性，比如qps设置为10，如果key不存在，就设置key过期时间1s，value=1；如果value小于10，则自增value；value达到10触发流控。示例lua代码如下：

local key = "rate.limit:" .. KEYS[1]
local limit = tonumber(ARGV[1])
local expire_time = ARGV[2]

local is_exists = redis.call("EXISTS", key)
if is_exists == 1 then
   if redis.call("INCR", key) > limit then
       return 0
   else
       return 1
   end
else
   redis.call("SET", key, 1)
   redis.call("EXPIRE", key, expire_time)
   return 1
end

参考：

• https://en.wikipedia.org/wiki/Leaky_bucket
• https://hechao.li/2018/06/25/Rate-Limiter-Part1/
• https://zhuanlan.zhihu.com/p/343754066
• https://konghq.com/blog/how-to-design-a-scalable-rate-limiting-algorithm/