聊聊TokenBucket限流器的基本原理及实现

## 限流器实现之TokenBucket 大家好，我是「Go学堂」的渔夫子。上篇文章我们讲解了漏桶（LeakyBucket）的实现原理。本文我们介绍另外一种限流器---令牌桶（TokenBucket）。  ### 令牌桶（TokenBucket）简介 ##### 令牌桶实现的基本思想 令牌桶，顾名思义，是一种通过让请求被处理前先行获取令牌，只有获取到令牌的请求才能被放行处理的一种限流方式。令牌桶的实现包含两个方面： - 一方面是按固定的速率来产生令牌并存入桶中，如果令牌数量超过桶的最大容量则直接丢弃掉。 - 一方面当有请求时先从桶中获取令牌，获取到令牌后才能通过进行处理，否则被直接丢弃或等待获取令牌。 ##### 令牌桶与漏桶（LeakyBucket）的区别 令牌桶与漏桶的区别在于漏桶控制的是请求被处理的速率。即当有请求的时候，先进入桶中进行排队，按固定的速率流出被处理；而令牌桶控制的是令牌产生的速率。即当有请求的时候，先从令牌桶中获取令牌，只要能获取到令牌就能立即通过被处理，不限制请求被处理的速度，所以也就可以应对一定程度的突发流量。如图所示二者的区别：  比如有100个请求同时进入。现在假设漏桶的速率是每10ms处理一个请求，那么要处理完这100个请求需要1秒钟，因为每处理完1个请求，都需要等待10ms才能处理下一个请求。 如果是令牌桶，假设令牌桶产生令牌的速率也是每10ms产生一个，那么1秒钟就是产生100个令牌。所以，一种极端的情况就是当这100个请求进入的时候，桶中正好有100个令牌，那么这100个请求就能瞬间被处理掉。 ### golang中的time/rate包 golang.org/x/time/rate 包就是基于令牌桶实现的。我们先来看下该包的使用，然后再分析该包的具体实现。 ```golang func main() { //构造限流器。第一个参数代表qps，即每秒钟能够产生多少令牌，第二个参数是指桶的最大容量，即最多能容下5个token limiter := NewLimiter(10, 5) for i := 0; i < 10; i++ { time.Sleep(time.Millisecond * 20) //Allow指去获取令牌，如果没获取到，返回false if !limiter.Allow() { fmt.Printf("%d passed\n", i) continue } //说明请求通过Allow获取到令牌了，继续处理请求 fmt.Println("%d droped\n" i) //todo 对请求的后续处理 } } ``` ### time/rate实现原理 在简介的部分我们提到，令牌桶需要按固定速率生成Token。直观的理解就是在令牌桶的实现中会有一个定时任务不断的生成Token。但在 Golang 的 time/rate 中的实现, 并没有单独维护一个定时任务，而是采用了 lazyload 的方式，直到每次有请求消费之前才根据时间差更新 Token 数目，同时通过计数的方式来计算当前桶中已有的Token数量。 #### Token的生成和消耗 在开头处我们提到，令牌桶是以固定的**速率**产生Token，该速率就是我们在使用NewLimiter构造一个限流器时指定的第1个参数limit，代表每秒钟可以产生多少个Token。 ```golang func NewLimiter(r Limit, b int) *Limiter { return &Limiter{ limit: r, burst: b, } } ``` 那么换算一下，就可以知道每生成一个Token的**间隔时间** perToken = 1秒/limit。假如我们指定的limit参数是100，那么perToken=1秒/100 = 10毫秒。 上文提到，time/rate包使用的是懒加载的方式生成的Token。什么是懒加载的方式呢？就是当有请求到来时，去桶中获取令牌的同时先计算一下从上次生成令牌到现在的这段时间应该添加多少个令牌，把增量的令牌数先加到总的令牌数据上即可，后面被取走的令牌再从总数中减去即可。所以，我们在限流器中应该记录下最近一次添加令牌的时间和令牌的总数，Limiter的结构体会是如下这样： ```golang type Limiter struct { limit Limit //QPS，一秒钟多少个token burst int //桶的容量，即最大能装多少个令牌 tokens float64 //当前的token数量 last time.Time //last代表最近一次更新tokens的时间 } ``` 好了，到这里，我们有了生成一个token的时间间隔、最近一次更新tokens的时间、当前时间、当前的token数量四个属性，就能很容易的计算每次有请求获取令牌时，应该生成的令牌数量以及当前桶中总剩余的令牌数了： ```shell tokens += (当前时间 - 最近一次更新tokens的时间last) / 时间间隔 ``` 消耗的话，就是看当前的令牌总数是不是大于0就好了，如果大于0，相当于该请求可以获取令牌，从tokens中减1，代表给该请求发放了一个令牌，该请求拿着令牌就能被通过进行处理了。 那到这里是不是该算法就结束了呢？并不是。那该TokenBucket是如何应对突发流量呢？ #### 如何应对突发流量 所谓突发流量，就是在某个时刻的流量突然比平时的流量要高。光有突发流量还不够，得系统能够应对才行，即能够正常处理，否则就不叫应对突发流量了。那令牌桶是如何应对突发流量的呢？**就是通过令牌桶缓存到的令牌来应对的，再加上令牌桶的最大容量约束，不会无限制的让流量通过。** 下面我们具体来看下应对突发流量的过程。  假设生成令牌的速率是每秒100个。而平常的请求平均值也就是每秒80个。也就是说每秒钟令牌数能剩余20个，那这剩余的令牌就是用来应对突发流量的。例如在10秒后，就会有200个令牌剩余，如果这个时候比平常多来200个请求，那么令牌数也足以让每个请求都领取到令牌从而被正常处理。 那么，问题就又来了，如果在很长一段时间内，我们的系统请求数都很平稳，这样我们就能积攒下很多剩余的令牌，如果剩余的令牌数很多，比如积攒了一千万个了，突然来了一波流量，假设也是一千万，按道理这一千万个请求都能获取到令牌，都能够被处理。可问题是我们的计算机系统本身的资源缺不足以应付这么多请求了，那该怎么办呢？ 这个时候我们的**令牌桶的最大容量属性就该上场了，即Limiter结构体中的burst字段**。burst字段是限制该桶能够存储的最大令牌数，令牌积攒的数量超过该值后，就直接丢弃，不再进行积攒了。该字段也代表我们的系统能够应对的最大的突发流量数。 例如，一种极端的情况，在一段时间内，一个请求都没有，但令牌会按照固定速率一直产生，这时令牌数达到了最大值burst。突然有一波请求来了，假设是burst+n个，那这波流量中也就只有burst个请求能被正常处理，其他的就被拒绝了。因为我们只有burst个令牌。 所以，burst值代表了我们系统应对突发流量的最大值。 #### 数值溢出问题 我们在一开始讲该算法的实现时首先要计算从最后一次更新tokens数量到当前这段时间内产生的令牌数，以及令牌总的数量，一般的计算方式应该如下： ```golang // elapsed表示最后一次更新tokens数量的时间到当前的时间差 elapsed := now.Sub(last) // delta 具有数值溢出风险， 表示elapsed这段时间应该产生的令牌数量 delta := elapsed.Seconds() * float64(limit) //tokens 表示当前总的令牌数量 tokens := lim.tokens + delta if burst := float64(lim.burst); tokens > burst { tokens = burst } ``` 这里有什么问题呢？ 如果last值很小，那么elapsed就会很大，而如果此时指定的token生成速率，即limit值也很大的话，那么一个大值 乘以 一个大值，**结果就很可能会溢出**。 那该怎么办呢？ 我们知道，令牌桶有一个最大值burst，如果超过这个burst，那么多余的其实是没用的。 因此，我们就可以先计算**要填满这个令牌桶最多需要多长时间maxElapsed，如果时间差now.Sub(last)已经超过了该值，那么说明令牌数就应该能达到最大值burst了**。反之，说明now.Sub(last)是一个较小的值，继续计算这段时间应该生成的令牌数即可，这样就规避了大值相乘可能溢出的问题。 如下是time/rate包中的实现： ```golang maxElapsed := lim.limit.durationFromTokens(float64(lim.burst) - lim.tokens) elapsed := now.Sub(last) if elapsed > maxElapsed { elapsed = maxElapsed } delta := lim.limit.tokensFromDuration(elapsed) tokens := lim.tokens + delta if burst := float64(lim.burst); tokens > burst { tokens = burst } ``` #### float64精度问题 我们在上面Limiter的结构体中会注意到，tokens的类型是float64的。你可能会问，难道令牌还有小数点，令牌数量不应该是整数吗？ **是的，令牌数是有可能是小数的。为什么呢？**。 假设，我们指定的生成令牌的速率是每秒产生965个令牌，那么每生成一个令牌的间隔是多少呢？大约是每1.0362毫秒产生一个令牌。那么如果是在100毫秒这段时间会产生多少个令牌呢？大约103.62个令牌。 好了，既然是float64，那么在计算给定时间段内产生的tokens总数时就会有精度问题。我们来看看time/rate包的第一版的实现： ```golang func (limit Limit) tokensFromDuration(d time.Duration) float64 { sec := float64(d/time.Second) * float64(limit) nsec := float64(d%time.Second) * float64(limit) return sec + nsec/1e9 } ``` time.Duration 是 int64 的别名，代表纳秒。分别求出秒的整数部分和小数部分，进行相乘后再相加，这样可以得到最精确的精度。 #### 总结 TokenBucket是以固定的速率生成令牌，让获得令牌的请求才能通过被处理。令牌桶的限流方式可以应对一定的突发流量。在实现TokenBucket时需要注意在计算令牌总数时的数值溢出问题以及精度问题。