This content originally appeared on DEV Community and was authored by Amir Keshavarz
In the previous post, we went through rate-limiting and what it is. Then, we introduced an algorithm called Token Bucket and implemented it in Python.
I've decided to turn this into a series and dedicate each post to an algorithm.
And in this post, we will learn about Fixed Window and its implementation in Python.
Fixed Window
As the name suggests, It's all about windows. In this algorithm, we divide the time into fixed windows and then map the incoming events into these windows.
The algorithm itself is pretty simple without any analogy but let's start with one anyway.
Imagine a moving train. There's a gateway and at any moment, people only can board one wagon (Yep, people are boarding a moving train, nothing weird).
Assume that the window of boarding for each wagon is 1 minute. So if a wagon gets full you need to wait for up to a minute for the next wagon.
In this analogy, the train is the time! The time is always moving forward and in each time frame, we have a fixed window of passing through.
Implementation
In this very simple implementation, We will build a rate-limiter that uses Fixed Window to limit packets in 1-second time frames.
We start by defining a class with 3 arguments when It's being instantiated.
- capacity: number of the allowed packets that can pass through in a second.
- forward_callback: this function is called when the packet is being forwarded.
- drop_callback: this function is called when the packet should be dropped.
We prefill a property named allowance to allow the packet to pass through in the first second.
current_time is the current time frame that the rate-limiter is using.
from time import time, sleep
class fixed_window:
def __init__(self, capacity, forward_callback, drop_callback):
self.current_time = int(time())
self.allowance = capacity
self.capacity = capacity
self.forward_callback = forward_callback
self.drop_callback = drop_callback
Then, we define handle() where the magic happens.
def handle(self, packet): #1
if (int(time()) != self.current_time): #2
self.current_time = int(time()) #3
self.allowance = self.capacity #3
if (self.allowance < 1): #4
return self.drop_callback(packet) #5
self.allowance -= 1 #6
return self.forward_callback(packet) #6
-
handleaccepts only 1 parameter: the packet. - check if we're in the current time frame or not.
- if we're not in the current time frame, update the
current_timeand reset theallowance. - check if we have any allowance left.
- drop the packet if we don't have any allowance left.
- in this part, we already know that there is allowance left, so we remove one from the allowance and forward the packet.
As you can see, Fixed Window is extremely simple. This is the final code:
from time import time, sleep
class fixed_window:
def __init__(self, capacity, forward_callback, drop_callback):
self.current_time = int(time())
self.allowance = capacity
self.capacity = capacity
self.forward_callback = forward_callback
self.drop_callback = drop_callback
def handle(self, packet):
if (int(time()) != self.current_time):
self.current_time = int(time())
self.allowance = self.capacity
if (self.allowance < 1):
return self.drop_callback(packet)
self.allowance -= 1
return self.forward_callback(packet)
def forward(packet):
print("Packet Forwarded: " + str(packet))
def drop(packet):
print("Packet Dropped: " + str(packet))
throttle = fixed_window(1, forward, drop)
packet = 0
while True:
sleep(0.2)
throttle.handle(packet)
packet += 1
You should be getting something like this:
Packet Forwarded: 0
Packet Dropped: 1
Packet Dropped: 2
Packet Forwarded: 3
Packet Dropped: 4
Packet Dropped: 5
Packet Dropped: 6
Packet Dropped: 7
Packet Forwarded: 8
Packet Dropped: 9
Packet Dropped: 10
Packet Dropped: 11
Packet Dropped: 12
Packet Forwarded: 13
In the code above, we built a rate-limiter with a rate of one packet per second. Then, we send a packet every 0.2 seconds to see the rate-limiter do its thing.
This algorithm is pretty useful to learn about rate-limiting but we rarely see it in the wild since it allows a burst of events at the beginning of the time frame but it really depends on your application.
Thank you for your time.
This content originally appeared on DEV Community and was authored by Amir Keshavarz
Amir Keshavarz | Sciencx (2021-07-21T17:21:33+00:00) Rate limiting using the Fixed Window algorithm. Retrieved from https://www.scien.cx/2021/07/21/rate-limiting-using-the-fixed-window-algorithm/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.