Rate Limiter: Four Algorithms Behind One Strategy Interface

14.1Problem Statement

Design a reusable rate limiter that caps how many requests a client may make in a time window — the kind of component you embed inside an API gateway or service middleware, sitting in front of every inbound call and answering exactly one question: let this one through, or not.

Functional requirements:

• allowRequest(clientId) returns whether a request is permitted right now.
• Support multiple algorithms, swappable per configuration: Token Bucket (tokens refill at a fixed rate, each request spends one), Leaky Bucket (requests queue and drain at a fixed rate), Fixed Window Counter (N requests per fixed time window), and Sliding Window Log / Counter (smooths the fixed-window boundary burst).
• Per-client limits — each clientId owns its own state, fully isolated from every other client's.

Non-functional requirements / constraints:

• Thread-safe: high-concurrency allowRequest calls on the same client must be correct, and the prompt explicitly warns against the lazy answer — avoid one global lock.
• The algorithm is a Strategy — it must swap without changing a single call site.
• Config (limits per client or tier) lives behind a Singleton registry, and limiters are produced by a Factory.
• Efficient: O(1) per check, bounded memory per client — someone has to answer for stale clients eventually.

Expected public interface:

class RateLimitStrategy {              // Strategy
public:
    virtual bool allowRequest(const std::string& clientId) = 0;
    virtual ~RateLimitStrategy() = default;
};

// e.g. TokenBucketLimiter, FixedWindowLimiter, SlidingWindowLimiter

class RateLimiterFactory {
public:
    static std::unique_ptr<RateLimitStrategy> create(AlgoType type, const RateLimitConfig& cfg);
};

class RateLimiter {
public:
    explicit RateLimiter(std::unique_ptr<RateLimitStrategy> strategy);
    bool allowRequest(const std::string& clientId);   // thread-safe
};

What the interviewer is really testing:

• Correct, clearly-explained algorithms — token refill math, and why sliding window beats fixed window at the boundary.
• The Strategy abstraction and a Factory that produces the right limiter without a switch leaking into every call site.
• The thread-safety story per client — a per-key lock or atomic token count, never one mutex guarding every client at once.
• Bounded memory: how stale client state eventually gets evicted.

Follow-up questions to expect:

1. Distributed rate limiting across many service instances (a centralized store, Redis-style counters) — discuss it even if you implement in-memory.
2. Tiered limits (free vs premium clients) and dynamic config reload.
3. Burst allowance vs steady-rate trade-offs.
4. Returning Retry-After / time-until-allowed instead of a bare boolean.

14.2How to Approach

Mine the hard constraints before designing anything, because they choose the shape of the answer outright. "Support multiple algorithms, swappable per configuration … the algorithm is a Strategy" names the pattern being tested by name — a single allowRequest with a switch (algoType) buried inside it is a fail, full stop. "Thread-safe … avoid one global lock" turns concurrency into a first-class requirement and tells you exactly which wrong answer it wants you to reject. "Efficient: O(1) per check, bounded memory" rules out any background refill thread and demands lazy, on-read math instead.

Circle the nouns — request, client, limiter, strategy, token, bucket, window, config, tier, factory — and the class list writes itself: a RateLimitConfig of knobs (capacity, refill rate, window size); a RateLimitStrategy interface holding the one swappable allowRequest(clientId) operation; concrete TokenBucketLimiter / FixedWindowLimiter / SlidingWindowLimiter strategies, each owning its own map of per-client state; a RateLimiterFactory that hides the enum-to-class mapping in exactly one place; and a RateLimiter facade that holds a strategy and never asks which one it was handed. That's the whole Strategy pattern — one interface, N concrete implementations, one context, one factory to build it — and the class list was sitting in the problem statement the whole time.

The four algorithms all answer the same question, but they disagree on how much history they keep and how forgiving they are of bursts:

The lazy-refill trick is the one idea worth memorizing from this problem: never run a background thread that adds tokens on a timer. Instead, compute the refill on read. Each client stores a token count and a last-refill timestamp; on every allowRequest, compute elapsed = now - lastRefill, add elapsed × refillRate tokens capped at capacity, and only then check whether a whole token is available to spend. No timer, one arithmetic step, O(1).

