首页>内容详情

四种算法入门限流机制

大熊•2024-12-01 10:52:30•算法,限流,架构

前言

文章主要介绍了限流机制，包括限流的概念（阈值和拒绝策略）、限流原因（防系统过载、提升稳定性、处理瞬时高峰）以及四种限流基本算法：固定窗口限流，简单但有请求分布不均等缺点；滑动窗口限流，精度高但仍存限流不准确问题；漏斗限流，能平滑处理但无法应对突发流量；令牌桶限流，可平滑流量且能应对流量增大。

什么是限流

限流是高并发场景下，通过控制系统处理请求的速率，迅速拒绝超过设定上限的请求，保障系统及上下游服务运行的稳定性

限流的两个概念：阈值和拒绝策略

阈值

阈值指的是在单位时间内允许的最大请求量，例如，将QPS(每秒请求数)限制为1000，意味着系统在1s内最多能接受1000次请求

拒绝策略

处理超过阈值请求的方法，常见的拒绝策略包括直接拒绝和排队等待
直接拒绝策略会直接拒绝超过阈值的请求，然后直接向用户返回
排队等待策略则是将请求放入队列中，按照一定规则处理，避免瞬间拒绝大量请求

选择合适的拒绝策略，在系统稳定性和用户体验之间取得平衡

为什么要限流

限流主要是保证在高并发场景下，可以拒绝掉一部分请求，避免因过载导致系统崩溃或性能下降等问题

防止系统过载，当请求量超过系统的处理能力的时候，CPU、内存、带宽等资源会被迅速消耗，导致系统负载过高
提升系统稳定性，如果一个服务过载，会影响到其他依赖该服务的组件，可能导致整个系统崩溃
瞬时高峰处理，在特定时间段，请求量可能突然增加，限流可以控制请求速率，平稳处理瞬时高峰流量

限流基本算法

固定窗口限流

固定窗口限流是最简单直观的一种限流算法，基本原理是将时间划分为固定大小的窗口，并在每个窗口内限制请求数量或速率

具体来说就是将请求按照时间顺序放入时间窗口中，并计算该时间窗口内的请求数量，如果请求数量超出限制，则拒绝请求

算法步骤：

将时间划分为固定大小的窗口，例如每秒一个
在每个时间窗口内，记录请求的数量
当新的请求到达时，将计数器的值 + 1
如果计数器的值超过了预设的阈值，则拒绝该请求
当时间窗口结束时，重置计数器

超出限流限制拒绝请求

public class FixedLimiter {
    private static final String FORMAT_TIME = "yyyy-MM-dd HH:mm:ss";
    private final long windowSize; // 窗口大小，单位为毫秒
    private final int maxRequests; // 最大请求数
    private int requests; // 当前窗口内的请求数
    private LocalDateTime lastReset; // 上次窗口重置时间
    private final Lock resetMutex; // 重置锁

    public FixedLimiter(Duration windowSize, int maxRequests) {
        this.windowSize = windowSize.toMillis();
        this.maxRequests = maxRequests;
        this.requests = 0;
        this.lastReset = LocalDateTime.now();
        this.resetMutex = new ReentrantLock();
    }

    public boolean allowRequest() {
        resetMutex.lock();
        try {
            LocalDateTime now = LocalDateTime.now();
            if (Duration.between(lastReset, now).toMillis() >= windowSize) {
                requests = 0;
                lastReset = now;
            }

            if (requests >= maxRequests) {
                return false;
            }

            requests++;
            return true;
        } finally {
            resetMutex.unlock();
        }
    }

    public static void main(String[] args) {
        System.out.println(System.currentTimeMillis() / 1000);
        FixedLimiter limiter = new FixedLimiter(Duration.ofSeconds(1), 3); // 每秒最多允许3个请求
        DateTimeFormatter formatter = DateTimeFormatter.ofPattern(FORMAT_TIME);
        ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);

        Runnable task = () -> {
            String now = LocalDateTime.now().format(formatter);
            if (limiter.allowRequest()) {
                System.out.println(now + " 请求通过");
            } else {
                System.out.println(now + " 请求被限流");
            }
        };

        for (int i = 0; i < 20; i++) {
            executor.schedule(task, i * 100, TimeUnit.MILLISECONDS);
        }

        executor.shutdown();
        try {
            if (!executor.awaitTermination(5, TimeUnit.SECONDS)) {
                executor.shutdownNow();
            }
        } catch (InterruptedException e) {
            executor.shutdownNow();
        }
    }
}

优点：算法实现非常简单，易于实现和理解
缺点：

请求分布不均匀：在固定窗口算法中，请求在窗口内的分布可能会不均衡，导致某些窗口请求多，有些请求少
应对突发流量能力有限：由于固定窗口算法的窗口大小是固定的，无法灵活调整，难以应对突发的流量高峰
存在明显的临界问题：在窗口结束时充值请求记述可能会导致处理请求的不公平。下图举例子

比如：限流阈值为每秒5个请求，单位时间窗口为1s，如果在前0.5s到1s的时间内并发5个请求，接着在1s到1.5s的时间内又并发5个请求，虽然这两个时间段各自都没有超过限流阈值，但如果计算0.5s到1.5s的总请求数，则一共是10个请求，超出1s不超过5个请求的限流规则

限流不均

滑动窗口限流

滑动窗口其实也是一种将时间窗口划分为一个一个小的时间段来限流的方法，每个小的时间段又称为小周期
相较于固定窗口限流，它可以根据时间滑动，删除过期的小周期，以解决固定窗口临界值的问题。

比如要限制1s内的请求数量，让时间窗口为1s，在前面固定窗口分析中，会出现临界值的问题。

滑动窗口将1s窗口划分为两个小周期，每个0.5s，每隔0.5s就往右滑动一个小周期，这样统计的整个窗口大小仍然是1s，只是过期的左边的小周期会随着时间删除，这样整个1s的统计周期就是随时间滑动的，简单来说就是以当前时间为基准，向前查找1s内的请求数。

滑动窗口限流

这样的话在固定窗口中出现的临界问题，比如0.5s和1.5s间假设来了10个请求，由于滑动窗口会统计到1s - 1.5s和0.5s - 1s

所以多余的请求就会被拒绝

public class SlidingLimiter {
    private final Duration windowSize; // 窗口小周期大小
    private final int maxRequests; // 最大请求数
    private final LinkedList<LocalDateTime> requestTimeList; // 窗口小周期内的请求时间
    private final Lock requestsLock; // 请求锁
    private static final DateTimeFormatter formatter = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm:ss");

    public SlidingLimiter(Duration windowSize, int maxRequests) {
        this.windowSize = windowSize;
        this.maxRequests = maxRequests;
        this.requestTimeList = new LinkedList<>();
        this.requestsLock = new ReentrantLock();
    }

    public boolean allowRequest() {
        requestsLock.lock();
        try {
            LocalDateTime currentTime = LocalDateTime.now();
            // 移除过期的请求
            while (!requestTimeList.isEmpty() && Duration.between(requestTimeList.peek(), currentTime).compareTo(windowSize) > 0) {
                requestTimeList.poll();
            }
            // 检查请求数是否超过阈值
            if (requestTimeList.size() >= maxRequests) {
                return false;
            }
            requestTimeList.add(currentTime);
            return true;
        } finally {
            requestsLock.unlock();
        }
    }

    public static void mockRequest(int n, Duration d, SlidingLimiter limiter) {
        ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);

        for (int i = 0; i < n; i++) {
            int requestId = i + 1;
            executor.schedule(() -> {
                String now = LocalDateTime.now().format(formatter);
                if (limiter.allowRequest()) {
                    System.out.printf("%s 请求通过\n", now);
                } else {
                    System.out.printf("%s 请求被限流\n", now);
                }
            }, i * d.toMillis(), TimeUnit.MILLISECONDS);
        }

