Distributed Rate Limiting for Multi Instance Rust Services

A rate limiter in each instance is easy and wrong for a fleet. With a limit of 100 requests per minute and ten replicas behind a load balancer, a client can make about a thousand. If the limit protects a downstream system or enforces a contract, it has to be global. That requires shared state, and the shared state brings atomicity, latency and failure questions. Versions: Rust 1.90, redis 0.32, Axum 0.8, Redis 7.4. The single-process version is in building a rate limiter.

Fixed window with INCR

The simplest shared limiter: one counter per key per window.

use redis::{aio::ConnectionManager, AsyncCommands};

pub struct Decision {
    pub allowed: bool,
    pub remaining: u32,
    pub retry_after_secs: u64,
}

pub async fn fixed_window(
    redis: &mut ConnectionManager,
    key: &str,
    limit: u32,
    window_secs: u64,
) -> redis::RedisResult<Decision> {
    let now = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_secs();
    let window = now / window_secs;
    let redis_key = format!("rl:{key}:{window}");

    let count: u32 = redis.incr(&redis_key, 1).await?;
    if count == 1 {
        let _: () = redis.expire(&redis_key, window_secs as i64 + 1).await?;
    }
    Ok(Decision {
        allowed: count <= limit,
        remaining: limit.saturating_sub(count),
        retry_after_secs: window_secs - (now % window_secs),
    })
}

INCR is atomic, so concurrent instances cannot lose updates. There is a small gap: if the process dies between INCR and EXPIRE, the key never expires, which is why the expiry is set when count == 1 and why production code uses a script or SET key 0 EX n NX first. The known weakness of fixed windows: a client can send limit requests at the end of one window and limit more at the start of the next, doubling the rate for a moment.

Atomic token bucket in Lua

A Lua script runs atomically inside Redis, so reading and updating the bucket cannot interleave with another instance:

const TOKEN_BUCKET: &str = r#"
local key      = KEYS[1]
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])   -- tokens per second
local now_ms   = tonumber(ARGV[3])
local cost     = tonumber(ARGV[4])

local data   = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(data[1])
local ts     = tonumber(data[2])
if tokens == nil then
  tokens = capacity
  ts = now_ms
end

local elapsed = math.max(0, now_ms - ts) / 1000.0
tokens = math.min(capacity, tokens + elapsed * rate)

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

redis.call('HSET', key, 'tokens', tokens, 'ts', now_ms)
redis.call('PEXPIRE', key, math.ceil(capacity / rate * 1000) + 1000)

local retry_ms = 0
if allowed == 0 then
  retry_ms = math.ceil((cost - tokens) / rate * 1000)
end
return { allowed, math.floor(tokens), retry_ms }
"#;

pub async fn token_bucket(
    redis: &mut ConnectionManager,
    key: &str,
    capacity: u32,
    per_second: f64,
) -> redis::RedisResult<Decision> {
    let now_ms = std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_millis() as u64;
    let (allowed, remaining, retry_ms): (i32, i64, i64) = redis::Script::new(TOKEN_BUCKET)
        .key(format!("rl:tb:{key}"))
        .arg(capacity)
        .arg(per_second)
        .arg(now_ms)
        .arg(1)
        .invoke_async(redis)
        .await?;
    Ok(Decision {
        allowed: allowed == 1,
        remaining: remaining.max(0) as u32,
        retry_after_secs: (retry_ms as u64).div_ceil(1000),
    })
}

The script uses the caller's clock for now_ms. Instances with skewed clocks distort refill, so either keep clocks synchronized (NTP) or use redis.call('TIME') inside the script as the single clock. redis::Script sends the script by hash after the first call. The key expires when the bucket would be full again, so idle clients cost no memory.

Choosing an algorithm

| Algorithm | Accuracy | Memory per key | Bursts | Notes | |---|---|---|---|---| | Fixed window | boundary spikes up to 2x | one counter | at window start | simplest | | Sliding window log | exact | one entry per request | no | sorted set; costly for large limits | | Sliding window counter | close | two counters | limited | weighted previous window | | Token bucket | exact rate | two fields | up to capacity | most flexible | | Leaky bucket | smooths output | queue | no | for shaping, not rejecting |

For API limits, token bucket or sliding window counter are the usual choices.

Keys

Pick the identity carefully: authenticated user or API key where available, IP otherwise (behind a proxy, from the trusted forwarded header; see behind a reverse proxy). Combine dimensions with tiers: per_ip:1.2.3.4, per_key:abc, per_route:login. Apply a stricter limit on expensive or abusive routes (login, password reset, search) (rate limiting for abuse). Avoid unbounded key growth from attacker-chosen values; keys expire, which bounds it.

The Axum layer and headers

use axum::{extract::{Request, State}, http::{header, HeaderValue, StatusCode}, middleware::Next, response::{IntoResponse, Response}};

pub async fn limit(State(app): State<AppState>, req: Request, next: Next) -> Response {
    let key = client_key(&req);
    let mut conn = app.redis.clone();

    match token_bucket(&mut conn, &key, 100, 100.0 / 60.0).await {
        Ok(d) if !d.allowed => {
            let mut res = StatusCode::TOO_MANY_REQUESTS.into_response();
            res.headers_mut().insert(header::RETRY_AFTER, HeaderValue::from(d.retry_after_secs.max(1)));
            res
        }
        Ok(d) => {
            let mut res = next.run(req).await;
            res.headers_mut().insert("x-ratelimit-remaining", HeaderValue::from(d.remaining));
            res
        }
        Err(e) => {
            tracing::error!("rate limiter unavailable: {e}");
            if app.fail_open { next.run(req).await } else { StatusCode::SERVICE_UNAVAILABLE.into_response() }
        }
    }
}

Retry-After and RateLimit-* headers let clients pace themselves. Test the whole thing with paused time against a fake clock and, for the Redis part, a real Redis in a container (testing rate limiters).

Failure policy

Redis down, slow or partitioned. Options:

• Fail open with a local in-process limiter at a looser (per-instance) limit as a backstop. Best for general APIs.
• Fail closed for abuse-sensitive endpoints, accepting that an outage blocks them.
• Timeouts: give the Redis call a tight timeout (tens of milliseconds) so the limiter never adds seconds of latency.

Log and count failures, and alert on them.

Alternatives

A gateway or CDN can enforce limits before traffic reaches you (Envoy, Nginx, cloud API gateways), which removes the code but ties the policy to infrastructure. Cell-based or sticky routing makes local limiters approximately right: route each client to one instance by key. For very high rates, approximate algorithms with local counters that sync every few hundred milliseconds trade accuracy for scale. See also Axum rate limiting and Redis data structures.