Back to Scaling, Load Balancing & Performance
Q5Question 5 of 21

How does the token bucket algorithm work for rate limiting

Answer: The token bucket algorithm limits API request rate by maintaining a bucket that holds a fixed number of tokens, refills tokens at a constant rate, and rejects requests when the bucket is empty.

Key Concepts
  • The token bucket algorithm controls request rate by maintaining a bucket of tokens that refills at a fixed rate and drains one token per request.
  • Each request tries to consume a token; if the bucket is empty, the request is rejected with HTTP 429 Too Many Requests.
  • The bucket capacity determines the maximum burst size, allowing short bursts of traffic above the average rate.
  • The refill rate determines the sustained throughput, measured in tokens per second.
  • Injecting java.time.Clock into the TokenBucket class makes tests deterministic by letting you control time progression.
  • Token bucket allows bursts (up to capacity) while fixed window and sliding window enforce stricter per-interval limits.
  • In a distributed system, store token state in Redis instead of local memory so rate limits apply across all service instances.

Definition

The token bucket algorithm limits API request rate by maintaining a bucket that holds a fixed number of tokens, refills tokens at a constant rate, and rejects requests when the bucket is empty.
  • Token bucket is a rate-limiting algorithm where each API request consumes one token from a bucket, and the bucket refills tokens at a fixed rate (for example, 10 tokens per second).
  • Capacity is the maximum number of tokens the bucket can hold, which determines the maximum burst size.
  • Refill rate is how many tokens are added to the bucket per second, which determines the sustained request throughput.
  • Burst is a short spike of requests that exceeds the refill rate but is allowed because the bucket has accumulated unused tokens.
  • HTTP 429 Too Many Requests is the standard response code returned when the rate limit is exceeded.

Think of the ATM withdrawal limit at National Bank of India. The ATM allows Rajesh to withdraw up to 50,000 rupees per day (capacity). Every day at midnight, the limit resets (refill). If Rajesh withdraws 20,000 in the morning and 20,000 in the afternoon, he has 10,000 left for the evening. If he tries to withdraw 15,000, the ATM declines because he only has 10,000 of daily limit remaining. The daily limit is the bucket capacity, the midnight reset is the refill, and the declined withdrawal is the HTTP 429 response.

Understanding the Concepts

What is the token bucket algorithm?

The token bucket algorithm is one of the most widely used rate-limiting algorithms. It works by maintaining a virtual bucket of tokens:

  1. The bucket starts full (at its maximum capacity).
  2. Tokens are added to the bucket at a constant rate (the refill rate).
  3. Each incoming request tries to take one token from the bucket.
  4. If a token is available, the request proceeds.
  5. If the bucket is empty, the request is rejected.
  6. The bucket never holds more tokens than its capacity.

The key advantage of token bucket over other algorithms is that it allows controlled bursts. If the API has been idle for a while, the bucket fills up. A sudden burst of requests can be served from the accumulated tokens, as long as the burst does not exceed the bucket capacity.

TEXT
Example: capacity=5, refill rate=1 token/second

Time   Tokens  Request   Result
0.0s   5       -         -
0.1s   5       Request 1  Allowed (tokens: 4)
0.2s   4       Request 2  Allowed (tokens: 3)
0.3s   3       Request 3  Allowed (tokens: 2)
0.4s   2       Request 4  Allowed (tokens: 1)
0.5s   1       Request 5  Allowed (tokens: 0)
0.6s   0       Request 6  REJECTED (429 Too Many Requests)
0.7s   0       Request 7  REJECTED
1.0s   1       -         (1 token refilled after 1 second)
1.1s   1       Request 8  Allowed (tokens: 0)

Why do we need rate limiting for banking APIs?

Banking APIs handle sensitive operations: fund transfers, balance inquiries, loan applications. Without rate limiting, the system is vulnerable to:

  • Denial of service. An attacker sends 100,000 requests per second to the /api/transfers endpoint, overwhelming the database and blocking legitimate customers.
  • Brute-force attacks. An attacker tries thousands of PIN combinations on the /api/auth/verify-pin endpoint.
  • Runaway clients. A partner system has a bug that sends duplicate transfer requests in a tight loop, draining customer accounts.
  • Cost control. Each API call has a cost (database queries, third-party calls). Unbounded traffic creates unbounded cost.

