Designing a Rate Limiter for an API Gateway with Redis and Spring

1. Overview

When many clients call the same API, a faulty or malicious client can bring down the backend for everyone. A rate limiter at the API gateway layer blocks requests that exceed the limit before they reach the downstream service.

This article walks through a complete case study. The steps include defining requirements, choosing an algorithm, designing data models and APIs, then implementing with Redis Lua scripts and Spring Cloud Gateway. By the end, you’ll be able to build a distributed rate limiter and know how to handle race conditions, clock skew, hot keys, and Redis failures.

2. Problem Requirements

2.1. Functional Requirements

• Limit by tenant API key and by route. For example, tenant shop-a is allowed to call POST /orders at most 100 requests/second, with bursts up to 200.
• Requests exceeding the limit receive 429 Too Many Requests with a Retry-After header.
• All responses include an X-RateLimit-Remaining header so clients can self-regulate.
• Rules can be changed at runtime without redeploying the gateway.

2.2. Scale and Constraints

• Around 50,000 RPS at peak hours, 20 gateway instances, 100,000 tenants.
• Added latency per request must be under 2ms at p99.
• The limit must be accurate across the entire cluster, not per-instance. If the limit is 100/s, the whole cluster together should allow roughly 100/s.
• The rate limiter must not become a single point of failure. When Redis fails, the gateway must still serve requests.
• Accept small errors (a few percent) in exchange for performance.

The third constraint rules out per-instance in-memory counting. We need a shared state store. Redis is a natural choice because it has low latency and atomic operations via Lua.

3. Algorithm Selection

Algorithm	Pros	Cons
Fixed window	Simple, one INCR	Burst doubles at window boundary
Sliding log	Perfectly accurate	Memory expensive, stores each timestamp
Sliding window counter	Approximate, lightweight	Hard to represent bursts
Token bucket	Natural burst support, only 2 fields	Requires refill calculation

We choose token bucket. Each bucket has capacity (burst size) and refill rate refillPerSecond. Each request takes one token. When tokens run out, the request is rejected. State is just two numbers: tokens and ts (last update time). With 100,000 tenants times a few routes, total memory is only tens of MB.

4. Data Model

4.1. Config Rules in SQL

Rules change infrequently and need administration, so we store them in PostgreSQL:

CREATE TABLE rate_limit_rule (
    id                 BIGSERIAL PRIMARY KEY,
    tenant_id          VARCHAR(64)  NOT NULL,
    route_id           VARCHAR(64)  NOT NULL,
    capacity           INT          NOT NULL CHECK (capacity > 0),
    refill_per_second  INT          NOT NULL CHECK (refill_per_second > 0),
    updated_at         TIMESTAMPTZ  NOT NULL DEFAULT now(),
    UNIQUE (tenant_id, route_id)
);

INSERT INTO rate_limit_rule (tenant_id, route_id, capacity, refill_per_second)
VALUES ('shop-a', 'create-order', 200, 100);

The gateway does not read this table on every request. Each instance loads all rules into memory and refreshes periodically, for example every 30 seconds. Another approach is to listen for rule-changed events via Kafka. The hot path never touches the database.

4.2. Bucket State in Redis

Each tenant–route pair is a Redis hash:

Key:    rl:{shop-a}:create-order
Fields: tokens = 153.4
        ts     = 1760256000123   (ms, Redis server time)
TTL:    auto-expires when unused

The {shop-a} part is a hash tag. On Redis Cluster, all keys of the same tenant fall into the same slot. If you later need to examine multiple buckets in a script, they’ll be on the same node.

5. API and Processing Flow

The client sees two types of response:

HTTP/1.1 200 OK
X-RateLimit-Remaining: 152

HTTP/1.1 429 Too Many Requests
Retry-After: 1
X-RateLimit-Remaining: 0

Processing flow in the gateway:

1. Get X-Api-Key to identify the tenant and extract the route ID from the matched route.
2. Look up the rule in the in-memory cache. If no rule exists, use a default rule.
3. Call a Lua script on Redis to refill and take a token in one atomic round-trip.
4. If allowed, set headers and forward. If denied, return 429.
5. On Redis error or timeout, fall back to the local limiter (section 7.3).

6. Implementation

6.1. Dependencies

<dependencyManagement>
    <dependencies>
        <dependency>
            <groupId>org.springframework.cloud</groupId>
            <artifactId>spring-cloud-dependencies</artifactId>
            <version>2025.0.0</version>
            <type>pom</type>
            <scope>import</scope>
        </dependency>
    </dependencies>
</dependencyManagement>

<dependencies>
    <dependency>
        <groupId>org.springframework.cloud</groupId>
        <artifactId>spring-cloud-starter-gateway-server-webflux</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-redis-reactive</artifactId>
    </dependency>
</dependencies>

6.2. Lua Script for Token Bucket

Place the file at src/main/resources/scripts/token_bucket.lua:

local key      = KEYS[1]
local capacity = tonumber(ARGV[1])
local refillMs = tonumber(ARGV[2]) / 1000.0   -- tokens per ms

local t   = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)

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

tokens = math.min(capacity, tokens + math.max(0, now - ts) * refillMs)

