Designing an In-Memory Rate Limiter

class RateLimiterConfig:
    def __init__(self, max_requests: int, window_size_ms: int):
        if max_requests <= 0:
            raise ValueError("max_requests must be positive")
        if window_size_ms <= 0:
            raise ValueError("window_size_ms must be positive")
        self._max_requests = max_requests
        self._window_size_ms = window_size_ms

    @property
    def max_requests(self) -> int:
        return self._max_requests

    @property
    def window_size_ms(self) -> int:
        return self._window_size_ms

    def __str__(self) -> str:
        return f"RateLimiterConfig[max={self._max_requests}, window={self._window_size_ms}ms]"

#pragma once
#include <stdexcept>
#include <string>

class RateLimiterConfig {
private:
    int maxRequests;
    long long windowSizeMs;

public:
    RateLimiterConfig(int maxRequests, long long windowSizeMs)
        : maxRequests(maxRequests), windowSizeMs(windowSizeMs) {
        if (maxRequests <= 0) throw std::invalid_argument("maxRequests must be positive");
        if (windowSizeMs <= 0) throw std::invalid_argument("windowSizeMs must be positive");
    }

    int getMaxRequests() const { return maxRequests; }
    long long getWindowSizeMs() const { return windowSizeMs; }

    std::string toString() const {
        return "RateLimiterConfig[max=" + std::to_string(maxRequests) +
               ", window=" + std::to_string(windowSizeMs) + "ms]";
    }
};

from abc import ABC, abstractmethod

class RateLimitStrategy(ABC):
    @abstractmethod
    def allow_request(self, key: str) -> bool:
        """Determine if a request from the given key should be allowed."""
        pass

    @abstractmethod
    def get_remaining_quota(self, key: str) -> int:
        """Get the remaining quota for the given key."""
        pass

#pragma once
#include <string>

class RateLimitStrategy {
public:
    virtual ~RateLimitStrategy() = default;

    /**
     * Determine if a request from the given key should be allowed.
     * @param key unique identifier for the client
     * @return true if allowed, false if rate limited
     */
    virtual bool allowRequest(const std::string& key) = 0;

    /**
     * Get the remaining quota for the given key.
     * @param key unique identifier for the client
     * @return number of remaining requests allowed in current window
     */
    virtual int getRemainingQuota(const std::string& key) = 0;
};

import time
import threading

class TokenBucketStrategy(RateLimitStrategy):
    def __init__(self, config: RateLimiterConfig):
        self._max_tokens = config.max_requests
        # Refill entire bucket over one window period
        self._refill_rate_per_ms = config.max_requests / config.window_size_ms
        self._buckets: dict[str, dict] = {}
        self._lock = threading.Lock()

    def allow_request(self, key: str) -> bool:
        with self._lock:
            now = time.time() * 1000  # current time in ms
            if key not in self._buckets:
                self._buckets[key] = {
                    "tokens": self._max_tokens,
                    "last_refill": now
                }

            bucket = self._buckets[key]

            # Refill tokens based on elapsed time
            elapsed = now - bucket["last_refill"]
            bucket["tokens"] = min(
                self._max_tokens,
                bucket["tokens"] + elapsed * self._refill_rate_per_ms
            )
            bucket["last_refill"] = now

            if bucket["tokens"] >= 1.0:
                bucket["tokens"] -= 1.0
                return True
            return False

    def get_remaining_quota(self, key: str) -> int:
        with self._lock:
            now = time.time() * 1000
            if key not in self._buckets:
                return self._max_tokens

            bucket = self._buckets[key]
            elapsed = now - bucket["last_refill"]
            current_tokens = min(
                self._max_tokens,
                bucket["tokens"] + elapsed * self._refill_rate_per_ms
            )
            return int(current_tokens)

#pragma once
#include <unordered_map>
#include <mutex>
#include <chrono>
#include <algorithm>
#include "RateLimitStrategy.hpp"
#include "RateLimiterConfig.hpp"

class TokenBucketStrategy : public RateLimitStrategy {
private:
    struct Bucket {
        double tokens;
        long long lastRefillTimestamp;
    };

    int maxTokens;
    double refillRatePerMs;
    std::unordered_map<std::string, Bucket> buckets;
    std::mutex mtx;

