限流技术中的常用算法及其优缺点
我们通常说缓存、降级，以及限流技术是高并发服务的三大利器，本文我们就来聊聊限流技术中常用的算法。为保证服务的可用性，限流往往是服务端接口的必备特性之一，用于对抗大规模恶意或无效请求，保护有限的计算和存储资源。关于接口限流有很多成熟的算法可供使用，包括：计数器、漏桶，以及令牌桶等，这些算法都为实际项目中的限流器设计提供了理论支撑。
计数器算法
计数器应该是最简单、最容易想到的限流策略，毕竟限流的本质就是限制一个接口在某个维度上单位时间内的响应次数。我们可以设置一个计数器对某一时间段内的请求进行计数，当请求量超过某个事先设定的阈值时则触发饱和策略，拒绝用户的请求。比如我们事先设定某个接口单一 IP 维度在 1 分钟内只能正常响应 100 次用户请求，那么如果范围内某个 IP 请求超过该阈值，就会拒绝后续请求。
计数器方法存在的一个缺点是计数不够平滑。考虑一个 10 点开放抢购的场景，如果一个恶意用户在 09:59:30 ~ 09:59:59 之间请求了 100 次，然后等到 10 点整时计数器被清空，这个时候该用户在 10:00:00 ~ 10:00:30 之间又可以再次请求 100 次，实际上在 09:59:30 ~ 10:00:30 这一分钟内该恶意用户请求了 200 次，成功绕过了限流策略。
针对计数器算法存在的上述缺陷，一种典型的解决方法就是采用 滑动窗口策略 。以上述场景为例，我们可以为 1 分钟 100 次的请求上限设置一个大窗口，并对该窗口进一步细分，比如每 10 秒设置一个小窗口，该窗口的频率上限同样设置为 100。这样，大窗口中包含了 6 个小窗口，并且每隔 10 秒大窗口就往前移动一个小窗口长度。这样的设计下，如果一个恶意用户在 09:59:30 ~ 09:59:59 之间请求了 100 次，等到 10:00:00 ~ 10:00:30 时这 100 次计数仍然是有效的，所以这个时间段该用户新的请求仍然会被拒绝。
漏桶算法
漏桶（Leaky Bucket）算法是限流方面比较经典的算法，该算法最早应用于网络拥塞控制方面。要理解该算法可以联想一个具体的漏桶模型，不管进水量有多大，漏桶始终以恒定的速率往外排水，如果桶被装满则后来涌入的水会漫出去。
对应接口限流而言，用户的请求可以看作是这里的水，不管用户的请求量有多大多不均衡，能够被处理的请求速率是恒定的，而且能够被接受的请求数也是有上限的，超出上限的请求会被拒绝，典型的我们可以采用队列作为这里的漏桶实现。
由上面的解释我们应该能够体会到漏桶算法非常适用于秒杀系统的限流。漏桶在这种应用场景下可以起到一定的削峰填谷的作用，并且漏桶的设计从根本上能够应对集中访问的问题，同时具备平滑策略。然而，始终恒定的处理速率有时候并不一定是好事情，对于突发的请求洪峰，在保证服务安全的前提下，应该尽最大努力去响应，这个时候漏桶算法显得有些呆滞。
令牌桶算法
令牌桶（Token Bucket）算法可以看作是计数器算法的逆过程，不过相对于计数器来说更加平滑。该算法要求系统以一定的速率发放访问令牌，用户的请求必须在持有合法令牌的前提下才能够被响应。我们可以按照权重设置一类请求被响应所需持有的令牌数，只有当桶中的令牌数目满足当前请求所需时才授予令牌，对于其它情况则拒绝请求。
由于发放令牌的速率是恒定的，所以对于集中请求来说，令牌桶算法能够很好的做平滑。例如前面列举的在 09:59:30 ~ 09:59:59 之间有 100 次的突发请求，那么等到 10 点整的时候系统并不会立即容忍 100 次新的请求，这个时候服务的响应受限于当前桶中的令牌数量。实际项目中我们可以基于当前服务能力动态调整令牌的发放速率，此外我们还需要为桶设置大小上限（或者为令牌设置生命周期），以防止大量令牌累积导致的“伪限流失效”现象。
Guava 库中的 RateLimiter 类是对令牌桶算法的单机版实现，基于 RateLimiter 我们可以设置每秒生成的令牌数，并允许以阻塞、尝试，以及超时等策略获取令牌。
总结
总的来说，计数器算法在实现层面比较简单，但是如果要做到平滑需要引入滑动窗口策略；漏洞算法天生具备平滑属性，但是在面对流量突增时调整起来不够方便，显得有些呆滞；令牌桶算法同样具备平滑属性，并且能够通过简单调整令牌的发放频率以应对流量突增，但是如果在流量突增时有大量累积可用的令牌则会导致短暂的限流失效假象。
限流器在实现层面并没有太多复杂的逻辑，不过正如以前听一位长者所说，限流的难点在于配置 ，不管是静态配置还是动态配置，如何让限流在不误伤的前提下尽量发挥硬件的最大性能是一个富有经验的问题，而压测是一个基础且行之有效的途径。