Rate limiting protects both the system and the customers. At National Bank of India, the /api/transfers endpoint might be limited to 10 requests per second per customer, and the /api/auth/verify-pin endpoint to 3 requests per minute.

TEXT
Rate limiting policy for National Bank of India API:

Endpoint                   Limit           Burst
/api/transfers             10 req/sec      20
/api/accounts/balance      50 req/sec      100
/api/auth/verify-pin       3 req/min       3
/api/statements            5 req/sec       10
/api/beneficiaries         20 req/sec      40

How does the token bucket algorithm work internally?

The token bucket does not use a background thread to refill tokens. Instead, it calculates how many tokens should have been added since the last request. This is called lazy refill.

When a request arrives:

  1. Calculate elapsed time since the last request.
  2. Calculate how many tokens to add: elapsed * refillRate.
  3. Update the token count: min(currentTokens + newTokens, capacity).
  4. Try to consume one token. If tokens > 0, decrement and allow. Otherwise, reject.

This approach is efficient because it requires no timers, no threads, and no scheduled tasks.

JAVA
package com.bank.ratelimit;

import java.time.Clock;
import java.time.Instant;

public class TokenBucket {

    private final int capacity;
    private final double refillRate; // tokens per second
    private final Clock clock;

    private double tokens;
    private Instant lastRefillTime;

    public TokenBucket(int capacity, double refillRate, Clock clock) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.clock = clock;
        this.tokens = capacity; // start full
        this.lastRefillTime = clock.instant();
    }

    public synchronized boolean tryConsume() {
        refill();
        if (tokens >= 1.0) {
            tokens -= 1.0;
            return true;
        }
        return false;
    }

    public synchronized double availableTokens() {
        refill();
        return tokens;
    }

    private void refill() {
        Instant now = clock.instant();
        double elapsedSeconds = (now.toEpochMilli()
            - lastRefillTime.toEpochMilli()) / 1000.0;
        double newTokens = elapsedSeconds * refillRate;

        if (newTokens > 0) {
            tokens = Math.min(capacity, tokens + newTokens);
            lastRefillTime = now;
        }
    }

    public int getCapacity() {
        return capacity;
    }
}
JAVA
package com.bank.ratelimit;

import java.time.Clock;

public class TokenBucketDemo {

    public static void main(String[] args) throws InterruptedException {
        // 5 tokens capacity, refill 2 tokens per second
        TokenBucket bucket = new TokenBucket(5, 2.0, Clock.systemUTC());

        System.out.println("Sending 8 requests in quick succession:");
        for (int i = 1; i <= 8; i++) {
            boolean allowed = bucket.tryConsume();
            System.out.printf("  Request %d: %s (tokens remaining: %.1f)%n",
                i, allowed ? "ALLOWED" : "REJECTED", bucket.availableTokens());
        }

        System.out.println("\nWaiting 2 seconds for refill...");
        Thread.sleep(2000);

        System.out.println("Sending 3 more requests:");
        for (int i = 9; i <= 11; i++) {
            boolean allowed = bucket.tryConsume();
            System.out.printf("  Request %d: %s (tokens remaining: %.1f)%n",
                i, allowed ? "ALLOWED" : "REJECTED", bucket.availableTokens());
        }
    }
}
TEXT
Sending 8 requests in quick succession:
  Request 1: ALLOWED (tokens remaining: 4.0)
  Request 2: ALLOWED (tokens remaining: 3.0)
  Request 3: ALLOWED (tokens remaining: 2.0)
  Request 4: ALLOWED (tokens remaining: 1.0)
  Request 5: ALLOWED (tokens remaining: 0.0)
  Request 6: REJECTED (tokens remaining: 0.0)
  Request 7: REJECTED (tokens remaining: 0.0)
  Request 8: REJECTED (tokens remaining: 0.0)

