首页 > 其他分享 >限流器设计思路（浅入门）

限流器设计思路（浅入门）

时间：2024-06-07 18:14:09浏览次数：21  
标签：令牌 false 入门 Bucket 限流 思路 Leaky true 请求

目录

限流器(Rate Limiter)是一种用于控制系统资源利用率和质量的重要机制。它通过限制单位时间内可以执行的操作数量，从而防止系统过载和保护服务的可靠性。在程序设计中，可以使用多种方式来实现限流器，下面是几个常见方案的介绍：

  • 令牌桶算法
  • 漏桶算法
  • 划窗算法
  • 固定窗口算法（缺点很大！）
  • 基于计数器的流量控制算法
  • ...

令牌桶算法(Token Bucket)

令牌桶算法是一种常见的限流实现方式。它维护一个存放令牌的桶,以固定的速率向桶中添加令牌。每次请求到来时,需要从桶中获取一个令牌,只有当桶中有足够的令牌时,请求才能被处理。否则,请求将被拒绝或阻塞。

image

实现思路如下:

  • 维护一个固定大小的令牌桶和一个记录上一次令牌被添加到桶中的时间戳。
  • 以固定的速率(每秒生成的令牌数)向桶中添加令牌。
  • 当请求到来时,尝试从桶中获取一个令牌。如果桶中有令牌,则处理请求并消耗一个令牌;否则,拒绝或阻塞请求。
  • 使用锁或其他同步机制来保证线程安全。

code:

package RateLimiter;
import java.util.concurrent.Semaphore;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;

// 令牌桶算法 (TokenBucketRateLimiter)
public class TokenBucketRateLimiter {
    /**
     * REFILL_PERIOD 表示令牌桶的refill周期,即每隔多长时间(秒)向桶中添加令牌。
     * MAX_TOKENS 表示令牌桶的最大容量,即桶中最多可以存放多少个令牌。
     * REFILL_TOKENS 表示每个refill周期向桶中添加的令牌数量。
     * lastRefillTimestamp 记录上一次refill的时间戳。
     * tokenBucket 是一个Semaphore实例,用于模拟令牌桶的行为。
     */
    private static final long REFILL_PERIOD = 1; // 1秒
    private static final long MAX_TOKENS = 5; // 桶容量
    private static final long REFILL_TOKENS = 2; // 每次添加令牌数
    /**
     * AtomicLong是Java中用于表示一个原子性的长整型值的类。它提供了一些原子操作方法,用于在多线程环境下安全地更新和访问长整型值。
     *  - 在这些限流器实现中,AtomicLong主要用于记录上一次令牌/请求刷新的时间戳。
     *  - 由于多个线程可能同时尝试获取令牌或请求,因此需要确保对时间戳的读写操作是原子性的,以避免竞态条件。
     */
    private AtomicLong lastRefillTimestamp = new AtomicLong(System.nanoTime());
    /**
     * Semaphore（信号量）是Java中一个并发控制工具，用于控制对共享资源的访问。
     *      - 它基于计数器的原理，可以限制同时访问某个资源的线程数量。用于模拟令牌桶的行为。
     *      - Semaphore使用acquire()和release()方法来获取和释放信号量：
     */
    private Semaphore tokenBucket = new Semaphore((int) MAX_TOKENS);

    /**
     * tryAcquire() 方法是获取令牌的入口:
     *
     * 1-获取当前时间戳 now。
     * 2-根据当前时间戳和上一次refill时间戳,计算出这段时间内应该添加多少个令牌 newTokens。
     * 3-更新上一次refill时间戳为当前时间戳。
     * 4-将新的令牌数量 newTokens 释放到 tokenBucket 中。
     * 5-尝试从 tokenBucket 中获取一个令牌,如果成功则返回 true,否则返回 false。
     */
    public boolean tryAcquire() {
        long now = System.nanoTime();
        long lastRefillTime = lastRefillTimestamp.get();
        long newTokens = calculateNewTokens(lastRefillTime, now);
        lastRefillTimestamp.set(now);

        tokenBucket.release((int) newTokens);
        return tokenBucket.tryAcquire();
    }