The boundary burst is the sliding window's whole reason for existing:

fixed window, capacity 3, window 1s

  |---------- window A ----------|---------- window B ----------|
                              3 requests here          3 requests here
                              (just before the edge)   (just after the edge)

  6 requests land inside a span far shorter than 1s -- the boundary burst.
  sliding window blends window A's count into window B's estimate, weighted
  by how much of window A is still "in view," so the estimate never spikes.

Thread safety is the other half of the grade. The requirement explicitly rules out one mutex guarding the whole limiter, which means the state has to be keyed per client and locked per client: a map from clientId to state, where the map itself is shared structure but each entry is independently lockable. The discipline that makes this safe is two-level locking — a brief lock on the map just to find or create an entry, released immediately, followed by the entry's own mutex held only while doing that one client's math. Holding the coarse map lock during the arithmetic is exactly how you'd accidentally rebuild the single global lock the problem told you to avoid.

The Factory is the one place allowed to know the AlgoType enum; every call site stays algorithm-blind and adding a fifth algorithm later is one new case, not an edit scattered across the codebase. For the config side, a Singleton ConfigRegistry maps tier name to RateLimitConfig — free gets a small bucket, premium gets a large one — and dynamic reload is just overwriting an entry under a lock; existing buckets pick up the new limit on their very next refill, no restart required. Resolve a request's tier, hand the resulting config to the Factory, and the tiering follow-up is already answered by machinery built for a different reason.

14.3Whole Solution

One synthesized, internally-consistent program: the RateLimitStrategy Strategy interface; three concrete strategies — Token Bucket, Fixed Window, and Sliding Window Counter (Leaky Bucket is discussed above and left as a named extension point, exactly like the distributed follow-up below) — each with its own per-client state and two-level locking; the RateLimiterFactory; the lock-free RateLimiter facade; a ConfigRegistry singleton for tiered, reloadable config; and a driver that exercises a burst, a throttle, a refill recovery, a fixed-window boundary burst, its sliding-window smoothing, and a tiered client resolved through the Factory.

// ============================================================
// Rate Limiter -- Strategy interface with four pluggable
// algorithms, a Factory that builds the right one, and per-client
// fine-grained locking so no single mutex ever serializes every
// client's traffic.
// ============================================================
#include <algorithm>
#include <chrono>
#include <iostream>
#include <memory>
#include <mutex>
#include <stdexcept>
#include <string>
#include <thread>
#include <unordered_map>

// ============================================================
// The pinned contract: one enum for the algorithm choice, one
// config struct of knobs, one Strategy interface, one Factory
// declaration (defined later, once the concrete strategies exist).
// ============================================================
enum class AlgoType { TOKEN_BUCKET, FIXED_WINDOW, SLIDING_WINDOW };

struct RateLimitConfig {
    int    capacity   = 10;    // max tokens / max requests per window
    double refillRate = 5.0;   // tokens per second (token bucket only)
    int    windowMs   = 1000;  // window length in ms (window algorithms only)
};

class RateLimitStrategy {                          // Strategy
public:
    virtual bool allowRequest(const std::string& clientId) = 0;
    virtual ~RateLimitStrategy() = default;
};

class RateLimiterFactory {                          // declared now, defined below
public:
    static std::unique_ptr<RateLimitStrategy> create(AlgoType type, const RateLimitConfig& cfg);
};

// ============================================================
// Leaves: a monotonic clock alias, and one state struct per
// algorithm. Every state struct carries its OWN mutex -- that is
// what makes "per-client locking" fall out for free later on.
// ============================================================
using Clock     = std::chrono::steady_clock;   // monotonic -- never jumps backward
using TimePoint = Clock::time_point;

struct TokenBucketState {
    double     tokens;        // fractional tokens available right now
    TimePoint  lastRefill;
    std::mutex mtx;           // per-client lock -- NOT one global lock
};

struct FixedWindowState {
    int        count;         // requests seen in the current window
    TimePoint  windowStart;
    std::mutex mtx;
};

