专栏首页后端开发你必须学会的干货高并发系统的限流算法与实现

高并发系统的限流算法与实现

开发高并发系统时有三把利器用来保护系统:缓存、降级和限流。

  • 缓存:缓存的目的是提升系统访问速度和增大系统处理容量。
  • 降级:降级是当服务器压力剧增的情况下,根据当前业务情况及流量对一些服务和页面有策略的降级,以此释放服务器资源以保证核心任务的正常运行。
  • 限流:限流的目的是通过对并发请求进行限速,或者对一个时间窗口内的请求进行限速来保护系统,一旦达到限制速率则可以进行拒绝服务、排队或等待、降级等处理。

限流是限制系统的输入和输出流量,以达到保护系统的目的,而限流的实现主要是依靠限流算法,限流算法主要有4种:

  1. 固定时间窗口算法(计数器)
  2. 滑动时间窗口算法
  3. 令牌桶算法
  4. 漏桶算法

1. 固定时间窗口算法

又称计数器算法。固定时间窗口算法就是统计记录单位时间内进入系统或者某一接口的请求次数,在限定的次数内的请求则正常接收处理,超过次数的请求则拒绝掉或者改为异步处理等限流措施。

时间窗口长度如果为1分钟,如图。

此算法在单机还是分布式环境下实现都非常简单,使用redis的incr原子自增性即可轻松实现。

单机伪代码如下。

class CounterDemo {
    public       long timeStamp = getNowTime();
    public       int  reqCount  = 0;
    public final int  limit     = 100; // 时间窗口内最大请求数
    public final long interval  = 1000; // 时间窗口ms

    public boolean grant() {
        long now = getNowTime();
        if (now < timeStamp + interval) {
            // 在时间窗口内
            reqCount++;
            // 判断当前时间窗口内是否超过最大请求控制数
            return reqCount <= limit;
        } else {
            timeStamp = now;
            // 超时后重置
            reqCount = 1;
            return true;
        }
    }
}

算法特点

  1. 实现简单。
  2. 时间窗口固定,每个窗口开始时计数为零,这样后面的请求不会受到之前的影响,做到了前后请求隔离。
  3. 因为两个时间窗口之间没有任何联系,所以调用者可以在一个时间窗口的结束到下一个时间窗口的开始这个非常短的时间段内发起两倍于阈值的请求。所以固定时间窗口算法无法限制窗口间突发流量。

2. 滑动时间窗口算法

滑动时间窗口算法其实是固定时间窗口算法的优化,主要是为了解决固定时间窗口算法无法限制窗口间突发流量的缺点。 上面的计数器的单位时间是1分钟,而在使用滑动时间窗口,可以把1分钟分成6格,每格时间长度是10s,每一格又各自管理一个计数器,单位时间用一个长度为60s的窗口描述。一个请求进入系统,对应的时间格子的计数器便会+1,而每过10s,这个窗口便会向右滑动一格。只要窗口包括的所有格子的计数器总和超过限流上限,便会执行限流措施。

由此可见,当滑动窗口的格子划分的越多,那么滑动窗口的滚动就越平滑,限流的统计就会越精确。

算法特点

  1. 因为窗口顺延,所以可以抵御窗口间突发流量(对比固定时间窗口算法)。
  2. 假如限流10万次/小时,如果某个调用者在前10分钟调用了10万次那么他必须再等待1小时才能发起下一次正常请求。所以没有做到前后请求隔离。

阿里开源的Sentinel,采用的是滑动窗口算法进行限流,可以阅读相关代码,加深对滑动时间窗口算法的理解。

3. 漏桶算法(leaky bucket)

漏桶算法其实很简单,可以粗略的认为就是注水漏水过程,往桶中以一定速率流出水,以任意速率流入水,当水超过桶流量则丢弃,因为桶容量是不变的,保证了整体的速率。这个从桶底流出去的水就是系统正常处理的请求,从旁边流出去的水就是系统拒绝掉的请求。

单机伪代码如下。

class LeakyDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 水漏出的速度
    public int water; // 当前水量(当前累积请求数)

    public boolean grant() {
        long now = getNowTime();
        water = max(0, water - (now - timeStamp) * rate); // 先执行漏水,计算剩余水量
        timeStamp = now;
        if ((water + 1) < capacity) {
            // 尝试加水,并且水还未满
            water += 1;
            return true;
        } else {
            // 水满,拒绝加水
            return false;
        }
    }
}