Waiting 2 seconds for refill...
Sending 3 more requests:
  Request 9: ALLOWED (tokens remaining: 3.0)
  Request 10: ALLOWED (tokens remaining: 2.0)
  Request 11: ALLOWED (tokens remaining: 1.0)

How do you use the token bucket in a Spring Boot filter?

A servlet filter checks the token bucket on every incoming request. If the bucket is empty, the filter returns HTTP 429 without calling the controller. The filter also adds rate-limit headers so the client knows how many requests it has left.

JAVA
package com.bank.ratelimit;

import jakarta.servlet.FilterChain;
import jakarta.servlet.ServletException;
import jakarta.servlet.http.HttpServletRequest;
import jakarta.servlet.http.HttpServletResponse;
import org.springframework.http.HttpStatus;
import org.springframework.stereotype.Component;
import org.springframework.web.filter.OncePerRequestFilter;
import java.io.IOException;
import java.time.Clock;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

@Component
public class RateLimitFilter extends OncePerRequestFilter {

    private static final int CAPACITY = 10;
    private static final double REFILL_RATE = 10.0; // 10 tokens per second
    private final Clock clock;

    // One bucket per client IP
    private final ConcurrentMap<String, TokenBucket> buckets =
        new ConcurrentHashMap<>();

    public RateLimitFilter(Clock clock) {
        this.clock = clock;
    }

    @Override
    protected void doFilterInternal(
            HttpServletRequest request,
            HttpServletResponse response,
            FilterChain filterChain) throws ServletException, IOException {

        String clientIp = request.getRemoteAddr();
        TokenBucket bucket = buckets.computeIfAbsent(clientIp,
            ip -> new TokenBucket(CAPACITY, REFILL_RATE, clock));

        // Add rate-limit headers
        response.setHeader("X-RateLimit-Limit",
            String.valueOf(bucket.getCapacity()));
        response.setHeader("X-RateLimit-Remaining",
            String.valueOf((int) bucket.availableTokens()));

        if (bucket.tryConsume()) {
            filterChain.doFilter(request, response);
        } else {
            response.setStatus(HttpStatus.TOO_MANY_REQUESTS.value());
            response.setContentType("application/json");
            response.getWriter().write(
                "{\"error\":\"Rate limit exceeded. Try again later.\"}");
        }
    }
}
JAVA
package com.bank.config;

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;
import java.time.Clock;

@Configuration
public class ClockConfig {

    @Bean
    public Clock clock() {
        return Clock.systemUTC();
    }
}
TEXT
Client sends 12 rapid requests to POST /api/transfers:

Request 1:  200 OK          X-RateLimit-Remaining: 9
Request 2:  200 OK          X-RateLimit-Remaining: 8
...
Request 10: 200 OK          X-RateLimit-Remaining: 0
Request 11: 429 Too Many    {"error":"Rate limit exceeded. Try again later."}
Request 12: 429 Too Many    {"error":"Rate limit exceeded. Try again later."}

After 1 second (10 tokens refilled):
Request 13: 200 OK          X-RateLimit-Remaining: 9

How do you inject Clock for deterministic testing?

Using java.time.Clock instead of System.currentTimeMillis() or Instant.now() allows tests to control time progression. You create a fixed clock, advance it manually, and verify the exact number of tokens.

JAVA
package com.bank.ratelimit;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;
import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.time.ZoneOffset;

import static org.assertj.core.api.Assertions.assertThat;

class TokenBucketTest {

    private Clock fixedClock(Instant instant) {
        return Clock.fixed(instant, ZoneOffset.UTC);
    }

    @Test
    @DisplayName("New bucket starts with full capacity")
    void shouldStartFull() {
        Clock clock = fixedClock(Instant.parse("2025-01-15T10:00:00Z"));
        TokenBucket bucket = new TokenBucket(5, 1.0, clock);

        assertThat(bucket.availableTokens()).isEqualTo(5.0);
    }

