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.

1. capacity: number of the allowed packets that can pass through in a second.
2. forward_callback: this function is called when the packet is being forwarded.
3. 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, sleepclass 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

1. handle accepts only 1 parameter: the packet.
2. check if we're in the current time frame or not.
3. if we're not in the current time frame, update the current_time and reset the allowance.
4. check if we have any allowance left.
5. drop the packet if we don't have any allowance left.
6. 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, sleepclass 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 = 0while True:    sleep(0.2)    throttle.handle(packet)    packet += 1

You should be getting something like this:

Packet Forwarded: 0Packet Dropped: 1Packet Dropped: 2Packet Forwarded: 3Packet Dropped: 4Packet Dropped: 5Packet Dropped: 6Packet Dropped: 7Packet Forwarded: 8Packet Dropped: 9Packet Dropped: 10Packet Dropped: 11Packet Dropped: 12Packet 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.