📌 1. Functional Requirements

A Rate Limiter system should:

• Limit requests per client/user

• Support multiple rate limiting algorithms

• Allow dynamic algorithm switching

• Support different limits per client

• Return Allow / Deny decision

• Track usage statistics

• Log rate limit violations

• Be extensible for distributed systems

📌 2. Non-Functional Requirements

• High performance (O(1) where possible)

• Extensible architecture

• Clean separation of concerns

• Algorithm pluggability

• Easy to test

📌 3. Supported Algorithms

We implement four major algorithms:

1️⃣ Fixed Window Counter

Idea: Allow N requests per time window.

Example:
Limit = 3 requests
Window = 10 seconds

After 3 requests → deny until window resets.

⏱ Complexity

• Time: O(1)

• Space: O(n clients)

2️⃣ Sliding Window Log

Idea: Store timestamps of each request.

Before allowing:

• Remove old timestamps

• Check remaining count

⏱ Complexity

• Time: O(k) (k = requests in window)

• Space: O(n × k)

3️⃣ Token Bucket

Idea:

• Tokens refill over time

• Each request consumes 1 token

• If no token → deny

⏱ Complexity

• Time: O(1)

• Space: O(n)

4️⃣ Leaky Bucket

Idea:

• Requests enter queue

• Requests leak at constant rate

• If queue full → deny

⏱ Complexity

• Time: O(1)

• Space: O(n × k)

📌 4. Design Patterns Used

Pattern	Where Used	Why
Strategy	Algorithms	Switch rate limiting strategy dynamically
Factory Method	Create limiter	Encapsulate creation logic
Singleton	Manager	One global configuration
Observer	Logging	Notify on rate limit exceed
Decorator	Logging wrapper	Add behavior without modifying core
Builder	Config creation	Clean configuration building
Repository	Client storage	Abstract client data layer
Command	Request execution	Encapsulate request action
Template Method	BaseRateLimiter	Standardize flow

📌 5. Class Design

classDiagram
    class Observer {
        <<abstract>>
        +update(string message) void
    }
    class Logger {
        +update(string message) void
    }
    Observer <|-- Logger

    class RateLimiterConfig {
        +int limit
        +int windowSize
    }

    class RateLimiterConfigBuilder {
        -RateLimiterConfig config
        +setLimit(int) Builder
        +setWindowSize(int) Builder
        +build() RateLimiterConfig
    }
    RateLimiterConfigBuilder --> RateLimiterConfig : creates

    class BaseRateLimiter {
        <<abstract>>
        #RateLimiterConfig config
        +BaseRateLimiter(RateLimiterConfig cfg)
        +allowRequest(string id) bool
        +process(string id) bool
    }
    BaseRateLimiter *-- RateLimiterConfig : contains

    class FixedWindowLimiter {
        -Map_Counter counter
        +process(string id) bool
    }
    BaseRateLimiter <|-- FixedWindowLimiter

    class SlidingWindowLimiter {
        -Map_Logs logs
        +process(string id) bool
    }
    BaseRateLimiter <|-- SlidingWindowLimiter

    class TokenBucketLimiter {
        -Map_Buckets buckets
        +process(string id) bool
    }
    BaseRateLimiter <|-- TokenBucketLimiter

    class LeakyBucketLimiter {
        -Map_Buckets buckets
        +process(string id) bool
    }
    BaseRateLimiter <|-- LeakyBucketLimiter

    class RateLimiterFactory {
        +createLimiter(string type, Config cfg) BaseLimiter
    }
    RateLimiterFactory --> BaseRateLimiter : creates

    class RateLimiterDecorator {
        #BaseLimiter limiter
        +RateLimiterDecorator(BaseLimiter l)
    }
    BaseRateLimiter <|-- RateLimiterDecorator
    RateLimiterDecorator o-- BaseRateLimiter : decorates

    class LoggingDecorator {
        -Observer observer
        +LoggingDecorator(BaseLimiter l, Observer obs)
        +process(string id) bool
    }
    RateLimiterDecorator <|-- LoggingDecorator
    LoggingDecorator --> Observer : notifies

    class ClientRepository {
        -Map_Clients clients
        +addClient(string id) void
        +exists(string id) bool
    }

    class Command {
        <<abstract>>
        +execute() void
    }
    class RequestCommand {
        -BaseLimiter limiter
        -string id
        +RequestCommand(BaseLimiter l, string id)
        +execute() void
    }
    Command <|-- RequestCommand
    RequestCommand --> BaseRateLimiter : uses

    class RateLimiterManager {
        -BaseLimiter limiter
        -RateLimiterManager()
        +getInstance() Manager
        +setLimiter(BaseLimiter l) void
        +getLimiter() BaseLimiter
    }
    RateLimiterManager o-- BaseRateLimiter : holds