    @Test
    @DisplayName("Consuming reduces available tokens")
    void shouldReduceTokensOnConsume() {
        Clock clock = fixedClock(Instant.parse("2025-01-15T10:00:00Z"));
        TokenBucket bucket = new TokenBucket(5, 1.0, clock);

        assertThat(bucket.tryConsume()).isTrue();
        assertThat(bucket.availableTokens()).isEqualTo(4.0);

        assertThat(bucket.tryConsume()).isTrue();
        assertThat(bucket.availableTokens()).isEqualTo(3.0);
    }

    @Test
    @DisplayName("Empty bucket rejects requests")
    void shouldRejectWhenEmpty() {
        Clock clock = fixedClock(Instant.parse("2025-01-15T10:00:00Z"));
        TokenBucket bucket = new TokenBucket(3, 1.0, clock);

        assertThat(bucket.tryConsume()).isTrue();  // 2 left
        assertThat(bucket.tryConsume()).isTrue();  // 1 left
        assertThat(bucket.tryConsume()).isTrue();  // 0 left
        assertThat(bucket.tryConsume()).isFalse(); // rejected
    }

    @Test
    @DisplayName("Bucket refills after time passes")
    void shouldRefillAfterTimePasses() {
        Instant start = Instant.parse("2025-01-15T10:00:00Z");
        // Use a mutable clock wrapper for time advancement
        MutableClock clock = new MutableClock(start);
        TokenBucket bucket = new TokenBucket(5, 2.0, clock); // 2 tokens/sec

        // Consume all 5 tokens
        for (int i = 0; i < 5; i++) {
            assertThat(bucket.tryConsume()).isTrue();
        }
        assertThat(bucket.tryConsume()).isFalse(); // empty

        // Advance clock by 2 seconds: 2 * 2.0 = 4 tokens refilled
        clock.advance(Duration.ofSeconds(2));
        assertThat(bucket.availableTokens()).isEqualTo(4.0);
        assertThat(bucket.tryConsume()).isTrue();
    }

    @Test
    @DisplayName("Refill does not exceed capacity")
    void shouldNotExceedCapacity() {
        Instant start = Instant.parse("2025-01-15T10:00:00Z");
        MutableClock clock = new MutableClock(start);
        TokenBucket bucket = new TokenBucket(5, 10.0, clock); // 10 tokens/sec

        // Consume 1 token
        bucket.tryConsume();
        assertThat(bucket.availableTokens()).isEqualTo(4.0);

        // Wait 10 seconds: 10 * 10 = 100 tokens added, but capped at 5
        clock.advance(Duration.ofSeconds(10));
        assertThat(bucket.availableTokens()).isEqualTo(5.0);
    }
}
JAVA
package com.bank.ratelimit;

import java.time.Clock;
import java.time.Duration;
import java.time.Instant;
import java.time.ZoneId;
import java.time.ZoneOffset;

/**
 * A mutable clock for testing. Starts at a fixed instant
 * and advances when advance() is called.
 */
public class MutableClock extends Clock {

    private Instant current;

    public MutableClock(Instant start) {
        this.current = start;
    }

    public void advance(Duration duration) {
        this.current = this.current.plus(duration);
    }

    @Override
    public Instant instant() {
        return current;
    }

    @Override
    public ZoneId getZone() {
        return ZoneOffset.UTC;
    }

    @Override
    public Clock withZone(ZoneId zone) {
        return this;
    }
}
TEXT
Test output:
  shouldStartFull() PASSED
  shouldReduceTokensOnConsume() PASSED
  shouldRejectWhenEmpty() PASSED
  shouldRefillAfterTimePasses() PASSED
  shouldNotExceedCapacity() PASSED

All tests deterministic. No Thread.sleep(), no flaky timing.

How is token bucket different from fixed window and sliding window?

