SECRET OF CSS

Creating a Basic Rate Limiter System With a Sliding Window in TypeScript | by Erez Lieberman | Aug, 2022


Learn the system design concepts

0*kfU2doj6Gy38m1hH
Photo by Saptarshi Roy on Unsplash

Rate Limiting is a fundamental concept in system design. One of the algorithms we can use to implement Rate Limiting is the “sliding window” algorithm.

Here is an example of a very basic rate-limiting system with a sliding window algorithm, we made it in type script and explained line by line:

class RateLimiter {
allowedRequests = 0;
timeFrameSize = 0;
queue = [];
constructor(n: number, t: number) {
this.allowedRequests = n;
this.timeFrameSize = t;
}
shouldAllow(timestamp: number): boolean {
const diff = timestamp - this.timeFrameSize;
while (this.queue[this.queue.length - 1] <= diff ) {
this.queue.pop();
}
if(this.queue.length < this.allowedRequests){
this.queue.unshift(timestamp)
return true;
}else{
return false
}
}
}

The input, output, and explanation of this class will be like this:

Input
[“RateLimiter”, “shouldAllow”, “shouldAllow”, “shouldAllow”, “shouldAllow”, “shouldAllow”]
[[3, 5], [1], [1], [2], [3], [8]]
Output
[null, true, true, true, false, true]
Explanation
RateLimiter rateLimiter = new RateLimiter(3, 5);
rateLimiter.shouldAllow(1); // returns True
// There are no previous requests, so this request is allowed.
rateLimiter.shouldAllow(1); // returns True
// We can allow 3 requests every 5 seconds, so this request is allowed.
// Timestamps of allowed requests are [1,1].
rateLimiter.shouldAllow(2); // returns True
// Timestamps of allowed requests are [1,1,2].
rateLimiter.shouldAllow(3); // returns False
// This request is not allowed because
// the time range [1,3] already has 3 allowed requests.
rateLimiter.shouldAllow(8); // returns True
// This request is allowed because
// the time range [4,8] does not have any allowed requests.

Now let’s go step by step and see how its works.

We have 3 vars when we init the class:

 allowedRequests = 0;
timeFrameSize = 0;
queue = [];

allowedRequests means how many requests we are allowing in a specific timeFrameSize (in seconds), both of them have a default of 0.

We also have a queue that is inited as an empty array, we will use it to monitor how many requests we currently have, and what was the last timestamp that the start of the window was set to.

In the class constructor, we set the allowedRequests and timeFrameSize to the values that we sent when we created the class.

Now let’s continue with the shouldAllow method. We will first jump to the 5th line in this method:

if(this.queue.length < this.allowedRequests){
this.queue.unshift(timestamp)
return true;
}else{
return false
}

This is pretty straightforward — if we don’t exceed the allowed number of requests:

queue.length < allowedRequests

We will add the timestamp of this request to the beginning of the array:

this.queue.unshift(timestamp)

And allow this request, by returning true.

If the queue.length === allowedRequests which means we should not allow any more requests in this time window. and we return false.

Now let’s go back to the first line of the shouldAllow method:

const diff = timestamp — this.timeFrameSize;
while (this.queue[this.queue.length — 1] <= diff ) {
this.queue.pop();
}

So first we set a const called diff.

diff holds the timestamp of the last allowed request, minus the timeFrameSize of our system (how many requests we allowed in a number of seconds).

While the timestamp of the last item (the first that we added to the queue) is equal to or less than the diff, we remove it from the queue and add space for the next coming requests. This is what makes the window “slide” forward.

Let’s take the example above to understand it more clearly — the input looks like this:

[[3, 5], [1], [1], [2], [3], [8]]

We allowed 3 requests every 5 seconds (the [3, 5] in the start).
In the first 3 times, the queue length is < or = to 3 (the timeFrameSize) so we allowed the requests and add them to the queue.

Now, our queue looks like below:

[ 2, 1, 1 ]

This explains why we got the result the following result:

[null, true, true, true, false, true]

The first null is when we init the class and get void, and the 3 subsquent true values after is the first 3 requests that were allowed. For the 4th, the queue length is already 3 so it’s not < from 3 (the timeFrameSize). This is why we got false for the 4th request.

In the 5th request, the last item in the queue is 1 and diff is 3 so for the first time:

this.queue[this.queue.length — 1] <= diff

Now we’ll delete all the requests that are small than 3 (all the items in the queue for this scenario) — and the queue is empty — so in the next request…

queue.length < allowedRequests

…in this case, we allowed the request and add it to the queue — now the queue looks like this [8] and we allowed 2 more requests to come.
Through this action, we “slide” the window from timestamp 1 to timestamp 8 — and start counting the 3 requests from 8.



News Credit

%d bloggers like this: