undefined | Better HN

0 pointsotterley1y ago0 comments

That's the typical design for a token-bucket rate limiter. A token-bucket limiter uses more memory but is a simpler design. I believe this bloom-filter based implementation is designed to be more memory efficient at the cost being less CPU efficient.

As usual, tradeoffs are everywhere.

0 comments

hinkley1y ago

Bloom filters really shine when they avoid a network round trip or pulling data from disk. Those are so far away you can easily afford to spend 5% of the cost of the request to avoid 99% of the requests.

otterleyOP1y ago

Agreed! In a typical token bucket implementation, bucket state must be shared across multiple servers, which means you need a shared state repository such as Redis or a database (SQL or noSQL). This can add milliseconds to each request being handled.

hinkley1y ago

> This can add milliseconds

My previous (very long) project was in such a state when I got there that it was only in the last year I was there that measuring things in microseconds was something I could get on other people's radars. I wish I had started sooner because I found a lot of microseconds in about a four month period. That was the most intensive period of user-visible latency reduction I saw the entire time it was there and second through fourth place took years of manpower to accomplish. Past me and future me are both still mad about that.

foobazgt1y ago

Rate limiters seem like the poster child for something you'd want to host in an in-memory KVS. Typical access times look more like ~100us, not milliseconds. Even if you have a complicated algorithm, you can still limit it to a single round trip by using a Redis Function or some moral equivalent.

2 more replies

j / k navigate · click thread line to collapse

0 comments

hinkley1y ago

otterleyOP1y ago

hinkley1y ago

> This can add milliseconds

foobazgt1y ago

2 more replies

j / k navigate · click thread line to collapse