FeatureToken BucketFixed WindowSliding Window Log
How it worksBucket of tokens, refill at constant rateCounter resets at fixed intervals (every minute)Timestamp log of each request, count in rolling window
Burst handlingAllows bursts up to bucket capacityAllows 2x burst at window boundaryNo burst, strict per-window limit
Memory per client2 values (token count, last refill time)1 counter + window start time1 timestamp per request in window
AccuracySmooth, average rate enforcementImprecise at window boundariesMost precise, exact rolling count
Example10 tokens, 2/sec refillMax 120 requests per minuteMax 120 requests in any 60-second window
Best forAPIs needing burst toleranceSimple counters, low precisionStrict rate enforcement

Fixed window boundary problem:

DIAGRAM
Fixed window: 10 requests per minute

  Minute 1 (10:00 - 10:01)      Minute 2 (10:01 - 10:02)
  ┌──────────────────────┐       ┌──────────────────────┐
  │ .........X           │       │ XXXXXXXXXX           │
  │ 0 req at 10:00:00    │       │ 10 req at 10:01:00   │
  │ ...                  │       │                      │
  │ 10 req at 10:00:59   │       │                      │
  └──────────────────────┘       └──────────────────────┘

At 10:00:59: 10 requests (allowed, window limit is 10)
At 10:01:00: Window resets, counter = 0
At 10:01:01: 10 more requests (allowed, new window)

Result: 20 requests in 2 seconds! The fixed window
boundary allows a burst of 2x the intended rate.

Token bucket with capacity=10, rate=10/min:
  Cannot exceed 10 burst at any moment.
  Refills gradually, not all at once.

Sliding window log:

TEXT
Sliding window: 10 requests per 60 seconds

Incoming request at 10:01:30:
  1. Look at all requests from 10:00:30 to 10:01:30
  2. Count: 8 requests in that window
  3. 8 < 10: ALLOWED
  4. Store timestamp 10:01:30 in the log

Incoming request at 10:01:31:
  1. Look at all requests from 10:00:31 to 10:01:31
  2. Count: 9 requests in that window
  3. 9 < 10: ALLOWED

Memory: stores up to 10 timestamps per client.
More precise than token bucket, but more memory per client.

How do you handle burst traffic?

The token bucket naturally handles bursts because accumulated tokens can be spent in quick succession. You control burst behavior by adjusting the capacity (burst size) independently of the refill rate (sustained throughput).

JAVA
package com.bank.ratelimit;

import java.time.Clock;

public class BurstDemo {

    public static void main(String[] args) throws InterruptedException {
        // Sustained rate: 5 requests/second
        // Burst capacity: 20 requests
        TokenBucket bucket = new TokenBucket(20, 5.0, Clock.systemUTC());

        System.out.println("Scenario: API idle for a while, then burst of traffic");
        System.out.println("Capacity: 20, Refill: 5/sec");
        System.out.println();

        // Simulate burst of 25 rapid requests
        System.out.println("Burst of 25 requests:");
        int allowed = 0;
        int rejected = 0;
        for (int i = 1; i <= 25; i++) {
            if (bucket.tryConsume()) {
                allowed++;
            } else {
                rejected++;
            }
        }
        System.out.println("  Allowed: " + allowed + ", Rejected: " + rejected);

        // Wait 2 seconds: 2 * 5 = 10 tokens refilled
        System.out.println("\nWaiting 2 seconds...");
        Thread.sleep(2000);

        System.out.println("After 2 seconds (10 tokens refilled):");
        allowed = 0;
        rejected = 0;
        for (int i = 1; i <= 15; i++) {
            if (bucket.tryConsume()) {
                allowed++;
            } else {
                rejected++;
            }
        }
        System.out.println("  Allowed: " + allowed + ", Rejected: " + rejected);
    }
}
TEXT
Scenario: API idle for a while, then burst of traffic
Capacity: 20, Refill: 5/sec

Burst of 25 requests:
  Allowed: 20, Rejected: 5

Waiting 2 seconds...
After 2 seconds (10 tokens refilled):
  Allowed: 10, Rejected: 5
TEXT
Tuning guidelines for a banking API:

