几种限流、控频策略对比

约定不等于承诺〃 2023-05-28 15:54 9阅读 0赞

这里主要讨论以下几种方式，有更好的建议，欢迎留言

*  基于数据库（Mysql为例）的统计进行限流
 *  基于redis自增长及过期策略的限流
 *  基于内存（linkedlist为例）的限流
 *  基于木桶算法的限流

本次介绍，主要关注实现策略、控制粒度及时间窗口问题，示例代码中可能存在编码不规范的情况，请忽略

### 1. 基于数据库的统计进行限流 ###

基于数据库的统计进行限流主要思想是，将每次的信息连同时间写入一条数据库记录，然后根据时间范围统计信息，决策是否需要限流。举例如下：

**场景：**  
       密码1分钟内输入错误次数超限，冻结账号。  
**要点：**  
      1. 登录失败时，将用户的登录名、登录时间写入数据库记录。  
      2.登录前根据登录名，查询近1分钟登录失败的次数。  
      3.判断登录次数是否大于设定的超限值，如果大于则进行冻结处理，如果未超过，正常执行登录判断（登录失败时执行第一要点）。  
**代码要点：**

select count(登录名) from 登录错误记录表 where 登录名='登录名' and 登录时间 > DATE_SUB(NOW(), INTERVAL 1 MINUTE)

**分析：**  
      此方案的粒度控制在于代码逻辑的堆砌和数据库的设计，较为灵活，时间窗口为最近一分钟（假定），属于滑动时间窗口；由于时基于数据库的，分布式部署的情况下也能有效，不足之处在于会增加数据库的压力。

### 2. 基于redis自增长及过期策略的限流 ###

基于redis自增长及过期策略主要思想是：在redis中维护一个key，并设置过期时间，每次控制前读取该key，如果该key对应的值大于了限制值，则被限制，如果不大于，则通过redis的incr对key进行自增长处理，如果为空，则重新维护key，并设置过期时间。如此往复达到限流目的。  
**场景：**  
      对接口进行会话级别的访问控制  
**要点**  
      1. 读取key，根据key对应值value的不同情况进行处理：  
      a. value不存在，设置set key 及过期时间  
      b. value大于限定值，限流  
      c. valuex不大于限定值，value自增长1  
**代码要点：**  
      涉及到的redis命令如下：

## 设置key的值5秒过期
    set kkk 1 EX 5
    ### 获取key的值
    get kkk
    ### 自增长
    incr kkk
    ### 手动设置过期时间
    expire kkk 5

代码示例

private boolean accessCheck(HttpSession session) { 
            String key = "ACCESS"+session.getId();
            long current = 1;
            // key不存在，进行设置
            if( valueOperations.get(key) == null){ 
                //一步到位 
                //valueOperations.set(key,1,5,TimeUnit.SECONDS);
                // 也可以分两步设置
                valueOperations.increment(key);
                valueOperations.getOperations().expire(key,5,TimeUnit.SECONDS);
            }else { 
            	// key已经存在了，自增+1
                valueOperations.increment(key);
                current = Long.parseLong(valueOperations.get(key));
            }
    
            if(current > 20){ 
                throw new RuntimeException("访问次数过于多");
            }
    
            return true;
        }

**分析：**  
      基于redis同样可以适用分布式环境，时间窗口固定，因redis特性，可适应较大流量冲击，控制粒度在于设计。

### 3. 基于内存（linkedlist为例）的限流 ###

基于内存的限流主要策略是在内存中维护一个时间窗口数据，基于对数据的统计进行限流。  
**场景：**  
      对接口调用频度进行控制  
**要点**  
      1.维护一个以时间正序的列表（不是正序需要扫描全部数据）  
      2.去除时间窗口之外数据  
      3.末尾处加入最新时间  
**代码要点：**  
      以linkedlist为例

private boolean accessCheckByLinkedList()  { 
            synchronized(accessList) { 
                Date data = null;
                Date now = new Date();
                if(accessList.size() > 0){ 
                    data = accessList.getFirst();
                    while (data != null && now.getTime() - data.getTime() > 5000) { 
                        accessList.removeFirst();
                        if(accessList.size() > 0){ 
                            data = accessList.getFirst();
                        }else { 
                            data = null;
                        }
                    }
                    if (accessList.size() > 5) { 
                        throw new RuntimeException( "访问次数过于多");
                    }
                }
                accessList.add(new Date());
            }
            return true;
        }

