Approach: use fixed-size circular shards per key (N sub-windows) representing equal-duration buckets covering the sliding window. For each key, store an array of AtomicLong counters plus a lastSeen timestamp. On each request, advance current shard index by time, zero out expired shards atomically, sum counters to get window count, and conditionally increment current shard. Use ConcurrentHashMap for key -> shard state and background TTL eviction to remove inactive keys.java
import java.time.Instant;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicLong;
public class SlidingWindowRateLimiter {
private final long windowMillis;
private final int shards;
private final long shardMillis;
private final long limit;
private final ConcurrentHashMap<String, Bucket> map = new ConcurrentHashMap<>();
private final ScheduledExecutorService cleaner = Executors.newSingleThreadScheduledExecutor();
public SlidingWindowRateLimiter(long windowMillis, int shards, long limit, long ttlMillis) {
this.windowMillis = windowMillis;
this.shards = shards;
this.shardMillis = windowMillis / shards;
this.limit = limit;
cleaner.scheduleAtFixedRate(() -> {
long now = System.currentTimeMillis();
map.entrySet().removeIf(e -> now - e.getValue().lastSeen.get() > ttlMillis);
}, ttlMillis, ttlMillis, TimeUnit.MILLISECONDS);
}
public boolean tryAcquire(String key, long permits) {
long now = System.currentTimeMillis();
Bucket b = map.computeIfAbsent(key, k -> new Bucket(shards, now));
return b.tryAcquire(now, shardMillis, shards, limit, permits);
}
static class Bucket {
final AtomicLong[] counts;
final AtomicLong lastSeen = new AtomicLong();
final AtomicLong lastShardStart = new AtomicLong(); // aligned start millis of current shard
Bucket(int shards, long now) {
counts = new AtomicLong[shards];
for (int i = 0; i < shards; i++) counts[i] = new AtomicLong(0);
lastSeen.set(now);
lastShardStart.set(now);
}
boolean tryAcquire(long now, long shardMillis, int shards, long limit, long permits) {
lastSeen.set(now);
long shardIndex = (now / shardMillis) % shards;
long base = (now / shardMillis) * shardMillis;
long prevBase = lastShardStart.getAndSet(base);
if (base != prevBase) {
// zero intermediate shards
long steps = (base - prevBase) / shardMillis;
if (steps >= shards) { // all expired
for (AtomicLong c : counts) c.set(0);
} else {
for (int i = 1; i <= steps; i++) {
int idx = (int)(( (prevBase / shardMillis) + i) % shards);
counts[idx].set(0);
}
}
}
long total = 0;
for (AtomicLong c : counts) total += c.get();
if (total + permits > limit) return false;
counts[(int)shardIndex].addAndGet(permits);
return true;
}
}
public void shutdown() { cleaner.shutdownNow(); }
}
