layout: post title: 不得不谈的限流算法
在开发中我们可能会遇到接口访问频次过高，这时候就需要做流量限制，你可能是用的 Nginx 这种 Web Server 来控制也可能是用了一些流行的类库实现。在分布式系统中更是如此，限流是高并发系统的一大杀器，在设计限流算法之前我们先来了解一下它们是什么。
限流的英文是 Rate limit（速率限制），维基百科中的定义比较简单。我们编写的程序可以被外部调用，Web 应用通过浏览器或者其他方式的 HTTP 方式访问，接口的访问频率可能会非常快，如果我们没有对接口访问频次做限制可能会导致服务器无法承受过高的压力挂掉，这时候也可能会产生数据丢失。
而限流算法就可以帮助我们去控制每个接口或程序的函数被调用频率，它有点儿像保险丝，防止系统因为超过访问频率或并发量而引起瘫痪。我们可能在调用某些第三方的接口的时候会看到类似这样的响应头：
X-RateLimit-Limit: 60 //每秒60次请求
X-RateLimit-Remaining: 23 //当前还剩下多少次
X-RateLimit-Reset: 1540650789 //限制重置时间
上面的 HTTP Response 是通过响应头告诉调用方服务端的限流频次是怎样的，保证后端的接口访问上限。为了解决限流问题出现了很多的算法，它们都有不同的用途，通常的策略就是拒绝超出的请求，或者让超出的请求排队等待。
计数器是最简单的限流算法，思路是维护一个单位时间内的计数器 Counter，如判断单位时间已经过去，则将计数器归零。
我们假设有个需求对于某个接口 /query 每分钟最多允许访问 <kbd>200</kbd> 次。
count，当过来一个请求我就将这个数 +1，同时记录请求时间。count 的计数值是否超过设定的频次，以及当前请求的时间和第一次请求时间是否在 1 分钟内。count 值还在限流范围内，就重置 count。伪代码实现
type Counter struct {
Count uint // 初始计数器
Limit uint // 时间窗口最大请求频次
Interval int64 // 单位毫秒 ms
RefreshTime int64 // 时间窗口
}
func (c *Counter) rateLimit() bool {
now := time.Now().Unix()
if now < (c.RefreshTime + c.Interval) {
// 在时间窗口内
c.Count++
return c.Count <= c.Limit
} else {
c.RefreshTime = now
c.Count = 0 // 超时重置
return true
}
}
这种方法虽然简单，但也有个大问题就是没有很好的处理单位时间的边界。
假设有个用户在第 59 秒的最后几毫秒瞬间发送 200 个请求，当 59 秒结束后 Counter 清零了，他在下一秒的时候又发送 200 个请求。那么在 1 秒钟内这个用户发送了 2 倍的请求，如下图：
<img alt="计数器法" title="计数器法" src="{{ '/public/images/2018/10/counter_bug.png' | prepend: site.cdnurl }}" width="80%" />
这种方式的缺点在于它没有更细粒度的划分临界点，如果我们可以把这个时间窗口划分成 6 份，每一份代表 10 秒，当然你可以将它划分的更细。那么如何解决这里的临界问题呢？来看看下面的滑动窗口吧。
所谓 滑动窗口（Sliding window）{:target="_blank"} 是一种流量控制技术，这个词出现在 TCP 协议中。我们来看看在限流中它是怎样表现的：
上图中我们用红色的虚线代表一个时间窗口（一分钟），每个时间窗口有 6 个格子，每个格子是 10 秒钟。每过 10 秒钟时间窗口向右移动一格，可以看红色箭头的方向。我们为每个格子都设置一个独立的计数器 Counter，假如一个请求在 0:45 访问了那么我们将第五个格子的计数器 +1（也是就是 0:40~0:50），在判断限流的时候需要把所有格子的计数加起来和设定的频次进行比较即可。
那么滑动窗口如何解决我们上面遇到的问题呢？来看下面的图：
当用户在 0:59 秒钟发送了 200 个请求就会被第六个格子的计数器记录 +200，当下一秒的时候时间窗口向右移动了一个，此时计数器已经记录了该用户发送的 200 个请求，所以再发送的话就会触发限流，则拒绝新的请求。
通过上面的分析相信你了解什么是滑动窗口了，回想一下其实计数器就是滑动窗口啊，只不过只有一个格子而已，所以我们想让限流做的更精确只需要划分更多的格子就可以了，真是秒啊！为了更精确我们也不知道到底该设置多少个格子，所以又出了 2 种流行的平滑限流算法分别是漏桶算法和令牌桶算法，继续往下看。
漏桶算法（Leaky Bucket）是什么呢？大家都用过水龙头，打开龙头开关水就会流下滴到水桶里，而漏桶指的是水桶下面有个漏洞可以出水。如果水龙头开的特别大那么水流速就会过大，这样就可能导致水桶的水满了然后溢出。
而我们讨论的漏桶算法的思路也很简单，水龙头打开后流下的水（请求）以一定的速率流到漏桶里（限流容器），漏桶以一定的速度出水（接口响应速率），如果水流速度过大（请求过多）就可能会导致漏桶的水溢出（访问频率超过接口响应速率），这时候我们需要关掉水龙头（拒绝请求），下面是经典的漏桶算法图示：
这张图中有 2 个变量，一个是桶的大小（capacity），另一个是水桶漏洞的大小（rate），那么我们可以写下如下代码来实现：
伪代码实现
type LeakyBucket struct {
Capacity int64 // 桶的容量
Rate int64 // 漏桶出水速度
Water int64 // 当前水量(当前累积请求数)
RefreshTime int64
}
func (b *LeakyBucket) rateLimit() bool {
now := time.Now().Unix()
// 先执行漏水，计算剩余水量
b.Water = max(0, b.Water-(now-b.RefreshTime)*b.Rate);
b.RefreshTime = now
if b.Water < b.Capacity {
// 水桶还没满，继续加 1
b.Water++
return true
} else {
// 水满，拒绝流入
return false
}
}
func max(a int64, b int64) int64 {
if b > a {
return b
}
return a
}
漏桶算法有以下特点：
漏桶限制的是常量流出速率（即流出速率是一个固定常量值），所以最大的速率就是出水的速率，不能出现突发流量。
令牌桶算法（Token Bucket）是网络流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一种算法。典型情况下，令牌桶算法用来控制发送到网络上的数据的数目，并允许突发数据的发送。
令牌桶算法和漏桶算法的方向刚好是相反的，我们有一个固定的桶，桶里存放着令牌（token）。一开始桶是空的，系统按固定的时间（rate）往桶里添加令牌，直到桶里的令牌数满，多余的请求会被丢弃。当请求来的时候，从桶里移除一个令牌，如果桶是空的则拒绝请求或者阻塞。
伪代码实现
type TokenBucket struct {
Capacity int64 // 桶的容量
Rate int64 // 令牌放入速度
Tokens int64 // 当前令牌数量
RefreshTime int64
}
func (t *TokenBucket) rateLimit() bool {
now := time.Now().Unix()
// 先添加令牌
t.Tokens = min(t.Capacity, t.Tokens+(now-t.RefreshTime)*t.Rate);
t.RefreshTime = now
if t.Tokens < 1 {
// 令牌数小于 1 拒绝请求
return false
} else {
// 还有令牌，领取令牌
t.Tokens--
return true
}
}
令牌桶有以下特点：
令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量。
计数器和滑动窗口比较
计数器算法实现起来最简单，可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器（每一个格子存一份），所以滑动窗口在实现上需要更多的存储空间。也就是说，如果滑动窗口的精度越高，需要的存储空间就越大。
漏桶算法和令牌桶算法比较
| 漏桶算法 | 令牌桶算法 | |
|---|---|---|
| 请求何时拒绝 | 流入请求速率任意，常量固定速率流出请求。当流入请求数积累到漏桶容量时，则拒绝新请求 | 固定速率往桶中添加令牌，如果桶中令牌不够，则拒绝新请求 |
| 速率限制 | 限制常量流出速率（流出速率是固定值），从而 平滑突发流入速率 | 限制平均流入速率，允许一定程度的突发请求（支持一次拿多个令牌） |
本文主要对常见的限流算法的实现思路进行了介绍，同时给出了一些简单的代码实现，下篇文章中会介绍一些常见的编程语言实现方式和针对场景的应对策略。