    long long nowMs() const {
        return std::chrono::duration_cast<std::chrono::milliseconds>(
            std::chrono::system_clock::now().time_since_epoch()
        ).count();
    }

public:
    TokenBucketStrategy(const RateLimiterConfig& config)
        : maxTokens(config.getMaxRequests()),
          refillRatePerMs(static_cast<double>(config.getMaxRequests()) / config.getWindowSizeMs()) {}

    bool allowRequest(const std::string& key) override {
        std::lock_guard<std::mutex> lock(mtx);
        long long now = nowMs();

        auto it = buckets.find(key);
        if (it == buckets.end()) {
            buckets[key] = Bucket{static_cast<double>(maxTokens), now};
            it = buckets.find(key);
        }

        Bucket& bucket = it->second;

        // Refill tokens based on elapsed time
        long long elapsed = now - bucket.lastRefillTimestamp;
        bucket.tokens = std::min(static_cast<double>(maxTokens),
                                  bucket.tokens + elapsed * refillRatePerMs);
        bucket.lastRefillTimestamp = now;

        if (bucket.tokens >= 1.0) {
            bucket.tokens -= 1.0;
            return true;
        }
        return false;
    }

    int getRemainingQuota(const std::string& key) override {
        std::lock_guard<std::mutex> lock(mtx);
        long long now = nowMs();

        auto it = buckets.find(key);
        if (it == buckets.end()) return maxTokens;

        const Bucket& bucket = it->second;
        long long elapsed = now - bucket.lastRefillTimestamp;
        double currentTokens = std::min(static_cast<double>(maxTokens),
                                         bucket.tokens + elapsed * refillRatePerMs);
        return static_cast<int>(currentTokens);
    }
};

import time
import threading
from collections import deque

class SlidingWindowLogStrategy(RateLimitStrategy):
    def __init__(self, config: RateLimiterConfig):
        self._max_requests = config.max_requests
        self._window_size_ms = config.window_size_ms
        self._client_logs: dict[str, deque] = {}
        self._lock = threading.Lock()

    def allow_request(self, key: str) -> bool:
        with self._lock:
            now = time.time() * 1000
            if key not in self._client_logs:
                self._client_logs[key] = deque()

            log = self._client_logs[key]

            # Evict timestamps outside the current window
            window_start = now - self._window_size_ms
            while log and log[0] <= window_start:
                log.popleft()

            if len(log) < self._max_requests:
                log.append(now)
                return True
            return False

    def get_remaining_quota(self, key: str) -> int:
        with self._lock:
            now = time.time() * 1000
            if key not in self._client_logs:
                return self._max_requests

            log = self._client_logs[key]
            window_start = now - self._window_size_ms
            count = sum(1 for ts in log if ts > window_start)
            return max(0, self._max_requests - count)

#pragma once
#include <unordered_map>
#include <deque>
#include <mutex>
#include <chrono>
#include <algorithm>
#include "RateLimitStrategy.hpp"
#include "RateLimiterConfig.hpp"

class SlidingWindowLogStrategy : public RateLimitStrategy {
private:
    int maxRequests;
    long long windowSizeMs;
    std::unordered_map<std::string, std::deque<long long>> clientLogs;
    std::mutex mtx;

    long long nowMs() const {
        return std::chrono::duration_cast<std::chrono::milliseconds>(
            std::chrono::system_clock::now().time_since_epoch()
        ).count();
    }

public:
    SlidingWindowLogStrategy(const RateLimiterConfig& config)
        : maxRequests(config.getMaxRequests()),
          windowSizeMs(config.getWindowSizeMs()) {}

    bool allowRequest(const std::string& key) override {
        std::lock_guard<std::mutex> lock(mtx);
        long long now = nowMs();
        long long windowStart = now - windowSizeMs;

        auto& log = clientLogs[key];

        // Evict timestamps outside the current window
        while (!log.empty() && log.front() <= windowStart) {
            log.pop_front();
        }

        if (static_cast<int>(log.size()) < maxRequests) {
            log.push_back(now);
            return true;
        }
        return false;
    }

