System requirements

Functional:

• rate limiting is enforced per api method and user on the server side
• the rate limiting is per minute

Non-Functional:

• performent: low latency, less memory overhead
• fault tolerance
• it should be distributed

Capacity estimation

Suppose we have a service

API design

There are serveral interfaces:

• the interface that how api owners to define the quota

the interface of quota server:

Database design

The only one need to be stored in DB is the rate limiting config.

ServiceConfig(id, version, serialized_service_config)

High-level design

• The service config is the source of truth to config the per api level rate limit
• During deployment time, the service config will be pulled by API gateway and rate limiting service
• API Gateway is the critical component in runtime to enforce the rate limiting
• In-mem KV store(redis) is the storage to support distributed quick read/write for rate limiting related metadata

Request flows

• the clients send requets to API gateway
• API Gateway collects rate limiting metadata from service config and requests, send to rate limiting service
• The rate limiting service check redis and decrement the remaining token if there is still some remaining
• The API Gateway receive the RLS response from rate limiting service. Reject requests with 429 if out of token or pass through the requests otherwise

Detailed component design

Synchronization issue: in redis, apparently, the rate limiting service can sends read write requetss to redis concurrently and we relies on sortedSet in redis to handle the synchronization problem.

Trade offs/Tech choices

Rate limiter locations: client-side/server-side/middle ware

The api rate limiter can be put in many places, like client-side/server-side/middle ware. Client-side isn't a good choice as malicious clients can get ride of rate limiter. As for server-sde and middleware, middleware is a better choice as it can be shared with other services as a standard solution.

Rate limiting algorithm choices:

We choose the token bucket as it is very simple and straighitward. Leaking bucket could fill up the queue with old requests and if they are not processed in time, recents requests wil be rate limited.

• token bucket: we maintain a bucket which will be refilled with token periodically. If there is still token, consume token and pass through the request. Otherwise, reject the requests
• leaking bucket: Use a queue to hold the incoming request and make the requests be consumed by fixed rate.

Failure scenarios/bottlenecks

The rate limiting service can be a bottlenecks if we have higher traffics so we can scale up the rate limiting service and also the redis.

Future improvements

Monitoring: we can add monitoring in the api gateway side to

• adjust different rate limiting algorithm by knowing how the rate limiting is enforced
• adjust the rate limit quota if needed

The rate limiting service should be per location instead of global so that we can have better performance