On Building a Rate Limiter with TypeScript Classes

Imagine this scenario - it's a bright and warm day in New York. You've just booted up your new MacBook, opened up Google Chrome, and go to check what's on your Jira docket for the day.

When suddenly, a super important Slack message appears! Someone has been spamming one of your application endpoints tens of times in a short period of time. Your server currently doesn't have any rate-limiting logic implemented at this moment, and so it's up to you to figure it out and implement it.

That's what we'll be doing as part of this technical challenge - minus the parts of actually integrating this into your server - and we'll be doing it using TypeScript classes.

Follow along for a thought-process on simple function rate-limiting. We'll define the internals of the class, the actual implementation of rate-limiting, and what we're thinking during each step.

Knowing our problem scenario above, the criteria for solving this particular situation could be something like the below - inspired by a real-world challenge I encountered

• Define a RateLimiter class in TypeScript

• It's construction method should accept a maximum number of requests that can be made and the time window, in milliseconds, during which that maximum number of requests can occur.

  An example would be 3-requests every 1-second. The 4th request made in such a time window should be rejected

• The class should have a requestAllowed function that receives a string argument indicating the path that request came from.

  The function will return a boolean based on whether or not the request from that path is allowed.

With all of this in mind, let's get to defining the basics of our class below

interface RequestPathRateLimit {
    /** The current number of requests we've received for this path */
    currentRequestCount: number;

    /** The start time of this current time window, against which we'll rate limit, in milliseconds  */
    currentDurationStart: number;
}

type RequestPath = string;

class RateLimiterV2 {
    /** The global setting for how many requests can be made during a particular time window */
    public maximumRequestCount: number;

    /** The time window during which the maximum request count can be made */
    public timeWindow: number;

    /** Our map that will store the current request count, and the duration start
     * for each of the request paths that we end up rate-limiting
     */
    public requestPathRateLimitMap: Map<RequestPath, RequestPathRateLimit>;

    constructor(maximumRequestCount: number, timeWindow: number) {
        this.maximumRequestCount = maximumRequestCount;
        this.timeWindow = timeWindow;

        // Instantiate an empty map for our `requestPathRateLimitMap` property
        this.requestPathRateLimitMap = new Map();
    }

    /** Function that will return true or false depending on if the provided request
     * from the request path is allowed.
     *
     * This is determined by checking the number of requests we've received from that
     * request path against this classes maximum request count property, and time window property
     * @param requestPath - The path from which this request is originating. 
     *                      An example request path, `/google`
     */
    public requestAllowed(requestPath: RequestPath): boolean {
        // TODO - Add rate-limiting logic here
    }
}

And there we have it. Most of our RateLimiter class is defined, and we've set a three properties as part of the class

• maximumRequestCount - Just a property to identify what the maximum amount of requests can be made
• timeWindow - Just a property to define how long the duration window of when the rate-limiting would take effect

• requestPathRateLimitMap - This is a Map which will keep track of how many requests have occurred for a duration against a particular request math.

  You can have a look at the RequestPathRateLimit interface to understand the data we're keeping track of in each value of the map, but it's essentially just the current request count and duration start for each particular request path encountered.

With the above properties and data structures in place, we're ready to implement the actual logic of rate-limiting in the next section.

Awesome! We have pretty much everything we need to implement the actual logic that will rate-limit requests from a particular request path.

We have the following available to us in our RateLimiter class

• The maximum request count that can be made
• The duration for which that maximum request count can be made
• A map where the key is the Request Path for a request we've received, and the value assigned to each key is information regarding the current request count for that path, and the when the current rate-limit window started

We're all good to go to begin ideating our approach using the above information. Our approach will be something like the following for implementation of the requestAllowed function

• Upon receiving a request, we'll define the current time. Because we don't know the request paths beforehand, we'll check if our requestPathRateLimitMap has an ongoing duration for this request path.  

  If it doesn't, then we'll initialize it using an current request count of 0, and setting the current duration start to now. This ensures we always have the above information about a request path  

• Next up, we'll extract the information about the current request count and current duration start from our map, for this particular request path.  

• Now comes the fun part. Remember the timeWindow property available on our RateLimiter class? We'll now make use of that property. We'll subtract the current duration start for this request path from the current point in time. This will give us the elapsed time since the current duration start.  

• If that calculated elapsed time happens to be greater than or equal to our timeWindow value, then effectively, the rate-limiting window is over. At this point, we can begin a new duration, and reset the current request count back to 0  

The above approach is the logic we'll capture and write into the code. The more tricky part of the rate-limiting aspect is determination of this time window, and when it is effectively over to reset our state.

After that, we can implement our straightforward logic of returning true or false dependent on whether or not we've reached the maximum request count. 

We've got our high-level approach up above. The more tenuous part of the rate-limiting function has been figured out, and we know what need to be done for our function to work.

See the below code for what the logic is like when added into the class. The comments in the code describe what's going on step-by-step

