Rate limiting using the Fixed Window algorithm
Tags: tutorial, computerscience, python, programming
Published: 2021-07-21 17:21:33

---
title: Rate limiting using the Fixed Window algorithm
published: true
description: Implement a rate-limiting algorithm called Fixed Window in Python
tags: tutorial,computerscience,python,programming
series: Rate limiting
---

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.

![Fixed Window](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i45cox7md3dt9h7t2syf.png)

# 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.
3. **forward_callback:** this function is called when the packet is being forwarded.
4. **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.


```python
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.
```python
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:
```python
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.