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

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

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.

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

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

(0)

相关推荐

  • 服务熔断、隔离、降级、限流 介绍

    服务降级:在高并发的情况下,防止用户一直等待,使用服务降级方式进行处理(返回友好的提示给客户端,fallback回调方法).当服务不可用的时候(正在等待的时候.网络延迟.响应时间过长),客户端会处于一 ...

  • 稳定性五件套-限流的原理和实现

    背景 最近了解到很多朋友对限流.熔断.降级.隔离.超时重试的概念和应用场景理解的不是很到位,所以想用五篇的篇幅稍微系统的介绍一下. 本篇是第一篇,是限流做详解,如果反馈好的话,我会继续写下面四篇.不好 ...

  • SpringCloud微服务网关做边缘服务限流方案

    优质文章,第一时间送达 66套java从入门到精通实战课程分享 在高并发的系统中,往往需要在系统中做限流,一方面是为了防止大量的请求使服务器过载,导致服务不可用,另一方面是为了防止网络攻击. 常见的限 ...

  • 6000多字 | 秒杀系统设计注意点【理论】

    在秒杀的场景中,对于系统的要求其实就三个字:快.准.稳. 本文主要内容: 五个架构原则 数据要尽量少 首先是指用户请求的数据能少就少.请求的数据包括上传给系统的数据和系统返回给用户的数据(通常就是网页 ...

  • 限流10万QPS、跨域、过滤器、令牌桶算法-网关Gateway内容都在这儿

    一.微服务网关Spring Cloud Gateway 1.1 导引 文中内容包含:微服务网关限流10万QPS.跨域.过滤器.令牌桶算法. 在构建微服务系统中,必不可少的技术就是网关了,从早期的Zuu ...

  • 【121期】网关Gateway:限流10万QPS、跨域、过滤器、令牌桶算法

    2020年百日百更原创Java最全面试题库之往期回顾 [000期]Java最全面试题库思维导图 [020期]JavaSE系列面试题汇总(共18篇) [028期]JavaWeb系列面试题汇总(共10篇) ...

  • token bucket令牌桶限流算法原理及代码【图文】

    token bucket令牌桶限流算法原理及代码【图文】

  • 单桶、桶强、雪莉桶、波本桶有什么区别?

    在选购威士忌的时候,我们经常能看到酒标上的单桶(Single Cask/Barrel).桶强(Cask Strength).雪利桶(Sherry Cask).波本桶(Bourbon Cask)等,那么 ...

  • 《算法帝国》:被算法和算法交易改变的未来

    当我们用崭新的视角去观察与思考,世界就会变成另外的模样.这是我们筹备举办"改变未来的算法与算法交易"研讨会的初衷. 美国雄霸全球依赖华尔街与硅谷等强大支柱,而近年来,算法对华尔街的 ...

  • 步进电机驱动算法——梯形加减速算法

    步进电机梯形加减速 电机的控制方式一般分为开环控制与闭环控制两种控制方式,其中开环控制原理框图如下: 这种种控制方式的特点是:控制简单.实现容易.价格较低,这种开环控制方式,负载位置对控制电路没有反馈 ...

  • 【枕边算法】回文算法题PHP实现

    ①选择任一数值: ②翻转此数值(例如,选择13则翻转为31),并将原数值和翻转数值相加(13+31): ③相加结果若不是回文,则返回②反复执行,若是回文则终止算法 举例: 13+31=44,44是回文 ...

  • 陈根:从算法权利到算法权力,打破算法赋权失衡

    文/陈根 当前,大数据的快速发展正使算法融入并重塑人们的生活,算法作为机器可读的程序性指令,利用汇集人类行为的大规模数据集影响着人们方方面面的社会生活.比如,算法推荐新闻.推送广告.排名商品.安排专车 ...

  • 「数据结构与算法」哈希算法的原理和应用详解

    在程序员的实际开发中,哈希算法常常能用得到,本文以哈希算法的原理和应用为核心,和大家详细讲解一下哈希算法的概念.常见算法以及原理.在信息安全的应用等等. 一.概念 哈希表就是一种以 键-值(key-i ...