限流算法之固定窗口算法

---

前言

固定窗口算法是一种常见的滑动窗口算法，用于处理数据流中的窗口操作。

---

优缺点

优点

• 易于理解：该实现使用了简单的队列和计数器，易于理解和实现。
• 高效：该实现使用了文件系统操作来检查文件是否存在和所在的目录是否符合限制，因此效率较高。
• 可扩展：该实现可以轻松地扩展到处理多个文件类型或目录。
• 持久化存储：通过使用目录结构，可以将数据持久化存储，以便在程序重启后继续使用。
• 灵活性：该实现可以根据需要调整窗口大小和目录结构，以适应不同的应用场景。
• 错误处理：该实现通过检查文件是否存在和目录结构是否正确，可以避免一些常见的错误情况。
• 并发访问：由于使用了文件系统操作，该实现可以在多线程环境下并发访问。

缺点

• 文件系统操作可能比较耗时：对于大型文件系统或大量事件的情况下，文件系统操作可能会成为性能瓶颈。这可以通过缓存或优化文件系统访问来解决。
• 误判风险：如果文件系统中的文件数量超过了窗口大小限制，该实现可能会拒绝一些合法的事件。这可以通过增加额外的检查或调整文件命名规则来减少误判的风险。
• 数据竞争：由于使用了文件系统操作，该实现可能存在数据竞争的问题。这可以通过使用同步机制或并发控制来解决。

示例代码

java

代码如下（示例）：

/**
 * @Date 2024/1/18 15:42
 * @Author yang
 */
public class FixedWindow {
    private int windowSize;
    private long[] timestamps;
    private int current;

    public FixedWindow(int windowSize) {
        this.windowSize = windowSize;
        this.timestamps = new long[windowSize];
        this.current = 0;
    }

    public void addTimestamp(long timestamp) {
        System.out.println("时间" + timestamp);
        System.out.println("当前" + current);
        timestamps[current] = timestamp;
        current = (current + 1) % windowSize;
    }

    public int getCountWithinWindow(long currentTime, long interval) {
        int count = 0;
        System.out.println("count" + count);
        for (int i = 0; i < windowSize; i++) {
            if (currentTime - timestamps[i] <= interval) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        FixedWindow fixedWindow = new FixedWindow(5);
        fixedWindow.addTimestamp(System.currentTimeMillis() - 10000);
        fixedWindow.addTimestamp(System.currentTimeMillis() - 8000);
        fixedWindow.addTimestamp(System.currentTimeMillis() - 5000);
        fixedWindow.addTimestamp(System.currentTimeMillis() - 2000);
        fixedWindow.addTimestamp(System.currentTimeMillis() - 1000);
        System.out.println("最近5秒内发生的事件: " + fixedWindow.getCountWithinWindow(System.currentTimeMillis(), 5000));
    }
}

---

适用场景

1. API接口限流：对于高流量的API接口，可以使用固定窗口算法来限制同时访问的请求数量，避免单个请求对系统造成过大压力。
2. 网络流量控制：在保证网络稳定性和可靠性的场景中，可以使用滑动窗口算法来动态调整发送数据的速率和数量。
3. 服务器资源管理：在服务器资源有限的情况下，可以使用滑动窗口算法来控制请求的处理速率和资源分配。

不推荐

原因如下：

固定窗口算法无法处理突发流量，当短时间内有大量请求到达时，请求会直接被拒绝，而无法平滑地控制流量。此外，窗口边界问题也可能导致系统过载，因为在窗口边界处可能会有大量的请求被允许通过，从而导致突发流量。因此，需要合理调整时间窗口大小以应对不同的流量情况。