I've been looking at implementing a local rate limiting solution satisfying certain guarantees. I've found surprisingly little literature on the extensions of the token bucket algorithm to hierarchies. I'm hoping that someone would know the name of this algorithm and similar algorithms for solving the same problem as well as know any analysis of right approach for "donating" tokens to your parent.
Assume that we have request handler A and request handler B handling e.g. HTTP requests and handler A is given 40% of the capacity while B is given 60%. Assume the server can handle 10000 requests / second and we want to donate any unused capacity. In other words, if A doesn't currently need much capacity, but B is going over the limit, B can take any capacity unused by A. The rate limiting algorithm I've thought about would then work as follows with a 1 second window:
- Have a root bucket
Rwith child buckets
- Each second
Ais reset to contain 4000 tokens and
Bto contain 6000.
Bcan choose to donate some of their tokens to the root bucket
Bis out of tokens, the respective handler can borrow tokens from
The actual interesting question is now the logic for how many tokens
B choose to donate to
R. Some approaches I can think of:
- Donate unused: If e.g.
Aonly tried to use 3000 tokens during the previous window, then donate 4000-3000=1000 tokens to
- Exponentially moving average: Donate an exponentially moving average of how many donated last time and how many were unused last time around (the first is a special case of this).
There's some tradeoff here between donating too many tokens if traffic ends up increasing and donating too few if traffic is dropping. Another concern is efficiency, i.e. using as few locks as possible for the implementation.
Does anyone know any papers that discuss algorithms similar to the one above?