Papers
Scaling your API with rate limiters
Paul Tarjan · Stripe Engineering Blog, 2017
The problem: protecting a shared API without punishing those who behave well
The text, published on Stripe's engineering blog, describes how the company uses rate limiters and load shedding mechanisms to keep the API available to all users. The first few times traffic spikes, it is reasonable to simply add capacity to accommodate user growth; after that, a production API needs to ensure that a single problematic actor, by accident or on purpose, does not affect the availability of everyone else. The author lists scenarios in which limiting helps: a user causes a traffic spike, a faulty script sends too many requests, a user sends many low-priority requests that could get in the way of critical ones, or something fails internally and low-priority traffic needs to be dropped. A rate limiter controls the speed of traffic and is appropriate when the client can change the pace of its calls without changing the outcome; if spacing out the requests isn't possible (typically real-time events), the author says that most of the time what's missing is more infrastructure capacity. The article also distinguishes the load shedder: during incidents, it drops low-priority requests and decides based on the state of the whole system, not on the user who made the call. Stripe operates four types of limiters in production and recommends starting with the request rate limiter.
The first two limiters: request rate and concurrent requests
The request rate limiter restricts each user to N requests per second. The author calls it by far the most important and says it triggers constantly, having rejected millions of requests in a single month, mostly in test mode, when a script gets out of control. Test and production modes have the same limiting behavior, so that a script does not run into side effects when moving to production. After analyzing traffic, Stripe added the ability to briefly exceed the cap during sudden spikes in real-time events, such as a flash sale. The second is the concurrent requests limiter, which instead of limiting calls per second says something like: there can only be 20 requests in flight at the same time. Some endpoints consume far more resources than others, and users frustrated by the wait retry, adding demand to an already overloaded resource. This limiter triggers far less often (12 thousand requests in the month cited), but, according to the author, it completely solved resource contention on the most expensive endpoints. It calls for a different programming model from the other: firing off X tasks that consume a queue, instead of hammering the API and backing off when receiving HTTP 429. Each API can choose the pattern that best fits its users.
The load shedders: fleet usage and worker utilization
The other two mechanisms decide based on the state of the system, not on the user. The fleet usage load shedder ensures that a portion of the fleet is always available for the most important requests. Stripe splits traffic into critical methods (the example is creating charges) and non-critical ones (the example is listing charges); a Redis cluster counts how many requests of each type exist at the moment. With a 20% reserve, any non-critical request above the 80% allocation is rejected with a 503 status. The author says it fired for a very small fraction of requests in the cited month, but that in other months it prevented outages. The worker utilization load shedder is the last line of defense: if workers start accumulating requests, it starts dropping lower-priority traffic. Traffic is split into four categories: critical methods, POSTs, GETs, and test mode traffic. Stripe tracks how many workers have free capacity; if a machine is too busy, it slowly starts dropping the least critical traffic, beginning with test traffic, and escalates to more dropping if that isn't enough. Dropping and readmitting load must be slow, to avoid flapping. Only about 100 requests were rejected by it in the cited month; it limits the impact of incidents already in progress, while the first three are more preventive.
Implementation and launch: token bucket, fail open, kill switches, and dark launch
For the algorithm, Stripe uses the token bucket: there is a central bucket host from which a token is taken on each request, while new tokens are replenished gradually; if the bucket is empty, the request is rejected. Each user has their own bucket. The implementation uses Redis, which can be operated by the team itself or, on AWS, through a managed service such as ElastiCache. The text gives four practical precautions. First, plug the limiters into the middleware safely: if there is a bug in the limiting code or Redis goes down, requests must not be affected, which means catching exceptions at every level to fail open. Second, show clear errors: decide between HTTP 429 (Too Many Requests) and HTTP 503 (Service Unavailable) depending on which is more accurate for the situation, with an actionable message. Third, have kill switches and feature flags to turn off limiters that fire by mistake, plus alerts and metrics on how often they fire. Fourth, do a dark launch of each limiter, observing the traffic it would block, to assess whether the decision is right and tune the thresholds without affecting existing usage patterns; the author admits this may require working with some users to change their code. The conclusion is that not all limiters are needed on day one and they can be introduced gradually.
See the ideas at work
Practice the designs that use this paper in the System Design school.