struct SlidingWindowState {
    TimePoint  windowStart;   // start of the window currently being counted
    int        currCount = 0; // requests counted in the current window
    int        prevCount = 0; // requests counted in the window right before it
    std::mutex mtx;
};

// ============================================================
// Concrete strategy #1: Token Bucket. Refill is computed lazily
// on read from elapsed time -- no background timer, O(1) per call.
// ============================================================
class TokenBucketLimiter : public RateLimitStrategy {
public:
    explicit TokenBucketLimiter(const RateLimitConfig& cfg) : cfg_(cfg) {}

    bool allowRequest(const std::string& clientId) override {
        TokenBucketState& st = stateFor(clientId);     // map lock held only inside stateFor
        std::lock_guard<std::mutex> lock(st.mtx);       // per-CLIENT lock only

        TimePoint now = Clock::now();
        double elapsedSec =
            std::chrono::duration<double>(now - st.lastRefill).count();

        st.tokens     = std::min(static_cast<double>(cfg_.capacity),
                                  st.tokens + elapsedSec * cfg_.refillRate);
        st.lastRefill = now;

        if (st.tokens >= 1.0) { st.tokens -= 1.0; return true; }  // spend a token
        return false;                                              // throttled
    }

private:
    // Find-or-create the client's bucket. The MAP mutex protects only the
    // lookup/insert; the per-client math below runs under st.mtx alone.
    TokenBucketState& stateFor(const std::string& clientId) {
        std::lock_guard<std::mutex> mapLock(mapMtx_);
        auto it = states_.find(clientId);
        if (it == states_.end()) {
            auto st = std::make_unique<TokenBucketState>();
            st->tokens     = cfg_.capacity;     // new clients start with a full bucket
            st->lastRefill = Clock::now();
            it = states_.emplace(clientId, std::move(st)).first;
        }
        return *it->second;
    }

    RateLimitConfig cfg_;
    std::mutex      mapMtx_;
    // unique_ptr so the stored State -- and its live mutex -- never moves
    // in memory when the unordered_map rehashes.
    std::unordered_map<std::string, std::unique_ptr<TokenBucketState>> states_;
};

// ============================================================
// Concrete strategy #2: Fixed Window Counter. Simplest possible
// shape -- a counter plus a window-start timestamp, hard reset when
// the window has fully elapsed.
// ============================================================
class FixedWindowLimiter : public RateLimitStrategy {
public:
    explicit FixedWindowLimiter(const RateLimitConfig& cfg) : cfg_(cfg) {}

    bool allowRequest(const std::string& clientId) override {
        FixedWindowState& st = stateFor(clientId);
        std::lock_guard<std::mutex> lock(st.mtx);

        TimePoint now = Clock::now();
        auto window = std::chrono::milliseconds(cfg_.windowMs);
        if (now - st.windowStart >= window) {     // window expired -> hard reset
            st.count       = 0;
            st.windowStart = now;
        }
        if (st.count < cfg_.capacity) { ++st.count; return true; }
        return false;
    }

private:
    FixedWindowState& stateFor(const std::string& clientId) {
        std::lock_guard<std::mutex> mapLock(mapMtx_);
        auto it = states_.find(clientId);
        if (it == states_.end()) {
            auto st = std::make_unique<FixedWindowState>();
            st->count       = 0;
            st->windowStart = Clock::now();
            it = states_.emplace(clientId, std::move(st)).first;
        }
        return *it->second;
    }

    RateLimitConfig cfg_;
    std::mutex      mapMtx_;
    std::unordered_map<std::string, std::unique_ptr<FixedWindowState>> states_;
};

// ============================================================
// Concrete strategy #3: Sliding Window Counter. Same shape as Fixed
// Window, but keeps one extra number -- the PREVIOUS window's count
// -- and blends it in, weighted by how much of that window is still
// "in view", to erase the boundary burst.
//   estimated = prevCount * overlapFraction + currCount
//   allow if estimated < capacity
// ============================================================
class SlidingWindowLimiter : public RateLimitStrategy {
public:
    explicit SlidingWindowLimiter(const RateLimitConfig& cfg) : cfg_(cfg) {}

