Fixed Window Rate Limiting Algorithm – A Simple Implementation

Fixed Window Rate Limiting algorithm is the simplest algorithm for applying rate limits out there.

Though this algorithm may not be the best choice for large-scale distributed systems, understanding it is useful because it clarifies the concepts around Rate Limiting.

In case you are interested in understanding the concept of rate limiting, check out my post on the Introduction to Rate Limiting.

In this post, I explain how the algorithm works and then look at a basic implementation of the same in Go.

1 – Fixed Window Rate Limiting Algorithm

In this algorithm, we divide the time into fixed time windows.

For each window of time, we maintain a counter that keeps track of the number of requests.

Every incoming request increments the counter by one and when the counter reaches the maximum limit, the subsequent requests are dropped until a new time window starts.

Check the below illustration that depicts the algorithm:

Here, the timeline is divided into fixed windows of 1 minute each. For every window, we allow a maximum of 3 requests. Any requests above that number are rejected.

The red requests in the above figure show the ones that have been rejected.

2 – Fixed Window Rate Limiting Drawback

While the algorithm is quite simple, it has one major drawback.

There is a big possibility of traffic spikes at the edges of the time window on either side. This can allow a huge number of requests to pass through in a short amount of time and overwhelm the server.

See the below illustration for reference:

3 – Implementation of Fixed Window Algorithm

Here’s a basic implementation of fixed window algorithm in Go programming language.

package main

import (
	"fmt"
	"sync"
	"time"
)

type RateLimiter struct {
	limit           int
	window          time.Duration
	requestCount    int
	lastRequestTime time.Time
	mu              sync.Mutex
}

func NewRateLimiter(limit int, window time.Duration) *RateLimiter {
	return &RateLimiter{
		limit:           limit,
		window:          window,
		requestCount:    0,
		lastRequestTime: time.Now(),
	}
}

func (rateLimiter *RateLimiter) Allow() bool {
	rateLimiter.mu.Lock()

	defer rateLimiter.mu.Unlock()

	now := time.Now()

	if now.Sub(rateLimiter.lastRequestTime) > rateLimiter.window {
		rateLimiter.lastRequestTime = now
		rateLimiter.requestCount = 1
		return true
	}

	if rateLimiter.requestCount < rateLimiter.limit {
		rateLimiter.requestCount++
		return true
	}

	return false

}

func main() {
	fmt.Println("Fixed Window Rate Limiting Demo")

	rateLimiter := NewRateLimiter(3, time.Second)

	fmt.Println("Limit:", rateLimiter.limit)
	fmt.Println("Window:", rateLimiter.window)
	fmt.Println("Request Count: ", rateLimiter, rateLimiter.requestCount)
	fmt.Println("Last Request Time:", rateLimiter.lastRequestTime)

	for i := 0; i < 20; i++ {
		if rateLimiter.Allow() {
			fmt.Printf("Request %d: Allowed\n ", i)
		} else {
			fmt.Printf("Request %d: Rejected\n", i)
			time.Sleep(3 * time.Second)
		}
	}
}

Let’s understand what’s going on over here:

• The struct RateLimiter stores the data for the rate limiter instance such as number of requests (limit), time window, request count and last request time.
• Then, we have a constructor function that returns a new instance of the Rate Limiter.
• The Allow() function is where the magic happens. Basically, this function determines whether a request is allowed or not.
• We first lock the rate limiter instance in the critical section to avoid concurrent requests from updating it.
• Next, we check if the request falls outside the previous time window. In that case, the counter is initialized to 1 and we return true.
• If the request is within the current time window, we check if the number of requests is within the limit. If yes, we return true.
• At the end, we return false to reject the request.
• Finally, within the main(), we simulate issuing multiple requests to see the rate limiter in action.

Now, this rate limiter is not meant for deploying in a real application but it servers to demonstrate how the algorithm really works.

Conclusion

As you can see, the fixed window rate limiting algorithm is a simple approach to implement a basic rate limiting in a system.

Of course, you can enhance it further for your needs but it has its own drawbacks with regards to handling traffic spikes.

If you have any comments or queries, please mention them in the comments section below.