Rate limiting sounds like one problem until you notice that 100 requests per minute is ambiguous. May I send all 100 in the first second?

Each algorithm is a different answer to exactly that question.

Token bucket

Start with the token bucket, the workhorse here. A bucket holds up to some number of tokens and refills at a steady rate. Each request spends one, and an empty bucket means refusal.

Read the depth as your burst allowance and the refill rate as your sustained average. A client can go quiet and then fire a full bucket at once. Real traffic is bursty, since page loads fire clusters of calls, and that is why this is the default in most gateways. Two integers per client is the entire state.

Flip the goal with a leaky bucket, where requests queue and drain at a fixed rate, so whatever arrives, what comes out is smooth. Choose it when the thing you are protecting genuinely cannot absorb bursts, and accept the queueing latency as the price of the smoothing.

Window counters, and where they leak

Avoid the fixed window counter, which counts requests per clock minute. It is trivially cheap, and its boundary leaks: 100 requests at 11:59:59 plus 100 more at 12:00:01 puts double your intended rate through in two seconds, and traffic synchronises on the reset tick.

Keep a sliding window log, a timestamp per request, and you can count the last 60 seconds exactly. Precise, and your memory grows with your request rate. That is backwards, because the limiter gets most expensive exactly when somebody abuses it.

Take the sliding window counter as the fix. Keep two window counters and weight the previous one by how much it still overlaps. One large CDN runs this across its edge and measured the approximation error as negligible on real traffic.

Reduce the choice for most systems to two options. Token bucket for API limits, sliding window counter when boundary bursts genuinely must not happen.

the shape of it

step 1 of 2

The bucket's depth permits bursts up to 40 while the refill rate caps the sustained average at 2 per second.

the token bucket, which is most of what you will ever need

Java

// Two integers per client. Depth allows a burst, refill rate caps
// the sustained average.
boolean allow(String client) {
  Bucket b = buckets.get(client);
  long now = System.nanoTime();

  // Refill for the time that has passed, never above capacity.
  double refill = (now - b.lastRefill) / 1e9 * RATE_PER_SEC;
  b.tokens = Math.min(CAPACITY, b.tokens + refill);
  b.lastRefill = now;

  if (b.tokens < 1) return false;      // empty bucket, refuse
  b.tokens -= 1;
  return true;
}

// Across ten gateways this has to be atomic, or two of them both
// read 99 tokens and both admit request 100. Read, refill, spend
// and answer in one server-side script.

Worked example

Shopify's public API makes the token bucket visible enough to teach from. Each app gets a bucket of 40 requests that refills at 2 per second, and every response carries a header like X-Shopify-Shop-Api-Call-Limit: 32/40. Jonas builds an inventory sync app and watches it live: his backfill fires 40 requests instantly, all succeed, and request 41 gets a 429 because the bucket is dry. He adds a governor that checks the header and throttles to 2 requests per second when the reading passes 35, and the backfill of 12,000 products completes in about 100 minutes with zero rejections. The burst capacity still helps him: interactive syncs of a few dozen products finish in one instant volley instead of dribbling out over 20 seconds.

The Algorithms

Token bucket

Window counters, and where they leak

Worked example