    bool allowRequest(const std::string& clientId) override {
        SlidingWindowState& st = stateFor(clientId);
        std::lock_guard<std::mutex> lock(st.mtx);

        TimePoint now = Clock::now();
        auto window = std::chrono::milliseconds(cfg_.windowMs);
        auto elapsedSinceStart = now - st.windowStart;

        if (elapsedSinceStart >= window) {
            auto windowsElapsed = elapsedSinceStart / window;   // whole windows that passed
            // Only the window immediately adjacent to the one just closed
            // still overlaps at all; anything older contributes nothing.
            st.prevCount    = (windowsElapsed == 1) ? st.currCount : 0;
            st.currCount    = 0;
            st.windowStart += window * windowsElapsed;
        }

        double elapsedInWindow =
            std::chrono::duration<double, std::milli>(now - st.windowStart).count();
        double overlapFraction = 1.0 - (elapsedInWindow / cfg_.windowMs);
        double estimated = st.prevCount * overlapFraction + st.currCount;

        if (estimated < cfg_.capacity) { ++st.currCount; return true; }
        return false;
    }

private:
    SlidingWindowState& stateFor(const std::string& clientId) {
        std::lock_guard<std::mutex> mapLock(mapMtx_);
        auto it = states_.find(clientId);
        if (it == states_.end()) {
            auto st = std::make_unique<SlidingWindowState>();
            st->windowStart = Clock::now();
            it = states_.emplace(clientId, std::move(st)).first;
        }
        return *it->second;
    }

    RateLimitConfig cfg_;
    std::mutex      mapMtx_;
    std::unordered_map<std::string, std::unique_ptr<SlidingWindowState>> states_;
};

// ============================================================
// The Factory: the one place that knows the enum. Adding a new
// algorithm later is a single new case here, no call site changes.
// ============================================================
std::unique_ptr<RateLimitStrategy>
RateLimiterFactory::create(AlgoType type, const RateLimitConfig& cfg) {
    switch (type) {
        case AlgoType::TOKEN_BUCKET:   return std::make_unique<TokenBucketLimiter>(cfg);
        case AlgoType::FIXED_WINDOW:   return std::make_unique<FixedWindowLimiter>(cfg);
        case AlgoType::SLIDING_WINDOW: return std::make_unique<SlidingWindowLimiter>(cfg);
        default: throw std::invalid_argument("unknown algorithm");
    }
}

// ============================================================
// The facade: holds one strategy, adds NO lock of its own. Every
// strategy already locks per client -- a second lock here would only
// rebuild the single global bottleneck the problem told us to avoid.
// ============================================================
class RateLimiter {
public:
    explicit RateLimiter(std::unique_ptr<RateLimitStrategy> strategy)
        : strategy_(std::move(strategy)) {}

    bool allowRequest(const std::string& clientId) {
        return strategy_->allowRequest(clientId);
    }

private:
    std::unique_ptr<RateLimitStrategy> strategy_;
};

// ============================================================
// Singleton config registry: per-tier limits (free vs premium),
// overwritable at runtime for dynamic reload. Whoever resolves a
// client's tier hands the resulting config to the Factory.
// ============================================================
class ConfigRegistry {
public:
    static ConfigRegistry& instance() {
        static ConfigRegistry r;
        return r;
    }

    RateLimitConfig configFor(const std::string& tier) {
        std::lock_guard<std::mutex> lock(mtx_);
        return tiers_.count(tier) ? tiers_[tier] : tiers_["default"];
    }

    void set(const std::string& tier, const RateLimitConfig& c) {
        std::lock_guard<std::mutex> lock(mtx_);
        tiers_[tier] = c;               // dynamic reload = overwrite under the lock
    }

private:
    ConfigRegistry() { tiers_["default"] = RateLimitConfig{}; }
    std::mutex mtx_;
    std::unordered_map<std::string, RateLimitConfig> tiers_;
};

