Table of Contents

What is a Rate Limiter?

Before the Age of AI, Companies used to do cost cutting by monitoring their server usage, to do that they had to limit what their users could ask for. i.e. To limit the usage of their resources by ensuring that no user exhausts or overuse the server than they are supposed to. One way to do this is to ask the user to promise that they will use it with care, other way is rate-limiter.

High-Level Design

Designing a rate limiter before deep diving into code:

Requirements

  • Functional Requirements
    • Identify user uniquely, so that we can limit them based on their usage.
    • Some Algo/Rule/Magic, basde on which we are going to monitor and limit the usage.
    • Let the user know, why they are getting limited/blocked, and for how long.
  • Non-Functional Requirements
    • The system should be available. availability»>consistency, because it is ok if i let some user hit 2-3 more requests than they are supposed to, rather than bring the whole prod down for minutes.
    • Make sure the whole process of checking and qualifying the requests has very low latency(<10ms), As the last thing we want is add more latency to our already slow system.
    • Ability to scale this to many requests(1M rps).

Core Entity

  • User: Those who are going to hit our api.
  • Request: Those request which the rate limiter is supposed to limit.
  • Rules: Those rules using which the rate limiter is going to make the decision of accepting or rejecting a request.

Design

Before jumping to the design, some approaches are needed to be reviewed:

  1. Not every service should have their own local rate limiter, because it will only limit the request to that instance and not to the whole system.
  2. If adding some more network latency is not an issue then we can keep the rate limiter as a separate service and call it on every requuests call.
  3. We can keep the rate limiter in the middle/reverse-proxy/load-balance/API-gateway layer. This will treat every incoming requests before it even reaches the system. This will need all the information to be present in the Request in the form of headers as rate limiter now doesn’t have access to the Business logic, like it used to in the above 2 approaches. Below is the design for this:
flowchart LR C[Client] subgraph G[API Gateway] RP[Reverse Proxy] RL[Rate Limiter] LB[Load Balancer] end M1[Microservice 1] M2[Microservice 2] M3[Microservice 3] M4[Microservice 4] C -->|Requests| RL RL -->|Allowed| M1 RL -->|Allowed| M2 RL -->|Allowed| M3 RL -->|Allowed| M4 RL -->|Rejected: 429/Too Many Requests| C

Important Questions

Some questions that are needed to be clarified before we deep dive in the implementation:

How to identify a user uniquely

It is important that we know how to identify user so that we can monitor their usage. It needs to see if the request is being received by rate limiter after it is authenticated or if JWT contain that info or if the headers has some indication about the user. Their is a possibility that requesst might have an API key in case of dev API. if there is nothing present then one can use IP to identify users but multiple people working at a company or accessing system from a college will have to share a limit that was supposed to be used by one user. Generally there are multiple rules like: * 100 rpm for an IP * 1000 rph for an authenticated user * 50K rps for whole system * 10 rpm for /getAll api

What are the rules that are going to define the rate limiting and how do they keep track of who has used what amount of their limit

Approaches which are used to keep track of requests for a user:

  • Fixed Window Counter
    • For every time window(say 1 minute), every user gets set limit(say 100) to exhaust.
    • No matter how many you used in last window, every window it resets for everyone.
    • Can be stored using a Hashmap like data store like a <User,Count> pair.
    • Problems:
        Overlimit: If say a window is going to exhaust at 3:10:00, and new window will start at that time and add new 100 limit for a user. then that user can call 100 requests at 3:09:59 and another 100 in 3:10:00, Thats 200 in 2 seconds. this can easily harm the system when millions(hackers) do this.
        Starving: If say a window is going to exhaust at 3:10:00, and new window will start at that time and add new 100 limit for a user. If a user calls 100 at 3:09:01, then user has to wait for a minute to reset the limit, this can also cause issue as this much of downtime for a user might become an issue.
  • Sliding Window Log
    • For every user keep log of Window and keep forwarding when new timestamps come in.
    • for every new request check the window log and calculate remaining limit and increase and change the reange accordingly.
    • Problems:
        Memmory Issue: To store a 1 minute window for 10k users and constantly updating that, will run into many memory issues as it scales.
        Calculation intensive: Going through a 10 minute window everytime for every user will be calculation intensive and hence incerease latency which we want to keep minimum.
  • Sliding Window Counter
    • Only 2 Counters are maintained, one that keeps count of requests in last window and one that keeps track of requests in current window and the remaining current window limit is calculated based on the approximation of previous window.
    • for every new request check the previoud window count and current window count and calculate remaining limit.
    • Example: suppose there were 10 requests in last 1 minute and in current minute we have seen 4 requests and we are on the 80% of the current window, i.e. we have seen 80% of the current window length. so the remaining limit for 20% is the 20% of previous window(10). which is 2, so we can still let 2 requests pass through.
  • Token Bucket
    • Every user have a bucket of fix size. that can have fixed number of tokens.
    • When a new request comes in, it checks if the bucket is empty or full, based on the timestamp and count it already has.
    • It is easy to implement and is very reliable as it takes care of Regular increment of user limits and also does not utilize memory and CPU while doing this.
    • It has an issue of cold start, when a user start using after a very long time, then they get full bucket to exhaust.