Endpoint: /api/transfers
  Sustained rate: 10 req/sec (normal customer usage)
  Burst capacity: 20 (handle batch operations)
  Refill: 10 tokens/sec

Endpoint: /api/auth/verify-pin
  Sustained rate: 0.05 req/sec (3 per minute)
  Burst capacity: 3 (no burst tolerance for security)
  Refill: 0.05 tokens/sec

Rule of thumb:
  capacity = 2x sustained rate for burst-tolerant endpoints
  capacity = sustained rate for security-sensitive endpoints

What are common mistakes?

Mistake 1: Using Thread.sleep in rate limit tests

WRONG: Tests that depend on Thread.sleep are slow and flaky. A 100ms sleep might take 150ms on a loaded CI server, causing intermittent failures.

JAVA
// WRONG: Flaky test with Thread.sleep
@Test
void testRefill() throws InterruptedException {
    TokenBucket bucket = new TokenBucket(5, 2.0, Clock.systemUTC());

    for (int i = 0; i < 5; i++) bucket.tryConsume();
    assertThat(bucket.tryConsume()).isFalse();

    Thread.sleep(1000); // flaky: might be 950ms or 1100ms
    assertThat(bucket.availableTokens()).isEqualTo(2.0); // fails randomly
}

CORRECT: Inject a Clock and advance it deterministically.

JAVA
// CORRECT: Deterministic test with MutableClock
@Test
void testRefill() {
    MutableClock clock = new MutableClock(
        Instant.parse("2025-01-15T10:00:00Z"));
    TokenBucket bucket = new TokenBucket(5, 2.0, clock);

    for (int i = 0; i < 5; i++) bucket.tryConsume();
    assertThat(bucket.tryConsume()).isFalse();

    clock.advance(Duration.ofSeconds(1)); // exactly 1 second
    assertThat(bucket.availableTokens()).isEqualTo(2.0); // always passes
}

Mistake 2: Using local in-memory rate limiting in a distributed system

WRONG: Each service instance has its own TokenBucket. With 5 instances, the effective rate limit is 5x the intended limit.

TEXT
WRONG: Local rate limiting with 5 pods

Pod 1: TokenBucket(10, 10/sec)  -> allows 10 req/sec
Pod 2: TokenBucket(10, 10/sec)  -> allows 10 req/sec
Pod 3: TokenBucket(10, 10/sec)  -> allows 10 req/sec
Pod 4: TokenBucket(10, 10/sec)  -> allows 10 req/sec
Pod 5: TokenBucket(10, 10/sec)  -> allows 10 req/sec

Total: 50 req/sec! You intended 10 req/sec per client.

CORRECT: Use Redis for shared state across instances.

JAVA
package com.bank.ratelimit;

import org.springframework.data.redis.core.StringRedisTemplate;
import org.springframework.data.redis.core.script.DefaultRedisScript;
import java.util.List;

public class RedisTokenBucket {

    private final StringRedisTemplate redis;
    private final DefaultRedisScript<Long> script;
    private final int capacity;
    private final double refillRate;

    public RedisTokenBucket(
            StringRedisTemplate redis,
            int capacity,
            double refillRate) {
        this.redis = redis;
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.script = new DefaultRedisScript<>(LUA_SCRIPT, Long.class);
    }

    public boolean tryConsume(String clientId) {
        String key = "rate_limit:" + clientId;
        Long result = redis.execute(
            script,
            List.of(key),
            String.valueOf(capacity),
            String.valueOf(refillRate),
            String.valueOf(System.currentTimeMillis())
        );
        return result != null && result == 1L;
    }

    // Lua script runs atomically in Redis
    private static final String LUA_SCRIPT = """
        local key = KEYS[1]
        local capacity = tonumber(ARGV[1])
        local refill_rate = tonumber(ARGV[2])
        local now = tonumber(ARGV[3])

        local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
        local tokens = tonumber(bucket[1]) or capacity
        local last_refill = tonumber(bucket[2]) or now

        local elapsed = (now - last_refill) / 1000.0
        tokens = math.min(capacity, tokens + elapsed * refill_rate)

        if tokens >= 1 then
            tokens = tokens - 1
            redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
            redis.call('EXPIRE', key, 60)
            return 1
        else
            redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
            redis.call('EXPIRE', key, 60)
            return 0
        end
        """;
}
DIAGRAM
CORRECT: Redis-based rate limiting with 5 pods

