一起学习下限流

学习心得 做棵大树 2周前 (04-01) 71次浏览 0个评论
文章目录[隐藏]

快手 #面试

限流是互联网系统中常见的一种保护机制,用于在系统面临大量请求时,保证系统资源的合理分配和系统的稳定运行。下面将对限流的概念、作用、影响、实现方式和相关算法进行详细介绍。

概念

限流,即限制流量,是指在一定时间内对访问频率或数量进行控制,以防止系统因为超负荷运行而崩溃。通过限流,可以保证系统在高并发情况下的稳定性和可用性,同时也能提升用户体验。

作用

  1. 保护系统资源:限流可以防止系统因为短时间内的大量请求而过载,从而保护服务器资源,避免因资源耗尽导致的服务中断。
  2. 提高系统可用性:通过限流,可以确保系统在高并发情况下依然能够稳定运行,提高系统的可用性。
  3. 优化用户体验:合理的限流策略可以避免用户在访问高峰期遇到服务不可用的情况,提升用户的满意度。
  4. 防止恶意攻击:限流还可以防止恶意用户或攻击者通过大量请求对系统进行拒绝服务攻击(DoS/DDoS)。

影响

限流虽然可以保护系统资源和提高系统稳定性,但同时也可能对用户体验产生一定的负面影响。例如,如果限流策略设置得过于严格,可能会导致正常用户的访问请求被拒绝,从而影响用户体验。因此,在实施限流策略时需要权衡好系统稳定性和用户体验之间的关系。

限流的实现方式

  1. 固定窗口计数器:在固定的时间窗口内,统计请求的数量,当请求超过设定的阈值时,后续的请求将被拒绝。
  2. 滑动窗口计数器:与固定窗口类似,但时间窗口是滑动的,这样可以更平滑地处理请求,避免因窗口切换导致的请求突增或突减。
  3. 令牌桶算法:系统以固定速率生成令牌,请求需要消耗令牌才能通过,如果令牌不足,请求将被拒绝或延迟处理。
  4. 漏桶算法:请求被放入一个漏桶中,以固定的速率从漏桶中释放请求进行处理,这样可以平滑请求的流量,避免短时间内的请求峰值。

相关算法

计数器算法

计数器算法是最简单直接的限流算法。它通过设置一个固定大小的计数器,用来记录在给定时间窗口内的请求数量。例如,如果我们希望每秒只处理 100 个请求,那么计数器的容量就设置为 100。

在每个请求到来时,系统会检查当前计数器的值。如果计数器的值还没有达到设定的阈值,那么请求被允许通过,并且计数器的值增加。如果计数器的值已经达到阈值,那么新的请求将被拒绝或者延迟处理,直到下一个时间窗口开始。

计数器算法的优点是实现简单,易于理解。但它的缺点也很明显,它不能处理突发流量,因为在时间窗口开始时,可能会有大量的请求同时到达,这可能导致系统在瞬间过载。

令牌桶算法

令牌桶算法是一种更加灵活的限流算法。它使用两个参数:令牌生成速率令牌桶的大小。系统会以固定的速率向令牌桶中添加令牌,当添加到最大容量时,就不再添加。每个请求在被处理前需要消耗一个令牌,如果桶中没有令牌,请求就会被拒绝或延迟。

令牌桶算法的优点是它不仅可以平滑突发流量,还可以允许一定程度的流量突发。这意味着在令牌桶未满时,系统可以处理比平均速率更高的请求,从而提高资源利用率

漏桶算法

漏桶算法是一种平滑流量的算法。它通过模拟一个有固定容量的漏桶,所有进入系统的请求都被先放入漏桶中。漏桶以固定的速率“漏出”请求,即以固定的速率处理请求。无论进入漏桶的请求速率如何,处理请求的速率都是恒定的。

漏桶算法的优点是它可以有效地防止系统因为短时间内的大量请求而过载,因为它保证了请求以稳定的速率被处理。但它的缺点是不能利用系统在低负载时的额外处理能力,因为即使系统当前负载很低,它也不会增加处理请求的速率。

固定窗口计数器与滑动窗口计数器

固定窗口计数器和滑动窗口计数器都是基于时间窗口的计数器算法,但它们处理时间窗口的方式不同。

固定窗口计数器在一个固定的时间窗口(例如,每分钟)内统计请求的数量。这种方法简单,但可能会导致在窗口开始时请求集中到达,造成系统负载瞬间增高。

滑动窗口计数器则将时间窗口分成多个小段,每个小段内独立统计请求数量。这样可以更平滑地处理请求,避免因窗口切换导致的请求突增或突减。但实现起来相对复杂,需要维护多个计数器。

分布式限流

在分布式系统中,限流需要考虑跨多个节点的一致性问题。分布式限流通常需要使用分布式锁或分布式存储系统(如 Redis、Zookeeper 等)来保证限流的一致性。

例如,使用 Redis 的分布式限流,可以通过 Redis 的原子操作来实现。每个请求在到达时,先尝试从 Redis 中获取一个令牌,如果获取成功,则处理请求;如果失败,则拒绝或延迟请求。通过设置 Redis 的过期时间,可以控制令牌的生成速率,从而实现限流。

分布式限流的优点是可以跨多个节点统一限流策略,保证整个系统的稳定性。但同时也带来了额外的复杂性,需要处理分布式系统中的一致性和可用性问题。

算法示例

以下是简单的 Java 实现的示例代码,以帮助理解如何在实际编程中应用这些限流算法。

计数器算法

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

public class CounterRateLimiter {
    private final AtomicInteger count = new AtomicInteger(0);
    private final int limit;
    private final long windowSize;
    private final long checkInterval;

