M3 Design Rate Limiter

Design Rate Limiter

Welcome everyone, today we will explore how to design a rate limiter, from simple single box counters to multi region enforcement, balancing accuracy, scalability, and tradeoffs.

From TAO edges to protecting every call

Dr. Wei: Every time you ship an A-P-I, you are also shipping an attack surface: one script can melt your databases faster than any organic growth. Today we are going to discover the core design patterns behind a production rate limiter. The good news is the core idea is simple: count, budget, and say no. We will go from the social graph world you just learned to concrete algorithms, then to a distributed architecture that still works when you have many servers and many datacenters.

Sam: So this connects to TAO because graph reads can fan out across a lot of edges, right?

Dr. Wei: Exactly. Last lecture: TAO has objects and associations, and association lists are basically ordered edges like friends or likes. That is powerful, but it also means a single request can trigger a lot of downstream work.

Dr. Wei: So rate limiting is a safety valve: it prevents one caller from turning an edge-heavy traversal into a fleet-wide incident.

Sam: Is the goal strict correctness, like never exceeding a limit, or is some error okay?

Dr. Wei: Great I-C-6 instinct: drive the ambiguity. In practice we want bounded error: a small amount of over-admission is okay, but big under-enforcement is not, because that is how you get abuse and outages.

Why rate limiting exists in real systems

Dr. Wei: Here is what interviewers are looking for on motivation: rate limiting is not a fancy feature, it is a reliability and abuse-control primitive.

Sam: When you say primitive, do you mean it is something you build once and then reuse across lots of services?

Dr. Wei: Yes. In practice it is centralized policy plus a shared library or a sidecar, so many services can reuse the same limiter behavior consistently.

Dr. Wei: First: prevent abuse, like bots scraping user data or brute forcing endpoints.

Sam: So it is security, not just performance.

Dr. Wei: Second: protect resources, especially the database and downstream services. A limiter is often cheaper than scaling the entire graph stack.

Sam: Does that include protecting third-party dependencies too, like a payments provider, where you might have a hard quota?

Dr. Wei: Third: fairness. Without limits, one noisy client can steal capacity from everyone else.

Dr. Wei: Fourth: product and revenue. Free tier versus paid tier is basically a rate limit policy with accounting and exceptions.

Requirements that actually drive the design

Dr. Wei: At Meta, the rate limiter is itself a high-throughput system. If you put a slow limiter in front of a fast service, you just built a bottleneck.

Sam: So the limiter has to scale like a core service, not like a side feature.

Dr. Wei: We need multiple dimensions: per user, per I P, per endpoint, and sometimes per service-to-service caller.

Sam: That sounds like a lot of keys. Is the data model basically key plus counter?

Dr. Wei: Yes, and that is why scale matters. Think on the order of one million queries per second of limiter checks for a large A P I surface.

Dr. Wei: Latency budget: ideally under one millisecond overhead, which usually implies a local fast path and aggressive caching.

Dr. Wei: Finally: distributed behavior. Strict global consistency across datacenters is expensive, so we usually accept bounded error and design for safe failure modes.

$A-P-I$ contract: what clients see

Dr. Wei: A good design includes the on-the-wire contract. Otherwise clients will retry in the worst possible way.

Dr. Wei: When we reject, we use H-T-T-P 429 too many requests. That makes rate limiting explicit and machine readable for clients, not just implied.

Sam: Is that where Retry-After comes in?

Dr. Wei: Yes. We return Retry-After with a wait time in seconds, so the client can back off instead of hammering.

Sam: And do you usually include those limit and remaining headers even though an attacker could read them too?

Dr. Wei: We often include rate limit headers like limit, remaining, and reset time. They are not security, but they are great for developer experience.

Dr. Wei: Finally, we decide hard versus soft limits. Soft can degrade to cached or partial responses; hard is a strict reject.

Token bucket: the burst-friendly workhorse

Dr. Wei: Rate limiting seems simple until you need it to work across many datacenters with millions of users. So we start with an algorithm that is stable and intuitive: token bucket.

