Loading...
Stop the same ip address from spamming endpoints on our system.
Latency, as we need the rate limiter that is transferring requests to be quick, otherwise it will hold up our server. Availability, our late limiter needs to either be available all the time or allow for requests to go through even when its down. So we want to make this fail-open. Also throughput is important because our rate limiter needs to be able to handle a very large amount of load.
Assuming our server gets 100 million requests a month, this is roughly 3 million requests per day or 33 requests per second. If this is how many times our server gets hit, the rate limiter needs to actually be able to handle more requests, and give an error message when the same user is spamming us. lets say 1000 requests per second.
The metadata we need to store per user hitting the api is just their uid or unique device id and last time they hit the server, and the api endpoint they are trying to hit lets say on average 1 byte/character, we can estimate at about 100 bytes per user. Assuming 100 million requests and an average of 5 per user a month at least, 20 million users. 20 million * 50 bytes = 100 million bytes. So 100Mb per month, or 1.2 Gb a year.
Lets assume we have api endpoint: https://server/home. We want to hit our rate limiter before we redirect to this endpoint or any endpoint for that matter. We can return the status code of the server if we go past the rate limiter otherwise we return 429 status code for too many requests. We can set a generic rate limiter of no more than 5 requests per api endpoint every minute. For authentication api endpoints we can set a more strict rate limiter.
We have a database of rules, and a redis cache for those rules just so we can do quick reads. We will check this cache on every user request to validate/invalidate the request coming in. We also have a background worker that updates the redis cache when there are new rules written to the database. It can do this periodically, or must be a function we enforce before any writes happen to the database in general.
For the user limits we can just use a redis cache, as having temporary storage makes sense here. We want to prioritize latency, and after a minute that cache no longer matters for that endpoint and that user. Also if the rate limiter crashes and the cache gets wiped thats okay to start from a clean slate.
We can store a key value pair based on { uid, time_unit, api_used, } and for every request check if the time_unit is within the last time_unit of what is in the cache, if so increment that value by 1, if we exceed a certain value number of requests per minute we return 429. Otherwise if its not within the last minute reset the counter to 0, and update the time_unit.
We can also use consistent hashing on our store based on uid so that it scaled horizontally whilst allowing it users to hit the same redis cache.
The algorithm we can use, is a fixed window algorithm, it makes things simple, and reduces the amount of data we have to store per minute.
We want to have a separate server for our rate limiter so that we can re-route its request to the server. We also want multiple rate limiters per server in case one stops functioning we can reroute the request still to the server, preventing SOFs. Also by separating concerns we can prevent over loading our original server, for example in the event of a ddos attack etc.
We are using a LRU cache for quick access to the data regarding the user and the endpoint they are hitting. We can do a write around cache method, so that we route the request if the hash doesn't exist in the hash, and then update our cache.
The algorithm we can use, is a fixed window algorithm, it makes things simple, and reduces the amount of data we have to store per minute.
Client hits rate limiter, rate limiter checks redis cache if endpoint and ip are over the limit within the extended time. If so we return a 429 to the client otherwise we route the request to our internal api, and then respond with the status code of that endpoint etc.
We would scale this system horizontally by creating more rate limiters, more redis caches per rate limiter as well. For example while we have just one cache currently for the whole server, we can have multiple, depending on which endpoints are more frequently used.
Separating the rate limiter from the original server was intentional to prevent too much load on the original server.
Using fixed window over sliding window, makes the rate limit less accurate but saves storage when it comes to our redis store.
Using a fail-open system means some malicious requests can get through but it decreases latency for most users in the system.
If all the rate limiters are down, we have no access to the server that should be functioning fine. We need to create more rate limiters to address this problem
If the rate limters are overloaded, aka waiting for extended times, we are increasing latency by not redirecting the requests through.
We can implement a fail-open system to redirect requests if our rate limiter is overloaded.
Create more rate limiters, more noSql rules databases, more redis caches and rules redis caches, more background workers to prevent single POF.
Create a timer per request coming in, and if the rate limiter does not return before the timer runs out, to redirect its request to the server.