local allowed = 0
if tokens >= 1 then
  tokens = tokens - 1
  allowed = 1
end

redis.call('HSET', key, 'tokens', tostring(tokens), 'ts', now)
redis.call('PEXPIRE', key, math.ceil(capacity / refillMs) * 2)

return { allowed, math.floor(tokens) }

Key points:

• redis.call('TIME') gets the Redis server’s time, not the gateway’s. 20 instances have clocks that differ by tens of milliseconds, so if each sends its own now, tokens will be refilled incorrectly. From Redis 7 onward, scripts use effects replication by default, so calling TIME before writing is safe.
• The entire sequence of read, compute, and write runs atomically because Redis executes scripts single-threaded. This is the solution to race conditions between instances.
• PEXPIRE is set to twice the time to refill the bucket. Unused buckets disappear automatically. When they reappear, they start full, which matches the intended semantics.
• The script returns [allowed, remaining]. Lua converts floats to integers on return, so we floor in advance for clarity.

6.3. Calling the Script from Java

public record RateLimitRule(int capacity, int refillPerSecond) {}

public record Decision(boolean allowed, long remaining) {}

@Component
public class RedisTokenBucket {

    private final ReactiveStringRedisTemplate redis;
    private final RedisScript<List> script =
            RedisScript.of(new ClassPathResource("scripts/token_bucket.lua"), List.class);

    public RedisTokenBucket(ReactiveStringRedisTemplate redis) {
        this.redis = redis;
    }

    @SuppressWarnings("unchecked")
    public Mono<Decision> tryAcquire(String tenant, String route, RateLimitRule rule) {
        String key = "rl:{" + tenant + "}:" + route;
        return redis.execute(script, List.of(key),
                        List.of(String.valueOf(rule.capacity()),
                                String.valueOf(rule.refillPerSecond())))
                .next()
                .map(r -> {
                    List<Long> res = (List<Long>) r;
                    return new Decision(res.get(0) == 1L, res.get(1));
                });
    }
}

Spring automatically computes the SHA1 of the script and uses EVALSHA. If Redis hasn’t cached the script, Spring falls back to EVAL. Only the first call sends the full script over the network.

6.4. Global Filter in the Gateway

@Component
public class RateLimitFilter implements GlobalFilter, Ordered {

    private static final RateLimitRule DEFAULT_RULE = new RateLimitRule(20, 10);

    private final RedisTokenBucket redisBucket;
    private final LocalFallbackLimiter fallback;
    private final RuleCache rules;

    public RateLimitFilter(RedisTokenBucket redisBucket,
                           LocalFallbackLimiter fallback, RuleCache rules) {
        this.redisBucket = redisBucket;
        this.fallback = fallback;
        this.rules = rules;
    }

    @Override
    public Mono<Void> filter(ServerWebExchange exchange, GatewayFilterChain chain) {
        String tenant = exchange.getRequest().getHeaders().getFirst("X-Api-Key");
        if (tenant == null) {
            exchange.getResponse().setStatusCode(HttpStatus.UNAUTHORIZED);
            return exchange.getResponse().setComplete();
        }
        Route route = exchange.getAttribute(ServerWebExchangeUtils.GATEWAY_ROUTE_ATTR);
        String routeId = route != null ? route.getId() : "default";
        RateLimitRule rule = rules.find(tenant, routeId).orElse(DEFAULT_RULE);

        return redisBucket.tryAcquire(tenant, routeId, rule)
                .timeout(Duration.ofMillis(5))
                .onErrorResume(e -> Mono.just(fallback.tryAcquire(tenant, routeId, rule)))
                .flatMap(decision -> {
                    var response = exchange.getResponse();
                    response.getHeaders().set("X-RateLimit-Remaining",
                            String.valueOf(decision.remaining()));
                    if (decision.allowed()) {
                        return chain.filter(exchange);
                    }
                    response.setStatusCode(HttpStatus.TOO_MANY_REQUESTS);
                    response.getHeaders().set("Retry-After",
                            String.valueOf(Math.max(1, 1 / rule.refillPerSecond())));
                    return response.setComplete();
                });
    }

    @Override
    public int getOrder() {
        return -100;
    }
}

The filter runs for all routes. It sets timeout(5ms) so a slow Redis node doesn’t drag down the entire gateway. On Redis error, onErrorResume falls back to the local limiter. Quick test with curl using a rule with capacity=2:

for i in 1 2 3; do
  curl -s -o /dev/null -w "%{http_code}\n" -H "X-Api-Key: shop-a" -X POST localhost:8080/orders
done

200
200
429

7. Challenges and Solutions

7.1. Race Conditions Between Instances

The naive approach is to call HGET, compute in Java, then HSET. Two instances could both read tokens=1 and both allow their request. A Lua script eliminates this race condition entirely. The WATCH/MULTI approach also works, but requires retry on conflict and costs more round-trips.

7.2. Hot Keys and Traffic Spikes

A large tenant might fire 20,000 RPS at a single key. A Redis node can handle ~100,000 ops/s, but that key becomes a hot spot. Two solutions:

