Rate Limiter (LLD)

Problem statement (interviewer prompt)

Design a rate limiter class with a clean strategy interface that supports token bucket, leaky bucket, fixed window, and sliding window. Per-key limits (user id or IP); thread-safe; pluggable storage (in-memory, Redis).

classDiagram
  class RateLimiter {
    <<interface>>
    +tryAcquire(key) boolean
    +tryAcquire(key, permits) boolean
  }
  class TokenBucketLimiter {
    -capacity : int
    -refillRate : double
    -storage : Storage
    +tryAcquire(key)
  }
  class LeakyBucketLimiter
  class FixedWindowLimiter
  class SlidingWindowLimiter
  class Storage {
    <<interface>>
    +get(k) state
    +cas(k, old, new) boolean
  }
  RateLimiter <|.. TokenBucketLimiter
  RateLimiter <|.. LeakyBucketLimiter
  RateLimiter <|.. FixedWindowLimiter
  RateLimiter <|.. SlidingWindowLimiter
  TokenBucketLimiter --> Storage

Strategy pattern: the algorithm is swappable; per-key state lives in pluggable Storage (memory map, Redis, DynamoDB).

The HLD version (in classics/rate-limiter) covers what algorithms to choose and why. This LLD focuses on the class design and concurrency contract.

The strategy interface

interface RateLimiter {
    boolean tryAcquire(String key);
    boolean tryAcquire(String key, int permits);
}

A single method per key/permit count. Returns true if the action is allowed; false otherwise. Some implementations also expose acquireBlocking that waits, but bounded latency requires care.

Token bucket

class TokenBucketLimiter implements RateLimiter {
    final double rate;       // tokens per second
    final double capacity;
    final Storage storage;   // pluggable

    public boolean tryAcquire(String key) {
        State old = storage.get(key);
        long now = System.currentTimeMillis();
        double tokens = Math.min(capacity, old.tokens + (now - old.lastRefill) / 1000.0 * rate);
        if (tokens < 1) return false;
        State next = new State(tokens - 1, now);
        return storage.cas(key, old, next);  // retry loop on CAS failure
    }
}

State per key: (tokens, lastRefillMillis). Atomic compare-and-swap so concurrent acquires don't double-spend.

Class hierarchy

classDiagram
  class RateLimiter {
    <<interface>>
    +tryAcquire(key) boolean
  }
  class AbstractLimiter {
    <<abstract>>
    #storage : Storage
    #clock : Clock
  }
  class TokenBucketLimiter
  class LeakyBucketLimiter
  class FixedWindowLimiter
  class SlidingWindowLogLimiter
  class SlidingWindowCounterLimiter

  class Storage {
    <<interface>>
    +get(key) State
    +cas(key, old, new) boolean
    +put(key, value, ttl)
  }
  class InMemoryStorage
  class RedisStorage

  RateLimiter <|.. AbstractLimiter
  AbstractLimiter <|-- TokenBucketLimiter
  AbstractLimiter <|-- LeakyBucketLimiter
  AbstractLimiter <|-- FixedWindowLimiter
  AbstractLimiter <|-- SlidingWindowLogLimiter
  AbstractLimiter <|-- SlidingWindowCounterLimiter
  AbstractLimiter --> Storage
  Storage <|.. InMemoryStorage
  Storage <|.. RedisStorage

Storage backends

Backend	Pros	Cons
ConcurrentHashMap	Fastest; single-JVM	Per-pod limits; no shared state
Redis with EVAL Lua	Atomic across cluster	Network hop per check
DynamoDB conditional updates	Serverless, multi-region	Cost / latency
Local + async replication	Best of both; eventually accurate	Slack in enforcement

Redis token bucket - Lua

local key = KEYS[1]
local rate = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local tokens = tonumber(redis.call("HGET", key, "tokens") or capacity)
local last = tonumber(redis.call("HGET", key, "last") or now)
local refill = (now - last) / 1000.0 * rate
tokens = math.min(capacity, tokens + refill)
if tokens < 1 then return 0 end
redis.call("HMSET", key, "tokens", tokens - 1, "last", now)
redis.call("EXPIRE", key, math.ceil(capacity / rate * 2))
return 1

