9 ms·
An Alternative Approach to Rate Limiting
- jnwatson 9y agoSounds like a lot of work to avoid writing 20 lines of Lua.
- jdwyah 9y agoagreed. I was a bit leery of diving into Lua as I was building http://ratelim.it http://ratelim.it but it really expands Redis's capabilities dramatically and was easy enough to add. My apps all write the lua into redis and store the hash when they boot up. Duplicative, but means everybody is on the same page and it's easy to store the lua in the main codebase.
- wpeterson 9y agoHey buddy! Reading all the design and discussion I was. Rey curious how you structured things at a brass tacks storage level.
- jdwyah 9y agoyoo! https://www.slideshare.net/jdwyah/diy-heroku-using-amazon-ecs-and-terraform https://www.slideshare.net/jdwyah/diy-heroku-using-amazon-ec... does have a bit of a pretty picture, but the basic idea is: For each rate limit you can choose to be in one of two modes: 1) Redis with a backing store of DynamoDB aka BestEffort since there are failure modes where you could lose an update. In this mode everything expects to happen in Redis, but if we don't find your limit there we check Dynamo. Writes are asynchronously persisted to Dynamo. 2) Token Buckets straight in DynamoDB. This is our Bombproof mode. (details in https://www.ratelim.it/documentation/safety https://www.ratelim.it/documentation/safety) It's worth noting that with either of these you can cache aggressively in the clients whenever the limits have gone over. Both the clients https://github.com/jdwyah/ratelimit-ruby https://github.com/jdwyah/ratelimit-ruby https://github.com/jdwyah/ratelimit-java https://github.com/jdwyah/ratelimit-java do that for you.
- deleted 9y ago[deleted]
- perfmode 9y agoI'd be curious to see the Lua code that implements this. Anyone care to indulge me?
- chickenfries 9y agoI'm guessing it would look something like this... I omitted checking if the token is in the 1 minute window. It returns false if the user has reached the rate limit, true if the user has more tokens left. If the user has tokens left, it decrements the token the user has left before returning true. local id = "user_1" -- Get the number of tokens the user has left local tokens = redis.call("HGET", id, "tokens") if tokens = 0 then -- User has no tokens left return false else -- User has tokens left, decrement token count redis.call("HINCRBY", id, "tokens" -1) return true end Redis lua scripts block while they are running, so the two redis calls here cannot be interleaved with other reads, as in the token bucket example from the article.
- perfmode 9y agothats really not bad at all.
- michaelmior 9y agoI wrote Locomotor[0] to automate the translation of Python code to Lua for Redis. Basically, you add an annotation to a function and the first time the code executes, it's converted to Lua and shipped to the server. You can see an example here[1]. It's far from foolproof and many Python language constructs have not been implemented, but it can handle some relatively complex code. [0] https://github.com/michaelmior/locomotor https://github.com/michaelmior/locomotor [1] https://github.com/michaelmior/locomotor/blob/master/bench/tpcc.py https://github.com/michaelmior/locomotor/blob/master/bench/t...
- timothycrosley 9y agoI would think if you have a consumer application that can't handle double what is set as the rate limit during a very small corner case (start and end of the the minute barrier) you have bigger problems. As you're still effectively enforcing your rate limit over time with that approach. This just sounds like micro-optimization at its worst.
- zokier 9y agoYeah, I was also thinking how meaningful ~20MB of memory use really would be in this context. Or how badly would racy token bucket perform in the real world. Still, enjoyed the read.
- jdwyah 9y agoI think this is an important point. Trying to store all of these in RAM means you can only have so many. Which is why I really like something that can use a backing store of a more cost efficient DB. Once you start thinking about what you could do if you could have 1000s of rate limits per user you end up thinking of lots of interesting ways to use them. Like limiting how often you log/track-usage to 1/hr per event per user. That's saved me a ton of money. Second thought: token buckets have a nice property of being really cacheable once they expire. You can push down a "won't refill until timestamp" and then clients can skip checking altogether.
- limeyx 9y agoThe racy code can behave very poorly based on some tests I did of my very first attempts at this !
- mattb314 9y agoAgreed. Especially given that these rate limits seemed to be aimed at stopping something catastrophic like spammers using 100x allotted capacity, a 2x innacuracy shouldn't really matter. The solution was interesting, however, and I could see it being useful in a situation where users are expected to run very close to their rate limits. For example, I could see AWS being fairly careful about not letting anyone use more than their allotted compute/network bandwidth because getting double bandwidth without paying for it is a pretty big deal.
- daliwali 9y agoI think rate limiting is the wrong idea. Say for example, a client wants to re-fetch everything that it has cached, it may send a burst of requests in a short amount of time, and some of those requests may be wrongly rejected due to rate limits. This is what happens when a browser refreshes a page for example. A better approach I think is delaying request handling based on resource allocation. If one client is disproportionately using up more time than others, then processing that clients' request will be queued up to process later, while well behaving clients will get their requests handled quickly. I think this is a more realistic approach and imposes less arbitrary restrictions.
- philsnow 9y agoWhere do you queue those requests ? If you do it anywhere under your own control, you will accumulate memory and open connections. If you issue a 429, the client knows it needs to wait and retry, and you've pushed the backpressure all the way past the demarcation line of your own infrastructure.
- daliwali 9y agoOne could limit concurrent connections per address. The idea is that an OPTIONS request which doesn't take much resources at all could be treated with a different weight than a POST which costs the server time to process.
- philsnow 9y agodepending on the resources being thrown at you, just trying to limit concurrent connections per address could help (there's the question about how to keep information about how many connections a given address has opened distributed to your load balancing layer and consistent, or at least consistent enough to mostly do the right thing most of the time) maybe that doesn't help with ipv6, though. you'd run out of memory if you tried to keep track of every /128, and different ISPs hand out different blocks to customers (some give out a /64, maybe some give each customer their own /72, etc). > The idea is that an OPTIONS request which doesn't take much resources at all could be treated with a different weight than a POST which costs the server time to process. I'm curious, what frameworks/libraries/whatever have you seen that use HTTP OPTIONS ?
- sarreph 9y agoThis is why I like HackerNews comments. As a primarily front-end dev building a SaaS, I'd already bookmarked this post and was planning implementing it. But it seems like the comments here are pointing me in a better direction.
- joaodlf 9y agoIt's a nice post with a lot of detail and nice imagery... With that said, how would a simple, slightly modified, exponential backoff work any worse?
- dvt 9y agoLiterally was about to post exactly this (I was thinking Fibonacci). The article's solutions seems like way too much work for something that shouldn't be half as complicated.
- cakoose 9y agoWhat? These are different things. This article is about the server deciding which requests to reject. Exponential backoff is a strategy clients use deciding when to retry after their request is rejected. (Plus, the article is about malicious clients; they're not going to follow your preferred backoff strategy.) More concretely, how would exponential backoff ensure that you don't allow more than 10 requests/second per user?
- stonelazy 9y agoWas wondering what would be the best way to rate limit API requests that are in the order of thousands per minute, am guessing not any of the methods suggested in this write up helps?! Help pls.
- jdwyah 9y agowhy not? 1000s/min should be NBD.
- stonelazy 9y agoReally ? In our product, an average user can send request of upto 4000/minute and we have about 1000 users now. Do you think would it be possible to scale ? Suppose, if maintained a list in redis with sorted time stamp, then for every incoming request i will have to make get query to redis for count of requests in last one minute, one hour, one day (3 calls) and then insert a timestamp for this current request. So, totally 4 requests. Apart from this suppose if concurrency handling (number of concurrent connections allowed by a particular user) is also built then that will also include additional redis calls. Do i make sense to you ?
- irgeek 9y agoIn response, we implemented a shadow ban: On the surface, the attackers continued to receive a 200 HTTP response code, but behind the scenes we simply stopped sending document invitations after they exceeded the rate limit. And right there they broke the service for legitimate users. Totally unacceptable collateral damage IMHO.
- matt_wulfeck 9y agoAgreed. This would be so absolutely frustrating to me and very easy to circumvent for nefarious people.
- nullnilvoid 9y agoThe problem with rate limiting is to distinguish a normal user from a spammer. A normal user can send more requests than usual sometimes. If a normal user gets rate-limited by mistake, you are going to get lots of upset users.
- vacri 9y agoRate-limiting is also used to protect against legitimate users who have made mistakes in config (or are poorly-skilled), not just spammers. It's much better to let them know why things aren't working than actively lie about it.
- vacri 9y agoWow, that's really bad. I get shivers at the thought of trying to troubleshoot that as a client.
- ioddly 9y agoI've had this happen before. Found out I was locked out from an email I read later while the login form happily rejected all my attempts.
- lenzm 9y agoShadow ban for everyone that exceeded the rate limit or just the one attacker? As others have said that's shitty for legitimate users that go over the rate limit.
- deleted 9y ago[deleted]
- joneholland 9y agoYou know you can implement a token bucket that doesn't share state between your API servers, in about 10 lines of code, using just a in memory map. Your incoming requests should be balanced across all of the servers so you just derive the allowed throughput and divide by the number front ends....
- drchickensalad 9y agoYou have to send all the traffic from one client to one server then right? Seems not without heavy drawbacks. Otherwise you can easily get them to hit their limit super early with bad luck.
- joneholland 9y agoNo, you evenly round robin all traffic to all servers. Each server contains a map of tokens per per client filling at a fixed interval. That interval is calculated by taking the total global token refresh rate and dividing it by the number of servers. The end result is exactly the same but, now you are stateless and have eliminated the bottleneck of a central token bucket.
- hyperpape 9y agoWait, each client does its own round robin (if you have three servers, I will hit 1 then 2 then 3)? Is that common?
- joneholland 9y agoThe client doesn't do it. You put your front ends behind a load balancer like an ELB, or use a reverse proxy like Nginx. Edit: And yes, round robin is the most commonly used load distribution technique, and works very well assuming each request has a roughly equivalent unit of work cost.
- hyperpape 9y ago
- pacaro 9y agoIt's good practice to rate limit endpoints for a variety of reasons, but in particular any endpoint that exposes user authentication should be rate limited. So this should be a tool that every service at scale has access to. IIRC the lack of rate limiting burned Apple relatively recently. Is this yet another area where we all reinvent the wheel? I've yet to see a recommendation for an off the shelf solution
- contingencies 9y agoZooming out a little, the fundamental problem here is broadly recognized as a modern protocol design challenge. To phrase the consideration roughly: the response to a request should not require more resources than the client has already spent to request it, either in terms of bandwidth or processing (including memory, storage IO bandwidth, etc.). Obviously, in some cases such design is not possible. The classic case is HTTP, where the entire purpose is to supply some (arbitrarily large) volume of data in response to a small request, and therefore there is a bandwidth challenge. Conventional defense strategies tend to utilize the fact that TCP requires a three-way handshake to instantiate, thus validating the peer's IP address (unlike UDP), and include: (1) An authenticated session, eg. using a session key derived from a separate API call. (2) Rate limiting per authenticated user, either based upon data over time or request frequency. (This alone is the subject of the article) (3) Segregating read-only, cacheable data (even if it expires within seconds) on separate infrastructure such as CDNs or memory-based caches. (4) Aggressive use of HTTP caching. (5) Careful tuning of HTTP session length related configuration to suit the application profile. A newer strategy is the use of captcha, however this is not viable in automated (ie. API) use cases. Another relatively 'new' (for HTTP) strategy is the use of websockets or other mechanisms for real time 'push', to avoid the latency and processing overheads of the conventionally enforced HTTP request-response model. Additional options would include segregating clients to speak to different servers (ideally in different data centers, on different links) such that overhead may be scaled across different infrastructure. Thus even if a single server is targeted by an attacker damage is limited in scope. Another architectural defense would be the enforcement of a gateway/proxy layer (internal or third party) obscuring real datacenter netblocks from attackers, however this comes at the cost of latency where data cannot be cached. Cloudflare basically provide all of the above (plus additional features) as a service. Finally, in native mobile application development where an API is the primary interface with some central system, another simple step that can be taken (with appropriate care regarding peer authentication and cache invalidation) is the use of a cached set of IP addresses within the client as a means to identify servers. In this way, attacks against DNS infrastructure will also be nullified, and you can focus the demands of segments of your user base on different infrastructure. (Here in China, DNS is often hijacked or broken, though this is much less of a concern in typical western environments. It will also reduce startup latency on slow mobile links the world over.)
- sulam 9y agoThere's a fixed memory solution that doesn't suffer from the boundary condition that allows you to double the rate. It's pretty straightforward, so I'll describe it in prose, since it's 6am and I'd rather not get the code wrong. :) The approach uses a ring buffer. If you're not familiar with them, they are a fix-sized array or linked list that you iterate through monotonically, wrapping around to the beginning when you are at the limit. Our ring buffer will hold timestamps and should be initialized to hold 0's -- ensuring that only someone with a time machine could be rate limited before they send any requests. The size of the buffer is the rate limit's value, expressed in whatever time unit you find convenient. As each request comes in, you fetch the value from the buffer at the current position and compare it to current time. If the value from the buffer is more than the current time minus the rate limit interval you're using, then you return a 420 to the client and are done. If not, their request is ok and you should serve it normally, but first you store the current time stamp in the buffer and then advance the counter/index.
- cakoose 9y agoThe article describes solutions that use Redis so that multiple app servers can share rate limits. The article's second solution is basically what you're describing, except adapted to work with Redis. Also, what do you mean by "fixed" memory? Sure, the memory doesn't grow over time, but neither does the memory of the other solutions. Of the solutions listed in the article, this is the most memory-hungry.
- sulam 9y agoThe other fixed memory solution that is specifically mentioned suffers from a defect that allows you to go up to 2X past the rate limit by sending 1X on both sides of an aggregation boundary. I thought readers might appreciate an alternative that is also fixed memory but that doesn't suffer from this defect. And sure, the fixed value is larger than other solutions (probably not larger than the Redis solution) but it's likely optimal if you care about being sure the rate limit is never exceeded within your given time interval. YMMV, I am making no claims about universal applicability. Finally, yes, it's not Redis -- but it could be exposed as a service if you wanted that pretty easily. Operational complexity will exist regardless and depending on your organization different solutions will be appealing for different reasons.
- seniorghost 9y agoThanks for referencing my earlier post in the article! We use the "sliding window log" you described at ClassDojo, but your more memory-efficient approach looks great. https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/ https://engineering.classdojo.com/blog/2015/02/06/rolling-ra...