01 : Designing a Rate Limiter

Detailed notes are available on - System Design

What is Rate Limiting ?

Imagine you are a hacker, and you want to take down a system with a Dos(Denial of Service) attack, so you think :

" HMMMMMMM..... what if I send this server a ridiculous number of requests?"

By sending these many requests at once you are trying to overwhelm the system, make the service slow or unavailable.

But here's the thing:

Even legitimate users can send a huge number of requests.

So how do we control this?

That's where RATE LIMITING comes in.

Rate limiting restricts how many requests a client is allowed to make within a particular period of time. It's goals are to protect system from overload and abuse, controlling traffic and make sure resource remain available and fairly accessible to all the users.

Requirements:

PS: DON'T EVER PROCEED TO DESIGN A SYSTEM WITHOUT UNDERSTANDING REQUIREMENTS!!!

Before we get into any designing part, it's really really important to think and understand first rather than just drawing stuff (I mean high level design(HLD) diagram).

If you are reading it to answer in an interview and the interviewer throws "Design a rate limiter for me". Don't just start drawing!!

Take a pause, think(or pretend to think), and ask for WHAT IS REQUIRED? Just like how you gather ingredients before you cook something, Here also you are Cooking, but a rate limiter.

Ask Questions like :

1. Is it client side or server side?

2. How do I throttle a request?

3. What should happen when a user exceeds the limit?

4. Is the limit applied per user, IP address, API key, or something else?

5. Do you want to inform users that they hit the quota of number of request ?

6. Do you want to design a distributed system ?

In short, What do you want your Rate Limiter to do?

Let's Explore Options

Client side

You should be clear that making a rate limiter on the client side will always have drawbacks cause you cannot control client side, It's in users hand.

A user can install any software or find ways to fake requests to make it look like normal.

Why ?

Cause, It's client side and client has the control. So, in this newsletter we will focus on Server side, cause we have control over our server.

Server Side

There are many ways to do so

1.Implement rate limiting inside servers

• Let's say you have 2 API servers each with a rate limiter (something like in the given picture.)

• what's happening here is that user 1 sends a request rate limiter allots to server 1 and user 1 send request again this time it's allocated to server 2. So, now server 1 is unaware that user 1 already sent the request and vice versa.

• Advantages are -> it's literally easiest to implement

• Disadvantages are -> Each server - separate state, hence user exceeds limit on separate servers. Again, different servers so counter needs to be synchronized. AND the most dangerous one is that rate limiting happens after the request reaches application serve

2.Use API Gateway

• Api Gateway, In layman terms Api gateway is like Watchman of your college, you have to pass through him to get in the college, no matter what.

• In Short, API gateway is like a centralized server that acts as a single entry point or a layer.

• In this method, Rate Limiter is at the API gateway so all the requests that goes to to API server goes through the API Gateway.

From now on whatever we will discuss, this will be the basics of it.

But wait ? How do we actually implement the rate limiter ?

Is there any specific code ? any algorithm ? any tool ?

Coming to that part, There are various Algorithms that can we used to implement Rate Limiting. I will be covering 3 i.e Token Bucket, Fixed Window Counter, sliding Log. feel free to search other methods on the internet.

1.Token Bucket

• In this method, bucket along with a refiller that contains a variable amount of token.

• There a Bucket refills every second or minute with the tokens, for every request

• Tokens are exhausted and if the bucket empties before the time exceeds. The request ends up being in the Dropped requests.

• Advantage - memory efficient, fast, Allows burst of traffic

• Must keep in consideration -Turing the refill rate and bucket size is tricky

2.Fixed window Counter

• This one simply has a threshold of number of requests a user can hit in a second or a minute.

• If the number exceeds the requests become a drop request.

• Advantages - again, simple and easy to implement, just keep a counter for the no of requests, if counter > no of req allowed then drop

• Memory efficient

• Disadvantage - Allows burst on the boundary

3.Sliding Window Log

• As the name suggests, Log, it keeps a log of all the incoming requests in the particular time frame and if the number exceeds the request gets dropped.

• Advantage - Very accurate, almost perfect, all requests handled correctly in a rolling window and time frame with itself.

• Disadvantage - Accuracy comes a cost, since we use a log, so we somewhere end up using memory for logs, so not very much memory efficient.

How to choose the best Algorithm ?

• There isn't a specific method that we can tag as the best, I mean if that was the case why would there be other methods in first place?

• So, always look for the requirements, input data, kind of system, no of requests. Basic idea remains the same, counter for requests is everywhere.

So, where do we store the counter ?

DB ? yes, but what kind ? We need frequent access, almost in milliseconds, Must use a fast one.

YES!!! We use Reddis.

Reddis - In Memory data Structure used for fast retrieval of information.

So our Final Diagram looks something like this :

Is the diagram complete ?

If you said yes, you are WRONGGG!

Why ?

Ohk let's say we are done.

Now imagine every company has different requirement, lets call them like a set of rules they want their rate limiter to follow.

where do we put those rule ? Yesss database AGAINNNN!!!

But wait Normal database ? or some other ? Let's think.......

let's say I use normal MySQL, now I get a request I send a query to my database, ok all good right ? but what if I send 10,000 request per min or more, you'll send that many queries to your database? Instead of making the system efficient it will become slow, because of the query retrieval. So best option is put a caching layer so you don't have to query your database again and again. Hence, SOLVED.

Till now we have been saying if no of requests exceeds then drop it, what if I don't want to drop it ? what if I want to re-process it when the limit refreshes. This one totally depends on what the company wants, You can just drop the request or add a message queue that sends the request back to the rate limiter.

Now, your final rate limiter looks something like this.

TADAAAAAA!!!!

YOU MADE IT !!!!

But wait ? Didn't we also talk about Distributer systems.

Haha, seems like it's not getting over that soon.

Distributed systems

Here, you don't have one particular server but rather have many computers called nodes which are connected to each other and can communicated from different point of the world. For eg AWS.

Now, suppose there are 2 clients(C) and 2 nodes(N), C1 sends the request and N1 was free C1 is alloted to N1, Now C2 comes in and N2 is alloted to C2. Now imagine both makes a second request and now C1 is alloted with N2 and C2 is alloted to N1. N1 had no idea that C2 has any history with N2 and vice versa.

Therefore in distributer systems, we have a common redis for all the rate limiters.

THANKYOU FOR READING(ONLY IF YOU MADE IT TO THE END)!!!