Java实现5种限流算法及7种限流方式

public class RateLimiterSimpleWindow {
    // 阈值
    private static Integer QPS = 2;
    // 时间窗口（毫秒）
    private static long TIME_windows = 1000;
    // 计数器
    private static AtomicInteger REQ_COUNT = new AtomicInteger();
    
    private static long START_TIME = System.currentTimeMillis();
 
    public synchronized static boolean tryAcquire() {
        if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
            REQ_COUNT.set(0);
            START_TIME = System.currentTimeMillis();
        }
        return REQ_COUNT.incrementAndGet() <= QPS;
    }
 
    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now = LocalTime.now();
            if (!tryAcquire()) {
                System.out.println(now + " 被限流");
            } else {
                System.out.println(now + " 做点什么");
            }
        }
    }
}

// 先休眠 400ms，可以更快的到达时间窗口。
Thread.sleep(400);
for (int i = 0; i < 10; i++) {
    Thread.sleep(250);
    if (!tryAcquire()) {
        System.out.println("被限流");
    } else {
        System.out.println("做点什么");
    }
}

package com.wdbyte.rate.limiter;
 
import java.time.LocalTime;
import java.util.concurrent.atomic.AtomicInteger;
 

public class RateLimiterSlidingWindow {
    
    private int qps = 2;
    
    private long windowSize = 1000;
    
    private Integer windowCount = 10;
    
    private WindowInfo[] windowArray = new WindowInfo[windowCount];
 
    public RateLimiterSlidingWindow(int qps) {
        this.qps = qps;
        long currentTimeMillis = System.currentTimeMillis();
        for (int i = 0; i < windowArray.length; i++) {
            windowArray[i] = new WindowInfo(currentTimeMillis, new AtomicInteger(0));
        }
    }
 
    
    public synchronized boolean tryAcquire() {
        long currentTimeMillis = System.currentTimeMillis();
        // 1. 计算当前时间窗口
        int currentIndex = (int)(currentTimeMillis % windowSize / (windowSize / windowCount));
        // 2.  更新当前窗口计数 & 重置过期窗口计数
        int sum = 0;
        for (int i = 0; i < windowArray.length; i++) {
            WindowInfo windowInfo = windowArray[i];
            if ((currentTimeMillis - windowInfo.getTime()) > windowSize) {
                windowInfo.getNumber().set(0);
                windowInfo.setTime(currentTimeMillis);
            }
            if (currentIndex == i && windowInfo.getNumber().get() < qps) {
                windowInfo.getNumber().incrementAndGet();
            }
            sum = sum + windowInfo.getNumber().get();
        }
        // 3. 当前 QPS 是否超过限制
        return sum <= qps;
    }
 
    private class WindowInfo {
        // 窗口开始时间
        private Long time;
        // 计数器
        private AtomicInteger number;
 
        public WindowInfo(long time, AtomicInteger number) {
            this.time = time;
            this.number = number;
        }
        // get...set...
    }
}

public static void main(String[] args) throws InterruptedException {
    int qps = 2, count = 20, sleep = 300, success = count * sleep / 1000 * qps;
    System.out.println(String.fORMat("当前QPS限制为:%d,当前测试次数:%d,间隔:%dms,预计成功次数:%d", qps, count, sleep, success));
    success = 0;
    RateLimiterSlidingWindow myRateLimiter = new RateLimiterSlidingWindow(qps);
    for (int i = 0; i < count; i++) {
        Thread.sleep(sleep);
        if (myRateLimiter.tryAcquire()) {
            success++;
            if (success % qps == 0) {
                System.out.println(LocalTime.now() + ": success, ");
            } else {
                System.out.print(LocalTime.now() + ": success, ");
            }
        } else {
            System.out.println(LocalTime.now() + ": fail");
        }
    }
    System.out.println();
    System.out.println("实际测试成功次数:" + success);
}

package com.wdbyte.rate.limiter;
 
import java.time.LocalTime;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;
 

public class RateLimiterSildingLog {
 
    
    private Integer qps = 2;
    
    private TreeMap<Long, Long> treeMap = new TreeMap<>();
 
    
    private long claerTime = 60 * 1000;
 
    public RateLimiterSildingLog(Integer qps) {
        this.qps = qps;
    }
 
    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 清理过期的数据老数据，最长 60 秒清理一次
        if (!treeMap.isEmpty() && (treeMap.firsTKEy() - now) > claerTime) {
            Set<Long> keySet = new HashSet<>(treeMap.subMap(0L, now - 1000).keySet());
            for (Long key : keySet) {
                treeMap.remove(key);
            }
        }
        // 计算当前请求次数
        int sum = 0;
        for (Long value : treeMap.subMap(now - 1000, now).values()) {
            sum += value;
        }
        // 超过QPS限制，直接返回 false
        if (sum + 1 > qps) {
            return false;
        }
        // 记录本次请求
        if (treeMap.containsKey(now)) {
            treeMap.compute(now, (k, v) -> v + 1);
        } else {
            treeMap.put(now, 1L);
        }
        return sum <= qps;
    }
 
    public static void main(String[] args) throws InterruptedException {
        RateLimiterSildingLog rateLimiterSildingLog = new RateLimiterSildingLog(3);
        for (int i = 0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now = LocalTime.now();
            if (rateLimiterSildingLog.tryAcquire()) {
                System.out.println(now + " 做点什么");
            } else {
                System.out.println(now + " 被限流");
            }
        }
    }
}

