ღゝ◡╹)ノ❤️

集中一点,登峰造极!

  menu
137 文章
0 浏览
0 当前访客
ღゝ◡╹)ノ❤️

限流算法

固定窗口限流算法

首先维护一个计数器,将单位时间段当做一个窗口,计数器记录这个窗口接收请求的次数。

  • 当次数少于限流阀值,就允许访问,并且计数器+1
  • 当次数大于限流阀值,就拒绝访问。
  • 当前的时间窗口过去之后,计数器清零。

伪代码

    /**
     * 固定窗口时间算法
     * @return
     */
    boolean fixedWindowsTryAcquire() {
        long currentTime = System.currentTimeMillis();  //获取系统当前时间
        if (currentTime - lastRequestTime > windowUnit) {  //检查是否在时间窗口内
            counter = 0;  // 计数器清0
            lastRequestTime = currentTime;  //开启新的时间窗口
        }
        if (counter < threshold) {  // 小于阀值
            counter++;  //计数器加1
            return true;
        }

        return false;
    }

优点:实现简单

缺点:临界问题

滑动窗口限流算法

解决了上个方法的缺点。

会先移除距离这个当前时间节点相应单位窗口之外的所有旧的请求,然后再来判断当前最近窗口的请求数量,如果请求的数量超过了限额,则会被拒绝掉,否则可以执行。

优点:解决了固定窗口的临界问题

缺点:请求都会直接暴力被拒绝。酱紫我们会损失一部分请求,这其实对于产品来说,并不太友好。

漏桶算法

漏桶算法面对限流,就更加的柔性,不存在直接的粗暴拒绝。

它的原理很简单,可以认为就是注水漏水 的过程。往漏桶中以任意速率流入水,以固定的速率流出水。当水超过桶的容量时,会被溢出,也就是被丢弃。因为桶容量是不变的,保证了整体的速率。

  • 流入的水滴,可以看作是访问系统的请求,这个流入速率是不确定的。
  • 桶的容量一般表示系统所能处理的请求数。
  • 如果桶的容量满了,就达到限流的阀值,就会丢弃水滴(拒绝请求)
  • 流出的水滴,是恒定过滤的,对应服务按照固定的速率处理请求。

优点:在正常流量的时候,系统可以按照固定的速率处理请求。

缺点:面对突发流量的时候,漏桶算法还是循规蹈矩地处理请求。

令牌桶算法

  • 有一个令牌管理员,根据限流大小,定速往令牌桶里放令牌。
  • 如果令牌数量满了,超过令牌桶容量的限制,那就丢弃。
  • 系统在接受到一个用户请求时,都会先去令牌桶要一个令牌。如果拿到令牌,那么就处理这个请求的业务逻辑;
  • 如果拿不到令牌,就直接拒绝这个请求。

可以使用限流组件:Guava的RateLimiter。


标题:限流算法
作者:哇哇哇哇
地址:https://wuxiangshi.vip/articles/2022/07/11/1657552875633.html