    int getRemainingQuota(const std::string& key) override {
        std::lock_guard<std::mutex> lock(mtx);
        long long now = nowMs();
        long long windowStart = now - windowSizeMs;

        auto it = clientLogs.find(key);
        if (it == clientLogs.end()) return maxRequests;

        int count = 0;
        for (long long ts : it->second) {
            if (ts > windowStart) count++;
        }
        return std::max(0, maxRequests - count);
    }
};

import time
import threading

class FixedWindowCounterStrategy(RateLimitStrategy):
    def __init__(self, config: RateLimiterConfig):
        self._max_requests = config.max_requests
        self._window_size_ms = config.window_size_ms
        self._counters: dict[str, dict] = {}
        self._lock = threading.Lock()

    def allow_request(self, key: str) -> bool:
        with self._lock:
            now = time.time() * 1000
            if key not in self._counters:
                self._counters[key] = {"count": 0, "window_start": now}

            counter = self._counters[key]

            # Check if the current window has expired
            if now - counter["window_start"] >= self._window_size_ms:
                counter["count"] = 0
                counter["window_start"] = now

            if counter["count"] < self._max_requests:
                counter["count"] += 1
                return True
            return False

    def get_remaining_quota(self, key: str) -> int:
        with self._lock:
            now = time.time() * 1000
            if key not in self._counters:
                return self._max_requests

            counter = self._counters[key]
            if now - counter["window_start"] >= self._window_size_ms:
                return self._max_requests
            return max(0, self._max_requests - counter["count"])

#pragma once
#include <unordered_map>
#include <mutex>
#include <chrono>
#include <algorithm>
#include "RateLimitStrategy.hpp"
#include "RateLimiterConfig.hpp"

class FixedWindowCounterStrategy : public RateLimitStrategy {
private:
    struct WindowCounter {
        int count;
        long long windowStart;
    };

    int maxRequests;
    long long windowSizeMs;
    std::unordered_map<std::string, WindowCounter> counters;
    std::mutex mtx;

    long long nowMs() const {
        return std::chrono::duration_cast<std::chrono::milliseconds>(
            std::chrono::system_clock::now().time_since_epoch()
        ).count();
    }

public:
    FixedWindowCounterStrategy(const RateLimiterConfig& config)
        : maxRequests(config.getMaxRequests()),
          windowSizeMs(config.getWindowSizeMs()) {}

    bool allowRequest(const std::string& key) override {
        std::lock_guard<std::mutex> lock(mtx);
        long long now = nowMs();

        auto it = counters.find(key);
        if (it == counters.end()) {
            counters[key] = WindowCounter{0, now};
            it = counters.find(key);
        }

        WindowCounter& counter = it->second;

        // Check if the current window has expired
        if (now - counter.windowStart >= windowSizeMs) {
            counter.count = 0;
            counter.windowStart = now;
        }

        if (counter.count < maxRequests) {
            counter.count++;
            return true;
        }
        return false;
    }

    int getRemainingQuota(const std::string& key) override {
        std::lock_guard<std::mutex> lock(mtx);
        long long now = nowMs();

        auto it = counters.find(key);
        if (it == counters.end()) return maxRequests;

        const WindowCounter& counter = it->second;
        if (now - counter.windowStart >= windowSizeMs) {
            return maxRequests;
        }
        return std::max(0, maxRequests - counter.count);
    }
};

from enum import Enum

class RateLimitAlgorithm(Enum):
    TOKEN_BUCKET = "TOKEN_BUCKET"
    SLIDING_WINDOW_LOG = "SLIDING_WINDOW_LOG"
    FIXED_WINDOW_COUNTER = "FIXED_WINDOW_COUNTER"

class RateLimiterFactory:
    @staticmethod
    def create(algorithm: RateLimitAlgorithm, config: RateLimiterConfig) -> "RateLimiter":
        if algorithm == RateLimitAlgorithm.TOKEN_BUCKET:
            strategy = TokenBucketStrategy(config)
        elif algorithm == RateLimitAlgorithm.SLIDING_WINDOW_LOG:
            strategy = SlidingWindowLogStrategy(config)
        elif algorithm == RateLimitAlgorithm.FIXED_WINDOW_COUNTER:
            strategy = FixedWindowCounterStrategy(config)
        else:
            raise ValueError(f"Unknown algorithm: {algorithm}")
        return RateLimiter(strategy)

