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;

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

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

  private SlideWindow() {}

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

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

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

}