Rate Limiting

How to cap the requests each client can make, so that one caller cannot overload a service, crowd out other users or run up costs: the algorithms, one limit across many servers, and what to tell the client.

Overview

A rate limiter caps how many requests a client can make in a period of time, such as 100 requests a minute for each API key. When a client goes over, the limiter refuses the extra requests, usually with the HTTP status 429 Too Many Requests, or makes them wait.

Every public API has one, and most internal services should. Without a limit, one client with a runaway script can slow a service down for everyone, a scraper can copy your data, and an attacker can try thousands of passwords a minute. Limits also keep costs in check when each request spends money, for example on a paid third-party API.

This chapter covers the five classic algorithms and the burst each one lets through, how to enforce one limit across many servers without race conditions, and what the server and the client should do when a limit is hit. The real limits quoted come from the published documentation of Stripe, GitHub, AWS and others, so you can use them in an interview.

What you will be able to do

  • Explain fixed window, sliding log, sliding window counter, token bucket and leaky bucket, and the burst each one allows.
  • Enforce one limit across many servers with Redis, without race conditions.
  • Choose where a limit belongs: in the client, at the edge, in the service, or in front of a dependency.
  • Design the 429 response and the client's retry behavior.
  • Pick what to key a limit on, and handle shared IP addresses, tiers and exemptions.

Key concepts

  • Fixed window
  • Sliding log
  • Sliding window counter
  • Token bucket
  • Leaky bucket
  • Atomic updates in Redis
  • Local and global limits
  • 429 and Retry-After
  • Backoff with jitter
  • Limit keys and tiers

Interview questions

  • Design a rate limiter for a public API.
  • What goes wrong at a fixed window boundary, and how do sliding windows fix it?
  • How does a token bucket work, and how would you choose its two numbers?
  • When would you choose a leaky bucket instead of a token bucket?
  • You run 20 API servers. How do you enforce 100 requests a minute per user across all of them?
  • Why is read, check, then write wrong for a Redis counter, and how do you fix it?
  • What should the server send when it refuses a request?
  • How should a client handle 429 responses?
  • The Redis behind your rate limiter goes down. What happens?
  • How do you choose what to key a limit on?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio