专栏首页系统高可用常见限流算法探究
原创

常见限流算法探究

前言

限流,顾名思义就是对请求应用的流量进行限制,对于超过限流阈值的流量进行丢弃,用于保护系统处于一个合理的流量压力之下,不会因为突发的不可预知的大量请求打死。

限流常见的应用场景是秒杀、下单和评论等 突发性 并发问题。

典型的限流算法有漏桶(leaky bucket)算法和令牌桶(token bucket)算法。

漏桶(leaky bucket)算法

漏桶算法

具体算法:

·一个固定容量的漏桶,按照常量固定速率流出水滴;

·如果桶是空的,则不需流出水滴;

·可以以任意速率流入水滴到漏桶;

·如果流入水滴超出了桶的容量,则流入的水滴溢出了(被丢弃),而漏桶容量是不变的。

令牌桶(Leaky Bucket)算法

令牌桶算法基本思路是按照恒定的速率向桶中放入令牌,每当请求经过时则消耗一个或多个令牌。当桶中的令牌为 0 时,请求则会被阻塞。

令牌桶算法

具体算法:

·假设限制2r/s,则按照500毫秒的固定速率往桶中添加令牌;

·桶中最多存放b个令牌,当桶满时,新添加的令牌被丢弃或拒绝;

·当一个n个字节大小的数据包到达,将从桶中删除n个令牌,接着数据包被发送到网络上;

·如果桶中的令牌不足n个,则不会删除令牌,且该数据包将被限流(要么丢弃,要么缓冲区等待)。

备注:令牌桶算法支持先消费后付款,比如一个请求可以获取多个甚至全部的令牌,但是需要后面的请求付费。也就是说后面的请求需要等到桶中的令牌补齐之后才能继续获取。

漏桶算法 VS令牌桶算法

·令牌桶是按照固定速率往桶中添加令牌,请求是否被处理需要看桶中令牌是否足够,当令牌数减为零时则拒绝新的请求;

·漏桶则是按照常量固定速率流出请求,流入请求速率任意,当流入的请求数累积到漏桶容量时,则新流入的请求被拒绝;

·令牌桶限制的是平均流入速率(允许突发请求,只要有令牌就可以处理,支持一次拿3个令牌,4个令牌),并允许一定程度突发流量;

·漏桶限制的是常量流出速率(即流出速率是一个固定常量值,比如都是1的速率流出,而不能一次是1,下次又是2),从而平滑突发流入速率;

开源限流组件对比

·Hystrix是Netflix的一款开源限流组件,目前已停止开发了,目前官方并没有给出原因。

·resilience4j 是一个比较轻量的熔断降级库,Hystrix官方推荐使用。

·Sentinel是阿里开源的一个包含流量控制、熔断降级、系统负载保护功能的组件。

最后

不论是对于令牌桶拿不到令牌被拒绝,还是漏桶的水满了溢出,都是为了保证大部分流量的正常使用,而牺牲掉了少部分流量,这是合理的,如果因为极少部分流量需要保证的话,那么就可能导致系统达到极限而挂掉,得不偿失。

参考

·常用限流方案的设计和实现

·限流熔断技术选型:从Hystrix到Sentinel

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 常见的限流算法

    计数器:在一定时间间隔内(时间窗),对请求数进行计数,达到阈值之后就拒绝请求服务。

    用户5705150
  • 三种常见的限流算法

    1、计数器算法 计数器算法是限流算法里最简单也是最容易实现的一种算法。比如我们规定,对于A接口来说,我们1分钟的访问次数不能超过100个。那么我们可以这么做:...

    林老师带你学编程
  • 三种常见的限流算法

    一般做接口限流主要是为了应对突发流量,避免突发流量拖垮服务。如下面一些场景就有可能发生突发流量

    Java识堂
  • 接口限流常见的四种算法

    将时间划分为多个窗口,窗口内出现一次请求就将计数器加一,如果计数器超过了限制数量,则本窗口内后续请求都被丢弃当,时间到达下一个窗口时,计数器重置。

    Java架构师必看
  • 探索常见的几种限流策略和实现

    常见的算法有 漏桶(leaky bucket)、 令牌桶(TokenBucket)、 计数器,本章通过最简单的代码和最直白的文字描述三种的实现方式(基于本地而不...

    battcn
  • 常见限流算法以及限流在单机分布式场景下的思考

    今天来说说限流的相关内容,包括常见的限流算法、单机限流场景、分布式限流场景以及一些常见限流组件。

    程序IT圈
  • Java并发编程(8)- 应用限流及其常见算法

    本文仅针对限流做一些简单的说明,那么何为限流呢?顾名思义,限流就是限制流量,就像你宽带包了1个G的流量,用完了就没了。通过限流,我们可以很好地控制系统的qps,...

    端碗吹水
  • 常见的限流解决方案

    降级是当服务出现问题或者影响到核心流程时,需要暂时屏蔽掉,待高峰或者问题解决后再打开限流限流的目的是通过对并发访问/请求进行限速,或者对一个时间窗口内的请求进行...

    用户3467126
  • 常见算法

    郭楷丰
  • 算法偏见侦探

    AI 科技评论按:随着越来越多的算法不断渗透入社会的层层面面,如医疗机构、政府部门,对算法偏见的讨论越来越多。这个月,Nature 杂志评选出 2018 年最受...

    AI科技评论
  • 常见hash算法

    hash算法的意义在于提供了一种快速存取数据的方法,它用一种算法建立键值与真实值之间的对应关系,(每一个真实值只能有一个键值,但是一个键值可以对应多个真实值),...

  • 简析限流算法

    限流顾名思义是限制流量,限制流量的目的是为了保障服务稳定运行,避免服务被流量冲垮。当流量超出服务处理能力时,部分请求将会被限流组件拦截。被拦截的请求可能会被丢弃...

    田小波
  • 接口限流算法

    爱撒谎的男孩
  • 流式计算常见模块用法说明

    StreamingPro有非常多的模块可以直接在配置文件中使用,本文主要针对流式计算中涉及到的模块。

    用户2936994
  • 常见限流方案设计与实现

    编者注:高并发系统设计的3个利器:缓存、限流、降级,本文就限流相关算法,分析其设计与实现。

    luoxn28
  • 《常见排序算法》

    1.概述 常见的排序算法,虽然很基础,但是很见功力,如果能思路清晰,很快写出来各个算法的代码实现,还是需要花一点功夫的,今天,就跟大家盘点下常用的一些算法。 冒...

    企鹅号小编
  • 图的常见算法

     图是由一系列点和边的集合构成的,一般有邻接矩阵和邻接表两种表示方式,c/c++可以看我的这篇文章:搜索(1)  这篇文章主要讲java语言中图的相关算法。首...

    mathor
  • 算法常见问题

    逻辑回归要点:逻辑回归是通过sigmoid函数使损失函数达到最小或者是似然函数达到最大通过相应的优化算法求出其中的参数值实现分类。(什么优化算法:了解过梯度下降...

    步履不停凡
  • 高效幂模算法探究:Montgomery算法解析

    模运算,又称模算数(modular arithmetic),是一个整数的算术系统,其中数字超过一定值后(称为模)会“卷回”到较小的数值,模运算最早是卡尔·弗里德...

    FB客服

扫码关注云+社区

领取腾讯云代金券