ratelimiter

限流, 微服务与go的rate.Limiter

限流

从算法上有两种限流实现:

令牌桶

每隔一段时间放到捅中一个令牌, task获取令牌才能执行.

令牌桶算法的描述如下：

• 假设限制2r/s，则按照500毫秒的固定速率往桶中添加令牌；
• 桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝；
• 当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上；
• 如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。

特性:

• 这个的特性就是只要有令牌就能运行.
• 实现上还可以实现预支令牌

具体的功能描述: 任意时刻最大流量是桶可以容纳的最大token数+可以预支的令牌数. 最大流量过后就只能等着下一个令牌被加入到桶中.

1. 这种方式不能避免突然增加的流量. 有可能在一段没有请求的时间之后(积累了一桶的令牌), 下一刻突增流量, 因为token很多, 所以全部并发的被执行. 可以是feature也可以是bug.

2. 通过控制桶容量和加入token的速度, 我们可以控制上面这种行文. 如果我们设置桶容量比较小, 但是加入令牌的速度比较快, 就可以得到一个持续的, 避免掉小高峰的限流器. 比如速度为 100 token/s, 而桶大小为10, 那么任意时刻最大并发是10, 而一秒内可以分发出去100个请求. (并行和吞吐的区别)

漏桶算法

规定一个出口速度, 一个桶容量. tasks向水流一样流入, 然后从桶底漏出.

漏桶作为计量工具（The Leaky Bucket Algorithm as a Meter）时，可以用于流量整形（Traffic Shaping）和流量控制（TrafficPolicing），漏桶算法的描述如下：

• 一个固定容量的漏桶，按照常量固定速率流出水滴；
• 如果桶是空的，则不需流出水滴；
• 可以以任意速率流入水滴到漏桶；
• 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

特性:

1. 这种算法从原理上讲更适合平滑流量. 规定漏桶出口速度, 那么一定小于这个流量.
2. 流量是慢速的, 如果 2 transaction/s. 那么每0.5s才能执行一个请求, 而不是2个transaction一起执行.
3. 漏桶算法的桶, 是用来让多余的流量直接拒, 处理完一些在加进来等待.(实现上没什么用, 因为一个请求过来要么可以用, 要么不可以)

令牌桶和漏桶对比：

• 令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；
• 漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；
• 令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；
• 漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；
• 令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率；

只限制并行数量

go 语言可以通过这种方式限制并行数量, 这种方式实际上就是队列, 这种方式只能限制同时有多少个task在执行, 不能控制速率, 一段时间完成的多少要看每个任务执行的速度.

这种方法因为任务执行速度不一样, qps也会变化.

var sem = make(chan int, MaxOutstanding)

func handle(r *Request) {
    sem <- 1    // Wait for active queue to drain.
    process(r)  // May take a long time.
    <-sem       // Done; enable next request to run.
}

func Serve(queue chan *Request) {
    for {
        req := <-queue
        go handle(req)  // Don't wait for handle to finish.
    }
}

微服务需要限流

一个服务的处理速度是有限的, 如果你不限制这个速度, 最终系统会被越来越多的流量拖垮, 一个请求也不能处理. 如果加上了限流, 无论调用方流量如何变化, 时钟能保证本服务的稳定. 限流可以是在客户端做, 也可以是现在服务段做. 最高的速度应该由服务方告知其他调用方.

go 提供的 rate.Limiter 的实现

Limiter 是一个令牌桶的, 使用时间差来计算令牌个数, 一个task过来获取令牌, 则判断当前时间距离上次更新时间可以获得多少个令牌.加入桶中. 然后看看桶内令牌够不够, 如果不够, 但是调用方愿意等一段时间, 那么计算一下要等待 -tokens 个令牌是否超过了调用方的deadline, 不超过就返回可以让其在等待xxx秒后通过.

非常重要的一件事是: 因为时钟不够精确(硬件原因), 当令牌加入速度过快的时候, 被拦截的tasks count是不准确的. rate过高时, 有1%的误差.

我一开始还以为是因为算法实现有问题, 浮点数加减不精确导致的, 后来自己写了一个不用浮点数记录当前可用的令牌, 而用整数, 对时间差取周期数, 不加余数(不加1.333个个令牌). 虽然比官方库好一点点(能多拦截几个), 但是还是不精确的.