学习
实践
活动
工具
TVP
写文章
专栏首页眯眯眼猫头鹰的小树杈固定窗口和滑动窗口算法了解一下

固定窗口和滑动窗口算法了解一下

前言

最近在参与一个识别热点数据的需求开发。其中涉及了限流算法相关的内容。所以这里记录一下自己了解的各种限流算法,以及各个限流算法的实现。

限流算法的应用场景非常广泛,比如通过限流来确保下游配置较差的应用不会被上游应用的大量请求击穿,无论是HTTP请求还是RPC请求,从而使得服务保持稳定。限流也同样可以用于客户端,比如当我们需要从微博上爬取数据时,我们需要在请求中携带token从而通过微博的网关验证。但是微博为了防止服务被单个客户端大量访问,往往会在服务端进行限流,比如可能是一个token一个小时只能发起1000次请求。但是爬虫发出的请求通常远远不止这个量级。所以在客户端进行限流可以确保我们的token不会失效或是查封。

限流算法可以从多种角度分类,比如按照处理方式分为两种,一种是在超出限定流量之后会拒绝多余的访问,另一种是超出限定流量之后,只是报警或者是记录日志,访问仍然正常进行。

目前比较常见的限流算法有以下几种:

  • 固定窗口
  • 滑动窗口
  • 令牌桶算法
  • 漏桶算法

本文主要记录一下固定窗口和滑动窗口。令牌桶算法在谷歌的开源guava包中有实现,下次再开一篇文章分享一下。文中错误的地方欢迎指出!如果guava中实现了滑动窗口算法也请告诉我,急需,目前没有找到orz。

固定窗口

这是限流算法中最暴力的一种想法。既然我们希望某个API在一分钟内只能固定被访问N次(可能是出于安全考虑,也可能是出于服务器资源的考虑),那么我们就可以直接统计这一分钟开始对API的访问次数,如果访问次数超过了限定值,则抛弃后续的访问。直到下一分钟开始,再开放对API的访问。

所有的暴力算法的共同点都是容易实现,而固定窗口限流的缺点也同样很明显。假设现在有一个恶意用户在上一分钟的最后一秒和下一分钟的第一秒疯狂的冲击API。按照固定窗口的限流规则,这些请求都能够访问成功,但是在这一秒内,服务将承受超过规定值的访问冲击(这个规定值很可能是服务器能够承受的最大负载),从而导致服务无法稳定提供。而且因为用户在这一秒内耗光了上一分钟和下一分钟的访问定额,从而导致别的用户无法享受正常的服务,对于服务提供方来说是完全不能接收的。

这里自己做了一个简单的实现:

import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

public class FixedWindowRateLimiter implements RateLimiter, Runnable {

    private static final int DEFAULT_ALLOWED_VISIT_PER_SECOND = 5;

    private final int maxVisitPerSecond;

    private AtomicInteger count;

    FixedWindowRateLimiter(){
        this.maxVisitPerSecond = DEFAULT_ALLOWED_VISIT_PER_SECOND;
        this.count = new AtomicInteger();
    }

    FixedWindowRateLimiter(int maxVisitPerSecond) {
        this.maxVisitPerSecond = maxVisitPerSecond;
        this.count = new AtomicInteger();
    }

    @Override
    public boolean isOverLimit() {
        return currentQPS() > maxVisitPerSecond;
    }

    @Override
    public int currentQPS() {
        return count.get();
    }

    @Override
    public boolean visit() {
        count.incrementAndGet();
        System.out.print(isOverLimit());
        return isOverLimit();
    }

    @Override
    public void run() {
        System.out.println(this.currentQPS());
        count.set(0);
    }