Dr. Wei: This equation is the state update: tokens grow over time at a refill rate, but never exceed the bucket capacity.

Sam: What is t zero here—like the last time we updated the bucket?

Dr. Wei: Yes. Think of t zero as the last observation or update time; when a request arrives at time t, you first refill based on the elapsed time since t zero, then cap at capacity.

Sam: So the bucket is like a savings account for burst traffic?

Dr. Wei: Exactly. Capacity controls how big a burst you can spend instantly.

Dr. Wei: Refill rate controls sustained throughput. Over long time windows, the average accepted rate is bounded by refill.

Sam: If different endpoints have different costs, do you ever worry that small requests get blocked behind a few expensive ones in the same bucket?

Sam: And after we refill, we immediately spend tokens for the request if we have enough, right?

Dr. Wei: Requests have a cost. Many real APIs use weights: one expensive endpoint might consume more tokens than a cheap one.

Dr. Wei: Decision rule: if you have enough tokens, accept and subtract the cost; otherwise reject with 429 and tell the client when to retry.

Token bucket example: burst $\,$vs sustained

Dr. Wei: Now we make this concrete with numbers, because numbers justify architecture in interviews.

Dr. Wei: With a capacity of one hundred and refill of ten per second, you can accept a burst of up to one hundred requests instantly.

Dr. Wei: After the burst, the sustained rate is about ten per second, because the refill is the long-term budget.

Sam: So if a client keeps hammering, they will just get a steady stream of 429s after the burst is gone.

Dr. Wei: Before I show it, predict: in a checkpoint with capacity ten and fifteen requests arriving at once, how many pass right away and how many get rejected?

Dr. Wei: Exactly: ten pass right away and five are rejected right away. And if you want to admit all fifteen, you need to wait about two and a half seconds to refill five more tokens at two per second.

Sliding window log: accurate, but expensive

Dr. Wei: Next algorithm: sliding window log. It is conceptually simplest: store every request time and count how many fall in the last window.

Dr. Wei: This equation is the exact count: you are literally counting timestamps newer than now minus the window length.

Sam: Implementation-wise, that is like a sorted set per key, right?

Dr. Wei: Yes: add the current timestamp, evict old timestamps, then check the cardinality. It is exact, but memory grows with traffic.

Sam: So for a hot key, you are storing basically one entry per request in that whole window, which can explode fast.

Dr. Wei: That cost can be brutal for high-Q-P-S keys: you store one entry per request in the time window, which is why this is rarely the Meta default.

Sliding window counter: cheap, approximate, good enough

Dr. Wei: Sliding window counter is the pragmatic compromise: you keep only two counters, then blend them based on how far into the current window you are.

Dr. Wei: This equation is the estimator: current count plus a weighted portion of the previous window count. Here a window is a fixed time bucket aligned to wall clock boundaries, like whole minutes. To compute alpha, first find the start of the current window by rounding the current time down to the nearest window boundary, then divide the elapsed time since that start by the window size.

Dr. Wei: In storage terms, that is just two integers per key with short T-T-Ls. That is why it scales.

Sam: Where does the approximation show up? Near the boundary?

Dr. Wei: Exactly. If traffic is bursty inside a window, averaging can misestimate, but the error is bounded and typically acceptable for abuse control.

Dr. Wei: Example: limit one hundred per minute; if the previous minute had eighty, and we are thirty seconds into the current minute with thirty so far, then the weighted previous part is forty, add the current thirty to get seventy, so we still allow.

Algorithm comparison: pick based on traffic shape

Dr. Wei: Interview signal: you are not graded on naming five algorithms, you are graded on choosing one and defending the tradeoff with traffic assumptions.

Dr. Wei: Fixed window is the simplest, but it has the boundary spike problem where you can double-spend across the cutoff.

Sam: This is the Redis increment with T-T-L idea I always start with, right?

Dr. Wei: Yes, and noticing that flaw is a good step up from I-C-4. Sliding log is exact but expensive. Sliding counter is cheap and usually good enough.

Dr. Wei: Token bucket is best when you want bursts but a stable long-term rate. This maps well to human behavior and mobile clients.

