Samsung Blog

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Classic System Designs · 12 minDesign a rate limiterCap how often a client can call an API: the common algorithms, where to put the limiter and how to make it work across many servers.Read hereClose

  The problem

  A rate limiter restricts how many requests a client may make in a period. It protects a service from abuse, accidental floods and runaway scripts, keeps costs predictable and shares capacity fairly.

  Requirements

  • Limit by user, API key or IP, with different limits per rule or plan.
  • Add very little latency to each request.
  • Work across many servers, not just one.
  • Tell rejected clients clearly what happened.
  • If the limiter itself fails, the API should not go down with it.

  Image: Digitura · CC0 · Source · Wikimedia Commons: Gulf, traffic jam 1970s

  Where to put it

  100%

  Figure SDA-CSD-01-1 · Rate limiter in front of the service · © forcsguy.com

  The usual home is the API gateway or a middleware layer, because it sees every request early and rejects cheaply. Building it into each service duplicates effort, and a client-side limiter cannot be trusted.

  Here is the same service without a limiter, and with one in front. Switch on Simulate and raise the traffic to see what each version does when a script floods it.

  Before: Nothing in front

  100%

  After: Limiter at the gateway

  100%

  What changed

  • The abusive client is stopped at the gateway, not at the service
  • Counters sit in one shared store, so every server sees the same count
  • Blocked requests cost almost nothing to answer

  Algorithms

  Algorithm	Idea	Good	Bad
  Token bucket	A bucket refills at a steady rate; each request takes a token	Allows bursts, tiny memory	Two numbers to tune
  Leaky bucket	Requests join a queue processed at a fixed rate	Smooth output rate	Bursts fill the queue, old requests delayed
  Fixed window counter	Count per minute, reset at the boundary	Simplest	Burst across a boundary doubles the limit
  Sliding window log	Keep a timestamp per request, count those within the window	Exact	Memory per request
  Sliding window counter	Weight the previous window's count by overlap	Cheap and close to exact	Approximate

  Token bucket is a strong default: it is cheap, and bursts are usually fine for real clients. The sliding window counter is a good choice when you need smoother accuracy.

  Token bucket in a few lines

  For each key store (tokens, last_refill_time). On a request:

  1. Add elapsed x refill_rate tokens, up to the bucket size.
  2. If at least one token is available, take it and allow the request.
  3. Otherwise reject.

  The algorithms in pictures

  Token bucket. Tokens drip into a bucket of fixed size; every request must take one.

  100%

  Figure SDA-CSD-01-2 · Token bucket decision · © forcsguy.com

  A walk through time (bucket of 4, refilled to full each minute):

  100%

  Figure SDA-CSD-01-3 · Token bucket over a minute · © forcsguy.com

  Leaky bucket. Requests wait in a bounded queue and leave at a fixed rate.

  100%

  Figure SDA-CSD-01-4 · Leaky bucket · © forcsguy.com

  Fixed window counter and its boundary problem. One counter per clock window is simple, but two bursts on either side of the boundary can pass double the limit.

  100%

  Figure SDA-CSD-01-5 · Fixed window boundary burst · © forcsguy.com

  Sliding window log. Keep a timestamp for every accepted request and count those inside the last window.

  100%

  Figure SDA-CSD-01-6 · Sliding window log (2 per minute) · © forcsguy.com

  Sliding window counter. Blend the previous window's count with the current one, weighted by how much of the previous window still overlaps the last minute.

  100%

  Figure SDA-CSD-01-7 · Sliding window counter estimate · © forcsguy.com

  Making it work across servers

  Counters must be shared, otherwise each server enforces its own limit and a client gets N times the allowance. A fast in-memory store such as Redis works well.

  • Use an atomic operation (INCR with expiry, or a small Lua script) so the check and the update happen together. A separate read then write lets two servers both slip through.
  • Put the key in a predictable shape: rate:{user}:{rule}:{window}.
  • Partition keys across several Redis nodes for scale (consistent hashing, covered in lesson 2).
  • To save round trips, some systems keep local counters and sync periodically, accepting small overshoot.

  Why counters must be shared when there are several limiter servers:

  100%

  Figure SDA-CSD-01-8 · Why limiter servers need shared state · © forcsguy.com

  The system around the algorithm

  100%

  Figure SDA-CSD-01-9 · Detailed rate limiter design · © forcsguy.com

  The race condition when two servers read the same counter at once, and the fix:

  100%

  Figure SDA-CSD-01-10 · Read-modify-write race on a counter · © forcsguy.com

  Responses and visibility

  Return HTTP 429. Include headers so clients can behave: how many requests are allowed, how many remain, and when they reset, plus Retry-After. Log rejections and watch them, since a sudden rise can mean an attack, a bug in a client or a limit set too low.

  Going deeper

  Two races hide in "read, check, write". If two requests read the counter at 3 at the same moment, both write 4 and one request goes uncounted. A lock fixes it but slows every request; the usual answers are an atomic script that does the read, check and increment in one step inside Redis, or a sorted set that stores one timestamp per request so each request is a single atomic add.

  Many limiter servers need shared state. If each server counted only the traffic it sees, a client could send half its requests to each and double its quota. Sticky routing (always the same limiter for a client) helps but breaks when servers change and uneven load builds up. A central store such as Redis, or periodic sync with eventual consistency, is the common fix. Across regions, accept a little over-admission in exchange for not paying a cross-ocean round trip on every request.

  Where the rules live. Keep rules as data on disk or in config (for example "login: 5 per minute", "marketing messages: 5 per day"), have workers refresh them into a cache, and let the limiter read them from there, so tightening a rule never needs a deploy.

  Measure it. Watch two things: rules that are too strict (many valid users rejected) and an algorithm that cannot absorb a flash-sale burst. In the second case a token bucket, which allows short bursts, is the usual swap.

  Other layers and the client's side. The same idea works lower down, for example per IP address in the network layer rather than per user in HTTP. Well-behaved clients cache responses, respect the limit headers, handle the rejection gracefully, and back off before retrying.

  An approximate sliding-window counter blends the previous window's count (weighted by how much of it still overlaps) with the current one. It assumes traffic was even in the previous window; published tests by one large CDN found only a tiny fraction of requests were misjudged, so for most uses the saving in memory is worth it.

  Failure and edge cases

  • Limiter store down: usually fail open (let requests through, alert loudly) so you do not turn a limiter outage into an API outage. For security-sensitive endpoints (login attempts) you may prefer failing closed.
  • Clock differences between servers: base windows on the store's clock, not each server's.
  • Hard versus soft limits: some rules throttle (delay), others reject.
  • Many identities: also limit by IP for anonymous traffic, and watch for one client rotating keys.

  A worked example: setting the limits

  Say your public API has a free plan and a paid plan. You decide a free client may make 60 requests per minute with bursts up to 10, and a paid client 600 per minute.

  • Token bucket for the free plan: capacity 10, refill 1 token per second. A client idle for 10 seconds can fire 10 requests at once (the burst) and then settles to 1 per second. After a 429, it must wait about a second for the next token.
  • How much traffic is that? If 50,000 free clients all use their full allowance, that is 3,000,000 requests per minute, or 50,000 per second. You almost never see that, because most clients use a fraction. Sizing from the allowance gives the worst case; sizing from observed use gives the normal case. Plan the limiter and the servers behind it for the first, and alert on the second.
  • Counter memory: a token bucket needs two numbers per client (tokens, last refill time), about 16 bytes plus key overhead, say 100 bytes. For 10 million active clients that is about 1 GB, comfortably within one Redis node. A sliding window log would store a timestamp per request, up to 60 per client, which is 5 to 10 times more, one reason counters and buckets are the usual choice.

  100%

  Figure SDA-CSD-01-11 · Choosing limits by plan · © forcsguy.com

  Walking through a rejected request

  1. A client sends its 61st request in a minute.
  2. The edge gateway extracts the key (API key, falling back to IP address) and asks the limiter for that key.
  3. The limiter reads the bucket from the shared store, sees no tokens, and answers "no" without touching the application servers.
  4. The gateway returns HTTP 429 with a Retry-After header and, if you publish them, headers such as X-RateLimit-Limit and X-RateLimit-Remaining, so well-behaved clients can slow themselves down.
  5. The rejection is counted in metrics. A rapid rise from one key suggests abuse; a rise from many keys suggests your limit is too tight or a new client release is misbehaving.

  The cost of refusing is tiny compared with the cost of doing the work, which is the whole point: the limiter's decision must be much cheaper than the request it protects.

  When the limiter itself fails

  A limiter is in the path of every request, so decide in advance what happens when its shared store is slow or down:

  • Fail open (let requests through): users keep working, but you lose protection exactly when something odd is happening. Good for most public APIs, usually with a local fallback limit per server.
  • Fail closed (reject everything): safe for anything where overload is worse than refusal, such as an expensive or sensitive operation.
  • Keep a small local, in-memory limit on each server as a backstop, so even with the shared store down a single server cannot be flooded.

  100%

  Figure SDA-CSD-01-12 · Fail open with a local backstop · © forcsguy.com

  Mistakes people make

  • Limiting only by IP address. Many users share one address (offices, mobile carriers), and attackers rotate addresses. Prefer an API key or user id, with IP as a fallback.
  • Using the wrong clock. Limiter servers whose clocks drift apart count windows differently. Take time from the shared store, not each server.
  • Race conditions on counters. Reading a counter, adding one and writing it back lets two requests slip through together. Use an atomic increment or a small server-side script.
  • No visibility. Without rejection metrics you cannot tell abuse from a limit set too low.
  • Rejecting without guidance. Send Retry-After so clients can back off properly instead of retrying immediately and making things worse.

  Try it yourself

  Open the System Builder challenge A noisy client. One abusive client sends 97% of the traffic. Try to survive it by adding servers (you cannot, within 12), then switch on the rate limiter and watch the real users' errors disappear. Then build the sliding window rate limiter lab and see the boundary burst for yourself. You can also open the noisy-client design on the free canvas and place the rate limiter where you think it belongs.

  More on this site

  Related reading

  • How we built rate limiting capable of scaling to millions of domainsCloudflare engineering · CloudflareCase Studies
  • Scaling Your API with Rate LimitersPaul Tarjan · StripeBlogs
  • Using load shedding to avoid overloadAmazon Builders' Library · Amazon Web ServicesBlogs
  • Rate Limiting with NGINXNGINX · F5 / NGINXBlogs

  Show 6 moreShow fewer

  • HTTP/3: the past, the present, and the futureCloudflareBlogs
  • Julia Evans' BlogJulia Evans · jvns.caBlogs
  • Redis BlogRedis engineers · Redis Ltd.Blogs
  • RFC 9114: HTTP/3IETFDocumentation
  • Samsung BlogSamsung engineers · SamsungBlogs
  • Databricks Engineering BlogDatabricks engineers · DatabricksBlogs

  Open this lesson with its quiz and exercise