限流算法介绍
前言
最近在看好未来开源的微服务框架go-zero，看到其中的限流算法时，感觉这方面自己不是很清楚，就查阅了下网上相关的资料，下面算是对查阅资料的整理吧。
限流介绍
限流，顾名思义就是“限制流量”，可以避免高并发系统中，在短时间内由于请求太多导致系统崩溃的问题。
常见的限流算法
常见的限流算法主要是计数器算法、令牌桶算法、漏桶算法。
计数器算法
计数器算法是限流算法里最简单、最容易实现的一种算法。使用计数器来进行限流，主要用来限制总并发数，比如数据库连接池、线程池、秒杀的并发数；只要全局总请求数或者一定时间段的总请求数达到设定的阀值则进行限流，是粗暴的总数量限流，而不是平均速率限流。
设置一个计数器counter，来一个请求counter的数值就+1，没超过counter设置的最大值就不限流，一段时间后就重置counter。这个算法简单粗暴，但是有一个漏洞就是，在重置counter的时刻前后有临界问题，这可能导致我们的系统流量瞬时超过counter的最大值。
为了降低临界问题带来的影响，这里我们可以引入滑动窗口算法，将原本的一段时间，平均分成多个时间窗口，每个时间窗口单独维护一个counter，当每过一个时间窗口的时段后，我们会把时间窗口向右移动一格，这样就能避免计数器算法的临界问题。(如下图)
回顾计数器算法，其实它就是滑动窗口算法，只不过它没有对时间段进行划分，时间窗口只有一格。由此可见，当滑动窗口的数量越多，窗口的移动就会更平滑，这样我们限流的统计也就越精确。
令牌桶算法
令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。桶中最多存放一定数量的令牌,当桶满时，新添加的令牌被丢弃或拒绝。
如图所示:
漏桶算法
漏桶作为计量工具（The Leaky Bucket Algorithm as a Meter）时，可以用于流量整形（Traffic Shaping）和流量控制（TrafficPolicing），漏桶算法的描述如下：
- 一个固定容量的漏桶，按照常量固定速率流出水滴；
- 如果桶是空的，则不需流出水滴；
- 可以以任意速率流入水滴到漏桶；
- 如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。
令牌桶和漏桶对比：
- 令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；
- 漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；
- 令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；
- 漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；
- 令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率；
- 两个算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的。(因此图就不画了)