#pragma once
#include <memory>
#include <stdexcept>
#include "RateLimiter.hpp"
#include "TokenBucketStrategy.hpp"
#include "SlidingWindowLogStrategy.hpp"
#include "FixedWindowCounterStrategy.hpp"

enum class RateLimitAlgorithm {
    TOKEN_BUCKET,
    SLIDING_WINDOW_LOG,
    FIXED_WINDOW_COUNTER
};

class RateLimiterFactory {
public:
    static RateLimiter create(RateLimitAlgorithm algorithm, const RateLimiterConfig& config) {
        std::unique_ptr<RateLimitStrategy> strategy;
        switch (algorithm) {
            case RateLimitAlgorithm::TOKEN_BUCKET:
                strategy = std::make_unique<TokenBucketStrategy>(config);
                break;
            case RateLimitAlgorithm::SLIDING_WINDOW_LOG:
                strategy = std::make_unique<SlidingWindowLogStrategy>(config);
                break;
            case RateLimitAlgorithm::FIXED_WINDOW_COUNTER:
                strategy = std::make_unique<FixedWindowCounterStrategy>(config);
                break;
            default:
                throw std::invalid_argument("Unknown algorithm");
        }
        return RateLimiter(std::move(strategy));
    }
};

import threading

class RateLimiter:
    def __init__(self, strategy: RateLimitStrategy):
        if strategy is None:
            raise ValueError("Strategy cannot be None")
        self._strategy = strategy
        self._lock = threading.RLock()

    def allow_request(self, key: str) -> bool:
        """Check if a request from the given key is allowed. Thread-safe."""
        with self._lock:
            return self._strategy.allow_request(key)

    def get_remaining_quota(self, key: str) -> int:
        """Get remaining quota for the given key."""
        with self._lock:
            return self._strategy.get_remaining_quota(key)

    def set_strategy(self, new_strategy: RateLimitStrategy) -> None:
        """Swap the rate limiting strategy at runtime."""
        if new_strategy is None:
            raise ValueError("Strategy cannot be None")
        with self._lock:
            self._strategy = new_strategy

#pragma once
#include <memory>
#include <shared_mutex>
#include <stdexcept>
#include "RateLimitStrategy.hpp"

class RateLimiter {
private:
    std::unique_ptr<RateLimitStrategy> strategy;
    mutable std::shared_mutex mtx;

public:
    RateLimiter(std::unique_ptr<RateLimitStrategy> strategy)
        : strategy(std::move(strategy)) {
        if (!this->strategy) throw std::invalid_argument("Strategy cannot be null");
    }

    // Move constructor for factory usage
    RateLimiter(RateLimiter&& other) noexcept
        : strategy(std::move(other.strategy)) {}

    RateLimiter& operator=(RateLimiter&& other) noexcept {
        strategy = std::move(other.strategy);
        return *this;
    }

    /**
     * Check if a request from the given key is allowed.
     * Thread-safe — uses a shared lock for concurrent reads.
     */
    bool allowRequest(const std::string& key) {
        std::shared_lock<std::shared_mutex> lock(mtx);
        return strategy->allowRequest(key);
    }

    /**
     * Get remaining quota for the given key.
     */
    int getRemainingQuota(const std::string& key) {
        std::shared_lock<std::shared_mutex> lock(mtx);
        return strategy->getRemainingQuota(key);
    }

    /**
     * Swap the rate limiting strategy at runtime.
     * Uses an exclusive lock to ensure no requests are mid-flight during the swap.
     */
    void setStrategy(std::unique_ptr<RateLimitStrategy> newStrategy) {
        if (!newStrategy) throw std::invalid_argument("Strategy cannot be null");
        std::unique_lock<std::shared_mutex> lock(mtx);
        strategy = std::move(newStrategy);
    }
};

import time

def test_limiter(limiter: RateLimiter, key: str):
    print(f"Sending 8 requests for key: {key}")
    for i in range(1, 9):
        allowed = limiter.allow_request(key)
        remaining = limiter.get_remaining_quota(key)
        status = "ALLOWED" if allowed else "DENIED"
        print(f"  Request {i}: {status} (remaining: {remaining})")