    /**
     * calculateNewTokens() 方法根据时间差计算出应该添加的令牌数量,但不会超过桶的最大容量。
     */
    private long calculateNewTokens(long lastRefillTime, long now) {
        long nanosElapsed = now - lastRefillTime;
        long refillPeriodCount = nanosElapsed / TimeUnit.SECONDS.toNanos(REFILL_PERIOD);
        return Math.min(refillPeriodCount * REFILL_TOKENS, MAX_TOKENS);
    }
}

漏桶算法(Leaky Bucket)

漏桶算法类似于令牌桶算法,不同之处在于它维护一个存放请求的队列,而不是令牌桶。当请求到来时,它们会被添加到队列中。队列以固定的速率漏水,即以固定的速率处理请求。

image

实现思路如下:

  • 维护一个固定大小的请求队列和一个上次处理请求的时间戳。
  • 当请求到来时,将其添加到队列中。如果队列已满,则拒绝或阻塞请求。
  • 以固定的速率(每秒处理的请求数)从队列中取出请求并处理。
  • 使用锁或其他同步机制来保证线程安全。

code:

package RateLimiter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicLong;

// 漏桶算法 (LeakyBucketRateLimiter)
public class LeakyBucketRateLimiter {
    /**
     * REFILL_PERIOD 表示漏桶的refill周期,即每隔多长时间(秒)处理请求。
     * MAX_REQUESTS 表示漏桶的最大容量,即桶中最多可以存放多少个请求。
     * REFILL_REQUESTS 表示每个refill周期处理的请求数量。
     * requestQueue 是一个队列,用于存放待处理的请求。
     * lastRefillTimestamp 记录上一次refill的时间戳。
     */
    private static final long REFILL_PERIOD = 1; // 1秒
    private static final long MAX_REQUESTS = 5; // 桶容量
    private static final long REFILL_REQUESTS = 2; // 每次处理请求数

    private Queue<Long> requestQueue = new LinkedList<>();
    private AtomicLong lastRefillTimestamp = new AtomicLong(System.nanoTime());

    /**
     * tryAcquire() 方法是获取请求的入口:
     *  - 获取当前时间戳 now。
     *  - 根据当前时间戳和上一次refill时间戳,计算出这段时间内应该处理多少个请求 newRequests。
     *  - 更新上一次refill时间戳为当前时间戳。
     *  - 将新的请求数量 newRequests 添加到 requestQueue 中,如果队列已满则移除最早的请求。
     *  - 如果队列大小不超过最大容量 MAX_REQUESTS,则返回 true,否则返回 false。
     */
    public boolean tryAcquire() {
        long now = System.nanoTime();
        long lastRefillTime = lastRefillTimestamp.get();
        long newRequests = calculateNewRequests(lastRefillTime, now);
        lastRefillTimestamp.set(now);

        for (long i = 0; i < newRequests; i++) {
            if (requestQueue.size() >= MAX_REQUESTS) {
                requestQueue.poll();
            }
            requestQueue.offer(now);
        }

        return requestQueue.size() <= MAX_REQUESTS;
    }

    /**
     * calculateNewRequests() 方法根据时间差计算出应该处理的请求数量。
     */
    private long calculateNewRequests(long lastRefillTime, long now) {
        long nanosElapsed = now - lastRefillTime;
        long refillPeriodCount = nanosElapsed / TimeUnit.SECONDS.toNanos(REFILL_PERIOD);
        return refillPeriodCount * REFILL_REQUESTS;
    }
}

滑动窗口(Sliding Window)

滑动窗口算法通过维护一个固定大小的窗口来限制单位时间内的请求数。当请求到来时,它会检查窗口内的请求数是否已达到限制。如果没有,则允许请求;否则,拒绝或阻塞请求。窗口会随着时间推移而滑动,移除较早的请求记录。

冷知识：
TCP协议中数据包的传输，同样也是采用滑动窗口来进行流量控制。

实现思路如下:

  • 维护一个队列或其他数据结构来存储请求的时间戳。
  • 当请求到来时,将其时间戳添加到队列中。
  • 检查队列中最近的一段时间内(窗口大小)的请求数是否超过限制。如果没有,则允许请求;否则,拒绝或阻塞请求。
  • 定期(或在每次请求到来时)移除队列中较早的请求记录,以维护窗口大小。
  • 使用锁或其他同步机制来保证线程安全。

