System requirements

Functional:

• Accurately limit excessive requests.
• Distributed rate limiting. The rate limiter can be shared across multiple servers or

processes.

• Exception handling. Show clear exceptions to users when their requests are throttled.

Non-Functional:

• Use as little memory as possible.
• Low latency. The rate limiter should not slow down HTTP response time.
• High fault tolerance. If there are any problems with the rate limiter (for example, a cache

server goes offline), it does not affect the entire system.

Capacity estimation

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

API design

Define what APIs are expected from the system...

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...

High-level design

flowchart TD

C["client"];

R["Rate limiter middleware"];

S["web servers"];

R1["Redis cluster"];

C --> R;

R --> S;

R --> R1;

• The client sends a request to rate limiting middleware.

• Rate limiting middleware fetches the counter from the corresponding bucket in Redis and

checks if the limit is reached or not.

• If the limit is reached, the request is rejected.

• If the limit is not reached, the request is sent to API servers. Meanwhile, the system

increments the counter and saves it back to Redis.

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...

Detailed component design

flowchart TD

C["client"];

R["Rate limiter middleware"];

S["web servers"];

R1["Redis cluster"];

n3["local cache"];

n4["workers"];

n5[("disk")];

subgraph n6["message queue"]

end

C --> R;

R --> S;

R --> R1;

R1 --> R;

R --> n3;

n3 --> n4;

n4 --> n5;

R --> n6;

algorithms we can choose:

• Token bucket

• Leaking bucket

• Fixed window

• Sliding window log

• Sliding window counter

Rules are stored on the disk. Workers frequently pull rules from the disk and store them

in the cache.

• When a client sends a request to the server, the request is sent to the rate limiter

middleware first.

• Rate limiter middleware loads rules from the cache. It fetches counters and last request

timestamp from Redis cache. Based on the response, the rate limiter decides:

• if the request is not rate limited, it is forwarded to API servers.

• if the request is rate limited, the rate limiter returns 429 too many requests error to

the client. In the meantime, the request is either dropped or forwarded to the queue.

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

• redis cluster was down
• traffic surge， rate limiter crash

Future improvements

• add monitor to check if the limit rule works
• compoments scale-out, like rate limiter middleware, add replicaes