// ============================================================
// Driver: burst, throttle, refill recovery, and per-client
// isolation under Token Bucket; the boundary burst under Fixed
// Window and its smoothing under Sliding Window; then a tiered
// config resolved through the Singleton and built by the Factory.
// ============================================================
int main() {
    // ---- Token Bucket ----
    RateLimitConfig tbCfg;
    tbCfg.capacity = 3; tbCfg.refillRate = 2.0;     // burst of 3, then ~2/sec steady

    RateLimiter tokenLimiter(RateLimiterFactory::create(AlgoType::TOKEN_BUCKET, tbCfg));

    std::cout << "== Token Bucket ==\n";
    for (int i = 0; i < 4; ++i)
        std::cout << "req " << i << ": "
                  << (tokenLimiter.allowRequest("alice") ? "OK" : "THROTTLED") << "\n";
    // OK, OK, OK, THROTTLED -- bucket of 3 drained

    std::this_thread::sleep_for(std::chrono::milliseconds(600));
    std::cout << "after 600ms wait: "
              << (tokenLimiter.allowRequest("alice") ? "OK" : "THROTTLED") << "\n"; // OK, ~1.2 tokens refilled

    std::cout << "bob (different client): "
              << (tokenLimiter.allowRequest("bob") ? "OK" : "THROTTLED") << "\n"; // OK -- independent bucket, independent lock

    // ---- Fixed Window ----
    RateLimitConfig fwCfg;
    fwCfg.capacity = 2; fwCfg.windowMs = 500;

    RateLimiter windowLimiter(RateLimiterFactory::create(AlgoType::FIXED_WINDOW, fwCfg));

    std::cout << "\n== Fixed Window ==\n";
    for (int i = 0; i < 3; ++i)
        std::cout << "req " << i << ": "
                  << (windowLimiter.allowRequest("carol") ? "OK" : "THROTTLED") << "\n";
    // OK, OK, THROTTLED -- 2 already spent this window

    std::this_thread::sleep_for(std::chrono::milliseconds(550));
    std::cout << "next window: "
              << (windowLimiter.allowRequest("carol") ? "OK" : "THROTTLED") << "\n"; // OK -- window reset

    // ---- Sliding Window: same shape, no boundary burst ----
    RateLimitConfig swCfg;
    swCfg.capacity = 2; swCfg.windowMs = 500;

    RateLimiter slidingLimiter(RateLimiterFactory::create(AlgoType::SLIDING_WINDOW, swCfg));

    std::cout << "\n== Sliding Window ==\n";
    slidingLimiter.allowRequest("dave");             // both requests spent right at
    slidingLimiter.allowRequest("dave");              // the tail end of the window
    std::this_thread::sleep_for(std::chrono::milliseconds(490));
    std::cout << "just after the boundary: "
              << (slidingLimiter.allowRequest("dave") ? "OK" : "THROTTLED")
              << "  (a fixed window would freely allow 2 more here)\n";

    // ---- Tiered config via the Singleton, resolved through the Factory ----
    ConfigRegistry::instance().set("premium", RateLimitConfig{100, 50.0, 1000});
    RateLimiter premiumLimiter(
        RateLimiterFactory::create(AlgoType::TOKEN_BUCKET,
                                    ConfigRegistry::instance().configFor("premium")));

    std::cout << "\n== Tiered config (premium) ==\n";
    std::cout << "premium client: "
              << (premiumLimiter.allowRequest("premium-client-1") ? "OK" : "THROTTLED") << "\n";

    return 0;
}

Strategy pattern

One interface (RateLimitStrategy), several interchangeable concrete implementations (Token Bucket, Fixed Window, Sliding Window), and one context (RateLimiter) that holds a pointer to the interface and never branches on which concrete type it was handed.

Lazy (on-read) refill

Reconstructing state from elapsed time at the moment it's needed, instead of mutating it continuously on a background timer. Store a timestamp; compute what should have happened since it, on read. O(1), no thread, no drift.

steady_clock

A monotonic C++ clock that never jumps backward, unlike system_clock, which can be adjusted by NTP. Elapsed-time math for refills and windows must use it, or a wall-clock adjustment could retroactively grant or revoke tokens.

Two-level locking

A brief lock on the shared map to find-or-create an entry, released immediately, followed by that entry's own lock held only for the per-client read-modify-write. Keeps unrelated clients from ever blocking each other.