Rate Limiter Filter

You will build a reusable OncePerRequestFilter that limits requests per client, first in memory with a token bucket, then distributed with a Redis Lua script implementing a sliding window. "Design a rate limiter" is one of the most common design questions, and this project lets you answer it with working code: algorithm trade-offs, atomicity, the race in naive Redis code, and what to return to the client.

Project layout

src/main/java/com/example/ratelimit/
  RateLimiter.java            interface: Decision tryAcquire(String key)
  TokenBucketLimiter.java     in-memory
  RedisSlidingWindowLimiter.java
  RateLimitFilter.java
src/main/resources/scripts/sliding_window.lua

The contract

Keep the filter independent of the algorithm so you can swap and compare implementations.

public interface RateLimiter {
    Decision tryAcquire(String key);
    record Decision(boolean allowed, long remaining, long retryAfterSeconds) {}
}

Token bucket in memory

A bucket holds up to capacity tokens and refills at refillPerSecond. Compute the refill lazily from elapsed time instead of running a timer. It allows bursts up to capacity while enforcing the average rate.

public class TokenBucketLimiter implements RateLimiter {
    private final long capacity; private final double refillPerSec;
    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();

    private static final class Bucket { double tokens; long lastNanos; }

    public Decision tryAcquire(String key) {
        Bucket b = buckets.computeIfAbsent(key, k -> {
            Bucket nb = new Bucket(); nb.tokens = capacity; nb.lastNanos = System.nanoTime(); return nb; });
        synchronized (b) {
            long now = System.nanoTime();
            b.tokens = Math.min(capacity, b.tokens + (now - b.lastNanos) / 1e9 * refillPerSec);
            b.lastNanos = now;
            if (b.tokens >= 1) { b.tokens -= 1; return new Decision(true, (long) b.tokens, 0); }
            return new Decision(false, 0, (long) Math.ceil((1 - b.tokens) / refillPerSec));
        }
    }
}

Locking per bucket keeps contention to one key. This works on one JVM only, and the map grows without bound; evict idle keys with Caffeine in production.

Sliding window with a Redis Lua script

A fixed window allows up to twice the limit across a boundary (the full limit at the end of one window and again at the start of the next). A sliding window log stores each request timestamp in a sorted set and counts entries in the last window. Redis runs a Lua script atomically, so no other command interleaves between the count and the add; a client-side ZCARD then ZADD would let concurrent requests all pass.

local key    = KEYS[1]
local now    = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit  = tonumber(ARGV[3])
local member = ARGV[4]

redis.call('ZREMRANGEBYSCORE', key, 0, now - window)
local count = redis.call('ZCARD', key)
if count < limit then
  redis.call('ZADD', key, now, member)
  redis.call('PEXPIRE', key, window)
  return {1, limit - count - 1}
end
return {0, 0}

public Decision tryAcquire(String key) {
    long now = System.currentTimeMillis();
    List<Long> r = redis.execute(script, List.of("rl:" + key),
        String.valueOf(now), "60000", "100", now + "-" + UUID.randomUUID());
    return r.get(0) == 1 ? new Decision(true, r.get(1), 0) : new Decision(false, 0, 60);
}

Define script as new DefaultRedisScript<>(new ClassPathResource("scripts/sliding_window.lua"), List.class). The member must be unique, otherwise two requests in the same millisecond collapse into one entry. Memory is O(limit) per key; a sliding window counter (two fixed windows weighted by overlap) trades exactness for O(1) memory. Take the time from one source: if each app server passes its own clock, skew breaks the window, so for strictness call redis.call('TIME') inside the script.

The filter

Return 429 Too Many Requests with Retry-After and informative headers. Decide the failure mode up front: if Redis is down, fail open (availability) or closed (protection).

@Override
protected void doFilterInternal(HttpServletRequest req, HttpServletResponse res, FilterChain chain)
        throws ServletException, IOException {
    Decision d;
    try { d = limiter.tryAcquire(clientKey(req)); }
    catch (RedisConnectionFailureException e) { chain.doFilter(req, res); return; }   // fail open
    res.setHeader("X-RateLimit-Remaining", String.valueOf(d.remaining()));
    if (!d.allowed()) {
        res.setStatus(HttpStatus.TOO_MANY_REQUESTS.value());
        res.setHeader("Retry-After", String.valueOf(d.retryAfterSeconds()));
        return;
    }
    chain.doFilter(req, res);
}

Comparing with Bucket4j

Bucket4j implements the token bucket (not a sliding window) with a Redis backend via Lettuce or Redisson, using compare-and-swap Lua internally.

Bucket bucket = proxyManager.builder().build(key,
    () -> BucketConfiguration.builder()
        .addLimit(Bandwidth.builder().capacity(100).refillGreedy(100, Duration.ofMinutes(1)).build())
        .build());
ConsumptionProbe p = bucket.tryConsumeAndReturnRemaining(1);

Use it when a token bucket fits: it is tested, supports multiple bandwidths and several backends. Write your own when you need a sliding window or custom keys and want no dependency. Benchmark both and note the Redis round trips per request (one each).

Testing

@Test
void allowsLimitThenBlocks() {
    var limiter = new TokenBucketLimiter(5, 1.0);
    long allowed = IntStream.range(0, 10)
        .filter(i -> limiter.tryAcquire("c1").allowed()).count();
    assertThat(allowed).isEqualTo(5);
}

@Test
void concurrentCallersNeverExceedCapacity() throws Exception {
    var limiter = new TokenBucketLimiter(50, 0.001);
    var pool = Executors.newFixedThreadPool(16);
    var results = pool.invokeAll(Collections.nCopies(500, () -> limiter.tryAcquire("c").allowed()));
    long ok = 0; for (var f : results) if (f.get()) ok++;
    assertThat(ok).isEqualTo(50);
}

Interview angle

• Token bucket vs leaky bucket vs sliding window? Token bucket allows bursts and bounds the average rate; leaky bucket smooths output to a constant rate; sliding window log is exact but O(n) memory; sliding window counter approximates in O(1).
• Why a Lua script? Redis executes it atomically, so check-and-update has no race; separate commands would let concurrent requests overshoot the limit. A MULTI/EXEC cannot branch on intermediate results.
• Where to rate limit? At the edge (gateway or CDN) for coarse protection and in the app for per-user or per-endpoint rules. Key choice matters: IP is shared behind NAT, API key or user id is fairer.
• What if Redis is down? Fail open with a local in-memory fallback limit, or fail closed for sensitive endpoints like login. State the trade-off and alert.