Definition
- 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:
- The bucket starts full (at its maximum capacity).
- Tokens are added to the bucket at a constant rate (the refill rate).
- Each incoming request tries to take one token from the bucket.
- If a token is available, the request proceeds.
- If the bucket is empty, the request is rejected.
- 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.
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.
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:
- Calculate elapsed time since the last request.
- Calculate how many tokens to add:
elapsed * refillRate. - Update the token count:
min(currentTokens + newTokens, capacity). - 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.
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;
}
}
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());
}
}
}
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.
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.\"}");
}
}
}
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();
}
}
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.
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);
}
}
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;
}
}
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?
| Feature | Token Bucket | Fixed Window | Sliding Window Log |
|---|---|---|---|
| How it works | Bucket of tokens, refill at constant rate | Counter resets at fixed intervals (every minute) | Timestamp log of each request, count in rolling window |
| Burst handling | Allows bursts up to bucket capacity | Allows 2x burst at window boundary | No burst, strict per-window limit |
| Memory per client | 2 values (token count, last refill time) | 1 counter + window start time | 1 timestamp per request in window |
| Accuracy | Smooth, average rate enforcement | Imprecise at window boundaries | Most precise, exact rolling count |
| Example | 10 tokens, 2/sec refill | Max 120 requests per minute | Max 120 requests in any 60-second window |
| Best for | APIs needing burst tolerance | Simple counters, low precision | Strict rate enforcement |
Fixed window boundary problem:
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:
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).
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);
}
}
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
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.
// 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.
// 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.
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.
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
""";
}
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.
// 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.
// 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.
# 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
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)
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"}
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.
---