System-Design-Notes

[System Design] Rate Limiter

High-Level Design

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

Token bucket algorithm

Bucket size: the max number of tokens; Refill rate: number of tokens put into.

• Pros: memory efficient; allow a burst in short periods;
• Cons: hard to tune the two parameters.

Leaking bucket algorithm

Bucket size: equal to the queue size; Outflow rate: processing speed.

• Pros: memory efficient (limited queue size); process at a fixed rate.
• Cons: a burst of traffic will fill up the queue and limit the recent requests; hard to tune the 2 parameters.

Sliding window log algorithm

Keep track of request timestamps using Redis; Remove outdated timestamps when new requests come; limit according to the log size.

• Pros: accurate, not exceeding the limit.
• Cons: consume lots of memory; need to store timestamp even if a request is rejected.

Sliding window counter algorithm

requests in the rolling window = Requests in current window + requests in the previous window * overlap percentage of the rolling window and previous window.

• Pros: smooth out spikes through avg; memory efficient.
• Cons: assume the previous window are evenly distributed.