📌 6. Complete C++ Implementation (Single Threaded)

⚠️ This is intentionally single-threaded for machine coding clarity.

🔹 1. Observer Pattern (Logger)

class Observer {
public:
    virtual void update(string message) = 0;
    virtual ~Observer() {}
};

class Logger : public Observer {
public:
    void update(string message) override {
        cout << "[LOG]: " << message << endl;
    }
};

🔹 2. Builder Pattern (Configuration)

class RateLimiterConfig {
public:
    int limit;
    int windowSize;
};

class RateLimiterConfigBuilder {
private:
    RateLimiterConfig config;

public:
    RateLimiterConfigBuilder& setLimit(int l) {
        config.limit = l;
        return *this;
    }

    RateLimiterConfigBuilder& setWindowSize(int w) {
        config.windowSize = w;
        return *this;
    }

    RateLimiterConfig build() {
        return config;
    }
};

🔹 3. Template Method Pattern

class BaseRateLimiter {
protected:
    RateLimiterConfig config;

public:
    BaseRateLimiter(RateLimiterConfig cfg) : config(cfg) {}

    bool allowRequest(string clientId) {
        return process(clientId);
    }

    virtual bool process(string clientId) = 0;
    virtual ~BaseRateLimiter() {}
};

📌 7. Strategy Pattern (All Algorithms)

🔹 Fixed Window

class FixedWindowLimiter : public BaseRateLimiter {
private:
    unordered_map<string, pair<int, time_t>> counter;

public:
    FixedWindowLimiter(RateLimiterConfig cfg)
        : BaseRateLimiter(cfg) {}

    bool process(string clientId) override {
        time_t now = time(nullptr);

        if(counter[clientId].second + config.windowSize <= now) {
            counter[clientId] = {1, now};
            return true;
        }

        if(counter[clientId].first < config.limit) {
            counter[clientId].first++;
            return true;
        }

        return false;
    }
};

🔹 Sliding Window

class SlidingWindowLimiter : public BaseRateLimiter {
private:
    unordered_map<string, vector<time_t>> logs;

public:
    SlidingWindowLimiter(RateLimiterConfig cfg)
        : BaseRateLimiter(cfg) {}

    bool process(string clientId) override {
        time_t now = time(nullptr);
        auto& timestamps = logs[clientId];

        timestamps.erase(remove_if(timestamps.begin(), timestamps.end(),
            [&](time_t t) { return t <= now - config.windowSize; }),
            timestamps.end());

        if(timestamps.size() < config.limit) {
            timestamps.push_back(now);
            return true;
        }

        return false;
    }
};

🔹 Token Bucket

class TokenBucketLimiter : public BaseRateLimiter {
private:
    struct Bucket {
        int tokens = 0;
        time_t lastRefill = 0;
    };

    unordered_map<string, Bucket> buckets;

public:
    TokenBucketLimiter(RateLimiterConfig cfg)
        : BaseRateLimiter(cfg) {}

    bool process(string clientId) override {
        time_t now = time(nullptr);
        auto& bucket = buckets[clientId];

        if(bucket.tokens == 0) {
            bucket.tokens = config.limit;
            bucket.lastRefill = now;
        }

        int refill = now - bucket.lastRefill;
        if(refill > 0) {
            bucket.tokens = min(config.limit, bucket.tokens + refill);
            bucket.lastRefill = now;
        }

        if(bucket.tokens > 0) {
            bucket.tokens--;
            return true;
        }

        return false;
    }
};

🔹 Leaky Bucket

class LeakyBucketLimiter : public BaseRateLimiter {
private:
    struct Bucket {
        queue<time_t> requests;
    };

    unordered_map<string, Bucket> buckets;

public:
    LeakyBucketLimiter(RateLimiterConfig cfg)
        : BaseRateLimiter(cfg) {}

