限流：计数器、漏桶、令牌桶三大算法的原理与实战（史上最全）

2024-03-14 20:44| 来源: 网络整理| 查看: 265

限流限流是面试中的常见的面试题（尤其是大厂面试、高P面试）

在这里插入图片描述

注：本文以 PDF 持续更新，最新尼恩架构笔记、面试题的PDF文件，请到文末《技术自由圈》公号获取

为什么要限流

简单来说：

限流在很多场景中用来限制并发和请求量，比如说秒杀抢购，保护自身系统和下游系统不被巨型流量冲垮等。

以微博为例，例如某某明星公布了恋情，访问从平时的50万增加到了500万，系统的规划能力，最多可以支撑200万访问，那么就要执行限流规则，保证是一个可用的状态，不至于服务器崩溃，所有请求不可用。

参考图谱

系统架构知识图谱（一张价值10w的系统架构知识图谱）

https://www.processon.com/view/link/60fb9421637689719d246739

秒杀系统的架构

https://www.processon.com/view/link/61148c2b1e08536191d8f92f

限流的思想

在保证可用的情况下尽可能多增加进入的人数，其余的人在排队等待，或者返回友好提示，保证里面的进行系统的用户可以正常使用，防止系统雪崩。

日常生活中，有哪些需要限流的地方?

像我旁边有一个国家景区，平时可能根本没什么人前往，但是一到五一或者春节就人满为患，这时候景区管理人员就会实行一系列的政策来限制进入人流量，为什么要限流呢?

假如景区能容纳一万人，现在进去了三万人，势必摩肩接踵，整不好还会有事故发生，这样的结果就是所有人的体验都不好，如果发生了事故景区可能还要关闭，导致对外不可用，这样的后果就是所有人都觉得体验糟糕透了。

限流的算法

限流算法很多，常见的有三类，分别是计数器算法、漏桶算法、令牌桶算法，下面逐一讲解。

限流的手段通常有计数器、漏桶、令牌桶。注意限流和限速（所有请求都会处理）的差别，视业务场景而定。

（1）计数器：

在一段时间间隔内（时间窗/时间区间），处理请求的最大数量固定，超过部分不做处理。

（2）漏桶：

漏桶大小固定，处理速度固定，但请求进入速度不固定（在突发情况请求过多时，会丢弃过多的请求）。

（3）令牌桶：

令牌桶的大小固定，令牌的产生速度固定，但是消耗令牌（即请求）速度不固定（可以应对一些某些时间请求过多的情况）；每个请求都会从令牌桶中取出令牌，如果没有令牌则丢弃该次请求。

计数器算法计数器限流定义：

在一段时间间隔内（时间窗/时间区间），处理请求的最大数量固定，超过部分不做处理。

简单粗暴，比如指定线程池大小，指定数据库连接池大小、nginx连接数等，这都属于计数器算法。

计数器算法是限流算法里最简单也是最容易实现的一种算法。

举个例子，比如我们规定对于A接口，我们1分钟的访问次数不能超过100个。

那么我们可以这么做：

在一开始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个请求的间隔时间还在1分钟之内，那么说明请求数过多，拒绝访问；如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter，就是这么简单粗暴。

计算器限流的实现 package com.crazymaker.springcloud.ratelimit; import lombok.extern.slf4j.Slf4j; import org.junit.Test; import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; // 计速器限速 @Slf4j public class CounterLimiter { // 起始时间 private static long startTime = System.currentTimeMillis(); // 时间区间的时间间隔 ms private static long interval = 1000; // 每秒限制数量 private static long maxCount = 2; //累加器 private static AtomicLong accumulator = new AtomicLong(); // 计数判断, 是否超出限制 private static long tryAcquire(long taskId, int turn) { long nowTime = System.currentTimeMillis(); //在时间区间之内 if (nowTime

【本文地址】

公司简介

联系我们

限流：计数器、漏桶、令牌桶 三大算法的原理与实战（史上最全）

限流：计数器、漏桶、令牌桶三大算法的原理与实战（史上最全）