限流器主要是防止高并发流量打垮服务，常见的限流器算法有计数器、令牌桶和漏桶，令牌桶在令牌不足时会直接拒绝请求，漏桶在请求不足时会阻塞请求。本文实现一个允许适量流量激增的限流器。只是写着玩，不要喷我写的挫谢谢。

计数器

计数器这种类型的限流器比较简单，只要无脑判断窗口内的请求有没有达到限制即可，同时也需要有个后台进程定期重置窗口的请求量。

1. 固定窗口

   限制单位时间内的请求，比如QPS 1k，判断1s内计数是否达到1k，到达就拒绝请求，1s之后清空计数器

   （1）需要一个goroutine每秒重置counter，利用time.Ticker即可

   （2）每次请求过来，都要判断下counter是否达到限制，如果达到限制则拒绝请求，否则执行请求。多个并发请求，需要获得锁才能够修改counter

2. 滑动窗口

   滑动窗口可以在固定窗口的基础上，做更细粒度的划分，比如把1s的请求分成1000个桶，每个桶代表1ms的时间范围。

   （1）每个桶单独维护当前时间范围内的请求个数。这样在请求到来的时候，需要遍历所有的桶计算请求总数

   （2）需要一个定时任务，每隔1ms移除掉一个桶，同时增加一个新桶，具体实现可以采用双向链表，桶对应到链表的一个节点

   下面是实现滑动窗口版需要的数据结构，Node的开始结束时间是为了在

   type Node struct {
   	next    *Node
   	counter int
   
   	start time.Time
   	end   time.Time
   }
   
   type LinkedList struct {
   	Size int
   	Head *Node
   	Tail *Node
   }
   
   type SlidingCounter struct {
   	Limit    int
   	interval int
   	list     *LinkedList
   
   	Ticker *time.Ticker
   	stopCh chan bool
   
   	sync.Mutex
   }

令牌桶

从名字来看，可以知道令牌桶其实就是请求到来的时候，如果能拿到令牌就可以继续请求，否则就会拒绝请求，这里我们需要一个后台进程定期往令牌桶里放入令牌，保证在时间窗口内的令牌数据是始终为最大限制。用golang的话写起来就很方便，搞一个buffered channel就可以了。

type Bucket struct {
	limit  int
	bucket chan bool

	ticker *time.Ticker
	stopCh chan bool
}

漏桶

漏桶可以接受一定量的请求激增，但是处理速度是固定的。比如QPS 1k/s，可以采用定时任务每1ms往一个buffered channel塞数据，这样可以保证固定的处理速率。这里就先不实现了，在令牌桶的基础上改一改就可以了。

我上面实现的都是比较粗糙的写法，真正的限流器用法应该是RateLimiter.take()，能够拿到就可以处理请求。

具体实现见代码rate-limiter

主流限流器实现方法

我的实现方法是可以理解为定时放令牌，而主流的方法是计算请求到来的时候可以拿多少个令牌。golang官方扩展包github/go/time是基于令牌桶实现，uber开源库是基于漏桶实现的。