devbox
weixin_40725706
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【知识点随笔分享 | 第九篇】常见的限流算法_固定时间窗口限流

作者：weixin_40725706 | 2024-03-20 15:29:28

赞

踩

固定时间窗口限流

目录

前言：

1.固定窗口限流： 

缺点： 

2.滑动窗口限流：

 优点：

滴桶限流：

缺点：

令牌桶限流： 

优点：

总结:

 

前言：

        当今互联网时代，随着网络流量的快速增长和系统负载的不断加重，限流算法作为一种重要的网络管理工具变得愈发重要。限流算法通过控制系统的输入和输出流量，有效地保护系统不受过载的影响，确保系统能够稳定可靠地运行。本文将介绍几种常见的限流算法及其应用场景，旨在帮助读者更好地理解限流算法的原理和实际应用，从而为网络性能优化提供有力支持。限流算法的研究和应用对于保障网络安全、提升系统稳定性具有重要意义，在当前信息化社会具有广泛的应用前景。 

1.固定窗口限流： 

        固定窗口限流  就是在单位时间（时间窗口）内，只能接收指定数量的请求。

  • 在固定窗口限流算法中，时间被划分为固定大小的窗口，并且每个窗口内允许通过的请求数是固定的。
  • 算法步骤：
    • 统计当前窗口内的请求数；
    • 如果请求数超过了限制值，则拒绝该请求；
    • 重置新的窗口开始计数。

用汉堡店举例：固定窗口限流就是  在固定的时间内只能接待指定数量的顾客。比如一个小时只能接待10个顾客。

固定窗口限流的思路比较简单，代码实现为：

  1. import java.util.concurrent.TimeUnit;
  2. import java.util.concurrent.atomic.AtomicInteger;
  3.  
  4. public class FixedWindowRateLimiter {
  5.     private final int limit;  // 限制的请求数
  6.     private final long windowSizeInMillis;  // 窗口大小（毫秒）
  7.     private final AtomicInteger counter;
  8.     private long windowStartTime;
  9.  
  10.     public FixedWindowRateLimiter(int limit, long windowSizeInMillis) {
  11.         this.limit = limit;
  12.         this.windowSizeInMillis = windowSizeInMillis;
  13.         this.counter = new AtomicInteger(0);
  14.         this.windowStartTime = System.currentTimeMillis();
  15.     }
  16.  
  17.     public boolean allowRequest() {
  18.         long currentTime = System.currentTimeMillis();
  19.         long elapsedTime = currentTime - windowStartTime;
  20.  
  21.         if (elapsedTime > windowSizeInMillis) {
  22.             // 进入新的窗口，重置计数器和窗口开始时间
  23.             counter.set(0);
  24.             windowStartTime = currentTime;
  25.         }
  26.  
  27.         // 检查请求数是否超过限制
  28.         if (counter.incrementAndGet() > limit) {
  29.             return false;  // 超过限制，拒绝请求
  30.         }
  31.  
  32.         return true;  // 没有超过限制，允许请求通过
  33.     }
  34. }

缺点： 

        固定窗口限流可能会引发流量突刺，也就是可能会发生以下情况：

我们用红色来标识 在该时间窗口区域发生了请求，也就是说固定窗口限流在窗口的边界处可能会发生流量突刺，在短时间内发生多次请求

2.滑动窗口限流：

           滑动窗口限流  就是在单位时间（时间窗口）内，只能接收指定数量的请求。但单位时间是滑动的。

  • 在滑动窗口限流算法中，时间被划分为固定大小的窗口，每个窗口内允许通过的请求数是固定的，同时可以滑动窗口来适应请求的变化。
  • 算法步骤：
    • 统计当前窗口内的请求数；
    • 如果请求数超过了限制值，则拒绝该请求；
    • 滑动窗口，将旧的窗口移除。

我们用图片来标识滑动窗口限流和固定窗口限流的区别：

这是固定窗口限流，他的时间窗口是由时间窗口大小决定的。 

 这是滑动窗口限流，他的时间窗口是不断滑动的。

也就是说：滑动窗口限流不会一次性消除旧窗口的请求次数，而是不断的通过滑动的方式抹除。

 用汉堡店举例：滑动窗口限流就是  单位时间内限制接客数，相比较于固定窗口而言，假设我们在5.59接待了五位客人，如果时间窗口长度为小时，滑动单位为1分钟，那么六点的时候，并不会刷新窗口接待客人人数，而是继续保留5.59的接待人数。因为此时二者仍位于一个窗口内。  

滑动窗口限流的代码思路为:

  1. import java.util.concurrent.TimeUnit;
  2. import java.util.concurrent.atomic.AtomicInteger;
  3. import java.util.concurrent.locks.Lock;
  4. import java.util.concurrent.locks.ReentrantLock;
  5.  
  6. public class SlidingWindowRateLimiter {
  7.     private final int limit;  // 限制的请求数
  8.     private final long windowSizeInMillis;  // 窗口大小（毫秒）
  9.     private final int[] counter;
  10.     private final Lock lock;
  11.     private long windowStartTime;
  12.  
  13.     public SlidingWindowRateLimiter(int limit, long windowSizeInMillis) {
  14.         this.limit = limit;
  15.         this.windowSizeInMillis = windowSizeInMillis;
  16.         this.counter = new int[(int) (windowSizeInMillis / 1000)];
  17.         this.lock = new ReentrantLock();
  18.         this.windowStartTime = System.currentTimeMillis();
  19.     }
  20.  
  21.     public boolean allowRequest() {
  22.         long currentTime = System.currentTimeMillis();
  23.         long elapsedTime = currentTime - windowStartTime;
  24.  
  25.         lock.lock();
  26.         try {
  27.             // 滑动窗口，将旧的窗口移除
  28.             if (elapsedTime > windowSizeInMillis) {
  29.                 int numToRemove = (int) ((elapsedTime - windowSizeInMillis) / 1000);
  30.                 for (int i = 0; i < numToRemove; i++) {
  31.                     counter[i] = 0;
  32.                 }
  33.                 windowStartTime = currentTime - (elapsedTime % windowSizeInMillis);
  34.             }
  35.  
  36.             // 统计请求数
  37.             int currentWindowIndex = (int) (elapsedTime / 1000);
  38.             counter[currentWindowIndex]++;
  39.  
  40.             // 检查请求数是否超过限制
  41.             int totalRequests = 0;
  42.             for (int i = 0; i < counter.length; i++) {
  43.                 totalRequests += counter[i];
  44.             }
  45.             if (totalRequests > limit) {
  46.                 return false;  // 超过限制，拒绝请求
  47.             }
  48.         } finally {
  49.             lock.unlock();
  50.         }
  51.  
  52.         return true;  // 没有超过限制，允许请求通过
  53.     }
  54. }

 优点：

                滑动窗口可以缓解流量突刺：例如固定窗口（窗口大小为1小时，每个窗口最多处理10个请求）可以在1.59进行了十次请求，2.01进行了十次请求。但是在滑动窗口中，如果我们将滑动参数设置为1min，窗口大小设置为1小时，那么1.59时，滑动窗口的范围是1.59-2.59。此时如果设置最大请求数量为10，那么1.59执行的十次请求就已经填满了请求数量上限。2.01的就无法进行请求。通过这种思路避免了窗口边界流量突刺这种情况。

滴桶限流：

滴桶限流 就是  接收指定数量的请求，按照指定的速率处理。

  • 在滴桶限流算法中，系统以恒定的速率漏水，并以固定速率接收请求。
  • 算法步骤：
    • 当有请求到达时，先检查桶中是否有水滴；
    • 如果有水滴可用，则允许请求通过并漏水；
    • 如果没有水滴可用，则拒绝该请求。

 

用汉堡店举例：滴桶限流就是每个小时接待6个客户，然后每十分钟处理一个客户的请求 

 java代码实现:

  1. import java.util.concurrent.TimeUnit;
  2.  
  3. public class LeakyBucketRateLimiter {
  4.     private final int capacity;  // 桶的容量
  5.     private final double rate;   // 水滴漏出速率（水滴/秒）
  6.     private double water;        // 当前桶中的水滴数量
  7.     private long lastLeakTime;   // 上次漏水的时间戳
  8.  
  9.     public LeakyBucketRateLimiter(int capacity, double rate) {
  10.         this.capacity = capacity;
  11.         this.rate = rate;
  12.         this.water = 0;
  13.         this.lastLeakTime = System.nanoTime();
  14.     }
  15.  
  16.     public synchronized boolean allowRequest() {
  17.         leak();
  18.  
  19.         if (water >= 1) {
  20.             water -= 1;
  21.             return true;  // 水滴足够，允许请求通过
  22.         } else {
  23.             return false;  // 水滴不足，拒绝请求
  24.         }
  25.     }
  26.  
  27.     private void leak() {
  28.         long now = System.nanoTime();
  29.         double elapsedTime = (now - lastLeakTime) / 1e9;
  30.         double waterToLeak = elapsedTime * rate;
  31.  
  32.         if (waterToLeak > 0) {
  33.             water = Math.max(0, water - waterToLeak);
  34.             lastLeakTime = now;
  35.         }
  36.     }
  37. }

缺点：

        滴桶限流的并发性比较差，我们在代码中就可以看到，他需要对水滴（请求）逐个进行处理

令牌桶限流： 

        令牌桶限流就是创建一个桶，生成指定数量的令牌，只有拿到令牌的请求才可以进行处理。

  • 在令牌桶限流算法中，系统以恒定的速率生成令牌并放入令牌桶中，每个请求需要获取一个令牌才能通过。
  • 算法步骤：
    • 每隔一段时间生成一定数量的令牌放入桶中；
    • 当有请求到达时，从桶中获取一个令牌，如果没有令牌可用，则拒绝该请求。
  1. import java.util.concurrent.TimeUnit;
  2.  
  3. public class TokenBucketRateLimiter {
  4.     private final int capacity;  // 令牌桶容量
  5.     private final double rate;   // 令牌生成速率（令牌/秒）
  6.     private double tokens;       // 当前桶中的令牌数
  7.     private long lastRefillTime; // 上次填充令牌的时间戳
  8.  
  9.     public TokenBucketRateLimiter(int capacity, double rate) {
  10.         this.capacity = capacity;
  11.         this.rate = rate;
  12.         this.tokens = capacity;
  13.         this.lastRefillTime = System.nanoTime();
  14.     }
  15.  
  16.     public synchronized boolean allowRequest() {
  17.         refill();
  18.  
  19.         if (tokens >= 1) {
  20.             tokens -= 1;
  21.             return true;  // 令牌足够，允许请求通过
  22.         } else {
  23.             return false;  // 令牌不足，拒绝请求
  24.         }
  25.     }
  26.  
  27.     private void refill() {
  28.         long now = System.nanoTime();
  29.         double elapsedTime = (now - lastRefillTime) / 1e9;
  30.         double tokensToAdd = elapsedTime * rate;
  31.  
  32.         if (tokensToAdd > 0) {
  33.             tokens = Math.min(capacity, tokens + tokensToAdd);
  34.             lastRefillTime = now;
  35.         }
  36.     }
  37. }

用汉堡店举例：令牌桶限流就是 汉堡店 有一个 餐卷桶，并且会按时补充餐卷桶的餐卷数，只有拿到了餐卷才可以购买汉堡

优点：

        令牌桶限流的并发性能比较高，我们可以批量对拿到令牌的请求进行处理。

总结:

        在实际的开发中，其实我们并不用手动去实现这些限流算法，很多第三方库都已经为我们实现了限流算法，我们只需要直接使用就好了。而在实际开发中，常用的限流算法是 滴桶限流和令牌桶限流。因此我们要掌握好这两个限流算法。

如果我的内容对你有帮助，请点赞，评论，收藏。创作不易，大家的支持就是我坚持下去的动力！

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/weixin_40725706/article/detail/274624?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号