Grokking the System Design Interview

0% completed

​

Designing an API Rate Limiter

1. What is a Rate Limiter?

Imagine we have a service which is receiving a huge number of requests, but it can only serve a limited number of requests per second. To handle this problem we would need some kind of throttling or rate limiting mechanism that would allow only a certain number of requests so our service can respond to all of them. A rate limiter, at a high-level, limits the number of events an entity (user, device, IP, etc.) can perform in a particular time window. For example:

  • A user can send only one message per second.

.....

.....

.....

Like the course? Get enrolled and start learning!
W

Whip

· 4 years ago

In the diagram in section 7, why does the rate limiter sit between the webserver and databases? Shouldn't the API servers be connected to the databases instead of the rate limiter?

W

Whip

· 4 years ago

What exactly is stored in the rate limiter databases? Why would this permanent storage be needed? Would it be a bad idea to have the rate limiter run entirely in memory, with no database backing? Worst case scenario, some users could potentially get double the allowable rate if a machine goes down after the user maxes out - this seems like it could often be acceptable to get a much simpler system.

Show 1 reply
J

Junaid Effendi

· 4 years ago

Sliding Window algorithm would not have the concurrent request issue? Lock would still be needed, could be a case where both read at the same time and both write at the same time which could result to 4 records per minute.

F

francesco.perna90

· 5 years ago

Hi,

Thanks for the courses, they are really great!

I've just one question about file storages.

Are DFS and CDN almost alike ?

Since normally I see serving static files ( or medias ) directly with CDNs ( providing redundancy by region ).

Show 3 replies
A

a7mad.3bass

· 3 years ago

Regarding the first algorithm, i don't think this is a fixed size algorithm, it's a sliding window, since the start time is reset to current time each time we get a new request that is out of the 1 minute window of the previous limiting period.

also if we take the example shown here in the article to explain the benefits of the sliding window, the first algorithm prevents that case.

|_____t1_t2 | _t3 _t4 ___t8|

the start time will be set to the time of the first t1, t3 and t4 will be throttled because a minute hasn't passed since start time which is set to t1, requests will be accepted only after t1 + 1 minute (demonstrated here as t8) which will also reset the value for start time

Show 1 reply
S

S

· 4 years ago

In the Sliding Window With Count approach, why do we need to store the counts for all 60 minutes? We only need to store it for one minute, and keep aggregating the hourly count to enforce the hourly limit. That would reduce our storage requirements to roughly match the fixed minutely window approach with some extra per-user storage for hourly usage. What am I missing?

S

S

· 4 years ago

Can you elaborate on how this was arrived at?

if we assume a rate limit of 10 requests per second, this would translate into 10 million QPS for our rate limiter! This would be too much for a single server.

Why would it be too much? Is there a calculation that shows this?

Show 2 replies
P

Pramod Kumar

· 5 years ago

Hi Team, When we say we have to use Consistent Hashing for data sharding, Is it like we have to use Cassandra or any no sql DB which supports consistent hashing.

Show 3 replies
H

hughnguyen

· 4 years ago

The rate limiter protects the API servers from the client making too many requests through the web server, but what protects the web server?

G

Gokul S

· 4 years ago

The material does not cover Token Bucket algorithm.