Java 實現(xiàn)滑動時間窗口限流算法的代碼

更新時間：2020年11月26日 11:10:44 投稿：mrr

這篇文章主要介紹了Java 實現(xiàn)滑動時間窗口限流算法的代碼,本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下

在網(wǎng)上搜滑動時間窗口限流算法，大多都太復雜了，本人實現(xiàn)了個簡單的，先上代碼：

package cn.dijia478.util;

import java.time.LocalTime;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 滑動時間窗口限流工具
 * 本限流工具只適用于單機版，如果想要做全局限流，可以按本程序的思想，用redis的List結構去實現(xiàn)
 *
 * @author dijia478
 * @date 2020-10-13 10:53
 */
public class SlideWindow {

  /** 隊列id和隊列的映射關系，隊列里面存儲的是每一次通過時候的時間戳，這樣可以使得程序里有多個限流隊列 */
  private volatile static Map<String, List<Long>> MAP = new ConcurrentHashMap<>();

  private SlideWindow() {}

  public static void main(String[] args) throws InterruptedException {
    while (true) {
      // 任意10秒內，只允許2次通過
      System.out.println(LocalTime.now().toString() + SlideWindow.isGo("ListId", 2, 10000L));
      // 睡眠0-10秒
      Thread.sleep(1000 * new Random().nextInt(10));
    }
  }

  /**
   * 滑動時間窗口限流算法
   * 在指定時間窗口，指定限制次數(shù)內，是否允許通過
   *
   * @param listId   隊列id
   * @param count   限制次數(shù)
   * @param timeWindow 時間窗口大小
   * @return 是否允許通過
   */
  public static synchronized boolean isGo(String listId, int count, long timeWindow) {
    // 獲取當前時間
    long nowTime = System.currentTimeMillis();
    // 根據(jù)隊列id，取出對應的限流隊列，若沒有則創(chuàng)建
    List<Long> list = MAP.computeIfAbsent(listId, k -> new LinkedList<>());
    // 如果隊列還沒滿，則允許通過，并添加當前時間戳到隊列開始位置
    if (list.size() < count) {
      list.add(0, nowTime);
      return true;
    }

    // 隊列已滿（達到限制次數(shù)），則獲取隊列中最早添加的時間戳
    Long farTime = list.get(count - 1);
    // 用當前時間戳 減去 最早添加的時間戳
    if (nowTime - farTime <= timeWindow) {
      // 若結果小于等于timeWindow，則說明在timeWindow內，通過的次數(shù)大于count
      // 不允許通過
      return false;
    } else {
      // 若結果大于timeWindow，則說明在timeWindow內，通過的次數(shù)小于等于count
      // 允許通過，并刪除最早添加的時間戳，將當前時間添加到隊列開始位置
      list.remove(count - 1);
      list.add(0, nowTime);
      return true;
    }
  }

}

運行可以看到，任意10秒內，通過的次數(shù)不超過2次。或者按照實現(xiàn)原理來說，任意通過2次內的時間差，都不超過10秒：