    public static void main(String[] args) {
        ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
        FixedWindowRateLimiter rateLimiter = new FixedWindowRateLimiter();
        scheduledExecutorService.scheduleAtFixedRate(rateLimiter, 0, 1, TimeUnit.SECONDS);
        new Thread(new Runnable() {
            @Override
            public void run() {
                while(true) {
                    rateLimiter.visit();
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                while(true) {
                    rateLimiter.visit();
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();

    }
}

其中RateLimiter是一个通用的接口,后面的其它限流算法也会实现该接口:

public interface RateLimiter {

    boolean isOverLimit();

    int currentQPS();

    boolean visit();
}

也可以不使用多线程的方式实现,更加简单高效:

public class FixedWindowRateLimiterWithoutMultiThread implements RateLimiter {
    private Long lastVisitAt = System.currentTimeMillis();
    private static final int DEFAULT_ALLOWED_VISIT_PER_SECOND = 5;

    private final int maxVisitPerSecond;

    private AtomicInteger count;

    public FixedWindowRateLimiterWithoutMultiThread(int maxVisitPerSecond){
        this.maxVisitPerSecond = maxVisitPerSecond;
        this.count = new AtomicInteger();
    }

    public FixedWindowRateLimiterWithoutMultiThread() {
        this(DEFAULT_ALLOWED_VISIT_PER_SECOND);
    }
    @Override
    public boolean isOverLimit() {
        return count.get() > maxVisitPerSecond;
    }

    @Override
    public int currentQPS() {
        return count.get();
    }

    @Override
    public boolean visit() {
        long now = System.currentTimeMillis();
        synchronized (lastVisitAt) {
            if (now - lastVisitAt > 1000) {
                lastVisitAt = now;
                System.out.println(currentQPS());
                count.set(1);
            }
        }
        count.incrementAndGet();
        return isOverLimit();
    }

    public static void main(String[] args) {
        RateLimiter rateLimiter = new FixedWindowRateLimiterWithoutMultiThread();
        new Thread(new Runnable() {
            @Override
            public void run() {
                while(true) {
                    rateLimiter.visit();
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                while(true) {
                    rateLimiter.visit();
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();

    }
}

滑动窗口

固定窗口就像是滑动窗口的一个特例。滑动窗口将固定窗口再等分为多个小的窗口,每一次对一个小的窗口进行流量控制。这种方法可以很好的解决之前的临界问题。

这里找的网上一个图,假设我们将1s划分为4个窗口,则每个窗口对应250ms。假设恶意用户还是在上一秒的最后一刻和下一秒的第一刻冲击服务,按照滑动窗口的原理,此时统计上一秒的最后750毫秒和下一秒的前250毫秒,这种方式能够判断出用户的访问依旧超过了1s的访问数量,因此依然会阻拦用户的访问。

使用定时任务实现的滑动窗口代码如下:

public class SlidingWindowRateLimiter implements RateLimiter, Runnable{
    private final long maxVisitPerSecond;

    private static final int DEFAULT_BLOCK = 10;
    private final int block;
    private final AtomicLong[] countPerBlock;

    private AtomicLong count;
    private volatile int index;

    public SlidingWindowRateLimiter(int block, long maxVisitPerSecond) {
        this.block = block;
        this.maxVisitPerSecond = maxVisitPerSecond;
        countPerBlock = new AtomicLong[block];
        for (int i = 0 ; i< block ; i++) {
            countPerBlock[i] = new AtomicLong();
        }
        count = new AtomicLong(0);
    }

    public SlidingWindowRateLimiter() {
        this(DEFAULT_BLOCK, DEFAULT_ALLOWED_VISIT_PER_SECOND);
    }
    @Override
    public boolean isOverLimit() {
        return currentQPS() > maxVisitPerSecond;
    }

    @Override
    public long currentQPS() {
        return count.get();
    }

    @Override
    public boolean visit() {
        countPerBlock[index].incrementAndGet();
        count.incrementAndGet();
        return isOverLimit();
    }

    @Override
    public void run() {
        System.out.println(isOverLimit());
        System.out.println(currentQPS());
        System.out.println("index:" + index);
        index = (index + 1) % block;
        long val = countPerBlock[index].getAndSet(0);
        count.addAndGet(-val);
    }

    public static void main(String[] args) {
        SlidingWindowRateLimiter slidingWindowRateLimiter = new SlidingWindowRateLimiter(10, 1000);
        ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
        scheduledExecutorService.scheduleAtFixedRate(slidingWindowRateLimiter, 100, 100, TimeUnit.MILLISECONDS);

        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    slidingWindowRateLimiter.visit();
                    try {
                        Thread.sleep(10);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    slidingWindowRateLimiter.visit();
                    try {
                        Thread.sleep(10);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }).start();
    }
}

参考文章

Protect Your API Resources with Rate Limiting

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://segmentfault.com/u/raledong复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 算法:滑动窗口(二)

    这算是滑动窗口的另外一个典型题目,在数据量比较少的时候,可以直接采用暴力法解决;不过数据量比较大的时候,我们就需要想办法解决窗口里面最大值的思路,这里我们采用双...

    灰子学技术
  • 精读《算法 - 滑动窗口》

    滑动窗口算法是较为入门题目的算法,一般是一些有规律数组问题的最优解,也就是说,如果一个数组问题可以用动态规划解,但又可以使用滑动窗口解决,那么往往滑动窗口的效率...

    黄子毅
  • 算法篇:滑动窗口(一)

    题目: https://leetcode-cn.com/problems/longest-substring-without-repeating-charact...

    灰子学技术
  • (2)sparkstreaming滚动窗口和滑动窗口演示

    一、滚动窗口(Tumbling Windows) 滚动窗口有固定的大小,是一种对数据进行均匀切片的划分方式。窗口之间没有重叠,也不会有间隔,是“首尾相接”的状态...

    NBI大数据
  • Nagle 算法与滑动窗口协议

    此前的文章中,我们介绍了 tcp 协议的基本概念和连接的建立与终止 最后,我们介绍了“经受时延的确认”,这是一种将 ACK 包与下一条数据包合并发送的策略,这样...

    用户3147702
  • leetcode必备算法:聊聊滑动窗口

    我们刷leetcode的时候,经常会遇到滑动窗口类型题目。滑动窗口问题非常经典,也很有技巧性,一般大厂也喜欢问。今天跟大家一起来学习滑动窗口的套路,文章如果有不...

    捡田螺的小男孩
  • 滑动窗口算法学习

    给一组大小为n的整数数组,计算长度为k的子数组的最大值 比如:数组{1,2,3,4,5,7,6,1,8},k=2,那么最终结果应该是7+6=13最大。 最简...

    全栈程序员站长
  • PHP版滑动时间窗口算法

    如果要精确计算,则要记录每次访问以元素的形式记录时间戳,到数组,每次请求的时候,遍历数组元素中的时间戳,与当前时间比较,清理掉 N分钟之前的元素,然后再计算个数...

    码农编程进阶笔记
  • 【C++】算法集锦(7)滑动窗口

    看到这个题,我不知道大家是怎么想的,我想到的就是暴力解法: 1、从头开始,以每个数字作为结果数组的头,找到刚好能大于s的结果数组。并记下结果数组中 [1:] ...

    看、未来
  • 双指针—滑动窗口算法解析

    用i,j表示滑动窗口的左边界和右边界,通过改变i,j来扩展和收缩滑动窗口,可以想象成一个窗口在字符串上游走,当这个窗口包含的元素满足条件,即包含字符串T的所有元...

    Wu_Candy
  • 算法通关手册:08 数组滑动窗口

    在计算机网络中,滑动窗口协议(Sliding Window Protocol)是传输层进行流控的一种措施,接收方通过通告发送方自己的窗口大小,从而控制发送方的发...

    程序员充电站
  • 九十六、双指针和滑动窗口算法模板

    在四种二分变种中,根据王争算法专栏中,写死low = 0,high = len(list) - 1。循环条件low <= high。往左移动high = mid...

    润森
  • LeetCode-算法-滑动窗口-第19天

    给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指字母相同,但排列不同的字符串。

    布衣者
  • 3493. 最大的和 (滑动窗口)

    你可以选择一个长度恰好为 k 的区间 [i,i+k−1],使得 ai∼ai+k−1 这 k 个元素的状态全部变为可选。

    浪漫主义狗
  • LeetCode-算法-滑动窗口-第6天

    给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。换句话说,s1 的排列之一是 s2 的 子串 。 具体题目链接

    布衣者
  • 有点难度,几道和「滑动窗口」有关的算法面试题

    滑动问题包含一个滑动窗口,它是一个运行在一个大数组上的子列表,该数组是一个底层元素集合。

    五分钟学算法
  • 日拱算法,滑动窗口的最大值

    携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第30天,点击查看活动详情

    掘金安东尼
  • [Go]GO实现滑动窗口限流算法-单机版

    本代码基于原博客java版本的GO实现 , 原文解释也比较详细 , 这里也放上原文链接:https://www.cnblogs.com/dijia478/p/1...

    大灰狼2

扫码关注腾讯云开发者

领取腾讯云代金券