Reference:
https://blog.csdn.net/legend050709/article/details/114917637

原理：
需要先看看固定窗口算法的原理和缺点，
image

动图：
image

image

image

code:

package RateLimiter;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 滑动窗口算法 (SlidingWindowRateLimiter)
 */
public class SlidingWindowRateLimiter {
    /**
     * WINDOW_SIZE 表示滑动窗口的大小(秒)。
     * MAX_REQUESTS 表示窗口内允许的最大请求数量。
     * requestTimestamps 是一个队列,用于存放请求的时间戳。
     */
    private static final long WINDOW_SIZE = 5; // 窗口大小(秒)
    private static final long MAX_REQUESTS = 10; // 最大请求数
    private Queue<Long> requestTimestamps = new LinkedList<>();

    /**
     * tryAcquire() 方法是获取请求的入口:
     *  - 获取当前时间戳 now。
     *  - 将当前时间戳添加到 requestTimestamps 队列中。
     *  - 计算窗口的开始时间 windowStartTime。
     *  - 移除队列中早于 windowStartTime 的时间戳,即移除窗口之外的请求记录。
     *  - 如果队列大小不超过 MAX_REQUESTS,则返回 true,否则返回 false。
     */
    public boolean tryAcquire() {
        long now = System.currentTimeMillis();
        requestTimestamps.add(now);

        long windowStartTime = now - WINDOW_SIZE * 1000;
        while (!requestTimestamps.isEmpty() && requestTimestamps.peek() < windowStartTime) {
            requestTimestamps.poll();
        }

        return requestTimestamps.size() <= MAX_REQUESTS;
    }
}

演示code：

package RateLimiter;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

