说说高并发限流策略

分析&回答

常用限流算法

计数器算法

单位时间内设定限频阈值，如果访问超过该阈值则拒绝。实现简单，缺点是容易在小突发流量情况下，拒绝很多请求，影响服务可用性

漏桶算法(Leaky Bucket)

漏桶作为计量工具（The Leaky Bucket Algorithm as a Meter）时，可以用于流量整形（Traffic Shaping）和流量控制（TrafficPolicing）。核心思想就是请求收到后，会先进入漏桶，然后再按照限定速度请求服务，及可以达到限流的目的，也可以保证后台收到的请求都是平稳的。但是也有一个缺点，就是突然流量的时候，会导致处理时间太长。当然流量更大的时候会被拒绝，这个是正常的。漏桶算法的描述如下：

一个固定容量的漏桶，按照常量固定速率流出水滴；
如果桶是空的，则不需流出水滴；
可以以任意速率流入水滴到漏桶；
如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

常见实现方式有：限制大小的队列

令牌桶算法(Token Bucket)

令牌桶算法是一个存放固定容量令牌的桶，按照固定速率往桶里添加令牌。核心思想是所有请求需要在令牌桶获取到令牌才可以处理，同时有一个服务匀速的往令牌桶装令牌。可以满足一定的突发请求处理，如果超过令牌桶的请求，也会被拒绝。令牌桶算法的描述如下：

假设限制2r/s，则按照500毫秒的固定速率往桶中添加令牌；
桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝；
当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上；
如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。

常见实现方式有：gauva包中的RateLimiter

应用级限流

限流总并发/连接/请求数

对于一个应用系统来说一定会有极限并发/请求数，即总有一个TPS/QPS阀值，如果超了阀值则系统就会不响应用户请求或响应的非常慢，因此我们最好进行过载保护，防止大量请求涌入击垮系统。

限流总资源数

如果有的资源是稀缺资源（如数据库连接、线程），而且可能有多个系统都会去使用它，那么需要限制应用；可以使用池化技术来限制总资源数：连接池、线程池。比如分配给每个应用的数据库连接是100，那么本应用最多可以使用100个资源，超出了可以等待或者抛异常。

限流某个接口的总并发/请求数

如果接口可能会有突发访问情况，但又担心访问量太大造成崩溃，如抢购业务；这个时候就需要限制这个接口的总并发/请求数总请求数了；因为粒度比较细，可以为每个接口都设置相应的阀值。

限流某个接口的时间窗请求数

即一个时间窗口内的请求数，如想限制某个接口/服务每秒/每分钟/每天的请求数/调用量。如一些基础服务会被很多其他系统调用，比如商品详情页服务会调用基础商品服务调用，但是怕因为更新量比较大将基础服务打挂，这时我们要对每秒/每分钟的调用量进行限速；

平滑限流某个接口的请求数

之前的限流方式都不能很好地应对突发请求，即瞬间请求可能都被允许从而导致一些问题；因此在一些场景中需要对突发请求进行整形，整形为平均速率请求处理（比如5r/s，则每隔200毫秒处理一个请求，平滑了速率）。这个时候有两种算法满足我们的场景：令牌桶和漏桶算法。Guava框架提供了令牌桶算法实现，可直接拿来使用。

Guava RateLimiter提供了令牌桶算法实现：平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。

分布式限流

分布式限流最关键的是要将限流服务做成原子化，而解决方案可以使使用redis+lua或者nginx+lua技术进行实现，通过这两种技术可以实现的高并发和高性能。

反思&扩展

令牌桶和漏桶对比：

令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；
漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；
令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；
漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；
令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率；
两个算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的。