重庆餐饮网站建设,wordpress没有评论框,天津正规制作网站公司,网站开发7个基本流程图「并发编程实战」常见的限流方案 文章目录「并发编程实战」常见的限流方案一、概述二、计数器限流方案三、时间窗口限流方案四、令牌桶限流方案五、漏桶限流方案六、高并发限流算法小结文章参考#xff1a; 追忆四年前#xff1a;一段关于我被外企CTO用登录注册吊打的不堪往事…「并发编程实战」常见的限流方案 文章目录「并发编程实战」常见的限流方案一、概述二、计数器限流方案三、时间窗口限流方案四、令牌桶限流方案五、漏桶限流方案六、高并发限流算法小结文章参考 追忆四年前一段关于我被外企CTO用登录注册吊打的不堪往事 新来个技术总监把限流实现的那叫一个优雅佩服 接口限流算法总结 一、概述
曾经在一个大神的里看到这样一句话在开发高并发系统时有三把利器用来保护系统缓存、降级和限流。那么何为限流呢顾名思义限流就是限制流量就像你宽带包了1个G的流量用完了就没了。通过限流我们可以很好地控制系统的qps从而达到保护系统的目的。本篇文章将会介绍一下常用的限流算法以及他们各自的特点。
什么是限流呢限流是限制到达系统的并发请求数量保证系统能够正常响应部分用户请求而对于超过限制的流量则通过拒绝服务的方式保证整体系统的可用性。
根据限流作用范围可以分为单机限流和分布式限流根据限流方式又分为计数器、滑动窗口、漏桶限令牌桶限流下面我们对这块详细进行讲解。 二、计数器限流方案
计数器方案属于限流算法中最简单、并且实现难度最低的算法比如以短信接口调用为例规定了「短信」接口的调用频率不允许在十分钟内超出三次。
这时实现起来就很简单在「短信」接口的类中创建一个MapString,AtomicInteger类型的容器即可其中Key存储用户ID而Value则存储一个原子计数器每当一个用户调用一次短信接口后就将容器中对应的计数器加一同时开启一个定时任务每十分钟对计数器做归零重置。 当然上述这种做法在用户量较大的情况下显然会对程序造成较大的性能损耗假设有100W用户那就需要维护100W个计数器这会使得内存占用率直线飙升同时还需要创建100W个定时器来分别维护每个用户的调用计数器。 更好一些的做法是借助中间件实现比如基于Redis缓存中间件来完成将用户ID设计成Key而Value则是计数器并且创建每个Key时将过期时间指定为10s这样就能充分利用资源不会造成太大的资源与性能开销伪逻辑如下
Autowired
private StringRedisTemplate redis;RequestMapping(/sendSmsVerification)
public ResultVO sendSmsVerification(String sign, String userId){// 用 SMS_ 拼接用户ID作为KeyString userIdSMS SMS_ userId;// 先通过前面生成的Key去Redis中进行查询String value redis.opsForValue().get(userIdSMS);// 如果目前已经达到了调用次数限制if (3.equals(value)) {return new ResultVO(200, 短信调用次数已达上限请在十分钟后重试...);}// 如果该用户的Key在Redis中不存在说明是第一次调用短信接口if (.equals(value)) {// 首次调用短信接口时则在Redis中创建一个计数器redis.opsForValue().set(lockKey, 1, 10, TimeUnit.SECONDS);} // 如果该用户的Key在Redis中存在说明并非第一次调用短信接口else {// 此时则通过Redis的incr命令把对应的计数器加一redis.opsForValue().increment(key);}// 省略其他业务代码......
}
复制代码这段限流代码并不算特别复杂整体下来无非还是前面说的那几步
①先通过用户ID拼接得到Key然后去Redis中进行查询。②如果查询出的结果为3说明目前已达到了调用限制则直接返回调用已达上限。③如果查询出的结果为空则说明用户是第一次调用短信接口此时则在Redis中创建计数器。④如果查询出的value和上面两条都不匹配则对Redis中的计数器加一。
这种计数器限流算法实现起来尤为简单但前面也聊过它所存在的问题临界问题如果在两个时间单位的临界处调用比如在第9:59秒调用了三次接着又在第10:01秒调用了三次那依旧会发生“超出调用上限”的情况毕竟以十分钟作为单位第9、10分钟属于一个时间单位内这时就超出了调用上限调用次数达到6次。 三、时间窗口限流方案
时间窗口限流方案被提出的主要目的就是为了解决传统的计数器方案存在的临界问题它的演变前身为TCP协议的滑动窗口如果对于TCP协议较为熟悉的小伙伴听到这个词汇相信一定不陌生如若对这块内容并不熟悉的小伙伴也没关系可参考之前文章中聊过的《TCP粘包、半包问题-滑动窗口》。 限流方案中的时间窗算法主要可被分为固定窗口限流、滑动窗口限流两种方案而前面聊到的计数器方案实际上就是一种特殊的固定窗口限流方案在前面的例子中时间窗口大小为10min速率限制为3次这种方案存在明显的临界限制问题。 下面重点聊一聊滑动时间窗口这种方案是解决临界问题而被提出的但对于滑动窗口的概念有些不好理解所以先上一副逻辑图如下 在上图中整个用虚红线圈出来的代表一个时间窗口以上述例子来说一个窗口的大小为600s/10min并且每个窗口被分为了三个单位每个单位大小是200s这也就意味着每过200s窗口会向后滑动一个单位这个动作也可以被称之为向后滑动一格目前的窗口分布如下
第一格0~200s第二格201~400s第三格401~600s
划分出来的每个格子都具备各自独立的计数器比如在第138s时发生了一次接口调用此时第一格的计数器就会1还是以之前的例子来说 第9:59秒调用了三次接着又在第10:01秒调用了三次。 将这里的分钟转换为具体秒数也就是在第599s调用了三次第601s调用了三次此时来看每当时间过去200s窗口就会向后滑动一格这也就意味着整个窗口会变成图中的下面的样子此时的窗口分布为
第一格201~400s第二格401~600s第三格601~800s
当第599s调用了三次「短信」接口后第二格的计数器会累加到3此时再当第601s尝试调用「短信」接口时就会检测出已达到调用上限此时就会拒绝用户的调用以此来解决传统计数器方案的临界问题。 WhyWhyWhy有些小伙伴可能到这里就有些晕了第601s是如何检测出调用超额的呐因为目前的时间窗口范围是201~800s而将整个时间窗口内的计数器求和就会得到调用总次数为3因而成功检测出了第601s的调用上限。 当出现调用达到上限时必须随着时间推移、窗口不断向后滑动这样整个窗口的计数器总和才会下降因此用户才能继续调用通过这种方式就能控制一个时间段的绝对限流。
但滑动窗口限流方案就不存在临界问题吗答案是No依旧存在Why来看下图 看上图中给出的案例因为目前的时间窗口大小是600s而199s~203s显然处于同一个时间窗口范围内但随着窗口向后滑动这里依旧会出现临界问题也就是在一个窗口范围内同样会出现打破调用次数上限的情况那这种情况下又该如何解决呢其实答案很简单把一个窗口的格子单位调小即可。 比如直接将每一格的单位大小从200s调整为1s此时每过一秒钟窗口就会向后滑动一格等到100s秒过后窗口会向后滑动100格此时窗口的区间范围是101~700s这就将199~203s这个范围包含了进去因此上述情况自然就不会出现 经过上述分析由此可以得出一条准则当滑动窗口的格子划分的单位越小整个窗口中的格子数量会越多滑动窗口的向后移动就越平滑限流的统计就会越精确。 四、令牌桶限流方案
前面简单聊完了时间窗口限流方案后接着再来聊一聊大名鼎鼎的令牌桶限流方案令牌桶算法是一种类似于“池化”思想的产物算法的大体过程如下 ①初始化令牌桶并设置最大令牌数当桶内的令牌达到阈值时新添加的令牌会被拒绝或丢弃。②根据限流大小启动一条线程并按照一定速率向令牌桶中不断添加新的令牌。③任何处于「限流范围」内的请求都需要先获取到一个可用令牌然后才会被处理。④当一个请求获取到可用令牌后才会真正执行业务逻辑执行完成后会将此令牌从桶内移除。⑤令牌桶除开有最大令牌数外也会有最小令牌数当桶内令牌数小于最小阈值时处理完请求并不会移除令牌而是会将令牌还给令牌桶。 对于令牌桶限流算法理解起来并没有前面的滑动时间窗口复杂但唯一要注意的是当桶内的令牌被一个请求获取后此时并不会立马从桶内移除该令牌会依旧停留在桶内只不过该令牌的状态会从可用状态变为不可用状态也就是其他请求无法再获取该令牌真正移除令牌的工作会在业务逻辑执行完成之后才触发。 五、漏桶限流方案
漏桶限流和令牌桶限流都属于桶类型的算法但漏桶算法更类似于MQ消息队列其算法的执行示意图如下 想要理解漏桶算法咱们先来看看日常生活中的漏斗比如现在我要用漏斗来给摩托车加油 倒油时我们可以用瓶子也可以用桶子也可以用加油枪…这也就意味着漏斗上方的进油速率并不固定但不管上方的进油速率如何下方的漏斗出口其速率确实固定的无论上方进油多快都不能影响下方的出油速率。
理解了日常生活中的漏斗后接着再来看看前面的漏桶限流算法请求会从漏桶上方进入而服务端则只会按照固定速率去处理请求。此时思考一个问题当请求进入的速率大于请求处理的速率会发生什么情况呢 此时依旧回到用漏斗给摩托车加油的例子中如果漏斗上方的倒油速度比较快而由于漏斗的结构原因下方的出口跟不上进油速度此时漏斗中的油量会直线上升直到超出漏斗的最大容量时再进入漏斗的汽油会溢出。 而限流中的漏桶算法同样如此请求进入的速率大于请求处理的速率时多出来的请求会被放入桶中等待当桶内阻塞等待的请求超过最大限制后后续进入的请求会被丢弃或拒绝。
从上述的讲解中诸位应该能够明显感受到漏桶算法的特点即宽进严出该算法中不会限制请求进入的速率但会限制请求处理的速率一些对稳定性要求较高的系统就可以采用该算法对系统进行限流。当然如果熟悉MQ的小伙伴也能感受出漏桶算法和MQ的削峰填谷有着异曲同工之妙当系统峰值流量较高时会将请求写入到MQ中然后再由具体的业务服务按照固定的速率拉取MQ中的消息进行处理。 六、高并发限流算法小结 计数器 VS 滑动窗口 计数器算法是最简单的算法可以看成是滑动窗口的低精度实现。滑动窗口由于需要存储多份的计数器每一个格子存一份所以滑动窗口在实现上需要更多的存储空间。也就是说如果滑动窗口的精度越高需要的存储空间就越大。 漏桶算法 VS 令牌桶算法 漏桶算法和令牌桶算法最明显的区别是令牌桶算法允许流量一定程度的突发。因为默认的令牌桶算法取走token是不需要耗费时间的也就是说假设桶内有100个token时那么可以瞬间允许100个请求通过。 令牌桶算法由于实现简单且允许某些流量的突发对用户友好所以被业界采用地较多。当然我们需要具体情况具体分析只有最合适的算法没有最优的算法。 在前面共计提到了计数器、滑动窗口、令牌桶、漏桶这四种常规的限流方案但要记住并不存在一种适用于任何场景的限流算法根据业务的需求不同系统的关注面不同应当采用不同的限流方案没有所谓的最好最后简单说一些成熟的限流实现
Guava中的RateLimiter工具类基于令牌桶实现的限流组件并且对其进行了预热拓展。Sentinel中的匀速排队限流策略基于漏桶思想的限流策略内部采用队列进行实现。Nginx的limit_req_zone限流模块基于漏桶思想的限流模块实现网关层的限流控制。........