/** Function that will return true or false depending on if the provided request
     * from the request path is allowed.
     *
     * This is determined by checking the number of requests we've received from that
     * request path against this classes maximum request count property, and time window property
     * @param requestPath - The path from which this request is originating.
     *                      An example request path, `/google`
     */
    public requestAllowed(requestPath: RequestPath): boolean {
        // TODO - Add rate-limiting logic here
        // Our first step will be to check if we've encountered this request path before
        // in our `requestPathRateLimitMap`. If not, we'll initialize and start a duration window
        // We'll also identify the time of this current request
        const currentTime = Date.now();

        // If we have not encountered this request path before, initialize our state
        // for rate-limiting this request path
        if (this.requestPathRateLimitMap.has(requestPath) === false) {
            this.requestPathRateLimitMap.set(requestPath, {
                currentRequestCount: 0,
                currentDurationStart: currentTime,
            });
        }

        // By here, we'll always have a current request count, and a duration window
        // for a request path. Let's check if it has expired and reset state if needed
        let {currentRequestCount, currentDurationStart} =
            this.requestPathRateLimitMap.get(requestPath)!;
        const elapsedTimeSinceDurationStart =
            currentTime - currentDurationStart;

        // If the elapsed time since the duration start is greater than
        // the time window of our rate-limiter, our time-window has expired
        // and we should reset the rate-limiting metrics back to initial state
        if (elapsedTimeSinceDurationStart >= this.timeWindow) {
            currentDurationStart = currentTime;
            currentRequestCount = 0;

            this.requestPathRateLimitMap.set(requestPath, {
                currentDurationStart,
                currentRequestCount,
            });
        }

        // By here, we are always in an active rate-limit duration, we just
        // have to check if our current request count allows this next request

        // If we've reached our maximum allowed request count, we return false
        if (currentRequestCount === this.maximumRequestCount) {
            return false;
        }

        // Otherwise, we have not yet reached the maximum allowed request count
        // for this path. We'll increment our current request count and then return true
        currentRequestCount = currentRequestCount + 1;
        this.requestPathRateLimitMap.set(requestPath, {
            currentDurationStart,
            currentRequestCount,
        });

        return true;
    }

Our logic above and the approach we've ideated so far make sense, and sounds like it could be correct, but we don't know that for sure.

And we certainly wouldn't want to deploy this rate-limiting code to Production without being fully confident that it'll indeed rate-limit a particular path for our given constraints.

So how can we confirm our hunch and be fully confident of our solution? We can write some tests to confirm our RateLimiter class actually gets the job done.

If you don't need to see the corresponding tests, and just want to understand a straightforward approach to rate-limiting, you can skip the next and final section.

Otherwise, continue onward!

The logic we captured into code with the RateLimiter class we wrote seems correct on paper. But we need to verify and validate against this hunch.

We also want to be sure our RateLimiter class correctly handles rate-limiting multiple request paths and is appropriately segmenting rate-limiting metrics by request path.

To achieve this, we'll utilize the expect package for basic function output verification against what we expect to happen. You can install the package on your local environment using

npm install --save-dev expect

And now that it's installed, we can go about writing some basic unit tests. Our approach will be

• Define a couple of static paths to use
• Set up a helper utility function for testing out a provided RateLimiter class instance
• Testing multiple paths against the RateLimiter to ensure one request paths rate-limit isn't leading to the rate-limiting of another path

And here's the approach captured in code

import expect from 'expect';

...

const PATH_ONE = '/path-one';
const PATH_TWO = '/path-two';

/** Function that accepts
 * @param rateLimiter - An instance of a rate-limiter to test
 * @param runCount - How many calls to `requestAllowed` to call
 * @param requestPath - The request path that should be provided to `requestAllowed`
 * @param expectation - A single-boolean of what each of those calls to `requestAllowed` should return
 */
function rateLimiterTester(
    rateLimiter: RateLimiterV2,
    runCount: number,
    requestPath: string,
    expectation: boolean
) {
    console.log(
        `These ${runCount} requests from "${requestPath} should ${expectation ? 'pass' : 'fail'}`
    );
    for (let count = 0; count < runCount; count++) {
        const result = rateLimiter.requestAllowed(requestPath);

        console.log(result);
        expect(result).toBe(expectation);
    }
}

async function testOne() {
    const rateLimiter = new RateLimiterV2(3, 1000);

    rateLimiterTester(rateLimiter, 3, PATH_ONE, true);
    rateLimiterTester(rateLimiter, 3, PATH_TWO, true);
    rateLimiterTester(rateLimiter, 5, PATH_ONE, false);

    console.log(
        `Waiting ${rateLimiter.timeWindow} ms before next set of requests`
    );
    await new Promise(resolve => {
        setTimeout(() => {
            resolve('');
        }, rateLimiter.timeWindow);
    });

    rateLimiterTester(rateLimiter, 2, PATH_ONE, true);
    rateLimiterTester(rateLimiter, 2, PATH_TWO, true);
    rateLimiterTester(rateLimiter, 1, PATH_TWO, true);
    rateLimiterTester(rateLimiter, 1, PATH_TWO, false);
}

testOne();

And running our code using a command like, and this will vary depending on how you are compiling and executing your TypeScript code, will be

node run dist/rateLimiter.js
...

These 3 requests from "/path-one" should pass
true
true
true
These 3 requests from "/path-two" should pass
true
true
true
These 5 requests from "/path-one" should fail
false
false
false
false
false
Waiting 1000 ms before next set of requests
These 2 requests from "/path-one" should pass
true
true
These 2 requests from "/path-two" should pass
true
true
These 1 requests from "/path-two" should pass
true
These 1 requests from "/path-two" should fail
false

And there we have it. We've implemented our RateLimiter class and the underlying requestAllowed logic.

We've enabled our RateLimiter class to capture and store information about rate-limiting multiple paths through keeping track of the number of requests received for each path using a Map object, and we keep track of when the latest duration window began.

Lastly, we reset that duration window as needed when we've identified that it expired, so that subsequent requests aren't incorrectly rate-limited.

See the attached RateLimiter Gist for the full-code and comments.