限流算法：漏桶与令牌桶

在大量并发访问的场景里，系统很容易由于过多的请求而崩溃。在系统被拆分成多个微服务之后，每个微服务具有独立性，有责任保护好自己。为了避免因为负载过高导致服务崩溃，可以使用限流。一、...

在大量并发访问的场景里，系统很容易由于过多的请求而崩溃。在系统被拆分成多个微服务之后，每个微服务具有独立性，有责任保护好自己。为了避免因为负载过高导致服务崩溃，可以使用限流。

一、漏桶

漏桶算法原理示意图

请求在到达服务器后，首先会被放到一个“桶”里面。系统会以恒定的速率从“桶”里面取请求进行处理。“桶”是有大小限制的，当“桶”满了的时候，再收到的请求是无法放到桶里面的，会做抛弃处理，可以向客户端返回稍后重试的错误。这个“桶”可以用队列来实现。为了解决竞争问题，可以使用阻塞队列。为了尽量减少多线程访问的冲突，可以使用无锁队列（对于无锁队列会在以后的文章中进行讲解）。

二、令牌桶

令牌桶算法原理示意图

请求到达服务器后，会申请令牌，如果能够拿到令牌则服务器进行处理，拿不到，则做抛弃处理。对于一次申请令牌的数量，可以每个请求一个或者按着请求的数据量进行分配，具体要根据场景来设定。服务器会定期的向“桶”内添加令牌，如果令牌基本没怎么消耗，超过了令牌“桶”的大小，则待添加的令牌会被丢弃，不会放入令牌桶。令牌桶算法常用Guava的RateLimiter来实现或者Semphore来实现。

三、二者比较

个人认为漏桶更适合异步请求，可以对突发的高并发请求进行削峰。但是这样带来的后果就是，在高并发时，请求的处理时间被变长。因为在超过处理能力之后，请求会被积压到“桶”里面，待前面的请求处理完后才会被处理。当用户请求是异步请求时，对用户体验较好，也能提供吞吐量。而令牌桶则适合同步请求，对于突发的请求能够以提高处理速率的方式消化请求。在当前的互联网下，请求响应的速度要快。令牌桶算法能够保证在处理能力范围内的请求都能够快速被处理。

总之，两个算法是从不同的方面处理高并发，漏桶是增加缓存，将1秒内到来的请求5秒处理完，使每秒的压力减小。令牌桶则是在处理能力范围内，加快处理速度，1s到来的请求1秒消化完。至于选择哪种算法，需要根据具体的业务场景，二者的区别已经在上面讲了，权衡利弊做出选择。

发表于 2020-02-12 16:54
阅读 ( 532 )

限流算法：漏桶与令牌桶

你可能感兴趣的文章

相关问题

0 条评论

作家榜 »