public class RateLimiterDemo {
    public static void main(String[] args) {
        // 创建限流器实例
        TokenBucketRateLimiter tokenBucketRateLimiter = new TokenBucketRateLimiter();
        LeakyBucketRateLimiter leakyBucketRateLimiter = new LeakyBucketRateLimiter();
        SlidingWindowRateLimiter slidingWindowRateLimiter = new SlidingWindowRateLimiter();

        // 创建线程池
        ExecutorService executorService = Executors.newFixedThreadPool(10);

        // 提交任务
        for (int i = 0; i < 20; i++) {
            executorService.submit(() -> {
                boolean tokenBucketAllowed = tokenBucketRateLimiter.tryAcquire();
                boolean leakyBucketAllowed = leakyBucketRateLimiter.tryAcquire();
                boolean slidingWindowAllowed = slidingWindowRateLimiter.tryAcquire();

                System.out.println("Token Bucket: " + tokenBucketAllowed +
                        ", Leaky Bucket: " + leakyBucketAllowed +
                        ", Sliding Window: " + slidingWindowAllowed);

                try {
                    TimeUnit.MILLISECONDS.sleep(500); // 模拟处理请求
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
        }

        // 关闭线程池
        executorService.shutdown();
    }
}

out:

Token Bucket: true, Leaky Bucket: true, Sliding Window: true
Token Bucket: false, Leaky Bucket: true, Sliding Window: true
Token Bucket: false, Leaky Bucket: true, Sliding Window: true
Token Bucket: false, Leaky Bucket: true, Sliding Window: true
Token Bucket: true, Leaky Bucket: true, Sliding Window: true
Token Bucket: false, Leaky Bucket: true, Sliding Window: true
Token Bucket: false, Leaky Bucket: true, Sliding Window: true
Token Bucket: true, Leaky Bucket: true, Sliding Window: true
Token Bucket: true, Leaky Bucket: true, Sliding Window: true
Token Bucket: true, Leaky Bucket: true, Sliding Window: true
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false
Token Bucket: false, Leaky Bucket: true, Sliding Window: false

总结

这三种算法都是通过控制请求的速率或数量来实现限流,但具体的实现方式有所不同。令牌桶算法和漏桶算法都依赖于时间来控制速率,而滑动窗口算法则是基于请求数量来控制。它们各有优缺点,适合不同的场景。具体选择哪种需要自己根据应用场景进行选择和调整。

同时,也可以考虑使用现有的限流器库或框架,如Guava RateLimiter、Netflix Hystrix等,以简化开发过程。

标签：令牌,false,入门,Bucket,限流,思路,Leaky,true,请求
From： https://www.cnblogs.com/mysticbinary/p/18237664

相关文章

  • 一个比较麻烦的限流需求
    主要环节1、前端接受用户请求，发送给后端建立任务；2、后端接受请求后，创建任务记录（初始状态），将记录发送到消息队列；2、消费者拿到任务后，将任务置为running，然后向外部平台发送请求，并向延时队列（5分钟）发送消息；3、外部平台收到请求后，（正常）会在2分钟内向我方的接收接口提交结果，也可能（5分......
  • 超详细！新手入门PMP®考试指南，收藏起来备考更高效​！
    回复数字“6”，查看PMP考试过关口诀无论你是刚刚踏入项目管理领域的新手，对于PMP®考试充满好奇与期待；还是已经在职场中摸爬滚打多年，希望通过PMP®认证来进一步提升自己的项目管理能力和职业竞争力。相信这份指南都会为你提供宝贵的报考信息和备考策略01PMP®考试简介PMP®......
  • ctfshow-web入门-命令执行（web37-web40）
    目录1、web37 2、web383、web394、web40命令执行，需要严格的过滤 1、web37 使用php伪协议：?c=php://inputpost写入我们希望执行的php代码：<?phpsystem('tacf*');?>拿到flag：ctfshow{5c555d9a-6f55-411a-a25f-d38b70240639}再看wp它用到是data://......
  • 测试用例设计方法六脉神剑——第一剑：入门试招，等价边界初探
    1背景及问题G.J.Myers在《软件测试技巧》中提出：测试是为了寻找错误而运行程序的过程，一个好的测试用例是指很可能找到迄今为止尚未发现的错误的测试，一个成功的测试是揭示了迄今为止尚未发现的错误的测试。对于新手来说，日常测试用例设计时，很少用到系统的方法论，大多是根据产品需......
  • GitHub飙升！京东认证的“Python编程入门三剑客”究竟好在哪？
    Python凭借着简单易学、功能强大，已经跃居TIOB编程语言榜首，并且已经开始了它的霸榜之旅。如何选择一套适合自己的Python学习教程，是每个Python爱好者面临的首要问题。今天给小伙伴们带来的是图灵&京东认证的“Python编程入门三剑客”，先看《Python编程从入门到实践》，打好Python入......
  • 学习前端3DThreejs一篇就够了，从入门到实战
    vue安装three.jsnpminstall--savethree引入three.jsimport*asTHREEfrom'three'three.js结构### three.js坐标创建一个场景scene场景，camera相机，renderer渲染器创建一个场景this.scene=newTHREE.Scene()创建一个透视摄像机this.camera=newTHR......
  • 梳理模型训练入门
    模型训练入门旨在理解和掌握模型训练的各个步骤，从数据准备、模型构建到模型评估和优化，并总结学习路径。一、数据准备获取数据公开数据集来源：Kaggle、UCI机器学习库等。示例：Kaggle上有许多公开的数据集和竞赛。自定义数据集根据项目需求自行收集或生成数据。示例：手......
  • AI预测平台处理思路
    AI预测平台处理思路配置：1.创建模型2.配置方案（设置训练周期与粒度）3.配置算法（设置算法）4.配置有效特征数据（影响因素）数据：1.历史数据2.特征数据（影响因素）数据取数：1.sql获取、灵活配置出参入参2.excel导入数据预测思路：根据历史数据，结合特征数据（影响因素），使用设置的算法......
  • AI 绘画零基础如何学习？AIGC绘画设计入门教学
    AI作画入门到是不难，有手就行。我们先从最简单的开始。完成这件事，只有一个步骤：找到一个能画画的AI工具，输入动机。这个工具叫做DiscoDiffusion。它只认识英文，不过这不是问题，你找个翻译软件把中文翻译成英文就行。如果你会科学上网，那么你打开这个网址，点击里面的"openincola......
  • Linux磁盘管理-LVM入门学习建议
    Linux磁盘管理-LVM入门学习建议准确掌握基础概念基础概念非常重要，以LVM逻辑卷为例，必须熟练掌握LV、PV以及VG的基本概念。之后才能进行更为复杂的管理操作。LVM基本大纲这里罗列出了学习LVM入门的基本大纲，供大家参考......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99