    bool process(string clientId) override {
        time_t now = time(nullptr);
        auto& bucket = buckets[clientId];

        while(!bucket.requests.empty() &&
              bucket.requests.front() <= now - config.windowSize) {
            bucket.requests.pop();
        }

        if(bucket.requests.size() < config.limit) {
            bucket.requests.push(now);
            return true;
        }

        return false;
    }
};

📌 8. Factory Pattern

class RateLimiterFactory {
public:
    static shared_ptr<BaseRateLimiter> createLimiter(
        string type, RateLimiterConfig config) {

        if(type == "FIXED")
            return make_shared<FixedWindowLimiter>(config);
        if(type == "SLIDING")
            return make_shared<SlidingWindowLimiter>(config);
        if(type == "TOKEN")
            return make_shared<TokenBucketLimiter>(config);
        if(type == "LEAKY")
            return make_shared<LeakyBucketLimiter>(config);

        return nullptr;
    }
};

📌 9. Decorator Pattern (Logging)

class RateLimiterDecorator : public BaseRateLimiter {
protected:
    shared_ptr<BaseRateLimiter> limiter;

public:
    RateLimiterDecorator(shared_ptr<BaseRateLimiter> l)
        : BaseRateLimiter(l->config), limiter(l) {}
};

class LoggingDecorator : public RateLimiterDecorator {
private:
    Observer* observer;

public:
    LoggingDecorator(shared_ptr<BaseRateLimiter> l, Observer* obs)
        : RateLimiterDecorator(l), observer(obs) {}

    bool process(string clientId) override {
        bool allowed = limiter->allowRequest(clientId);

        if(!allowed)
            observer->update("Rate limit exceeded for: " + clientId);

        return allowed;
    }
};

📌 10. Repository Pattern

class ClientRepository {
private:
    unordered_map<string, int> clients;

public:
    void addClient(string id) {
        clients[id] = 1;
    }

    bool exists(string id) {
        return clients.count(id);
    }
};

📌 11. Command Pattern

class Command {
public:
    virtual void execute() = 0;
    virtual ~Command() {}
};

class RequestCommand : public Command {
private:
    shared_ptr<BaseRateLimiter> limiter;
    string clientId;

public:
    RequestCommand(shared_ptr<BaseRateLimiter> l, string id)
        : limiter(l), clientId(id) {}

    void execute() override {
        bool allowed = limiter->allowRequest(clientId);
        cout << "Request for " << clientId
             << (allowed ? " Allowed" : " Denied") << endl;
    }
};

📌 12. Singleton Manager

class RateLimiterManager {
private:
    shared_ptr<BaseRateLimiter> limiter;

    RateLimiterManager() {}

public:
    static RateLimiterManager& getInstance() {
        static RateLimiterManager instance;
        return instance;
    }

    void setLimiter(shared_ptr<BaseRateLimiter> l) {
        limiter = l;
    }

    shared_ptr<BaseRateLimiter> getLimiter() {
        return limiter;
    }
};

📌 13. Main Function

int main() {

    RateLimiterConfig config =
        RateLimiterConfigBuilder()
            .setLimit(3)
            .setWindowSize(10)
            .build();

    auto limiter = RateLimiterFactory::createLimiter("SLIDING", config);

    Logger logger;
    auto decoratedLimiter =
        make_shared<LoggingDecorator>(limiter, &logger);

    RateLimiterManager::getInstance().setLimiter(decoratedLimiter);

    string client = "clientA";

    for(int i = 0; i < 5; i++) {
        RequestCommand cmd(
            RateLimiterManager::getInstance().getLimiter(),
            client
        );
        cmd.execute();
    }

    return 0;
}

Complete running code

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
#include <memory>
#include <ctime>

using namespace std;

//////////////////////////////////////////////////////////////
// OBSERVER PATTERN
//////////////////////////////////////////////////////////////

class Observer {
public:
    virtual void update(string message) = 0;
    virtual ~Observer() {}
};

class Logger : public Observer {
public:
    void update(string message) override {
        cout << "[LOG]: " << message << endl;
    }
};

//////////////////////////////////////////////////////////////
// BUILDER PATTERN
//////////////////////////////////////////////////////////////

class RateLimiterConfig {
public:
    int limit;
    int windowSize;
};