def main():
    # Config: 5 requests per 1000ms (1 second)
    config = RateLimiterConfig(max_requests=5, window_size_ms=1000)

    print("=== Token Bucket Strategy ===")
    limiter = RateLimiterFactory.create(RateLimitAlgorithm.TOKEN_BUCKET, config)
    test_limiter(limiter, "user-1")

    print("\n=== Sliding Window Log Strategy ===")
    limiter.set_strategy(SlidingWindowLogStrategy(config))
    test_limiter(limiter, "user-2")

    print("\n=== Fixed Window Counter Strategy ===")
    limiter.set_strategy(FixedWindowCounterStrategy(config))
    test_limiter(limiter, "user-3")

    print("\n=== Per-Client Isolation Test ===")
    isolation_limiter = RateLimiterFactory.create(RateLimitAlgorithm.TOKEN_BUCKET, config)
    # client-A uses up all tokens
    for _ in range(5):
        isolation_limiter.allow_request("client-A")
    # client-B should still have full quota
    print(f"client-A remaining: {isolation_limiter.get_remaining_quota('client-A')}")
    print(f"client-B remaining: {isolation_limiter.get_remaining_quota('client-B')}")

    print("\n=== Refill Test (Token Bucket) ===")
    refill_limiter = RateLimiterFactory.create(RateLimitAlgorithm.TOKEN_BUCKET, config)
    # Exhaust tokens
    for _ in range(5):
        refill_limiter.allow_request("user-refill")
    print(f"After exhausting: {refill_limiter.get_remaining_quota('user-refill')}")
    # Wait for refill
    time.sleep(1.1)
    print(f"After 1.1s wait: {refill_limiter.get_remaining_quota('user-refill')}")


if __name__ == "__main__":
    main()

#include <iostream>
#include <thread>
#include <chrono>
#include "RateLimiterConfig.hpp"
#include "RateLimiterFactory.hpp"

void testLimiter(RateLimiter& limiter, const std::string& key) {
    std::cout << "Sending 8 requests for key: " << key << std::endl;
    for (int i = 1; i <= 8; i++) {
        bool allowed = limiter.allowRequest(key);
        int remaining = limiter.getRemainingQuota(key);
        std::cout << "  Request " << i << ": "
                  << (allowed ? "ALLOWED" : "DENIED")
                  << " (remaining: " << remaining << ")" << std::endl;
    }
}

int main() {
    // Config: 5 requests per 1000ms (1 second)
    RateLimiterConfig config(5, 1000);

    std::cout << "=== Token Bucket Strategy ===" << std::endl;
    auto limiter = RateLimiterFactory::create(RateLimitAlgorithm::TOKEN_BUCKET, config);
    testLimiter(limiter, "user-1");

    std::cout << "\n=== Sliding Window Log Strategy ===" << std::endl;
    limiter.setStrategy(std::make_unique<SlidingWindowLogStrategy>(config));
    testLimiter(limiter, "user-2");

    std::cout << "\n=== Fixed Window Counter Strategy ===" << std::endl;
    limiter.setStrategy(std::make_unique<FixedWindowCounterStrategy>(config));
    testLimiter(limiter, "user-3");

    std::cout << "\n=== Per-Client Isolation Test ===" << std::endl;
    auto isolationLimiter = RateLimiterFactory::create(RateLimitAlgorithm::TOKEN_BUCKET, config);
    // client-A uses up all tokens
    for (int i = 0; i < 5; i++) {
        isolationLimiter.allowRequest("client-A");
    }
    // client-B should still have full quota
    std::cout << "client-A remaining: " << isolationLimiter.getRemainingQuota("client-A") << std::endl;
    std::cout << "client-B remaining: " << isolationLimiter.getRemainingQuota("client-B") << std::endl;

    std::cout << "\n=== Refill Test (Token Bucket) ===" << std::endl;
    auto refillLimiter = RateLimiterFactory::create(RateLimitAlgorithm::TOKEN_BUCKET, config);
    // Exhaust tokens
    for (int i = 0; i < 5; i++) {
        refillLimiter.allowRequest("user-refill");
    }
    std::cout << "After exhausting: " << refillLimiter.getRemainingQuota("user-refill") << std::endl;
    // Wait for refill
    std::this_thread::sleep_for(std::chrono::milliseconds(1100));
    std::cout << "After 1.1s wait: " << refillLimiter.getRemainingQuota("user-refill") << std::endl;

    return 0;
}