Pod 1 ─┐
Pod 2 ─┤
Pod 3 ─┼── Redis (shared TokenBucket state) ── 10 req/sec per client
Pod 4 ─┤
Pod 5 ─┘

All pods check the same Redis key. Total limit: 10 req/sec.
Lua script ensures atomicity: no race conditions.

Mistake 3: Not including rate-limit headers in the response

WRONG: The client has no idea how many requests it has left or when it can retry.

TEXT
// WRONG: Just 429 with no information
HTTP/1.1 429 Too Many Requests
{"error": "Rate limit exceeded"}

The client does not know:
  - How many requests are allowed per second
  - How many requests remain
  - When the rate limit resets

CORRECT: Include standard rate-limit headers.

TEXT
// CORRECT: Informative 429 response
HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 10
X-RateLimit-Remaining: 0
Retry-After: 1

{"error": "Rate limit exceeded. Try again in 1 second."}

What should a senior or principal engineer know?

- Token bucket vs leaky bucket. The token bucket allows bursts (send accumulated tokens all at once). The leaky bucket processes requests at a fixed rate, queuing excess requests. For banking APIs, token bucket is preferred because it tolerates legitimate bursts (batch transfers) while enforcing an average rate.

- Hierarchical rate limiting. In production, you apply multiple rate limits: per-IP (100 req/sec), per-user (20 req/sec), per-endpoint (10 req/sec for transfers), and global (10,000 req/sec cluster-wide). A request must pass all levels.

- Spring Cloud Gateway rate limiter. Spring Cloud Gateway has a built-in Redis rate limiter using the token bucket algorithm. You configure it with redis-rate-limiter.replenishRate and redis-rate-limiter.burstCapacity in the route definition.