        executor.shutdown();
        try {
            if (!executor.awaitTermination(5, TimeUnit.SECONDS)) {
                executor.shutdownNow();
            }
        } catch (InterruptedException e) {
            executor.shutdownNow();
        }
    }

    public static void main(String[] args) {
        System.out.println("=================滑动窗口算法=================");
        // 创建一个滑动窗口限流器，窗口大小为500毫秒，每个小周期最多允许2个请求，每秒允许4个请求
        SlidingLimiter limiter = new SlidingLimiter(Duration.ofMillis(500), 2);
        // 发送20个请求，每100毫秒发送一个
        mockRequest(20, Duration.ofMillis(100), limiter);
        System.out.println("------------------------------------------");
    }
}

优点：精度高，灵活性高，简单易实现
缺点：

滑动窗口算法本质上是固定窗口算法的细化版本，它能够在一定程度上提高限流的精度和实时性，但不能解决请求分布不均匀的问题
该算法依赖窗口的大小和时间间隔，在突发流量和请求分布不均匀的极端情况下，仍可能导致限流不准确，
因为滑动窗口本质就是将窗口的粒度缩小，但是不管多小，仍然是以窗口来限制的，所以总会存在流量不均导致限流不准确的问题

漏斗限流

漏斗限流算法的核心思想是将请求存储在一个漏斗中，漏斗以固定的速率漏出请求

如果漏斗被填满，新到达的请求将会被丢弃。请求可以以不定的速率流入漏斗，而漏斗以固定的速率流出

所以漏斗算法可以将突发的流量均匀的分配，确保系统在稳定的负载下运行

算法步骤：

设置漏斗容量：定义服务器在瞬间能够接受的最大请求数
确定处理速率：设定每秒能够处理的请求数
请求处理计算：

计算处理完成的请求数： 已处理的请求数 = （当前请求时间 - 上次请求时间）* 处理速率
更新当前请求数：最新的当前请求数 = 当前请求数 - 已处理的请求数

比较和处理请求：

如果当前请求数超过漏斗容量，则拒绝本次请求
否则，允许请求通过，并将当前请求数 + 1

滴桶算法

public class LeakyBucketLimiter {
    private int rate;
    private int capacity;
    private int currentReqNum;
    private Instant lastTime;
    private final ReentrantLock lock = new ReentrantLock();

    public LeakyBucketLimiter(int rate, int capacity) {
        this.rate = rate;
        this.capacity = capacity;
        this.currentReqNum = 0;
        this.lastTime = Instant.now();
    }

