feat(rate-limiting): leaky bucket rate limiter

[vartec]

Leaky bucket rate limiter which allows for defining both max burst rate as well as sustained rate limit.

• While the bucket is not yet full, the requests are accepted until it's full (bucket size = max burst limit)
• When the bucker is full, new request are accepted only after a drop drips out (drip rate = sustained rate limit)

This is a metered (i.e. counter) implementation, which is far less resource heavy, but only limits the traffic, doesn't attempt to smooth it out.

[codecov[bot]]

Codecov Report

Attention: Patch coverage is 79.26829% with 17 lines in your changes missing coverage. Please review.

Project coverage is 78.06%. Comparing base (cdc03d3) to head (839a557). Report is 174 commits behind head on master.

Additional details and impacted files

@@            Coverage Diff             @@
##           master   #73484      +/-   ##
==========================================
- Coverage   78.07%   78.06%   -0.02%     
==========================================
  Files        6654     6653       -1     
  Lines      297329   297314      -15     
  Branches    51166    51171       +5     
==========================================
- Hits       232135   232086      -49     
- Misses      58810    58859      +49     
+ Partials     6384     6369      -15     

Files	Coverage Δ
src/sentry/ratelimits/leaky_bucket.py	79.26% <79.26%> (ø)

... and 135 files with indirect coverage changes

[wedamija]

This makes sense, although I'm wondering if it's much different to RedisSlidingWindowRateLimiter in practice?

[vartec]

@wedamija

This makes sense, although I'm wondering if it's much different to RedisSlidingWindowRateLimiter in practice?

It allows absorbing bursts (bucket size) while at the same time allows defining significantly lower sustained rate (drip rate), without needing to tie both of them together.

Though to your point, if you'd set LeakyBucket to burst rate X and drip rate to Y per second, it's would give you similar result as setting SlidingWindow to quota X and window length X/Y seconds and granularity of at least 1/Y seconds.

That being said LeakyBucket is far simpler algorithm and this implementation doesn't have the granularity vs data size trade-off. With this implementation you have microsecond granularity storing just a single hash with two floats (current_level, and last_drip).

Also, this is more opinion based, but I believe burst and sustained rate are easier to reason about than sliding window params.

[vartec]

Though to your point, if you'd set LeakyBucket to burst rate X and drip rate to Y per second, it's would give you similar result as setting SlidingWindow to quota X and window length X/Y seconds and granularity of at least 1/Y seconds.

Actually giving it more thought, this is not true... The overall throughput will be the same, but behavior with sustained traffic will be different.