It protects applications from abuse, DoS attacks, resource exhaustion, and traffic spikes, ensuring fair resource usage.
Rate limiting is commonly applied per user, API key, IP address, tenant, or service.
Requirements
A correct rate limiter should meet the following requirements:1. Allow requests up to a configured limit.
2. Reject requests that exceed the configured limit.
3. Automatically allow new requests after the configured time window expires.
4. Support concurrent requests safely.
5. Execute request validation with minimal latency.
The two most commonly used rate-limiting algorithms are Sliding Window and Token Bucket.
Sliding Window stores timestamps of recent requests and removes expired entries. It provides accurate rate limiting but consumes more memory.
Token Bucket generates tokens at a fixed rate. A request is allowed only if a token is available. It supports controlled bursts and is widely used in production systems.
Design
This implementation uses the Sliding Window algorithm. Each client has a queue containing timestamps of its recent requests.A ConcurrentHashMap stores the queue for every client.
Before accepting a request, expired timestamps are removed from the queue. If the queue size is below the configured limit, the current timestamp is added and the request is accepted.
Otherwise, the request is rejected.
ConcurrentHashMap
+-----------+-----------------------------+
| user-101 | [1000,1200,1600,1800] |
| user-205 | [2100,2200] |
| user-301 | [1500,1700,1900,2000,2300] |
+-----------+-----------------------------+
Java Implementation
The following implementation uses a sliding time window to accurately limit requests by tracking the timestamp of each request for every client.It stores request timestamps in a thread-safe queue and removes expired entries before deciding whether to allow or reject the current request.
import java.util.Queue;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;
public class SlidingWindowRateLimiter {
private final int maxRequests;
private final long windowSizeMillis;
private final ConcurrentHashMap<String, Queue<Long>> requests = new ConcurrentHashMap<>();
public SlidingWindowRateLimiter(int maxRequests, long windowSizeMillis) {
this.maxRequests = maxRequests;
this.windowSizeMillis = windowSizeMillis;
}
public boolean allowRequest(String clientId) {
long now = System.currentTimeMillis();
Queue<Long> queue = requests.computeIfAbsent(
clientId,
key -> new ConcurrentLinkedQueue<>()
);
synchronized (queue) {
while (!queue.isEmpty()
&& now - queue.peek() >= windowSizeMillis) {
queue.poll();
}
if (queue.size() >= maxRequests) {
return false;
}
queue.offer(now);
return true;
}
}
}
The synchronization ensures that removing expired timestamps, checking the request count, and inserting a new timestamp execute atomically.
Example
This example demonstrates how the sliding window rate limiter enforces the maximum request limit and automatically allows new requests after older ones expire from the time window.public class Main {
public static void main(String[] args) throws InterruptedException {
SlidingWindowRateLimiter limiter = new SlidingWindowRateLimiter(3, 5000);
String client = "user-101";
System.out.println(limiter.allowRequest(client)); // true
System.out.println(limiter.allowRequest(client)); // true
System.out.println(limiter.allowRequest(client)); // true
System.out.println(limiter.allowRequest(client)); // false
Thread.sleep(5000);
System.out.println(limiter.allowRequest(client)); // true
}
}
true
true
true
false
true
Complexity
Each request removes only expired timestamps. Therefore, the average request executes in O(1) time, while cleaning up many expired entries at once can take O(n) time.Time Complexity
Average request → O(1)
Worst case cleanup → O(n)
Space Complexity → O(number of stored timestamps)
For a single JVM instance, an in-memory implementation is usually sufficient.
In distributed systems, rate-limiting state should be shared across instances using Redis or another distributed cache. Atomic operations or Lua scripts prevent race conditions.
Old client entries should be periodically removed to prevent unbounded memory growth. Different APIs can have different request limits by maintaining separate configurations.
Clients are typically identified using user ID, API key, IP address, or OAuth token.
Token Bucket Implementation
The Token Bucket algorithm is commonly used in production because it supports controlled bursts while maintaining a steady average request rate.import java.util.concurrent.locks.ReentrantLock;
public class TokenBucketRateLimiter {
private final int capacity;
private final double refillRate;
private double tokens;
private long lastRefillTime;
private final ReentrantLock lock = new ReentrantLock();
public TokenBucketRateLimiter(int capacity, double refillRatePerSecond) {
this.capacity = capacity;
this.refillRate = refillRatePerSecond;
this.tokens = capacity;
this.lastRefillTime = System.nanoTime();
}
public boolean allowRequest() {
lock.lock();
try {
refill();
if (tokens >= 1) {
tokens--;
return true;
}
return false;
} finally {
lock.unlock();
}
}
private void refill() {
long now = System.nanoTime();
double elapsedSeconds = (now - lastRefillTime) / 1_000_000_000.0;
tokens = Math.min( capacity, tokens + elapsedSeconds * refillRate );
lastRefillTime = now;
}
}