Sam: So if the product wants to allow quick refreshes but stop sustained scraping, token bucket is usually the first thing to reach for.

Dr. Wei: Meta-style detail: Graph A-P-Is often use a points system where endpoints have different costs, which is basically weighted token bucket plus accounting.

Distributed rate limiting: where correctness breaks

Dr. Wei: Now the real problem: distributed enforcement. If a user hits server A and server B, each server has only partial truth.

Dr. Wei: This bullet is the classic failure: limit eighty per minute, but A sees fifty and B sees fifty, so both allow while the user actually did one hundred.

Sam: If traffic spreads evenly across N servers and each uses only a local counter with a limit of eighty per minute, what is the maximum total the system could admit?

Dr. Wei: Pause and compute it. In the worst case, assume there is no sticky routing or affinity and the same client can hit every server. What number do you get for the total?

Sam: I think it could be eighty times N, because each server would independently allow up to eighty for the same user.

Dr. Wei: Exactly. In that worst case, you can admit up to eighty times N per minute, because each server can independently allow eighty for the same key. With sticky sessions or consistent hashing, you can reduce this, but without coordination the overshoot can grow with the number of servers.

Dr. Wei: Option three is the common answer: hybrid. Local fast path plus periodic sync to a shared store, which bounds the overshoot to a known error window instead of letting it grow with the number of servers.

Reference architecture: local fast path $+$ shared backstop

Dr. Wei: Here is a high-level architecture that an interviewer will recognize as realistic: a fast decision locally, with a shared system to keep you honest and configurable.

Dr. Wei: First component: the limiter sits near the edge, often in the API gateway or a sidecar, so every request is checked before expensive work.

Dr. Wei: Second: a local in-memory cache holds hot buckets and counters so most requests avoid a network call. This is how you hit sub-millisecond overhead.

Sam: What kind of strategy do you use to keep the local cache from drifting too far from the shared store, especially during bursts?

Sam: Where does the shared truth live? Some kind of key-value store?

Dr. Wei: Right: a shared store like Redis or another key-value database. The key is it is not on the critical path for every request.

Dr. Wei: Third: periodic sync and auditing. You can stream aggregated usage through an async log pipeline, then reconcile and adjust budgets.

Dr. Wei: Finally: rules are config-driven, often behind feature flags, so you can change limits instantly during incidents. Examples in real stacks include internal flag services, or tools like LaunchDarkly.

Rules engine: multi-tier limits and weighted costs

Dr. Wei: A production limiter is not one limit. It is a rules engine: multiple tiers, multiple dimensions, and different actions.

Dr. Wei: First: rule dimensions. You might limit per user and per endpoint and globally, all at the same time.

Dr. Wei: Second: multi-tier example. A request must pass the per-user bucket, the per-endpoint bucket, and the global bucket.

Sam: And the weighted points idea fits naturally: each endpoint burns a different amount of budget.

Dr. Wei: Exactly. With weights, you are approximating real cost. That is why Graph-style scoring is robust: expensive calls consume more points.

Sam: If a request matches multiple rules, do you fail fast on the first violation, or do you want to evaluate all rules for better logging?

Dr. Wei: Third: dynamic adjustments. During incidents you can drop limits quickly, and for trusted apps you can raise limits, all without redeploys.

Failure modes, tradeoffs, and an exit ticket

Dr. Wei: Before we close, I want two things: the failure modes that make your design credible, and a small practice problem to test if the algorithm is internalized.

Dr. Wei: Practice: token bucket with capacity one hundred and refill ten per second. If you have twelve tokens now and each request costs five tokens, you can accept two requests immediately, then you need about three tenths of a second to get enough tokens for one more request.

Sam: Because two requests cost ten tokens, leaving two, and you need three more tokens at ten per second.

Dr. Wei: Reflection: when would you place the limiter at the gateway versus inside the app? Gateway protects shared infrastructure earlier; app-layer can use richer identity and context but it is later in the request path and more expensive.

Thank you for watching!

Thanks for watching. Subscribe and share if you found this useful—see you next time!