限流算法

1、漏桶限流算法

漏桶限流算法是一种常见的限流算法，它的基本思想是模拟一个漏桶来控制流量。这个漏桶可以看作一个固定容量的桶，所有的请求都先进入到这个桶里，然后按照一定的速率流出，如果请求进来的速度过快，超过了桶的容量，那么多余的请求就会被直接丢弃或者排队等待处理。

漏桶限流算法的实现方式也很简单，大致可以分为以下几个步骤：

初始化一个固定容量的漏桶，并设置流出速率。
当有请求进来时，先将其放入漏桶中。
如果漏桶还有剩余容量，那么这个请求就可以被处理，同时从漏桶中流出一个请求。
如果漏桶已经满了，那么这个请求就被丢弃或者排队等待处理。
在实际编程中，我们可以使用一个定时任务来模拟漏桶的流出速率，每次定时任务执行时，从漏桶中流出一个请求进行处理。

以下是一个简单的Java实现漏桶限流算法的示例代码：

public class LeakyBucket {
    private final int capacity;  // 漏桶容量
    private final int rate;      // 流出速率，单位为请求数/秒
    private int water;           // 当前水量
    private long timestamp;      // 上次流出时间

    public LeakyBucket(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.water = 0;
        this.timestamp = System.currentTimeMillis();
    }

    public boolean allowRequest() {
        // 先计算当前漏桶中的水量
        long now = System.currentTimeMillis();
        int out = (int) ((now - timestamp) / 1000 * rate);
        water = Math.max(0, water - out);

        // 检查漏桶是否已经满了
        if (water >= capacity) {
            return false;  // 漏桶已满，拒绝请求
        }

        // 漏桶还有剩余容量，将请求放入漏桶中，并更新时间戳和水量
        timestamp = now;
        water++;
        return true;
    }
}

在上面的代码中，LeakyBucket类表示一个漏桶限流器，它包含漏桶的容量、流出速率、当前水量以及上次流出时间等属性。allowRequest方法用于处理请求，如果漏桶还有剩余容量，那么这个请求就可以被处理，同时从漏桶中流出一个请求。否则，漏桶已满，拒绝请求。

2、滑动窗口限流算法

滑动窗口限流算法是一种常见的限流算法，用于控制请求流量，防止系统被过多的请求压垮。

该算法的基本思想是，将时间划分成固定大小的多个时间段，每个时间段称为一个桶，将请求分配到不同的桶中。如果某个桶中的请求数量超过了阈值，就拒绝该桶中多余的请求。

具体实现中，我们可以使用一个固定大小的队列来表示滑动窗口，队列中的每个元素表示一个时间段对应的桶。每当有请求到来时，就将其放入当前时间段对应的桶中，并计算当前滑动窗口中所有桶的请求数量。如果总请求数量超过了阈值，就拒绝该请求。同时，我们需要定期移除队列中最老的元素，以保证滑动窗口能够不断向前移动。

滑动窗口限流算法简单易懂，适用于大多数场景，但需要根据具体业务场景调整桶的大小和阈值的设定，以达到最佳的限流效果。

import java.util.LinkedList;
import java.util.Queue;

public class SlidingWindowRateLimiter {
    private Queue<Long> window;
    private final int limit;
    private final long windowSize;

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

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        if (window.size() >= limit) {
            long oldest = window.peek();
            if (now - oldest < windowSize) {
                return false; // Reject request
            }
            window.poll();
        }
        window.offer(now);
        return true; // Accept request
    }
}