What’s a good rate limiting algorithm?

by

Here the simplest algorithm, if you want just to drop messages when they arrive too quickly (instead of queuing them, which makes sense because the queue might get arbitrarily large):

rate = 5.0; // unit: messages
per  = 8.0; // unit: seconds
allowance = rate; // unit: messages
last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds

when (message_received):
  current = now();
  time_passed = current - last_check;
  last_check = current;
  allowance += time_passed * (rate / per);
  if (allowance > rate):
    allowance = rate; // throttle
  if (allowance < 1.0):
    discard_message();
  else:
    forward_message();
    allowance -= 1.0;

There are no datastructures, timers etc. in this solution and it works cleanly 🙂 To see this, ‘allowance’ grows at speed 5/8 units per seconds at most, i.e. at most five units per eight seconds. Every message that is forwarded deducts one unit, so you can’t send more than five messages per every eight seconds.

Note that rate should be an integer, i.e. without non-zero decimal part, or the algorithm won’t work correctly (actual rate will not be rate/per). E.g. rate=0.5; per=1.0; does not work because allowance will never grow to 1.0. But rate=1.0; per=2.0; works fine.

More Related Contents:

  1. What happens when start value < end value with range() cmd in Python?
  2. Check if all elements in a list are identical
  3. Permutations between two lists of unequal length
  4. Pythonic way to check if a list is sorted or not
  5. Detecting consecutive integers in a list [duplicate]
  6. Evenly distributing n points on a sphere
  7. Efficient way to apply multiple filters to pandas DataFrame or Series
  8. Rolling or sliding window iterator?
  9. What is the best way to get all the divisors of a number?
  10. How to efficiently compare two unordered lists (not sets)?
  11. Efficient calculation of Fibonacci series
  12. Python – Is a dictionary slow to find frequency of each character?
  13. How to implement a binary tree?
  14. In Python, what is the fastest algorithm for removing duplicates from a list so that all elements are unique *while preserving order*? [duplicate]
  15. Best way to determine if a sequence is in another sequence?
  16. Mapping a range of values to another
  17. How to test if one string is a subsequence of another? [duplicate]
  18. Find elements of array one nearest to elements of array two
  19. Complexity of list.index(x) in Python
  20. Fast prime factorization module
  21. Why does Python’s itertools.permutations contain duplicates? (When the original list has duplicates)
  22. Python: find closest string (from a list) to another string
  23. Split a list of numbers into n chunks such that the chunks have (close to) equal sums and keep the original order
  24. In Python, how do you find the index of the first value greater than a threshold in a sorted list?
  25. String similarity metrics in Python [duplicate]
  26. What is the time complexity of heapq.nlargest?
  27. creating a spiral array in python?
  28. Understanding change-making algorithm
  29. What is this odd sorting algorithm?
  30. counting combinations and permutations efficiently

Leave a Comment