Rate limiting using the Fixed Window algorithm

#tutorial #computerscience #python #programming

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 FixedWindow:

    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

handle accepts 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_time and reset the allowance.
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 FixedWindow:

    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 = FixedWindow(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.