An Alternative Approach to Rate Limiting • Hacker News Board

Re: An Alternative Approach to Rate Limiting

#71

Post by stonelazy » Fri, Apr 14, 2017, 3:05 AM UTC

jdwyah wrote: post #64

stonelazy wrote: post #54

Was 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.

why not? 1000s/min should be NBD.

Really ? 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 ?

Re: An Alternative Approach to Rate Limiting

#72

Post by limeyx » Fri, Apr 14, 2017, 10:27 PM UTC

zokier wrote: post #10

timothycrosley wrote: post #4

I 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.

Yeah, 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.

The racy code can behave very poorly based on some tests I did of my very first attempts at this !

Re: An Alternative Approach to Rate Limiting

#73

Post by sulam » Fri, Apr 14, 2017, 10:34 PM UTC

cakoose wrote: post #70

sulam wrote: post #67

There'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 y…

The 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.

The 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.