[jsw]

I mentioned this in another place on this thread, but a simple AIMD algorithm paired with a token bucket is surprisingly effective at dynamically adjusting to available capacity, even across a fleet of services not sharing state other than the contended resource.

Pretty easy to pair AIMD with token bucket (eg https://github.com/webriots/rate)

[hxtk]

I notice that library self-identifies a problem of generally keeping a fixed-size number of buckets and addressing them with hashing, which leads to great memory usage but introduces a risk of collision.

Stochastic Fair Blue shares that problem, so I think you might find the solution it uses interesting: it rotates hashes on fixed intervals by re-seeding to ensure that if a responsive flow collides with a non-responsive flow that's being rate-limited, it is at least guaranteed not to do it for very long.

This leads to a problem similar to the problem with Fixed Window Counter rate limiting where it would basically forget the rate limit history every interval. To solve this, two queues are fed input data at a time: the router enforces one of them, while just feeding the other data and ignoring its output in order to warm up its buckets.

I imagine if I tried to make use of the library you linked and didn't absolutely need per-user granularity, I'd do something similar by concatenating the user's identifier with a seed value for each of the two queues and rotating at regular intervals.

[jsw]

Love the simplicity and elegance of the design to address this problem.