You Don't Know Rate Limiter

What is a Rate Limiter 🤔

Rate Limiter is a web application decision engine that decides whether a client request should be fulfilled or rejected. A rate limiter tracks the request rate against each client and if that exceeds a certain threshold, it just rejects the upcoming requests from that particular client.

Advantages of using a Rate Limiter 🔥

• Secure Applications

  • It helps servers to survive brute-force attacks. When a web application is under attack, it faces a huge number of requests, hence in that situation if a rate limiter is available, it can control the request rate from such clients and block them from the server.

Rate Limiting Algorithms ⚒️

There are different algorithms for this purpose, each having its advantages. Here are the four algorithms that are implemented in this application.

Token Bucket Algorithm 💡

Important Definitions

1. Token: A Token is like a lifeline for a client request.

2. Token_Rate: Rate at which new tokens are added.

3. Threshold: Maximum value of Token.

Algorithm

• Against each client, a Token count is stored. It is like a lifeline for that client. When a request arrives, if the Token count is greater than 0, it allows the request, otherwise, it discards it.

• Tokens are added to the Token variable at a rate Token_Rate.

• When a token is added if the Token the count becomes greater than the Threshold value, it discards the Token.

Fixed Window Counter 💡

Algorithm

• The timeline is divided into small time chunks of equal size, called a Window.

• For each client, it stores the number of requests the client made at a particular time Window.

• If the request count exceeds a Threshold value, it discards the request.

• This process is repeated for each window.

Sliding Window Log 💡

Algorithm

• It is a bit dynamic compared to the Fixed Window Counter.

