限流器是微服务中必不缺少的一环，可以起到保护下游服务，防止服务过载等作用。上一篇文章《Golang限流器time/rate使用介绍》简单介绍了time/rate的使用方法，本文则着重分析下其实现原理。建议在正式阅读本文之前，先阅读下上一篇文章。

上一篇文章讲到，time/rate是基于Token Bucket(令牌桶)算法实现的限流。本文将会基于源码，深入剖析下Golang是如何实现Token Bucket的。其代码也非常简洁，去除注释后，也就200行左右的代码量。

同时，我也提供了time/rate注释版，辅助大家理解该组件的实现。

背景

简单来说，令牌桶就是想象有一个固定大小的桶，系统会以恒定速率向桶中放Token，桶满则暂时不放。 而用户则从桶中取Token，如果有剩余Token就可以一直取。如果没有剩余Token，则需要等到系统中被放置了Token才行。

一般介绍Token Bucket的时候，都会有一张这样的原理图：


从这个图中看起来，似乎令牌桶实现应该是这样的：

有一个Timer和一个BlockingQueue。Timer固定的往BlockingQueue中放token。用户则从BlockingQueue中取数据。

这固然是Token Bucket的一种实现方式，这么做也非常直观，但是效率太低了：我们需要不仅多维护一个Timer和BlockingQueue，而且还耗费了一些不必要的内存。

timer/rate

Token的生成和消费

我们在上一篇文章中讲到，Token的消费方式有三种。但其实在内部实现，最终三种消费方式都调用了reserveN函数来生成和消费Token。

我们看下reserveN函数的具体实现，整个过程非常简单。在正式讲之前，我们先了解一个简单的概念：

在`time/rate`中，`NewLimiter`的第一个参数是速率limit，代表了一秒钟可以产生多少Token。
那么简单换算一下，我们就可以知道一个Token的生成间隔是多少。

有了这个生成间隔，我们就可以轻易地得到两个数据：
1. 生成N个新的Token一共需要多久。time/rate中对应的实现函数 durationFromTokens。
2. 给定一段时长，这段时间一共可以生成多少个Token。time/rate中对应的实现函数为tokensFromDuration。

那么，有了这些转换函数，整个过程就很清晰了，如下：
1. 计算从上次取Token的时间到当前时刻，期间一共新产生了多少Token：
我们只在取Token之前生成新的Token，也就意味着每次取Token的间隔，实际上也是生成Token的间隔。我们可以利用tokensFromDuration, 轻易的算出这段时间一共产生Token的数目。
那么，当前Token数目 = 新产生的Token数目 + 之前剩余的Token数目 - 要消费的Token数目。

2. 如果消费后剩余Token数目大于零，说明此时Token桶内仍不为空，此时Token充足，无需调用侧等待。
如果Token数目小于零，则需等待一段时间。
那么这个时候，我们可以利用durationFromTokens将当前负值的Token数转化为需要等待的时间。

3. 将需要等待的时间等相关结果返回给调用方。

从上面可以看出，其实整个过程就是利用了Token数可以和时间相互转化的原理。 而如果Token数为负，则需要等待相关时间即可。

注意：如果当消费时，Token桶中的Token数目已经为负值了，依然可以按照上述流程进行消费。随着负值越来越小，等待的时间将会越来越长。 从结果来看，这个行为跟用Timer+BlockQueue实现是一样的。

此外，整个过程为了保证线程安全，更新令牌桶相关数据时都用了mutex加锁。

我们模拟下请求与Token数变化的关系：
1. 当某一时间，桶内Token数为3, 此时A线程请求5个Token。那么此时桶内Token不足，因此A线程需要等待2个Token的时间。且此时桶内Token数变为-2。
2. 同时，B线程请求4个Token，此时桶内Token数为-2，因此B线程需要等待2+4=6个Token的时间，且此时桶内Token数变为-6。

对于Allow函数实现时，只要判断需要等待的时间是否为0即可，如果大于0说明需要等待，则返回False，反之返回True。

t := time.NewTimer(delay)

float精度问题

durationFromTokenstokensFromDuration
tokensFromDuration
d.Seconds()

所以就有了这个issue:golang.org/issues/34861。

修改后新的版本如下：

time.Durationint64

数值溢出问题

我们讲reserveN函数的具体实现时，第一步就是计算从当前时间到上次取Token的时刻，期间一共新产生了多少Token，同时也可得出当前的Token是多少。

我最开始的理解是，直接可以这么做：

lim.tokenslim.lastlim.burst

这么做看起来也没什么问题，然而并不是这样。

time/rate
now.Sub(lim.last)lim.limit.durationFromTokens(float64(lim.burst) - lim.tokens)

这么做算出的结果肯定是正确的，但是这么做相比于我们的做法，好处在哪里？

now.Sub(lim.last)lim.limit
time/rate

Token的归还

Reservation.Delay()Reservation.Cancel()Cancel()

此外，我们在上一篇文章中讲到，Wait函数可以通过Context进行取消或者超时等， 当通过Context进行取消或超时时，此时消费的Token数也会归还给Token桶。

然而，归还Token的时候，并不是简单的将Token数直接累加到现有Token桶的数目上，这里还有一些注意点：

r.tokensr.timeToActr.lim.lastEvent
r.limit.tokensFromDuration(r.lim.lastEvent.Sub(r.timeToAct))

根据代码来看，要归还的Token要是该次消费的Token减去新消费的Token。 不过这里我还没有想明白，为什么归还的时候，要减去新消费数目。

按照我的理解，直接归还全部Token数目，这样对于下一次消费是无感知影响的。这块的具体原因还需要进一步探索。

总结

Token Bucket其实非常适合互联网突发式请求的场景，其请求Token时并不是严格的限制为固定的速率，而是中间有一个桶作为缓冲。 只要桶中还有Token，请求就还可以一直进行。当突发量激增到一定程度，则才会按照预定速率进行消费。

此外在维基百科中，也提到了分层Token Bucket(HTB)作为传统Token Bucket的进一步优化，Linux内核中也用它进行流量控制。

参考


关于time/rate的使用介绍，可点击查看下面文章：