• Batch token allocation (local pre-fetch): Each instance pre-requests a batch of tokens, say 50 at a time, then drains them locally. Redis calls drop ~50×. In exchange, the total limit might temporarily exceed number of instances × batch size. Given the “a few percent error” tolerance in section 2.2, this is acceptable.
• Bucket sharding: Split the 20,000/s limit into 10 sub-buckets rl:{shop-a}:create-order:0..9, each 2,000/s. Requests randomly pick a sub-bucket. Drop the hash tag for these keys so they spread across multiple nodes.

Legitimate bursts are absorbed by capacity. That’s why we chose token bucket over fixed window.

7.3. Redis Unavailable: Controlled Fail-Open

Fail-closed (rejecting all requests when Redis dies) turns a dependent infrastructure outage into a full system failure. Complete fail-open loses the protection layer. The middle ground is a local limiter with limits divided equally among instances:

@Component
public class LocalFallbackLimiter {

    private final int instanceCount;
    private final LongSupplier clock;
    private final ConcurrentHashMap<String, LocalBucket> buckets = new ConcurrentHashMap<>();

    public LocalFallbackLimiter(@Value("${gateway.instances:20}") int instanceCount) {
        this(instanceCount, System::currentTimeMillis);
    }

    LocalFallbackLimiter(int instanceCount, LongSupplier clock) {
        this.instanceCount = instanceCount;
        this.clock = clock;
    }

    public Decision tryAcquire(String tenant, String route, RateLimitRule rule) {
        double cap = Math.max(1, rule.capacity() / (double) instanceCount);
        double perMs = rule.refillPerSecond() / (double) instanceCount / 1000.0;
        LocalBucket b = buckets.computeIfAbsent(tenant + ":" + route,
                k -> new LocalBucket(cap, clock.getAsLong()));
        return b.take(cap, perMs, clock.getAsLong());
    }

    static final class LocalBucket {
        private double tokens;
        private long ts;

        LocalBucket(double tokens, long ts) {
            this.tokens = tokens;
            this.ts = ts;
        }

        synchronized Decision take(double cap, double perMs, long now) {
            tokens = Math.min(cap, tokens + Math.max(0, now - ts) * perMs);
            ts = now;
            if (tokens >= 1) {
                tokens -= 1;
                return new Decision(true, (long) tokens);
            }
            return new Decision(false, 0);
        }
    }
}

Each instance holds 1/instanceCount of the limit. Total cluster-wide is still roughly correct without Redis. In production, wrap the Redis call with a circuit breaker (e.g., Resilience4j). When Redis is down, the circuit breaker avoids burning 5ms timeout per request.

7.4. Multi-Region Consistency

If the gateway runs in two regions, syncing Redis across regions per request breaks the 2ms requirement. The pragmatic approach is to split limits by region proportionally to traffic, say 70/30, and accept that a tenant might be throttled in one region while another has spare capacity. For finer tuning, a background job can adjust the split every few minutes based on actual metrics.

8. Testing

Token bucket logic should be tested independently of real time. Since LocalFallbackLimiter takes a LongSupplier, we can advance time with an AtomicLong:

class LocalFallbackLimiterTest {

    @Test
    void shouldRejectWhenBucketEmptyAndRefillOverTime() {
        AtomicLong now = new AtomicLong(0);
        var limiter = new LocalFallbackLimiter(1, now::get);
        var rule = new RateLimitRule(2, 1);

        assertThat(limiter.tryAcquire("shop-a", "create-order", rule).allowed()).isTrue();
        assertThat(limiter.tryAcquire("shop-a", "create-order", rule).allowed()).isTrue();
        assertThat(limiter.tryAcquire("shop-a", "create-order", rule).allowed()).isFalse();

        now.addAndGet(1_000);

        Decision d = limiter.tryAcquire("shop-a", "create-order", rule);
        assertThat(d.allowed()).isTrue();
        assertThat(d.remaining()).isZero();
    }
}

This test confirms three behaviors: bursts are allowed up to capacity, requests beyond the limit are rejected, and tokens are refilled correctly over time. For the Lua script, write an integration test using Testcontainers with image redis:7. Fire 1,000 concurrent requests and verify that the number of allowed requests does not exceed capacity.

Common pitfalls:

• Using the gateway’s System.currentTimeMillis() as now in the script. Clock drift between instances causes tokens to refill incorrectly.
• Forgetting to set a TTL on the key. Redis memory bloats as new tenants appear.
• Identifying clients by IP after NAT or load balancing. An entire company shares one bucket.
• Using the gateway’s rate limiter instead of overload protection in the service itself (bulkhead, load shedding). The gateway only counts requests; it doesn’t know which are heavy.

9. Conclusion

In this article, we designed a rate limiter for an API gateway from requirements to implementation. Token bucket handles bursts elegantly. Lua scripts on Redis solve race conditions with a single atomic round-trip. Using Redis’s time eliminates clock skew between instances.

The real challenges lie beyond the algorithm. Hot keys need batch token allocation or sharding. Redis outages need controlled fail-open with a local limiter. Multi-region systems need split limits instead of tight synchronization. At each step, we trade small accuracy losses for low latency and availability, honoring the constraints we set at the start.