当前位置：首页 > article >正文

你了解哪些Java限流算法?

article 2025/1/31 6:26:48

大家好，我是锋哥。今天分享关于【你了解哪些Java限流算法?】面试题。希望对大家有帮助；

你了解哪些Java限流算法?

1000道互联网大厂Java工程师精选面试题-Java资源分享网

Java 中常用的限流算法主要有以下几种，它们广泛应用于处理流量控制、API请求限制等场景：

1. 令牌桶算法（Token Bucket）

令牌桶算法是限流中最常用的一种方法。其基本思想是：

系统按固定速率向桶中放入令牌，每次请求需要消耗一个令牌。
如果桶中没有足够的令牌，请求会被拒绝或者被延迟处理。
如果令牌桶的容量大于实际请求速率，系统允许突发流量（超过速率的流量）。

特点：

支持突发流量。
限制速率比较平滑，可以动态调整。

实现方式：

使用一个线程定时向桶中放入令牌。
请求到达时，检查令牌桶是否有令牌。

public class TokenBucket {
    private final long capacity;
    private final long refillInterval;
    private long availableTokens;
    private long lastRefillTime;

    public TokenBucket(long capacity, long refillInterval) {
        this.capacity = capacity;
        this.refillInterval = refillInterval;
        this.availableTokens = capacity;
        this.lastRefillTime = System.currentTimeMillis();
    }

    public synchronized boolean acquire() {
        long now = System.currentTimeMillis();
        long elapsedTime = now - lastRefillTime;
        long tokensToAdd = elapsedTime / refillInterval;
        availableTokens = Math.min(capacity, availableTokens + tokensToAdd);
        lastRefillTime = now;

        if (availableTokens > 0) {
            availableTokens--;
            return true;
        }
        return false;
    }
}

2. 漏斗算法（Leaky Bucket）

漏斗算法通过一个固定容量的桶来控制请求速率。桶中有一定的容量，固定的速率会“漏掉”桶中的水，水（请求）按一定速率流出。

特点：

控制流量的输出速率平稳。
不允许突发流量，所有流量都按固定速率流出。

实现方式：

每次请求到来时，检查桶中的水量（请求数），如果桶已经满了，就拒绝请求。
否则允许请求进入桶，按固定速率流出。

public class LeakyBucket {
    private final long capacity;
    private final long leakRate;
    private long waterLevel;
    private long lastLeakTime;

    public LeakyBucket(long capacity, long leakRate) {
        this.capacity = capacity;
        this.leakRate = leakRate;
        this.waterLevel = 0;
        this.lastLeakTime = System.currentTimeMillis();
    }

    public synchronized boolean acquire() {
        long now = System.currentTimeMillis();
        long elapsedTime = now - lastLeakTime;
        long leakedWater = elapsedTime / leakRate;
        waterLevel = Math.max(0, waterLevel - leakedWater);
        lastLeakTime = now;

        if (waterLevel < capacity) {
            waterLevel++;
            return true;
        }
        return false;
    }
}

3. 计数窗口算法（Fixed Window Counter）

计数窗口算法是最简单的一种限流算法，它将时间划分为多个固定的时间窗口，每个时间窗口内可以接受一定数量的请求。

特点：

简单易理解。
容易受到“窗口切分”的影响，可能会在窗口的边界出现突发流量。

实现方式：

每个窗口内计数器限制请求次数。
请求到来时，检查当前时间窗口是否超过了限制。

public class FixedWindowCounter {
    private final int limit;
    private int count;
    private long lastWindowStartTime;

    public FixedWindowCounter(int limit) {
        this.limit = limit;
        this.count = 0;
        this.lastWindowStartTime = System.currentTimeMillis();
    }

    public synchronized boolean acquire() {
        long currentTime = System.currentTimeMillis();
        if (currentTime - lastWindowStartTime >= 1000) { // New window
            count = 0;
            lastWindowStartTime = currentTime;
        }
        if (count < limit) {
            count++;
            return true;
        }
        return false;
    }
}

4. 滑动窗口算法（Sliding Window Log）

滑动窗口算法是对固定窗口的改进，避免了固定窗口中产生的突发流量问题。它通过记录每个请求的时间戳，然后根据时间戳来判断请求是否超出了时间窗口。

特点：

较为精确地控制请求数量，避免了固定窗口的突发流量问题。
实现相对复杂。

实现方式：

使用队列记录每个请求的时间戳，当新请求到来时，去除过期的时间戳并检查当前窗口内的请求数量。

import java.util.LinkedList;

public class SlidingWindowLog {
    private final int limit;
    private final long windowSize;
    private LinkedList<Long> requests;

    public SlidingWindowLog(int limit, long windowSize) {
        this.limit = limit;
        this.windowSize = windowSize;
        this.requests = new LinkedList<>();
    }

    public synchronized boolean acquire() {
        long currentTime = System.currentTimeMillis();
        while (!requests.isEmpty() && currentTime - requests.peekFirst() >= windowSize) {
            requests.pollFirst();
        }
        if (requests.size() < limit) {
            requests.addLast(currentTime);
            return true;
        }
        return false;
    }
}

5. Redis限流

使用 Redis 进行限流是分布式环境中常见的一种做法，主要使用 Redis 的 INCR 和 EXPIRE 命令来实现。

特点：

适用于分布式系统。
可扩展性强。

实现方式：

使用 Redis 存储请求计数，设置过期时间。
请求时进行计数和判断。

public class RedisRateLimiter {
    private final String redisKey;
    private final int limit;
    private final long period;
    private final Jedis jedis;

    public RedisRateLimiter(String redisKey, int limit, long period, Jedis jedis) {
        this.redisKey = redisKey;
        this.limit = limit;
        this.period = period;
        this.jedis = jedis;
    }

    public boolean acquire() {
        long currentTime = System.currentTimeMillis() / 1000;
        String key = redisKey + ":" + currentTime;

        Long count = jedis.incr(key);
        if (count == 1) {
            jedis.expire(key, (int) period);
        }
        return count <= limit;
    }
}