How to store the infor?

Use redis to store the info of users(like token count and timestamps). Because:

  • It is fast.
  • It stores to cleanup the data automatically with the help of expiry.
  • Atomic operations and on top of that supports LUA scripts.
  • Supports Replication.
What if limit is reached?

There are 2 roads when limit is reached:

  1. Queue the requests and replay them when they have some limit left. This way they are not getting a failure message, but this way they are not getting any message. And it is now our resposibility to queue their requests, which brings more overhead to our system. This can work for batch-processing but in general other road is chosen.
  2. Return Too Many Requests 429 status and set appropriate headers.
sequenceDiagram participant C as Client participant RL as Rate Limiter C->>RL: HTTP Request RL-->>C: HTTP/1.1 429 Too Many Requests RL-->>C: X-RateLimit-Limit: 200 RL-->>C: X-RateLimit-Remaining: 0 RL-->>C: X-RateLimit-Reset: 1780445400 RL-->>C: Retry-After: 30 RL-->>C: Content-Type: application/json Note over C,RL: Response Body RL-->>C: {"error":"Rate limit exceeded","message":"You have exceeded the rate limit of 200 requests per minute. Try again in 30 seconds."}

Scaling

As the Redis has capacity to run 100,000-200,000 ops-per-second, and as each rate limit check has 2 ops(1 read and 1 write), It means that we can only entertain 50,000-100,000 ops-per-second. To scale this, we will need multple redis instances, this will be done by using a redis cluster. redis cluster by itself takes care of hasing the key and use consistent hashing and sharding based on that. Lets say if we use a cluster of 10 redis instances, then 10*100,000 = 1M requests can be handled by our system.

What if this dream gets over?

If Any redis instance comes down, then there is a possibility that, many requests are not getting response correctly and this can also cause thundering herd problem. In that case, some thing needs to be done so that at least users are unblocked:

  1. Fail-Closed: Fail all the requests with service unavailable 503 Status. This can cause another issue where users will start hitting the api aggresively to get some results. Example: Banks generally do this, because for them security is priority.
  2. Fail-Open: Pass all the requests, don’t check for rate limiting as long as the ystem is ready till then the server needs to work at high capacity and might need scaling. this also has a risk to cause cascading failure.

Steps to increase latency

Use connection pooling, so that no need to create a new TCP connection and do 3-way handshake everytime.

Handle Dynamic rules

Sometime there is a need to add dynamic rules without any code release. In that case there are 2 approaches of how the system will know about those rules:

  • Poll rules at Interval
    • Push/Add new rules in a configuration service or DB, and rate limiter poll that at an interval(say 1 minute)
    • A config can be something like <timestamp,limit,Users,endpoints>.
    • Problem: It takes 1 minute to sync the rules, this can cause issue when there is an emergency and we want the rules to immediately take effect.
  • Push to system
    • Push/Add new rules in a configuration service or DB, and config pushes
    • A config can be something like <timestamp,limit,Users,endpoints>.
    • Zookeeper is ideal for this purpose, as it can automatically take care of retries and failures.
    • Problem: It takes 1 minute to sync the rules, this can cause issue when there is an emergency and we want the rules to immediately take effect.

Final Design

architecture-beta group redis(database)[Redis Cluster] group gateway(cloud)[Gateway Cluster] group services(server)[Microservices Tier] service Zookeeper(cloud)[Zookeeper] service client(internet)[Client App] service r1(database)[Redis 1] in redis service r2(database)[Redis 2] in redis service g1(server)[Gateway 1] in gateway service g2(server)[Gateway 2] in gateway service m1(cog)[Microservice 1] in services service m2(cog)[Microservice 2] in services service m3(cog)[Microservice 3] in services %% Direct connection between Client and Gateway Cluster client:R -- L:g2 %% Gateway to Redis Cluster (Top) g2:T -- B:r2 %% Gateway to Microservices Tier (Right) g2:R -- L:m2 g2:B -- T:Zookeeper

References

I am no genius, i have stolen all of this from the links provided below: