Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Alternative Approach to Rate Limiting

medium.com

Post reply on HN
Print view View original

61–70 of 73 posts

Re: An Alternative Approach to Rate Limiting

#61

Post by scaryclam »

karmakaze wrote: post #51
irgeek wrote: post #26

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

Without shadow ban, you're just telling the spammers how to be effective and stay just under the limit.

So? Users playing by the rules of the service get to use the service unhindered. A much better approach to shadow banning would be to make better rules and enforce them. Spammers don't want to jump through hoops, so if you implement rules based on bounces and spam reports you'll get the same result (less spammers) but without screwing over legitimate users.

This is how Mailgun and their ilk operate, and while it's annoying to get bitten by their rules (we forgot to warm up a mailing list once and got a temporary suspension as our bounce rate was too high) they treated us like adults, told us why our service had been suspended and proceeded to help us clean up the mailing list. If they had pulled some shadow banning BS we'd have just left the service as we wouldn't be able to trust that they're not messing us (and our clients) around.

Shadow banning works just fine for online forums and the like. It's a pretty terrible method of rate limiting though.

Re: An Alternative Approach to Rate Limiting

#62

Post by jdwyah »

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.

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

Re: An Alternative Approach to Rate Limiting

#63

Post by jdwyah »

wpeterson wrote: post #41
jdwyah wrote: post #3

Earlier quoted context omitted.

agreed. I was a bit leery of diving into Lua as I was building 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.

Hey buddy! Reading all the design and discussion I was. Rey curious how you structured things at a brass tacks storage level.

yoo! 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)

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-java do that for you.

Re: An Alternative Approach to Rate Limiting

#65

Post by forgottenpass »

scaryclam wrote: post #61
karmakaze wrote: post #51

Earlier quoted context omitted.

Without shadow ban, you're just telling the spammers how to be effective and stay just under the limit.

So? Users playing by the rules of the service get to use the service unhindered. A much better approach to shadow banning would be to make better rules and enforce them. Spammers don't want to jump through hoops, so if you implement rules based on bounces and spam reports you'll get the same result (less spammers) but without screwing over legitimate users. This is how Mailgun and their ilk operate, and while it's an…

This is how Mailgun and their ilk operate

That's because their business model is to facilitate the level of spamming that sits right below the threshold of anti-spam measures.

Of course they're going to help you send out as many messages as possible. That's what you pay them for.

Without saying that OPs approach was the most appropriate solution to their problem, I'll point out that Figma's bottom line isn't directly connected to how many document invite emails they shoot out. That's just a collaboration feature of a larger product.

Re: An Alternative Approach to Rate Limiting

#66

Post by sametmax »

lenzm wrote: post #48
irgeek wrote: post #26

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

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

You should only shadow ban manually marked attackers. The one you are sure, very sure that are not legitimate users. This way you can't annoy real customers, as the shadow ban is not automatic and can't trigger on them.

Re: An Alternative Approach to Rate Limiting

#67

Post by sulam »

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

Re: An Alternative Approach to Rate Limiting

#68

Post by hyperpape »

joneholland wrote: post #44
hyperpape wrote: post #43

Earlier quoted context omitted.

Wait, each client does its own round robin (if you have three servers, I will hit 1 then 2 then 3)? Is that common?

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

I'm surprised you wouldn't run into cases where the requests being rate-limited can't end up unevenly distributed between servers. There are assumptions you could add that would make that not a problem, but I'm surprised they'd hold.

Re: An Alternative Approach to Rate Limiting

#70

Post by cakoose »

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.

Post reply on HN