写点什么

漏桶算法和令牌桶算法,区别到底在哪里?

用户头像
华仔
关注
发布于: 2021 年 07 月 29 日

漏桶算法和令牌桶算法是接口限流设计中常用的两种算法,网上关于这两个算法的介绍文章有很多,但不同的人有不同的理解,导致很多技术人员在学习的时候,会陷入迷茫的状态,比如说:

1)如果要让自己的系统不被打垮,用令牌桶。如果保证别人的系统不被打垮,用漏桶算法;参考链接

2)在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,所以它适合于具有突发特性的流量。参考链接


我在架构实战营中总结两种算法的技术本质和优缺点分别如下:


大家会看到,与网上的一些文章对比,会有几个区别,而这几个区别就是容易引起混淆的地方,因此我再针对这些地方进一步展开详细解读。


首先,漏桶和令牌桶的区别是保护自己还是保护别人吗?

很显然不是,令牌桶保护自己和保护下游都可以,而不是说保护自己用令牌桶,保护别人用漏桶。

原因很简单,令牌桶就是一个速率控制,你可以用来控制自己的处理速度,也可以控制请求别人的处理速度,都可以起到保护作用;

其实漏桶也可以既保护自己又保护下游,因为请求太多的时候把请求先缓存到漏桶里面了,漏桶放不下就丢弃新的请求,这也是保护机制。


既然如此,两者的区别是什么呢?

其实就是我在课件上写的:漏桶的本质是总量控制,令牌桶的本质是速率控制。至于这个控制,你可以用来保护自己,也可以用来保护别人。

有的技术人员对于“保护别人”可能不太理解,这个主要应用于访问第三方,最典型的例子就是双十一的支付宝,支付的时候要访问银行的接口,银行的接口实际上处理高并发的能力并不强(例如澳门某银行对外提供的移动支付接口,峰值 TPS 是 30 次/s),这个时候支付宝自己处理性能再高都没用,而且越高越容易把下游的银行给压垮,所以支付宝不得不针对下游接口请求做限流。


网上的文章都说令牌桶更适合“突发流量”,为何你这里说漏桶更适合“瞬时高并发”?

其实,令牌桶的“突发流量”跟我们通常理解的“业务高并发”并不一样。令牌桶的算法原本是用于网络设备控制传输速度的,而且它控制的目的是保证一段时间内的平均速率控制,之所以说令牌桶适合突发流量,是指在网络传输的时候,可以允许某段时间内(一般就几秒)超过平均传输速率,这在网络环境下常见的情况就是“网络抖动”,但这个短时间的突发流量是不会导致雪崩效应,网络设备也能够处理得过来。对应到令牌桶应用到业务处理的场景,就要求即使有突发流量来了,系统自己或者下游系统要真的能够处理的过来,否则令牌桶允许突发流量进来,结果系统或者下游处理不了,那还是会被压垮。


而我说漏桶算法更适合“突发流量”,是指秒杀、抢购、整点打卡签到、微博热点事件这种业务高并发场景,它不是由于“XX 抖动”引起的,而是由业务场景引起的,并且持续的事件可能是几分钟甚至几十分钟,这种业务场景为了用户体验和业务尽量少受损,优先采取的不是丢弃大量请求,而是缓存请求,避免系统出现雪崩效应。因此我们会看到,漏桶和令牌桶都有保护作用,但漏桶的保护是尽量缓存请求(缓存不下才丢),令牌桶的保护主要是丢弃请求(即使系统还能处理,只要超过指定的速率就丢弃,除非此时动态提高速率)。


所以如果在秒杀、抢购、整点打卡签到、微博热点事件这些业务场景用令牌桶的话,会出现大量用户访问出错,因为请求被直接丢弃了;而用漏桶的话,处理可能只是会慢一些,用户体验会更好一些,所以我认为漏桶更适合“突发流量”。


维基百科的词条Token bucket上也有类似的内容:

The leaky bucket as a queue is therefore applicable only to traffic shaping, and does not, in general, allow the output packet stream to be bursty, i.e. it is jitter free. It is therefore significantly different from the token bucket algorithm.


其实,漏桶算法限流还是会丢请求,如果你觉得漏桶算法应对突发流量都还不够好,那就要更进一步,采取排队的方式来实现了,排队的方案其实就是一个更复杂的“漏桶”实现,例如下图中的“消息队列”,本质上就是一个“漏桶”:

看到这里,相信你已经对漏桶和令牌桶的区别有了更加清晰的理解,那留一道题目考考你:既然排队里面也用到了一个类似的漏桶,限流也用到了漏桶,这两者的区别又是什么呢


用户头像

华仔

关注

还未添加个人签名 2018.04.24 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
通透了,感谢华仔老师的讲解
2021 年 07 月 29 日 14:24
回复
没有更多了
漏桶算法和令牌桶算法,区别到底在哪里?