class RateLimiterConfigBuilder {
private:
    RateLimiterConfig config;

public:
    RateLimiterConfigBuilder& setLimit(int l) {
        config.limit = l;
        return *this;
    }

    RateLimiterConfigBuilder& setWindowSize(int w) {
        config.windowSize = w;
        return *this;
    }

    RateLimiterConfig build() {
        return config;
    }
};

//////////////////////////////////////////////////////////////
// TEMPLATE METHOD PATTERN
//////////////////////////////////////////////////////////////

class BaseRateLimiter {
protected:
    RateLimiterConfig config;

public:
    BaseRateLimiter(RateLimiterConfig cfg) : config(cfg) {}

    bool allowRequest(string clientId) {
        return process(clientId);
    }

    virtual bool process(string clientId) = 0;
    virtual ~BaseRateLimiter() {}
};

//////////////////////////////////////////////////////////////
// STRATEGY PATTERN (Algorithms)
//////////////////////////////////////////////////////////////

class FixedWindowLimiter : public BaseRateLimiter {
private:
    unordered_map<string, pair<int, time_t>> counter;

public:
    FixedWindowLimiter(RateLimiterConfig cfg)
        : BaseRateLimiter(cfg) {}

    bool process(string clientId) override {
        time_t now = time(nullptr);

        if(counter[clientId].second + config.windowSize <= now) {
            counter[clientId] = {1, now};
            return true;
        }

        if(counter[clientId].first < config.limit) {
            counter[clientId].first++;
            return true;
        }

        return false;
    }
};

class SlidingWindowLimiter : public BaseRateLimiter {
private:
    unordered_map<string, vector<time_t>> logs;

public:
    SlidingWindowLimiter(RateLimiterConfig cfg)
        : BaseRateLimiter(cfg) {}

    bool process(string clientId) override {
        time_t now = time(nullptr);
        auto& timestamps = logs[clientId];

        timestamps.erase(remove_if(timestamps.begin(), timestamps.end(),
            [&](time_t t) { return t <= now - config.windowSize; }),
            timestamps.end());

        if(timestamps.size() < config.limit) {
            timestamps.push_back(now);
            return true;
        }

        return false;
    }
};

class TokenBucketLimiter : public BaseRateLimiter {
private:
    struct Bucket {
        int tokens;
        time_t lastRefill;
    };

    unordered_map<string, Bucket> buckets;

public:
    TokenBucketLimiter(RateLimiterConfig cfg)
        : BaseRateLimiter(cfg) {}

    bool process(string clientId) override {
        time_t now = time(nullptr);
        auto& bucket = buckets[clientId];

        if(bucket.tokens == 0) {
            bucket.tokens = config.limit;
            bucket.lastRefill = now;
        }

        int refill = (now - bucket.lastRefill);
        if(refill > 0) {
            bucket.tokens = min(config.limit, bucket.tokens + refill);
            bucket.lastRefill = now;
        }

        if(bucket.tokens > 0) {
            bucket.tokens--;
            return true;
        }

        return false;
    }
};

class LeakyBucketLimiter : public BaseRateLimiter {
private:
    struct Bucket {
        queue<time_t> requests;
    };

    unordered_map<string, Bucket> buckets;

public:
    LeakyBucketLimiter(RateLimiterConfig cfg)
        : BaseRateLimiter(cfg) {}

    bool process(string clientId) override {
        time_t now = time(nullptr);
        auto& bucket = buckets[clientId];

        while(!bucket.requests.empty() &&
              bucket.requests.front() <= now - config.windowSize) {
            bucket.requests.pop();
        }

        if(bucket.requests.size() < config.limit) {
            bucket.requests.push(now);
            return true;
        }

        return false;
    }
};

//////////////////////////////////////////////////////////////
// FACTORY METHOD
//////////////////////////////////////////////////////////////

class RateLimiterFactory {
public:
    static shared_ptr<BaseRateLimiter> createLimiter(
        string type, RateLimiterConfig config) {

        if(type == "FIXED")
            return make_shared<FixedWindowLimiter>(config);
        if(type == "SLIDING")
            return make_shared<SlidingWindowLimiter>(config);
        if(type == "TOKEN")
            return make_shared<TokenBucketLimiter>(config);
        if(type == "LEAKY")
            return make_shared<LeakyBucketLimiter>(config);

        return nullptr;
    }
};

