## DEV Community is a community of 667,450 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Rate limiting using the Fixed Window algorithm

Amir Keshavarz
Cloud Infrastructure nerd

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, 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

``````
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, 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.