Lua runs atomically in Redis; no race even across many app pods.

Threading

In-memory: AtomicReference<State> or LongAdder per key; CAS loop in tryAcquire. Watch out for ABA on State swaps if you reuse objects.

Per-tier / dynamic limits

RateLimit limit = limitResolver.resolve(userId); // free=10, pro=100, enterprise=∞
limiter.tryAcquire(userId, 1, limit);

Inject a LimitResolver; load policy from a control plane (LaunchDarkly, internal config service).

Edge cases

• Clock skew: in distributed clocks, use System.nanoTime for monotonic deltas; Redis can return server time.
• Cold start: lazy-init bucket on first request, full capacity.
• Burst behaviour: token bucket allows controlled bursts up to capacity; leaky bucket smooths absolutely.
• Fairness: a single key starving others - use weighted fair queueing if needed.

Where rate-limiter LLD fits

flowchart TB
  RL((Rate limiter<br/>LLD))
  RLS["Rate limiter (HLD)<br/>system complement"]
  BPL[Behavioral patterns<br/>Strategy underlies]
  CON[Concurrency primitives<br/>CAS, atomic refs]
  BP[Backpressure<br/>rate limit is one form]
  RLS -. complement .- RL
  BPL --> RL
  CON --> RL
  BP -. broader .- RL

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class RL service;
    class RLS,BPL,CON,BP datastore;

Glossary & fundamentals

Tag	Concept	What it is	Page
HLD	Rate limiter (system)	the HLD complement	rate-limiter
LLD	Behavioral patterns	Strategy underlies this design	behavioral-patterns
LLD	Concurrency primitives	CAS, atomic refs	concurrency-primitives
HLD	Backpressure	rate limit is one form	backpressure

Quick reference

Interface

tryAcquire(key, permits=1) -> boolean

Algorithms

Algo	Burst	Smoothness	Notes
Token bucket	Yes	Bursty	Most popular
Leaky bucket	No	Strict	Constant outflow
Fixed window	Boundary spike	Coarse	Simple counter
Sliding window log	Exact	Expensive	Keep timestamps
Sliding window counter	Approx	Cheap	Two-bucket weighted avg

Storage backends

• ConcurrentHashMap (single JVM)
• Redis + Lua EVAL (cluster-safe atomic)
• DynamoDB conditional updates
• Hybrid: local + async sync (eventually accurate)

Thread-safety

• AtomicReference + CAS loop
• LongAdder for hot counters
• Lua atomicity in Redis

Per-tier limits

LimitResolver → policy from control plane (LaunchDarkly, config service).

Production libraries

• Guava RateLimiter (token bucket)
• Bucket4j (Java)
• redis-cell (Redis module, GCRA algorithm)

Pitfalls

• Wall clock vs nanoTime (use monotonic)
• Cold-start bucket initialization
• ABA on State object reuse
• Single-key starvation - need fairness

Refs

• Stripe rate limiter blog
• Guava RateLimiter docs
• bucket4j.com

FAQ

Which rate limiter algorithm should you pick?

Token bucket allows controlled bursts and is the default. Sliding window log is most accurate but memory-heavy. Sliding window counter approximates accuracy with O(1) memory.

How does the token bucket algorithm work?

A bucket of capacity C refills at R tokens per second; a request consumes one token. If the bucket is empty, the request is rejected or queued.

How do you make a rate limiter distributed?

Centralise counters in Redis using INCR with EXPIRE for fixed window, or a Lua script for atomic token bucket updates so multiple app instances share state.

How is a sliding window counter implemented?

Track the count in the current and previous fixed window; estimate the sliding count by weighting the previous window by how much of it overlaps the sliding range.

Which design pattern fits a rate limiter?

Strategy: a RateLimiter interface with TokenBucket, LeakyBucket, FixedWindow, and SlidingWindow implementations behind it lets callers swap policy without code changes.

Related Topics

• Rate Limiter (HLD): the system-design complement
• Behavioral Patterns: Strategy + Factory underlie the design
• Backpressure: broader flow-control context

Further reading

• Doc - Guava RateLimiter
• Blog - Stripe - Scaling our API rate limiter
• Doc - Bucket4j