In this article, I'll cover the implementation of algorithms I've integrated for the rate limiting library: token bucket, fixed window counter, sliding window log, and sliding window counter.

Token Bucket

This algorithm works by maintaining a bucket of tokens, where each token represents permission to perform a request:

• Tokens are added to the bucket at a constant rate.
• The algorithm checks if the bucket contains enough tokens on every request. If so, the request is allowed, and the corresponding number of tokens is removed from the bucket. If not, the request is denied.
• The bucket has a maximum capacity, so tokens that exceed this capacity are discarded.

Knowing the rules, there are two ways to implement constant rate refill: to use a timer or calculate during a new request. The second way is more efficient because it's synchronous, but it has a small downside in getting the remaining points because it requires calculation.

class TokenBucket {
    tokens: number;
    refillRate: number;
    lastRefillTime: number;
    capacity: number;

    constructor(refillRate: number, capacity: number) {
        this.capacity = capacity;
        this.tokens = capacity;
        this.refillRate = refillRate;
        this.lastRefillTime = Date.now();
    }

    refill() {
        const now = Date.now();
        const tokensToAdd = Math.floor(
            (now - this.lastRefillTime) / this.refillRate
        );
        this.tokens = Math.min(this.tokens + tokensToAdd, this.capacity);
        this.lastRefillTime =
            this.lastRefillTime + tokensToAdd * this.refillRate;
    }

    request() {
        this.refill();
        if (this.tokens > 0) {
            this.tokens--;
            return true;
        }
        return false;
    }
}

Fixed Window Counter

The fixed window counter algorithm is the simplest method for rate limiting. It works by keeping track of the number of requests made within a fixed time window.

• The counter is reset to zero at the start of each time window.
• Each request increments the counter.
• The request is denied when the counter exceeds the limit within the time window.

class FixedWindowCounter {
    counter: number;
    limit: number;
    window: number;
    lastWindowReset: number;

    constructor(window: number, limit: number) {
        this.counter = 0;
        this.limit = limit;
        this.window = window;
        this.lastWindowReset = Date.now();
    }

    request() {
        const now = Date.now();
        if (now - this.lastWindowReset >= this.window) {
            this.counter = 0;
            this.lastWindowReset = now;
        }

        if (this.counter < this.limit) {
            this.counter++;
            return true;
        }
        return false;
    }
}

Sliding Window Log

The sliding window log algorithm is a variation of the fixed window counter algorithm that addresses the issue of traffic bursts near the time window's boundary. It logs request timestamps within a sliding time window.

• Requests are logged with their timestamps.
• The algorithm removes old entries on every request outside the current time window.
• The request is denied if the number of logs exceeds the limit.

Two things are worth mentioning about my implementation:

1. Requests are stored as timestamps.
2. Denied requests are not stored in the log.

The reason behind the second is that doing otherwise makes the user unable to make a successful request until the full window time has elapsed.

class SlidingWindowLog {
    requests: number[];
    limit: number;
    window: number;

    constructor(window: number, limit: number) {
        this.requests = [];
        this.limit = limit;
        this.window = window;
    }

    request() {
        const now = Date.now();
        let i = 0;
        for (; i < this.requests.length; i++) {
            if (this.requests[i]! + this.window > now) {
                break;
            }
        }
        this.requests.splice(0, i);

        if (this.requests.length < this.limit) {
            this.requests.push(now);
            return true;
        }
        return false;
    }
}

Sliding Window Counter

The sliding window counter algorithm is a hybrid approach that combines the fixed window counter and sliding window log. It uses two time windows and their percentage of the current sliding window to calculate the estimated count.

• Estimated count formula: requests in the current window + requests in the previous window * overlap percentage of the rolling window and previous window.
• The request is denied if the estimated count exceeds the limit.

There are multiple ways to implement this algorithm. My solution is to use two time windows and move the edge time when the previous window becomes current.

class SlidingWindowCounter {
    currPoints: number;
    prevPoints: number;
    edgeTime: number;
    limit: number;
    window: number;

    constructor(window: number, limit: number) {
        this.currPoints = 0;
        this.prevPoints = 0;
        this.edgeTime = Date.now();
        this.limit = limit;
        this.window = window;
    }

    updateCurrentWindow(now: number) {
        if (now - this.edgeTime > 2 * this.window) {
            this.prevPoints = 0;
            this.currPoints = 0;
            this.edgeTime = now;
        } else if (now - this.edgeTime > this.window) {
            this.prevPoints = this.currPoints;
            this.currPoints = 0;
            this.edgeTime = this.edgeTime + this.window;
        }
    }

    getEstimatedPoints(now: number) {
        return (
            this.currPoints +
            this.prevPoints *
                ((this.window - (now - this.edgeTime)) / this.window)
        );
    }

    request() {
        const now = Date.now();
        this.updateCurrentWindow(now);
        const estimatedPoints = this.getEstimatedPoints(now);

        if (estimatedPoints < this.limit) {
            this.currPoints++;
            return true;
        }
        return false;
    }
}

The four algorithms we’ve explored - token bucket, fixed window counter, sliding window log, and sliding window counter - offer unique approaches to managing request rates.

The token bucket algorithm provides a flexible method for rate limiting, allowing for bursts of requests up to a maximum capacity. The fixed window counter is a simple and efficient method, but it can allow for double the requests at the window boundaries. The sliding window log addresses this issue by maintaining a log of request timestamps, providing a more evenly distributed limit enforcement. However, storing logs can be costly with a big limit number. Lastly, the sliding window counter combines the strengths of the fixed window counter and sliding window log while mitigating their weaknesses. Despite this, sometimes it can fail to rate limit the request due to the approximation nature of the algorithm.

Choosing the right algorithm depends on your specific use case and system requirements. It’s important to understand the trade-offs of each method and test them under different load scenarios to ensure they meet your needs.