Rate Limiting with Token Bucket · Account Lockout and Rate Limiting in Spring Security | Spring Security

The Algorithm

A token bucket holds up to capacity tokens. Each request takes one token; tokens are added back at a fixed rate. Short bursts are allowed (up to capacity), but the long-run rate is capped.

Algorithm	Idea	Notes
Fixed window	max N per calendar minute	simple; allows 2N at a window edge
Sliding window	max N in any 60-second period	accurate; more memory
Token bucket	refill tokens at a steady rate, allow bursts	used by Bucket4j, Spring Cloud Gateway, AWS API Gateway
Leaky bucket	process requests at a constant rate from a queue	smooths traffic; adds delay

Example

One bucket per user: capacity 5, one new token every 2 seconds. Times are simulated milliseconds:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        RateLimiter limiter = new RateLimiter(5, 2000);
        // a burst of 7 login attempts from asha, 100 ms apart
        for (long t = 0; t <= 600; t += 100) {
            System.out.printf("t=%4d ms  asha -> %s%n", t, limiter.allow("asha", t) ? "200 OK" : "429 Too Many Requests");
        }
        System.out.printf("t=%4d ms  ravi -> %s%n", 650L, limiter.allow("ravi", 650) ? "200 OK" : "429 Too Many Requests");
        // 4.1 seconds later, two tokens have been added back
        for (long t = 4100; t <= 4300; t += 100) {
            System.out.printf("t=%4d ms  asha -> %s%n", t, limiter.allow("asha", t) ? "200 OK" : "429 Too Many Requests");
        }
    }
}

class TokenBucket {
    private final long capacity;
    private final long refillEveryMillis;
    private long tokens;
    private long lastRefill;

    TokenBucket(long capacity, long refillEveryMillis, long now) {
        this.capacity = capacity;
        this.refillEveryMillis = refillEveryMillis;
        this.tokens = capacity;
        this.lastRefill = now;
    }

    synchronized boolean tryConsume(long now) {
        long newTokens = (now - lastRefill) / refillEveryMillis;
        if (newTokens > 0) {
            tokens = Math.min(capacity, tokens + newTokens);
            lastRefill += newTokens * refillEveryMillis;     // keep the remainder for next time
        }
        if (tokens == 0) return false;
        tokens--;
        return true;
    }
}

class RateLimiter {
    private final Map<String, TokenBucket> buckets = new HashMap<>();
    private final long capacity, refillEveryMillis;

    RateLimiter(long capacity, long refillEveryMillis) {
        this.capacity = capacity;
        this.refillEveryMillis = refillEveryMillis;
    }

    boolean allow(String key, long now) {
        return buckets.computeIfAbsent(key, k -> new TokenBucket(capacity, refillEveryMillis, now)).tryConsume(now);
    }
}

Output

t=   0 ms  asha -> 200 OK
t= 100 ms  asha -> 200 OK
t= 200 ms  asha -> 200 OK
t= 300 ms  asha -> 200 OK
t= 400 ms  asha -> 200 OK
t= 500 ms  asha -> 429 Too Many Requests
t= 600 ms  asha -> 429 Too Many Requests
t= 650 ms  ravi -> 200 OK
t=4100 ms  asha -> 200 OK
t=4200 ms  asha -> 200 OK
t=4300 ms  asha -> 429 Too Many Requests

Practice

Exercise: Change the limiter so that the "send OTP" endpoint allows at most 3 SMS per phone number per 10 minutes, with no burst beyond that.

Show answer

// capacity 3, and refill one token every 200 seconds (3 per 10 minutes)
RateLimiter otpLimiter = new RateLimiter(3, 200_000);

if (!otpLimiter.allow(phoneNumber, clock.millis())) {
    throw new ResponseStatusException(HttpStatus.TOO_MANY_REQUESTS,
            "Too many OTP requests. Please wait before trying again.");
}
smsService.sendOtp(phoneNumber);