• It also has the concept of Window of a particular duration(let's say Window_Size).

• Against each client, it stores the timestamps at which the client made a request.

• When a request arrives, it discards all the previous timestamps that lie outside of the Window i.e. (now - Window_Size ➡️ now)

• Then it counts the number of available timestamps in the current Window, if it exceeds a particular Threshold value, then it discards the request.

Sliding Window Counter 💡

Algorithm

• Sliding Window Counter combines Fixed Window Counter and Sliding Window Log.

• It divides the timeline into Window the same sizes.

• For each client, it stores the request count for both the Current and Previous windows.

• To calculate the estimated request count for the current, if it's 37% through in the Current Window, it takes 63% of the requests made in the Previous Window to make up for it.

• Then it compares the value against a particular Threshold value and decides whether to allow or discard the request.

So, till now we have covered the basic theory of different rate-limiting algorithms, It's time to implement them.

Token Bucket Algorithm 👨‍💻

For each client IP address, the algorithm maintains a TokenBucket.

type TokenBucket struct {
    Capacity        int        // max Token at a time
    TokenCount      int        // current Token count
    TokenRefillRate int        // rate of token filling
    LastRefillTime  time.Time  // to calc total token needed to add
    mut             sync.Mutex  
}

Here is how the algorithm counts the number of tokens at the current timestamp when a new request arrives. It checks the last token filling time and using tokenRefillRate, it calculates the amount of token that needs to be added.

func (t *TokenBucket) RefillBucket() {
    t.mut.Lock()
    defer t.mut.Unlock()
    now := time.Now()
    duration := now.Sub(t.LastRefillTime)
    tokensToAdd := int(duration.Seconds()) * t.TokenRefillRate
    t.TokenCount = min(t.TokenCount+tokensToAdd, t.Capacity)
    t.LastRefillTime = now
}

When a request arrives, it quickly refills the bucket, based on the time difference since the last filling, and then if the current token count is 0, it rejects the request otherwise allows the request.

Fixed Window Counter 👨‍💻

Here the algorithm only maintains CurrentRequestCount for each client.

type FixedWindowEntry struct {
    CurrentRequestCount int
}

It is straightforward to implement, for each time window let's say 0-60s, it sets a zero value to CurrentRequestCount, and then it increases it for each incoming request from the same client. If it exceeds a certain Threshold value, it rejects incoming requests.

The main problem was to reset the CurrentRequestCount value to 0 at the beginning of each time window. For that, I used ticker that tickets at the start of each time window.

func FixedWindowCounterHelper() {
    go func() {
        ticker := time.NewTicker(time.Second)
        for {
            select {
            case t := <-ticker.C:
                if t == constants.FixedWindowCounter_EndTimeStamp {
                    constants.Mut.Lock()
                    for _, v := range FixedWindowCounterList {
                        v.Reset()
                    }
                    constants.Mut.Unlock()
                    constants.FixedWindowCounter_EndTimeStamp = constants.FixedWindowCounter_EndTimeStamp.Add(time.Second * constants.FixedWindowCounter_WindowSize)
                }
            }
        }
    }()
}

the ticker structure has a channel onto which the ticks are delivered, so by collecting those ticks, we can reset the CurrentRequestCount to 0.

Sliding Window Log 👨‍💻

This algorithm maintains an array of timestamps for each client.

type SlidingWindowLog struct {
    TimeStamps []time.Time
}

It also has a window size, when a new request arrives, it removes the timestamps, outside of the window size from the current time.

func (s *SlidingWindowLog) RemoveRedundantTimeStamps(t time.Time) {
    startTimestamp := t.Add(time.Second * constants.SlidingWindowLog_WindowSize * (-1))
    var result []time.Time
    for _, timestamp := range s.TimeStamps {
        if timestamp.After(startTimestamp) {
            result = append(result, timestamp)
        }
    }
    copy(s.TimeStamps, result)
}

Then while handling the request, if the timestamp array length is greater than a certain threshold value, it rejects the request or allows the request.

Sliding Window Counter 👨‍💻

This algorithm is a bit mix of both fixed window counter and sliding window log.

type SlidingWindowCounterEntry struct {
    CurrentWindowCount int
    PrevWindowCount    int
    WindowStartTime    time.Time
    WindowEndTime      time.Time
}

When the time is WindowEndTime it resets the entry for that specific entry. One important thing to note here is to maintain the PrevWindowCount. It assigns the CurrentWindowCount to it at the end of the current time window.

func (e *SlidingWindowCounterEntry) WindowReset() {
    e.PrevWindowCount = e.CurrentWindowCount
    e.CurrentWindowCount = 0
    e.WindowStartTime = e.WindowEndTime
    e.WindowEndTime = e.WindowStartTime.Add(time.Second * constants.SlidingWindowCounter_WindowSize)
}

It doesn't maintain a global window. If it is 40% through in the current window, it takes 60% of the PrevWindowCount to calculate the current window count. If it is greater than a threshold value, it rejects the request. Here's how it handles incoming requests.

func (e *SlidingWindowCounterEntry) HandleIncomingRequest() bool {
    var now time.Time = time.Now()
    var durationFromWindowStart time.Duration = now.Sub(e.WindowStartTime)
    var percentThroughWindow float32 = float32(durationFromWindowStart.Seconds()) / (constants.SlidingWindowCounter_WindowSize)
    var windowCount float32 = percentThroughWindow*float32(e.CurrentWindowCount) + (1-percentThroughWindow)*float32(e.PrevWindowCount)
    if windowCount >= constants.SlidingWindowCounter_WindowThreshold {
        fmt.Printf("%f   %v   ... so disallow\n", windowCount, constants.SlidingWindowCounter_WindowThreshold)
        return false
    }
    e.CurrentWindowCount = e.CurrentWindowCount + 1
    fmt.Printf("%f   %v   ... so allow\n", windowCount, constants.SlidingWindowCounter_WindowSize)
    return true
}

So, these are the four algorithms, that I implemented in my rate-limiter project. It was a great learning experience. You can check it out here: https://github.com/melsonic/rate-limiter

Conclusion 📢

The rate limiter is a very important component in modern web applications, It controls the client flow to the server. Even though it fails to predict a malicious server attack because then uses the proxy to send requests from different IP addresses, it still has an important role in modern applications. You also need a load-balancer etc to handle such incidents.