    public boolean allow() {
        lock.lock();
        try {
            long elapsed = Duration.between(lastTime, Instant.now()).toMillis();
            double seconds = elapsed / 1000.0;
            int leakyReqCount = (int) (seconds * rate);

            if (leakyReqCount > 0) {
                currentReqNum -= leakyReqCount;
                lastTime = Instant.now();
            }

            if (currentReqNum < 0) {
                currentReqNum = 0;
            }

            if (currentReqNum < capacity) {
                currentReqNum++;
                return true;
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public static void mockRequest(int n, long delay, LeakyBucketLimiter limiter) {
        for (int i = 0; i < n; i++) {
            try {
                Thread.sleep(delay);
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
            if (limiter.allow()) {
                System.out.printf("第%d个请求通过\n", i + 1);
            } else {
                System.out.printf("第%d个请求被限流\n", i + 1);
            }
        }
    }


    public static void main(String[] args) {
        System.out.println("=================漏桶算法=================");
        LeakyBucketLimiter limiter = new LeakyBucketLimiter(4, 5);
        mockRequest(10, 50, limiter);
        System.out.println("------------------------------------------");
    }
}

优点：可以平滑处理请求速度
缺点：还是无法应对突发流量

令牌桶限流

令牌桶算法是维护一个固定的存放令牌的桶，令牌以固定的速率产生，并发入桶中。每个令牌代表一个请求的许可。

当请求到达时，需要从令牌桶中获取一个令牌才能通过。如果令牌桶中没有足够的令牌，则请求被限制或丢弃
算法步骤：

桶的容量：定义桶的容量，即服务器在一瞬间最多可以接受的请求数
令牌生成速率：定义令牌生成的速率，例如每秒生成的令牌数
计算当前令牌数：

每次请求时，计算桶中剩余的令牌数，也就是当前令牌数
(本次请求时间 - 上次请求时间) * 令牌生成速率 = 两次请求间隔内生成的令牌数
当前令牌数 (本次请求前剩余令牌数) + 请求间隔内生成的令牌数 = 最新的当前令牌数(本次请求后剩余的令牌数)

处理请求：

比较当前令牌数是否还有剩余，如果有就将令牌数 - 1，请求得到正常处理
如果令牌耗尽，请求就会被拒绝

令牌限流方法

public class TokenBucketLimiter {
    private final int rate; // 令牌产生的速度，即每秒生成多少个令牌
    private final int capacity; // 令牌桶容量，最多可存储令牌数
    private int currentTokenNum; // 当前令牌数
    private LocalDateTime lastTime; // 上次请求时间
    private final Lock lock; // 请求锁

    public TokenBucketLimiter(int rate, int capacity) {
        this.rate = rate;
        this.capacity = capacity;
        this.currentTokenNum = 0;
        this.lastTime = LocalDateTime.now();
        this.lock = new ReentrantLock();
    }

    public int getCurrentTokenNum() {
        return currentTokenNum;
    }

    public int getRate() {
        return rate;
    }

    public int getCapacity() {
        return capacity;
    }

    public boolean allow() {
        lock.lock();
        try {
            long millisSinceLast = ChronoUnit.MILLIS.between(lastTime, LocalDateTime.now());
            int tokenCount = (int) (millisSinceLast / 1000.0 * rate);

            if (tokenCount > 0) {
                currentTokenNum += tokenCount;
                lastTime = LocalDateTime.now();
            }

            if (currentTokenNum > capacity) {
                currentTokenNum = capacity;
            }

            if (currentTokenNum > 0) {
                currentTokenNum--;
                return true;
            }
            return false;
        } finally {
            lock.unlock();
        }
    }

    public static void mockRequest(int n, Duration d, TokenBucketLimiter limiter) {
        ScheduledExecutorService executor = Executors.newScheduledThreadPool(1);

        for (int i = 0; i < n; i++) {
            int requestId = i + 1;
            executor.schedule(() -> {
                if (limiter.allow()) {
                    System.out.printf("第%d个请求通过\n", requestId);
                } else {
                    System.out.printf("第%d个请求被限流\n", requestId);
                }
            }, i * d.toMillis(), TimeUnit.MILLISECONDS);
        }

        executor.shutdown();
        try {
            if (!executor.awaitTermination(5, TimeUnit.SECONDS)) {
                executor.shutdownNow();
            }
        } catch (InterruptedException e) {
            executor.shutdownNow();
        }
    }

    public static void main(String[] args) {
        System.out.println("=================令牌桶算法=================");
        // 创建一个令牌桶，令牌的生成速度为每秒4个，桶容量为5个请求
        TokenBucketLimiter limiter = new TokenBucketLimiter(4, 5);
        // 发送10个请求，每50ms发送一个
        mockRequest(10, Duration.ofMillis(50), limiter);
        System.out.println("------------------------------------------");
    }
}

优点：平滑流量，将突发流量平滑的分散到一定时间内，由于令牌可以在桶中积累，当流量增大时，系统也可以快速响应

上一篇：6种常见的缓存策略，请查收

下一篇：10W QPS高并发，如何防止重复下单？