coding challenges · advanced

Rate Limiter — Token Bucket + Hierarchical Limits

Microsoft event-gateway rate limiter. Each request passes two checks: a global per-event-type limit and a per-user-per-event limit. The algorithm is a token bucket with lazy refill — on each request, add elapsed×rate tokens (capped at capacity) using a monotonic steady_clock; consume one per request, reject when empty. Lazy refill makes it O(1) with no background timer and naturally allows bursts up to capacity. Extensibility (a stated NFR) comes from a Strategy interface ILimiter with a config-driven factory, so leaky/sliding-window algorithms drop in without changing the orchestrator (Open/Closed + dependency inversion). The orchestrator checks global first, then a lazily-created per-user bucket, under a lock. At scale, the single mutex is the bottleneck (use striped/per-bucket locks or atomics), the per-user map must be bounded (LRU/TTL eviction), and multi-node needs shared counters (Redis). Know token vs leaky vs fixed vs sliding window trade-offs.

🔑 Key line

Rate limiter = two-level check (global event limit, then per-user-per-event) using token buckets with LAZY refill (tokens += elapsed*rate, capped; steady_clock; O(1), no timer, allows bursts). Strategy interface (ILimiter) + factory from config makes algorithms pluggable (Open/Closed). At scale: striped locks for contention, LRU/TTL to bound memory, Redis for multi-node.

The code

// Rate limiter for an event gateway. Two levels per request:
//   (1) global limit for the event type, (2) per-user-per-event limit.
// Token bucket: 'capacity' tokens, refilled at 'rate' tokens/sec.
class TokenBucket {
    double capacity_, tokens_, rate_;            // rate = tokens per second
    std::chrono::steady_clock::time_point last_;
public:
    TokenBucket(double cap, double rate)
        : capacity_(cap), tokens_(cap), rate_(rate),
          last_(std::chrono::steady_clock::now()) {}

    bool allow(double cost = 1.0) {
        refill();
        if (tokens_ >= cost) { tokens_ -= cost; return true; }
        return false;                            // drop / 429
    }
private:
    void refill() {
        auto now = std::chrono::steady_clock::now();
        double dt = std::chrono::duration<double>(now - last_).count();
        tokens_ = std::min(capacity_, tokens_ + dt * rate_);  // lazy refill
        last_ = now;
    }
};

// Strategy interface lets you swap algorithms (leaky bucket, sliding window)
struct ILimiter { virtual bool allow() = 0; virtual ~ILimiter() = default; };

class RateLimiter {                              // orchestration layer
    std::unordered_map<EventType, TokenBucket> global_;        // per event type
    std::unordered_map<std::string, TokenBucket> userEvent_;   // "user:event" key
    std::mutex m_;
public:
    bool isAllowed(const std::string& user, EventType ev) {
        std::lock_guard<std::mutex> lk(m_);
        if (!global_.at(ev).allow()) return false;             // (1) global first
        auto& b = userEvent_[user + ":" + name(ev)];           // (2) per user
        return b.allow();
    }
};

What this lesson walks through

01Every request passes TWO gates
02Token bucket — consume one per request
03Empty bucket → reject (429)
04Lazy refill — no background timer
05Pluggable algorithm + scaling it

A request is allowed only if it passes the global limit for its event type (protect the service) AND the per-user limit (stop one user hogging). Check the cheap shared gate first, then the per-user one.

See it animated — step by step, at your own pace

Unlock the full interactive walkthrough of Rate Limiter — Token Bucket + Hierarchical Limits and 100+ animated C++ interview lessons.

Start free →Already a member? Log in →