//////////////////////////////////////////////////////////////
// DECORATOR PATTERN (Logging)
//////////////////////////////////////////////////////////////

class RateLimiterDecorator : public BaseRateLimiter {
protected:
    shared_ptr<BaseRateLimiter> limiter;

public:
    RateLimiterDecorator(shared_ptr<BaseRateLimiter> l)
        : BaseRateLimiter(l->config), limiter(l) {}
};

class LoggingDecorator : public RateLimiterDecorator {
private:
    Observer* observer;

public:
    LoggingDecorator(shared_ptr<BaseRateLimiter> l, Observer* obs)
        : RateLimiterDecorator(l), observer(obs) {}

    bool process(string clientId) override {
        bool allowed = limiter->allowRequest(clientId);

        if(!allowed)
            observer->update("Rate limit exceeded for: " + clientId);

        return allowed;
    }
};

//////////////////////////////////////////////////////////////
// REPOSITORY PATTERN
//////////////////////////////////////////////////////////////

class ClientRepository {
private:
    unordered_map<string, int> clients;

public:
    void addClient(string id) {
        clients[id] = 1;
    }

    bool exists(string id) {
        return clients.count(id);
    }
};

//////////////////////////////////////////////////////////////
// COMMAND PATTERN
//////////////////////////////////////////////////////////////

class Command {
public:
    virtual void execute() = 0;
    virtual ~Command() {}
};

class RequestCommand : public Command {
private:
    shared_ptr<BaseRateLimiter> limiter;
    string clientId;

public:
    RequestCommand(shared_ptr<BaseRateLimiter> l, string id)
        : limiter(l), clientId(id) {}

    void execute() override {
        bool allowed = limiter->allowRequest(clientId);
        cout << "Request for " << clientId
             << (allowed ? " Allowed" : " Denied") << endl;
    }
};

//////////////////////////////////////////////////////////////
// SINGLETON MANAGER
//////////////////////////////////////////////////////////////

class RateLimiterManager {
private:
    shared_ptr<BaseRateLimiter> limiter;

    RateLimiterManager() {}

public:
    static RateLimiterManager& getInstance() {
        static RateLimiterManager instance;
        return instance;
    }

    void setLimiter(shared_ptr<BaseRateLimiter> l) {
        limiter = l;
    }

    shared_ptr<BaseRateLimiter> getLimiter() {
        return limiter;
    }
};

//////////////////////////////////////////////////////////////
// MAIN
//////////////////////////////////////////////////////////////

int main() {

    RateLimiterConfig config =
        RateLimiterConfigBuilder()
            .setLimit(3)
            .setWindowSize(10)
            .build();

    auto limiter = RateLimiterFactory::createLimiter("SLIDING", config);

    Logger logger;
    auto decoratedLimiter =
        make_shared<LoggingDecorator>(limiter, &logger);

    RateLimiterManager::getInstance().setLimiter(decoratedLimiter);

    string client = "clientA";

    for(int i = 0; i < 5; i++) {
        RequestCommand cmd(
            RateLimiterManager::getInstance().getLimiter(),
            client
        );
        cmd.execute();
    }

    return 0;
}

📌 14. Complexity Summary

Algorithm	Time	Space
Fixed Window	O(1)	O(n)
Sliding Window	O(k)	O(n×k)
Token Bucket	O(1)	O(n)
Leaky Bucket	O(1)	O(n×k)

📌 15. Interview-Level Talking Points

✔ Why Strategy? → Switch algorithms dynamically

✔ Why Template Method? → Standardize request flow

✔ Why Decorator? → Add logging without modifying core

✔ Why Builder? → Clean configuration

✔ Why Factory? → Decouple creation

✔ Why Singleton? → Global configuration control

🚨 Multithreading Problems in the Above Rate Limiter Implementation

Our current implementation is single-threaded.

If multiple threads call:

allowRequest(clientId);

simultaneously → the system becomes unsafe.

Below is a complete breakdown of all concurrency problems and their proper solutions.

🔴 PROBLEM 1: Data Race on unordered_map

Where?

In every algorithm:

unordered_map<string, ...> logs;
unordered_map<string, ...> counter;
unordered_map<string, Bucket> buckets;

Why It’s Dangerous?

unordered_map is NOT thread-safe.

Two threads doing:

logs[clientId]

can:

• Corrupt internal bucket structure

• Cause undefined behavior

• Crash program