Requirements

Functional Requirements:

• per-user / per-API rate limits.
• Admins can add/update/delete/view rate-limit rules via an API or console.

Non-Functional Requirements:

• Allow bursts
• Immediate response if too many requests
• Allow request if below the limit set

API Design

This API design applies to the Admin user:

• POST /rule: Adds a per-user or per-api rate limit rule, based on number per requests in a given period of time. Stores the rule in PostgreSQL (user, api name, number of tokens (requests) per time unit, token capacity in the bucket).
• GET /rule: Gets a rule by user id or api name. Returns the current rule (number of tokens -requests- per time unit, capacity of the token bucket)
• PUT /rule: Allows you to update the user or api rule. The main parameters to update are token capacity of the bucket, time unit and number of requests (tokens).
• DELETE /rule: With this you can remove an user or api rule.

High-Level Design

There are 2 mains flows, from Admin and User perspectives.

User:

1. Wants to call one of the endpoints executed by the API servers, and call it.
2. The API Gateway gets the request, and checks against the Counter using the cached rules.
3. The Counter (Redis) updates the token bucket for that user/api by consuming tokens (one by request + all tokens according to the rate since the last request).
4. If there are no tokens available, the Counter returns a reject with a Retry-After header informing about the seconds needed to retry again.
5. If there are tokens available, the Gateway redirects to the endpoint that the user wanted to hit in the first place
6. The API gateway keeps the cached rules up-to-date by hitting the rules db.

Admin:

1. Add/update/view/delete the Rules DB by using the Admin API.
2. The main parameters to update are the capacity of the token bucket but also the refill rate for the bucket. This applies to user and API.
3. Configuration rollout: When an Admin modifies a rule in one of the ways above, the API gateway updates the rules within 5 minutes/the time we want. For urgent changes we can publish to Redis using Pub/Sub.

Detailed Component Design

The main components are:

1. API gateway: In charge of caching the rate limiter rules from PostgreSQL refreshing after a given cadence (for instance 5 minutes since rules should not change very often). For every request from a non-admin user, it would use those cached rules as input parameters for Redis that will respond with 429 and a Retry-After header specifying the seconds where the user should retry or allowing the request to the API servers.
2. Counter (Redis): Implements the token bucket algorithm on demand. This means that for every request received checks the number of tokens allowed for user/API that is the minimum between the capacity of the token bucket and number of remaining tokens plus the refill rate (if we have 100 req per minute, the rate is 100/60 per second, so we calculate the number of seconds that have passed since the last timestamp and now). If the number of tokens after this operation is greater than one we allow the operation so the gateway can redirect to the API servers. Otherwise it is 429 after saving in the counter the current number of tokens and now (will be used in the next iteration)
3. Rules DB: SQL db that will store the rules to be applied by the rate limit. It is modified by the Admin via API. This DB is consulted directly by the API gateway to keep the cache up-to-date so it can be used as input parameters for the counter.

In terms of capacity and scalability:

• The API Gateway is stateless so we can bring up as many instances as required, since all consult the same Redis. If Redis is the bottleneck, we can have a Redis Cluster using the user_id to shard.
• Connection pool saturation: Limit the number of connections that a Gateway can make to Redis since it is single-threaded. We could introduce a local rate limiter as a first layer to avoid calling Redis.
• The Admin can increase the rate limit per user and API using the Admin API. The system would allow potential bursts since it consumes tokens, avoiding common issues with other rate limit approaches (like fixed windows where a user might not fit in the right interval).
• Clock skew: We use the Redis clock instead of the gateway clock. Since it is distributed we would avoid this problem.

Failover:

• Burst traffic/high QPS: We have a load balancer in front of the api gateways to distribute among instances.
• Redis would work on replica mode with automatic failover (a replica would become primary). If Redis is completely down, we would follow a fail-open mechanism since restricting all requests would be worse.
• If the Rules DB goes down, the API Gateway can still function using the cache. For scalability in this sense I would have read replicas, write sharding would not apply here since the rules are just updated by Admin users.