Sounds like a lot of work to avoid writing 20 lines of Lua.
I'd be curious to see the Lua code that implements this. Anyone care to indulge me?
An Alternative Approach to Rate Limiting
11–20 of 73 posts
Re: An Alternative Approach to Rate Limiting
#12I 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 dispro…
Once you start getting into quality-of-service, basic rate limiting like the discussed is not enough. I think Stripe did a better job of covering such concerns in their rate limiter post. They specifically talk about being lenient to "bursty" traffic, as that was a legitimate use-case for clients.
Re: An Alternative Approach to Rate Limiting
#13I 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 dispro…
Once you start getting into quality-of-service, basic rate limiting like the discussed is not enough. I think Stripe did a better job of covering such concerns in their rate limiter post. They specifically talk about being lenient to "bursty" traffic, as that was a legitimate use-case for clients. https://stripe.com/blog/rate-limiters https://news.ycombinator.com/item?id=13997029
Yes, this is why you want to use a token bucket rate limiter (which for some reason was considered and rejected by the original post). We wrote it up here and have an open-source impl on github that's in production serving hundreds of millions of rate limits: https://medium.com/smyte/rate-limiter-df3408325846
Re: An Alternative Approach to Rate Limiting
#14Sounds like a lot of work to avoid writing 20 lines of Lua.
I 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
[1] https://github.com/michaelmior/locomotor/blob/master/bench/t...
Re: An Alternative Approach to Rate Limiting
#15Earlier quoted context omitted.
Where 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.
One 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.
depending 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 ?
Re: An Alternative Approach to Rate Limiting
#16It'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?
Re: An Alternative Approach to Rate Limiting
#17I 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 dispro…
This is why I've suggested, and used, fair queuing for rate limiting.
Any source can make lots of requests, but they queue up by IP address. (In practice, you have queues organized by hashed IP address, which you service round-robin. That's how routers do fair queuing.) If one queue gets very long, then you start sending 429 errors for new adds to that queue. Otherwise, the requests from the heavy load source just take a little longer.
Unlike most rate limiters, this requires little or no tuning. Each source IP address gets an equal amount of service. Sources which generate heavy load compete with themselves, not others.
The main tuning parameter is how long a queue can get. It's useful to have both length and time limits. But only hostile sources should hit those. They don't change with capacity or number of users. Brief load transients should be handled normally, if slowly.
This won't stop a distributed denial of service attack from many IP addresses. But anything coming from a small number of sources will be handled without much trouble.
Re: An Alternative Approach to Rate Limiting
#18I 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.
Agreed. 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.
Re: An Alternative Approach to Rate Limiting
#19Sounds like a lot of work to avoid writing 20 lines of Lua.
I'd be curious to see the Lua code that implements this. Anyone care to indulge me?
I'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
Re: An Alternative Approach to Rate Limiting
#20Earlier quoted context omitted.
One 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.
depending 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 memor…
More sophisticated ways to reject connections rely on heuristics and may result in denying legitimate requests. I don't have all the answers, I'm just suggesting a way that doesn't consider all requests equal.
Every CORS pre-flight request uses the OPTIONS method. It is also used to advertise which methods are available on a route.