What's a good rate limiting algorithm?
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.
What is the best way to implement a rate-limiting algorithm for web requests?
Use a fast memory-based hashtable like memcached. The keys will be the target you are limiting (e.g. an IP) and the expiration of each stored value should be the maximum limitation time.
The values stored for each key will contain a serialized list of the last N attempts they made at performing the action, along with the time for each attempt.
Distributed rate limiting algorithm
I've implemented a solution based on this article (archive.org). I think the algorithm is called Leaky Bucket but it works fine. It's not perfect since it allows the entire quota to be used in a burst, but overall it's very fast with node.js and Redis. The difference between accepted requests and rate can be quite high and depend on the ratio between sample window and bucket size.
Related Topics
Assign Environment Variables from Bash Script to Current Session from Python
Boto3 Client Noregionerror: You Must Specify a Region Error Only Sometimes
Detecting When a Child Process Is Waiting for Input
Importerror: Libcblas.So.3: Cannot Open Shared Object File: No Such File or Directory
Creating Same Random Number Sequence in Python, Numpy and R
Computing Cross-Correlation Function
Loading .Rdata Files into Python
Which Key/Value Store Is the Most Promising/Stable
Financial Charts/Graphs in Ruby or Python
How to Make a Single Legend for Many Subplots with Matplotlib
Syntaxerror: Non-Ascii Character '\Xa3' in File When Function Returns '£'
How to Take the First N Items from a Generator or List
Binning Data in Python with Scipy/Numpy
How to Write Output in Same Place on the Console