Rate Limiting in Golang: Understanding Fixed and Sliding Windows Algorithm

Imagine you're at an amusement park waiting for a ride. Only a certain number of people are allowed to board each hour. If the line gets too long, anyone arriving has to wait until the next hour before they can board. This idea of restricting access is much like rate limiting in programming, where we control the number of requests a system can handle to avoid overload.

In Golang, we often implement rate limiting with algorithms like the Fixed Window and Sliding Window. Let’s explore these, with examples to help you build your rate limiter.

Fixed Window Rate Limiting

The Fixed Window algorithm allows a set number of requests within a defined period (e.g., 100 requests per minute). If the limit is reached within that period, any additional requests are denied until the next period starts.

How it Works

Think of a fixed window as a "bucket" that resets every minute. If your limit is 100 requests per minute, then you have a fresh bucket every minute to count requests. Once you hit 100, the bucket overflows and additional requests are blocked until the next minute.

Fixed Window Code Example

Here’s a simple example of a fixed window rate limiter in Golang. We'll use a map to track requests by minute:

 package main

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

type RateLimiter struct {
    requests     int
    maxRequests  int
    resetTime    time.Time
    lock         sync.Mutex
}

func NewRateLimiter(maxRequests int, interval time.Duration) *RateLimiter {
    return &RateLimiter{
        maxRequests: maxRequests,
        resetTime:   time.Now().Add(interval),
    }
}

func (rl *RateLimiter) Allow() bool {
    rl.lock.Lock()
    defer rl.lock.Unlock()

    // Reset the count when the interval has passed
    if time.Now().After(rl.resetTime) {
        rl.requests = 0
        rl.resetTime = time.Now().Add(time.Minute)
    }

    // Check if the request can be allowed
    if rl.requests < rl.maxRequests {
        rl.requests++
        return true
    }

    return false
}

func main() {
    limiter := NewRateLimiter(5, time.Minute)

    for i := 0; i < 10; i++ {
        if limiter.Allow() {
            fmt.Println("Request", i+1, "allowed")
        } else {
            fmt.Println("Request", i+1, "denied - rate limit reached")
        }
        time.Sleep(10 * time.Second)
    }
}

Explanation:

• This example allows 5 requests per minute.

• Each time Allow() is called, it checks if the current request count exceeds the limit.

• After a minute, the counter resets.

Sliding Window Rate Limiting

The Sliding Window algorithm is a little more flexible. Instead of counting requests in strict chunks of time, it allows requests in a "moving window" (e.g., the last 60 seconds).

How it Works

Imagine a conveyor belt where items move continuously. As new requests are added to one end, old requests fall off the other end after a certain time. This prevents a "rush" at the start of each minute and provides smoother request handling.

Sliding Window Code Example

To create a sliding window in Golang, we can track the timestamps of each request, ensuring only those within the last 60 seconds are counted.

package main

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

type SlidingWindowRateLimiter struct {
    timestamps  []time.Time
    maxRequests int
    interval    time.Duration
    lock        sync.Mutex
}

func NewSlidingWindowRateLimiter(maxRequests int, interval time.Duration) *SlidingWindowRateLimiter {
    return &SlidingWindowRateLimiter{
        maxRequests: maxRequests,
        interval:    interval,
    }
}

func (swl *SlidingWindowRateLimiter) Allow() bool {
    swl.lock.Lock()
    defer swl.lock.Unlock()

    now := time.Now()
    // Remove timestamps older than the interval
    validTimestamps := []time.Time{}
    for _, ts := range swl.timestamps {
        if now.Sub(ts) < swl.interval {
            validTimestamps = append(validTimestamps, ts)
        }
    }
    swl.timestamps = validTimestamps

    // Allow request if we have room within the window
    if len(swl.timestamps) < swl.maxRequests {
        swl.timestamps = append(swl.timestamps, now)
        return true
    }

    return false
}

func main() {
    limiter := NewSlidingWindowRateLimiter(5, time.Minute)

    for i := 0; i < 10; i++ {
        if limiter.Allow() {
            fmt.Println("Request", i+1, "allowed")
        } else {
            fmt.Println("Request", i+1, "denied - rate limit reached")
        }
        time.Sleep(10 * time.Second)
    }
}

Explanation:

• This example allows up to 5 requests per minute, but with a sliding window.

• Each request's timestamp is stored in an array, and only those within the last minute are kept.

• When a new request comes in, we discard any timestamps older than the interval. If there’s room within the count, the request is allowed.

Comparing Fixed and Sliding Windows

• Fixed Window: Easier to implement and more predictable, but can lead to bursts at the start of each interval.

• Sliding Window: Smoother request handling since it moves continuously, though a bit more complex to implement.

Conclusion

Using rate limiting, we can control the flow of requests to keep our systems stable. The fixed window is simple and effective, while the sliding window offers more flexibility.