算法特点

  1. 因为流出的速度是一定的,可以抵御突发流量,做到更加平滑的限流,而且不允许流量突发。

4. 令牌桶算法(Token Bucket)

令牌桶算法是比较常见的限流算法之一,Google开源项目Guava中的RateLimiter使用的就是令牌桶算法。流程如下:

  1. 所有的请求在处理之前都需要拿到一个可用的令牌才会被处理。
  2. 根据限流大小,设置按照一定的速率往桶里添加令牌。
  3. 桶设置最大的放置令牌限制,当桶满时、新添加的令牌就被丢弃或者拒绝。
  4. 请求到达后首先要获取令牌桶中的令牌,拿着令牌才可以进行其他的业务逻辑,处理完业务逻辑之后,将令牌直接删除。

单机伪代码如下,分布式环境可以使用Redisson。

class TokenBucketDemo {
    public long timeStamp = getNowTime();
    public int capacity; // 桶的容量
    public int rate; // 令牌放入速度
    public int tokens; // 当前令牌数量

    public boolean grant() {
        long now = getNowTime();
        // 先添加令牌
        tokens = min(capacity, tokens + (now - timeStamp) * rate);
        timeStamp = now;
        if (tokens < 1) {
            // 若桶中没有令牌,则拒绝
            return false;
        } else {
            // 还有令牌,领取令牌
            tokens -= 1;
            return true;
        }
    }
}

算法特点

  1. 可以抵御突发流量,因为桶内的令牌数不会超过给定的最大值
  2. 可以做到更加平滑的限流,因为令牌是匀速放入的。
  3. 令牌桶算法允许流量一定程度的突发。(相比漏桶算法)

在时间点刷新的临界点上,只要剩余token足够,令牌桶算法会允许对应数量的请求通过,而后刷新时间因为token不足,流量也会被限制在外,这样就比较好的控制了瞬时流量。因此,令牌桶算法也被广泛使用。

更多内容,欢迎关注微信公众号:全菜工程师小辉~

本文分享自微信公众号 - 全菜工程师小辉(mseddl),作者:全菜工程师小辉

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 安全发布对象-发布与逸出

    简单来说就是提供一个对象的引用给作用域之外的代码。比如return一个对象,或者作为参数传递到其他类的方法中。

    全菜工程师小辉
  • 彻底搞懂MySQL的索引

    MyISAM和InnoDB是MySQL最常用的两个存储引擎,本文将进行详尽的介绍和对比。对于MySQL其余几种存储引擎,请读者自行搜索学习。

    全菜工程师小辉
  • TCP粘拆包详解与Netty代码示例

    TCP是个“流”协议,所谓流,就是没有界限的一串数据。可以想想河里的流水,是连成一片的,其间并没有分界线。TCP底层并不了解上层业务数据的具体含义,它会根据TC...

    全菜工程师小辉
  • 使用延迟的FileSystemWatcher来避免重复触发事件

      程序里需要监视某个目录下的文件变化情况: 一旦目录中出现新文件或者旧的文件被覆盖,程序需要读取文件内容并进行处理;但在实际处理中发现当一个文件产生变化时,C...

    跟着阿笨一起玩NET
  • 门面模式浅析

    在生活中,比如在医院有接待员帮助病人完成门诊、挂号、付费以及取药,病人只接触接待员即可,由接待员负责与医院的各个部门打交道。

    孟君
  • 吴恩达放宽招聘条件:周工作时间减少20小时;中文流利加分

    允中 发自 凹非寺 量子位 出品 | 公众号 QbitAI 好消息,成为大师门徒的门槛降低了~ 大约一周之前,吴恩达“finally”开始招聘。他发出的招聘贴中...

    量子位
  • 如何借助GitHub搭建属于自己的maven仓库

    借助GitHub搭建属于自己的maven仓库 I. 背景 在Github上也写了不少的项目了,然后经常遇到的一个问题就是,很多自己写的项目,希望在另外一个项目中...

    一灰灰blog
  • Spring基础知识之基于注解的AOP

    背景概念:   1)横切关注点:散布在应用中多处的功能称为横切关注点   2)通知(Advice):切面完成的工作。通知定了了切面是什么及何时调用。     5...

    用户1134788
  • table标签 在谷歌和ie浏览器下不同的表现效果

      我需要利用vue的模板语法v-for循环生成tr,这个tr是需要双重循环来确定其个数的,

    Theone67
  • Python Ajax请求及返回 jso

    py3study

扫码关注云+社区

领取腾讯云代金券