<exclusion>
   <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
   <version>31.0.1-jre</version>
</exclusion>

// qps 2
RateLimiter rateLimiter = RateLimiter.create(2);
for (int i = 0; i < 10; i++) {
    String time = LocalDateTime.now().format(DateTimeFormatter.ISO_LOCAL_TIME);
    System.out.println(time + ":" + rateLimiter.tryAcquire());
    Thread.sleep(250);
}

void resync(long nowMicros) { // 当前微秒时间
    // 当前时间是否大于下一个令牌生成时间
    if (nowMicros > this.nextFreeTicketMicros) { 
       // 可生成的令牌数 newPermits = （当前时间 - 下一个令牌生成时间）/ 令牌生成时间间隔。
       // 如果 QPS 为2，这里的 coolDownIntervalMicros 就是 500000.0 微秒(500ms)
        double newPermits = (double)(nowMicros - this.nextFreeTicketMicros) / this.coolDownIntervalMicros();
    // 更新令牌库存 storedPermits。
       this.storedPermits = Math.min(this.maxPermits, this.storedPermits + newPermits);
    // 更新下一个令牌生成时间 nextFreeTicketMicros
       this.nextFreeTicketMicros = nowMicros;
    }
}

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
</dependency>

spring:
  redis:
    database: 0
    passWord: 
    port: 6379
    host: 127.0.0.1
    lettuce:
      shutdown-timeout: 100ms
      pool:
        min-idle: 5
        max-idle: 10
        max-active: 8
        max-wait: 1ms

local count = redis.call("incr",KEYS[1])
if count == 1 then
  redis.call('expire',KEYS[1],ARGV[2])
end
if count > tonumber(ARGV[1]) then
  return 0
end
return 1

@SpringBootTest
class RedisLuaLimiterByIncr {
    private static String KEY_PREFIX = "limiter_";
    private static String QPS = "4";
    private static String EXPIRE_TIME = "1";
 
    @Autowired
    private StringRedisTemplate stringRedisTemplate;
 
    @Test
    public void redisLuaLimiterTests() throws InterruptedException, IOException {
        for (int i = 0; i < 15; i++) {
            Thread.sleep(200);
            System.out.println(LocalTime.now() + " " + acquire("user1"));
        }
    }
 
    
    public boolean acquire(String key) {
        // 当前秒数作为 key
        key = KEY_PREFIX + key + System.currentTimeMillis() / 1000;
        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
        redisScript.setResultType(Long.class);
        //lua文件存放在resources目录下
        redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter.lua")));
        return stringRedisTemplate.execute(redisScript, Arrays.asList(key), QPS, EXPIRE_TIME) == 1;
    }
}

--KEYS[1]: 限流 key
--ARGV[1]: 时间戳 - 时间窗口
--ARGV[2]: 当前时间戳（作为score）
--ARGV[3]: 阈值
--ARGV[4]: score 对应的唯一value
-- 1. 移除时间窗口之前的数据
redis.call('zremrangeByScore', KEYS[1], 0, ARGV[1])
-- 2. 统计当前元素数量
local res = redis.call('zcard', KEYS[1])
-- 3. 是否超过阈值
if (res == nil) or (res < tonumber(ARGV[3])) then
    redis.call('zadd', KEYS[1], ARGV[2], ARGV[4])
    return 1
else
    return 0
end

@SpringBootTest
class RedisLuaLimiterByZset {
 
    private String KEY_PREFIX = "limiter_";
    private String QPS = "4";
 
    @Autowired
    private StringRedisTemplate stringRedisTemplate;
 
    @Test
    public void redisLuaLimiterTests() throws InterruptedException, IOException {
        for (int i = 0; i < 15; i++) {
            Thread.sleep(200);
            System.out.println(LocalTime.now() + " " + acquire("user1"));
        }
    }
 
    
    public boolean acquire(String key) {
        long now = System.currentTimeMillis();
        key = KEY_PREFIX + key;
        String oldest = String.valueOf(now - 1_000);
        String score = String.valueOf(now);
        String scoreValue = score;
        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
        redisScript.setResultType(Long.class);
        //lua文件存放在resources目录下
        redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter2.lua")));
        return stringRedisTemplate.execute(redisScript, Arrays.asList(key), oldest, score, QPS, scoreValue) == 1;
    }
}