TEXT
# Spring Cloud Gateway rate limiter configuration
spring:
  cloud:
    gateway:
      routes:
        - id: transfer-service
          uri: lb://transfer-service
          predicates:
            - Path=/api/transfers/**
          filters:
            - name: RequestRateLimiter
              args:
                redis-rate-limiter.replenishRate: 10
                redis-rate-limiter.burstCapacity: 20
                key-resolver: "#{@userKeyResolver}"

- Retry-After header. When returning 429, include a Retry-After header telling the client how many seconds to wait. Calculate it as (1 - availableTokens) / refillRate. Well-behaved clients use this to implement exponential backoff.

- Rate limiting and idempotency. For financial APIs, rate limiting alone is not enough. If a transfer request is retried (because the first response was lost), the transfer should not execute twice. Combine rate limiting with idempotency keys: the client sends a unique key with each request, and the server ensures each key is processed only once.

- Thread safety. The synchronized keyword in the TokenBucket class ensures thread safety for single-instance deployment. For high-throughput scenarios, consider using AtomicLong or LongAdder to avoid contention. For distributed deployment, Redis Lua scripts provide atomicity without Java-level synchronization.

What are common interview follow-up questions?

  • How does the token bucket algorithm differ from the leaky bucket algorithm?
  • How do you implement rate limiting across multiple service instances?
  • What HTTP status code and headers should a rate-limited response include?
  • How do you rate-limit by user ID instead of IP address?
  • How do you handle rate limiting for authenticated vs unauthenticated requests?
  • What is the sliding window counter algorithm and when is it better than token bucket?
  • How do you test a rate limiter without using Thread.sleep?
  • How does Spring Cloud Gateway implement rate limiting with Redis?

Visual Overview

TEXT
  Token Bucket Algorithm
  ========================

  Bucket: capacity=5, refill=2 tokens/sec

  State at t=0:  [*] [*] [*] [*] [*]   5 tokens (full)
  Request 1:     [*] [*] [*] [*] [ ]   4 tokens (allowed)
  Request 2:     [*] [*] [*] [ ] [ ]   3 tokens (allowed)
  Request 3:     [*] [*] [ ] [ ] [ ]   2 tokens (allowed)
  Request 4:     [*] [ ] [ ] [ ] [ ]   1 token  (allowed)
  Request 5:     [ ] [ ] [ ] [ ] [ ]   0 tokens (allowed)
  Request 6:     [ ] [ ] [ ] [ ] [ ]   REJECTED (429)

  ... 1 second passes, 2 tokens refill ...

  State at t=1:  [*] [*] [ ] [ ] [ ]   2 tokens
  Request 7:     [*] [ ] [ ] [ ] [ ]   1 token  (allowed)
  Request 8:     [ ] [ ] [ ] [ ] [ ]   0 tokens (allowed)
  Request 9:     [ ] [ ] [ ] [ ] [ ]   REJECTED (429)
DIAGRAM
  Rate Limiting in a Banking Microservice
  =========================================

  Client (Rajesh)
       │
       │  POST /api/transfers
       ▼
  ┌─────────────────────────────────────┐
  │  RateLimitFilter                    │
  │                                     │
  │  1. Get client IP or user ID        │
  │  2. Look up TokenBucket for client  │
  │  3. bucket.tryConsume()             │
  │     ├── true:  proceed to controller│
  │     └── false: return 429           │
  │  4. Set X-RateLimit-Remaining header│
  └────────────┬────────────────────────┘
               │
        ┌──────┴──────┐
        │             │
   [allowed]     [rejected]
        │             │
        ▼             ▼
  Controller     429 Response
  processes      {"error":"Rate limit
  transfer        exceeded"}
DIAGRAM
  Local vs Distributed Rate Limiting
  ====================================

  Local (WRONG for multi-instance):
  ┌────────┐  ┌────────┐  ┌────────┐
  │ Pod 1  │  │ Pod 2  │  │ Pod 3  │
  │ Bucket │  │ Bucket │  │ Bucket │
  │ 10/sec │  │ 10/sec │  │ 10/sec │
  └────────┘  └────────┘  └────────┘
  Total: 30 req/sec (3x intended!)

  Distributed (CORRECT):
  ┌────────┐  ┌────────┐  ┌────────┐
  │ Pod 1  │  │ Pod 2  │  │ Pod 3  │
  └───┬────┘  └───┬────┘  └───┬────┘
      │           │           │
      └─────┬─────┴───────────┘
            │
       ┌────┴────┐
       │  Redis  │
       │ 10/sec  │
       │ (shared)│
       └─────────┘
  Total: 10 req/sec (correct)

Key Takeaway

The token bucket algorithm is a simple and effective way to rate-limit API requests. It maintains a bucket of tokens that refills at a constant rate. Each request consumes one token. If the bucket is empty, the request is rejected with HTTP 429. The bucket capacity controls the maximum burst size, and the refill rate controls the sustained throughput.

For a banking API at National Bank of India, rate limiting protects against denial-of-service attacks, brute-force PIN attempts, and runaway partner systems. The /api/transfers endpoint might allow 10 requests per second with a burst capacity of 20, while the /api/auth/verify-pin endpoint allows only 3 requests per minute with no burst tolerance.

The implementation uses lazy refill: instead of a background thread adding tokens, the tryConsume method calculates how many tokens should have accumulated since the last call. Injecting java.time.Clock into the TokenBucket class makes tests deterministic. A MutableClock lets you advance time by exact durations without Thread.sleep, eliminating flaky test failures.

For production microservices, local in-memory rate limiting is not enough because each pod has its own bucket, multiplying the effective limit by the number of instances. Store token state in Redis using a Lua script for atomic read-modify-write operations. Spring Cloud Gateway provides a built-in Redis rate limiter based on the token bucket algorithm.

Remember one sentence: the token bucket refills tokens at a constant rate, drains one token per request, and rejects with 429 when empty.

---

Share
Use ← → arrow keys to navigate