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 R with child buckets A and B.
  • Each second A is reset to contain 4000 tokens and B to contain 6000.
  • A and B can choose to donate some of their tokens to the root bucket R.
  • If A or B is out of tokens, the respective handler can borrow tokens from R.

The actual interesting question is now the logic for how many tokens A and B choose to donate to R. Some approaches I can think of:

  • Donate unused: If e.g. A only tried to use 3000 tokens during the previous window, then donate 4000-3000=1000 tokens to R.
  • 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.