Loading...
We build a middleware that, is supported by most HTTP libraries in most languages. Each request goes to the middleware and returns HTTP 429 when requests are throttled
/// Returns error when request is blocked, else Ok
rust
fn is_rate_limited(uid: String) -> Result<Unit, Error> {
}```
For each request we will following header. So, if client wants to handle limits such that, they never exhaust limits. this becomes very important
X-RATELIMIT-LIMIT: INDICATION LIMIT PER TIME WINDO
X-RATELIMIT-REMAINING: INDICATION TOTAL LIMITS REMAINING IN THE CURRENT TIME WINDOW
we will set the following headers in the response when `is_rate_limited((uid: String)` returns error.
X-RATELIMIT-RETRY-AFTER: INDICATION RATE LIMITED, RETRY AFTER A TIME WINDOW
Cache
Entity (Table)
String ID
Number Count
Number Last_Added
With our rules config, we define what how we support various user types. premium or freemium. With domain type we could use user or system for network bandwidth or apply to business domains etc..
Rules Config
domain: user
metadata:
user_id: abc123
type: freeium
rate_limit:
rules:
total_requests: 10
allowed_in_minutes: 1
domain: user
metadata:
user_id: abc123
type: premium
rate_limit:
rules:
total_requests: 100
allowed_in_minutes: 1
domain: system
metadata:
user_id: abc123
type: premium
rate_limit:
rules:
bandwidth: 100gb/s
read_ops_per_min: 100
write_ops_per_min: 10
Below is the the proposed high level design.
A request reaches to rate-limiter middleware and is directed to distributed rate limiter. Since, we have distributed environment, we use a centralised store to track whether a request is to be throttled or allowed.
With our rules-config loaded at the start which helps determine the rate limiting criteria per domain, a domain be user, resource, business etc. The, our rate-limiter will use Token bucket algorithm to implement rate limiting. for each user we grant them a bucket and tokens, if the bucket is empty we throttle the request else we allow the request to go through. We store bucket and tokens with our cache store.
See High level diagram
With request, rate limiter check if the request is allowed or not.
While our high level design talks about Token bucket algorithm, it doesn't mention how we refill the bucket. Generally this is implemented with a refill process that runs in background to refill buckets periodically. However, with over 1.2 Million unique users per day, this will be a significant strain on over cache and we may even slow down HTTP requests. To avoid this, I propose, each user gets their own bucket and the bucket contains count and last_added (in seconds) and we set TTL for the time window defined in rule.
This way we are just using 2 counters, less memory and still have low latency.
This process helps us resolve race condition as we are doing all operations in one trip i.e. ATOMIC operation. had we used timestamp and compared last timestamp with current timestamp (). we would have done two trips thus, a potential for a race condition.
It is also worth mentioning that Redis Sorted Sets are famous data structure to be used for this implementation.
Lets also deep dive into reliability, Assuming clients requests are routed to their nearest application server, using dns based Geo routing, then, application middleware will call a Load-balancer that will route users request to the same or the closest region the request originated from.
We can host our rate limiter to a cloud like deployments, where we use all app supported regions and avoid downtimes.
See detailed diagram
While these could be bottlenecks, it is important to highlight that, this model follows a shared responsibility model. So, another scenario is, how do ensure our SLA. we could do that by frequent exercises of fault injections and chaos testing and measure carefully the SLA of each stakeholder. Moreover, we can design a SLO dashboard using our SLIs to derive SLA.
I would like to add metrics for monitoring latencies
Build a Regional SLO dashboard to monitor our SLA across regions. This will involve key SLI (service level indicators) and Error budgets from all stakeholders.