    public CounterRateLimiter(int limit, long windowSize, long checkInterval) {
        this.limit = limit;
        this.windowSize = windowSize;
        this.checkInterval = checkInterval;
    }

    public synchronized boolean tryAcquire() {
        int currentCount = count.get();
        long now = System.currentTimeMillis();
        // 如果当前时间超过了窗口结束时间,重置计数器
        if (now - lastUpdate > windowSize) {
            count.set(1);
            lastUpdate = now;
        } else {
            // 在窗口内,尝试增加计数
            if (currentCount < limit) {
                count.incrementAndGet();
                return true;
            }
        }
        return false;
    }
}

令牌桶算法

import java.util.concurrent.atomic.AtomicInteger;

public class TokenBucketRateLimiter {
    private final AtomicInteger tokens = new AtomicInteger(0);
    private final int maxTokens;
    private final long refillInterval;

    public TokenBucketRateLimiter(int maxTokens, int refillTokens, long refillInterval) {
        this.maxTokens = maxTokens;
        this.refillInterval = refillInterval;
        refillTokens();
    }

    private void refillTokens() {
        int newTokens = Math.min(maxTokens, tokens.get() + refillTokens);
        tokens.set(newTokens);
    }

    public boolean tryAcquire() {
        if (tokens.get() > 0) {
            int tokensToUse = 1;
            tokens.addAndGet(-tokensToUse);
            return true;
        }
        return false;
    }

    // 定时任务,用于定期补充令牌
    public void scheduleRefill() {
        new Timer().schedule(new TimerTask() {
            @Override
            public void run() {
                refillTokens();
            }
        }, 0, refillInterval);
    }
}

漏桶算法

import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.TimeUnit;

public class LeakyBucketRateLimiter {
    private final LinkedBlockingQueue<Request> queue = new LinkedBlockingQueue<>();
    private final int permits;
    private final long maxBurst;

    public LeakyBucketRateLimiter(int permits, long maxBurst) {
        this.permits = permits;
        this.maxBurst = maxBurst;
    }

    public boolean tryAcquire() throws InterruptedException {
        Request request = new Request(System.currentTimeMillis());
        if (queue.size() < maxBurst) {
            queue.put(request);
            return true;
        }
        // 检查队列头部请求的时间,如果当前时间超过该时间加上漏桶速率,则拒绝
        if (System.currentTimeMillis() - queue.peek().time > permits) {
            return false;
        }
        queue.put(request);
        return true;
    }

    private static class Request {
        final long time;

        public Request(long time) {
            this.time = time;
        }
    }
}

滑动窗口

滑动窗口限流算法相较于固定窗口算法,能够更平滑地处理请求,因为它不会在窗口开始时立即消耗所有的令牌。下面是一个简单的滑动窗口限流算法的 Java 实现示例:

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.TimeUnit;
import java.util.Date;

public class SlidingWindowRateLimiter {
    private final AtomicInteger counter = new AtomicInteger(0);
    private final LinkedBlockingQueue<Date> window = new LinkedBlockingQueue<>();
    private final int limit;
    private final long windowSizeInMillis;

    public SlidingWindowRateLimiter(int limit, long windowSize) {
        this.limit = limit;
        this.windowSizeInMillis = windowSize;
    }

    public boolean tryAcquire() {
        // 获取当前时间
        Date now = new Date();
        // 移除过期的请求
        while (!window.isEmpty() && window.peek().before(now)) {
            window.poll();
        }
        // 增加新的请求
        window.offer(now);
        // 更新计数器
        int newCount = counter.addAndGet(1);
        // 检查是否超过限制
        return newCount <= limit;
    }

    // 可以添加一个定时任务,定期清理过期的请求
    public void startCleanupTask() {
        new Thread(() -> {
            while (true) {
                try {
                    TimeUnit.MILLISECONDS.sleep(windowSizeInMillis);
                    tryAcquire(); // 调用 tryAcquire 来清理过期的请求
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                    break;
                }
            }
        }).start();
    }
}

在这个实现中,我们使用了LinkedBlockingQueue来存储窗口内的请求时间。每次尝试获取令牌时,我们首先检查队列中的最早请求是否已经过期(即是否早于当前时间减去窗口大小)。如果是,我们就将其从队列中移除,然后添加一个新的请求时间,并更新计数器。
如果计数器的值超过了限制,tryAcquire方法将返回false,表示请求被拒绝。否则,它将返回true,表示请求被允许。

此外,我们提供了一个startCleanupTask方法来启动一个定时任务,定期清理过期的请求。这样可以避免手动调用tryAcquire来清理。

注意,上述代码仅为示例,实际应用中需要根据具体需求进行调整和完善。例如,我们可能需要添加更多的错误处理、日志记录、配置参数等功能。同时,对于分布式限流,您可能需要使用如 Redis 这样的外部存储系统来实现跨 JVM 的限流。

总结

限流算法的选择需要根据具体的业务场景和系统特点来决定。对于需要平滑流量、防止系统过载的场景,漏桶算法和分布式限流可能更加合适;而对于需要处理突发流量、提高资源利用率的场景,令牌桶算法可能更加适用。计数器算法和滑动窗口计数器则适用于简单的限流需求。在实际应用中,可能需要结合多种算法来达到最佳的限流效果。同时,限流策略的实施也需要配合监控和反馈机制,以便及时发现并解决可能出现的问题。


做棵大树 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明一起学习下限流
喜欢 (0)
[欢迎投币]
分享 (0)
关于作者:
一个整天无所事事的,有时候忽然热血的孩子
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址