Enable per-user concurrency limits by supporting negative cost in the rate limiting protocol

[brightbyte]

Title: Enable per-user concurrency limits by supporting negative cost in the rate limiting protocol

Description:
Add a hits_subtrahend field to the rate limiting (RLS) protocol that acts like the hits_addend field, but decreases the rate limit counter instead of increasing it. Together with the apply_on_stream_done flag this would enable the emulation of per-user concurrency limits.

Goal: Ensure that each client can only have n requests open at the same time. This ensures fair resource allocation among clients and protects against "accidental DoS", and is simpler to implement and to reason about than cost-based limits.

Approach: Use a rate limit counter to track the number of requests the user has currently open by incrementing the counter at the beginning of the request (as usual with rate limiting) and then decrementing it again when the request is complete (using apply_on_stream_done with hits_subtrahend). This would limit the number of requests the client can perform in parallel, without limiting the total number per unit time.

Considerations:

• If envoy (or the node it runs on) terminates unexpectedly while a client request is ongoing, the counter will fail to be decremented, leading to a situation wherea client could potentially be "locked out". This is solved naturally by the fact that rate limit counters are reset (for fixed window) or decremented (for sliding window) at regular intervals. In the conztext of enforcing a concurrency limit, the time unit for which the limit is defined determines how often concurrency counts are "forgiven", allowing "stuck" clients to be unstuck.
• As a consequence of this mechanism it is possible for clients to exceed the provided limit at certain times up to a factor of two (assuming the connection timeout it smaller than the time window of the limit): if the client already has n requests in flight at the end of a time window, the counter will be reset and the client will be able to make another n requests even before the first set of requests is finished. This is no worse and the fact that, with fixed window semantics, a client can exceed the request count limit (or cost limit) by a factor of two if it makes requests just before and right after the end of a time window.

Example, with a limit of 2 per minute (per client):

1. start request 1, increment counter to 1
2. start request 2, increment counter to 2
3. start request 3, denied, too many requests
4. end request 2, decrement counter to 1
5. start request 4, increment counter to 2
6. ...envoy terminates unexpectedly, counter remains at 2
7. start request 5, denied, too many requests
8. start request 6, denied, too many requests
9. ...when the end of the 1 minute time window is reached...
10. counter is reset to 0
11. start request 7, increment counter to 1
12. end request 7, decrement counter to 0

[brightbyte]

@wbpcode we talked about the need for per-user concurrency control a while ago. How do you like the idea of implementing it by introducing hits_subtrahend?

[brightbyte]

From a quick look at the ratelimit source code it seems to me like this would be trivial to implement by changing GetHitsAddends to return []int64 instead of a []unit64, and make it look at the new HitsSubtrahend field in the request in addition to the existing HitsAddend field. The code applying the increment would have to be changed to ensure that the counter cannot go below 0, but that should be easy enough. A hits_addend value above 2^63 would cause an overflow, but that case seems rather unlikely.

The necessary code change to envoy itself also seems doable based on the small numbers of places that mention hits_addend, though my knowledge of CPP is limited.

[kanurag94]

/assign

[repokitteh-read-only]

kanurag94 is not allowed to assign users.

🐱

Caused by: a #41219 (comment) was created by @kanurag94.

see: more, trace.

[wbpcode]

I think this is affected by the duration of the request. If the duration is much longer than the limit refresh time window, it cannot works correctly because N * (duration / windows) requests will be allowed.

I still think this is a little weird, like a hack...

[rudrakhp]

@wbpcode you are right. So the guarantee is: at most N concurrent requests within a window, with no strong guarantees across window boundaries. This is the same class of guarantee that existing rate limiting already provides, i.e., number of requests across window is not guaranteed if request scope goes beyond the window. For use cases where this level of fairness is sufficient (basic per-client resource usage fairness), this can be a well-defined and useful feature to have. WDYT?

[brightbyte]

Indeed, the concurrency control would have exactly the same limitations/quirks as the rate limits, which are a consequence of using fixed-window semantics.