System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• rate limiter is supposed to be a separate service that takes a yaml config which defines rate limitations for all endpoints. rate definition is specified here.
• rate limiting can be done based on either ip or user. this should be field in the yaml specification for a given endpoint.
• rate limiting algo implemented here is token bucket. this would help deal with bulk requests at a time and can also put a max cap on the max number of requests that can be done. refilling rate can be set via the config.

Non-Functional:

List non-functional requirements for the system...

• each api consultation at max would take around 10ms.
• It is expected to scale horizontally as load increases.
• To keep count of api hits, per person/ip, we can use redis in cluster setup to store the count. Ratelimiter service is supposed to interact with that service.
• When a user hits their max limit, they get http 429 as response.

Capacity estimation

Estimate the scale of the system you are going to design...

• assume 100k daily active users for a given application across all API endpoints.
• assume 500 calls per user, per day.
• number of calls/day for all users = 500 * 100k = 50000k
• lets say at peak period of 4 hours, it would be 40% of all day calls = 0.4 * 50000k = 20000k calls
• during peak hours, avg calls per person per hour during peak window = 20000k/100k = 200 calls per person, for the 4 hours.
• amount of calls per second in that peak window = 20000k/4/3600 =1.39 K
• 1390 requests / second on peak. So the design is supposed to scale to accommodate this. During non peak hours, they can be scaled down.
• assuming each request would take around 1ms to process on a 3GHz processor single core (3*10^6 instructions executed), 1390 requests would take around 1390ms worth of cpu time. because promised max time is 5ms, we need to process within that window, we take 1390/5 =278 cores.
• storage side, we need to track sessions per user. for each user, let say we need a total of ( 4B for integer to count, assuming 64B for user id) = 68B per endpoint. So total storage needed per day fore all users for all endpoints = 68B * 100k * 4 (assuming application has 4 endpoints configured for rate limiting) = 27MB.

API design

Define what APIs are expected from the system...

set of APIs :

GET /checkAllow

Body : { user, api_endpoint, timestamp of request }

Response : Status 200, Body : True / False and time left for refill if False.

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

Database I use here to keep track of count is redis.

It is a kv store.

I would use INCR on the key to increase the count.

{

key : userid + api endpoint

val : count

}

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

I have drawn the diagram.

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

there are different algos that can be used and which one to use depends on the use case. In this I have designed the ratelimiter for token bucket where you have fixed number of tokens per bucket (userid+apiendpoint) and each request would consume a token. if the bucket is 0, no api call is supposed to go through and api gateway will return 429. and the bucket keeps refilling at a fixed interval.

From the rate limiting service side, this would scale well because it essentially has no state attached to any one of the vm instances and the part where count is tracked is offloaded to redis to scale independently.

redis would run in cluster mode, where for a given key (user id + api endpoint), val of count is incremented using INCR command.

this should also scale well since, this is stored in memory. use consistent hashing for the key for a evenly distributed load across all redis nodes. Incase redis fails, the api gateway should scale up rapidly and allow only around N requests per endpoint. N depends on the available resources.

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

I have used redis here and redis offers AP and no strong consistency though it can be ensured to make masters wait until a slave acknowledges write. Each write gets written to a master and master replicates to its replicas. There would be inconsistency when there is a master failure or network partitioning, but because redis allows fast access to in memory kv pairs, we have chosen this and once in a while master failure and subsequent extra load should be handled in such a way that redis' availability is well in tune with the extra buffer we have for the api system.