**分析：**  
      基于内存的限流，其粒度控制依赖于设计的是否高明，因为实在内存中处理的，需要考虑线程间同步（采用同步的存储如ConcurrentHashMap，可能不需要处理同步问题，但是要注意排序问题）及并发问题。控制粒度为应用级别，能从应用层面控制当前访问的压力，避免负载均衡策略失效或异常情况下带来的大流量冲击。

### 4. 基于木桶算法的限流 ###

基于木桶算法的限流策略主要是维护一个固定大小的“池”，根据场景消耗“池”的存量，并不断的向内添加，但永远维护“池”中存量不会超过最大值  
**场景：**  
      应用级别接口请求频度控制  
**要点**  
      1.增加“池”中存量，存量达到最大值，暂停增加  
      2.使用“池”中存量，存量小于0限流  
      3.保证使用“池”不会溢出，也不会透支  
**代码要点：**  
      基于该策略，以下完整代码描述了整个过程，其中的各频度控制仅为实验效果而定。

public class BucketAlgorithmTest { 
        public static void main(String[] args) throws InterruptedException { 
            // 定时流入
            new Thread(()-> { 
                while (true){ 
                    Bucket.add();
                    try { 
                        Thread.sleep(50);
                    } catch (InterruptedException e) { 
                        e.printStackTrace();
                    }
                }
            }).start();
            Thread.sleep(200);// 如果直接默认初始值为满的，此处可省略
            // 定时流出，模拟控制域
            new Thread(()->{ 
                int errorcout = 0;
                while (errorcout < 10) { 
                    try { 
                        Bucket.get();
                        Thread.sleep(40);
                    } catch (Exception e) { 
                        errorcout ++;
                        e.printStackTrace();
                        try { 
                            Thread.sleep(100);
                        }catch (Exception ee){ 
    
                        }
                    }
                }
            }).start();
        }
    
    
    }
    class Bucket{ 
    	/** * 当前存量 */
        private static Integer currentSize = 0;
        
    	/** * 容量 */
        private final static int totalSize = 20;
        /** * 流入 */
        public static void add(){ 
            synchronized (currentSize) { 
                if(currentSize < totalSize) { 
                    currentSize++;
                    System.out.println("[添加++++]可用" + Bucket.getCurrentSize());
                }
            }
        }
        /** * 流出 */
        public static void get(){ 
            synchronized (currentSize) { 
                if(currentSize > 0) { 
                    currentSize--;
                    System.out.println("[使用---]可用" + Bucket.getCurrentSize());
                }else { 
                    throw new RuntimeException("当前没有剩余连接可供使用");
                }
            }
        }
        public static Integer getCurrentSize(){ 
            return currentSize;
        }
    }

为方便理解，这里给补充一张运行结果方便理解  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hc3RlcjMzNg_size_16_color_FFFFFF_t_70]

**分析：**  
      木桶原理算法控制粒度可调性较大，依赖对算法原理的理解程度，在峰值大流量冲击下，可能造成恢复时间增长（相对而言），该策略也类似是滑动“时间”窗口（其实滑动的是流量，这里简单理解为滑动窗口吧）。该策略的数据既可以在内存中，也可以在数据库中，也可以在redis等缓存中，使用场景也可以根据需要灵活设定，可应用级，也可以在负载层面作为负载策略的扩充。

### 简单总结对比一下 ###

<table> 
 <thead> 
  <tr> 
   <th>方案</th> 
   <th>时间窗口</th> 
   <th>基于</th> 
   <th>分布式环境</th> 
   <th>应用范围</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>基于数据库</td> 
   <td>滑动</td> 
   <td>数据库</td> 
   <td>适用</td> 
   <td>登录控制</td> 
  </tr> 
  <tr> 
   <td>基于Redis</td> 
   <td>固定</td> 
   <td>Redis</td> 
   <td>适用</td> 
   <td>接口访问控制</td> 
  </tr> 
  <tr> 
   <td>内存</td> 
   <td>滑动</td> 
   <td>内存</td> 
   <td>不适用</td> 
   <td>应用级别访问控制</td> 
  </tr> 
  <tr> 
   <td>木桶算法</td> 
   <td>滑动</td> 
   <td>内存/Redis/数据库</td> 
   <td>适用</td> 
   <td>根据应用位置而定</td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hc3RlcjMzNg_size_16_color_FFFFFF_t_70]: /images/20230528/9ed54217c8634e8ab71566ba8016059c.png