Rate Limiting in Go: Leaky Bucket, Token Bucket, Sliding Window

When external libraries cannot be used, rate‑limiting can be achieved with three classic algorithms.

1. Leaky Bucket Algorithm

Algorithm Idea : Requests are placed into a bucket; workers remove tasks at a fixed rate. If the bucket is full, excess requests are rejected immediately.

Suitable Scenarios : Ideal for smoothing traffic, such as protecting a database by processing requests at the DB's sustainable QPS. Not suitable for sudden spikes like flash sales because it reacts less flexibly and may require a separate bucket per user/IP.

Go Implementation

package main

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

type Task struct {
    handler func() Result
    resChan chan Result
    taskID  int
}

type Result struct{}

func handler() Result {
    time.Sleep(300 * time.Millisecond)
    return Result{}
}

func NewTask(id int) Task {
    return Task{handler: handler, resChan: make(chan Result), taskID: id}
}

type LeakyBucket struct {
    BucketSize int
    NumWorker  int
    bucket     chan Task
}

func NewLeakyBucket(bucketSize int, numWorker int) *LeakyBucket {
    return &LeakyBucket{BucketSize: bucketSize, NumWorker: numWorker, bucket: make(chan Task, bucketSize)}
}

func (b *LeakyBucket) validate(task Task) bool {
    select {
    case b.bucket <- task:
    default:
        fmt.Printf("request[id=%d] is refused
", task.taskID)
        return false
    }
    <-task.resChan
    fmt.Printf("request[id=%d] is run
", task.taskID)
    return true
}

func (b *LeakyBucket) Start() {
    go func() {
        for i := 0; i < b.NumWorker; i++ {
            go func() {
                for {
                    task := <-b.bucket
                    result := task.handler()
                    task.resChan <- result
                }
            }()
        }
    }()
}

func main() {
    bucket := NewLeakyBucket(10, 4)
    bucket.Start()
    var wg sync.WaitGroup
    for i := 0; i < 20; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            task := NewTask(id)
            bucket.validate(task)
        }(i)
    }
    wg.Wait()
}

2. Token Bucket Algorithm

Algorithm Idea : Tokens are added to a bucket at a constant rate. A request proceeds only if a token can be taken; otherwise it is rejected. This allows handling burst traffic while keeping the average rate bounded.

Characteristics : Supports bursts because accumulated tokens can be consumed quickly; the token generation rate and bucket capacity control the average throughput and burst size.

Suitable Scenarios : Perfect for e‑commerce flash sales or social‑media spikes where occasional bursts are expected.

Go Implementation

package main

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

var recordMu map[string]*sync.RWMutex

func init() {
    recordMu = make(map[string]*sync.RWMutex)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

type TokenBucket struct {
    BucketSize int
    TokenRate  time.Duration
    records    map[string]*record
}

type record struct {
    last  time.Time
    token int
}

func NewTokenBucket(bucketSize int, tokenRate time.Duration) *TokenBucket {
    return &TokenBucket{BucketSize: bucketSize, TokenRate: tokenRate, records: make(map[string]*record)}
}

func (t *TokenBucket) getUidOrIp() string { return "127.0.0.1" }

func (t *TokenBucket) getRecord(uidOrIp string) *record {
    if r, ok := t.records[uidOrIp]; ok {
        return r
    }
    return &record{}
}

func (t *TokenBucket) storeRecord(uidOrIp string, r *record) { t.records[uidOrIp] = r }

func (t *TokenBucket) validate(uidOrIp string) bool {
    rl, ok := recordMu[uidOrIp]
    if !ok {
        var mu sync.RWMutex
        rl = &mu
        recordMu[uidOrIp] = rl
    }
    rl.Lock()
    defer rl.Unlock()

    r := t.getRecord(uidOrIp)
    now := time.Now()
    if r.last.IsZero() {
        r.last, r.token = now, t.BucketSize
    } else if r.last.Add(t.TokenRate).Before(now) {
        r.token += max(int(now.Sub(r.last)/t.TokenRate), t.BucketSize)
        r.last = now
    }
    var result bool
    if r.token > 0 {
        r.token--
        result = true
    }
    t.storeRecord(uidOrIp, r)
    return result
}

func (t *TokenBucket) IsLimited() bool { return !t.validate(t.getUidOrIp()) }

func main() {
    tokenBucket := NewTokenBucket(5, 100*time.Millisecond)
    for i := 0; i < 6; i++ {
        fmt.Println(tokenBucket.IsLimited())
    }
    time.Sleep(100 * time.Millisecond)
    fmt.Println(tokenBucket.IsLimited())
}

3. Sliding Window Algorithm

Algorithm Idea : The time axis is divided into small slots (e.g., 100 ms). Each slot records the number of requests. The window slides forward, discarding slots older than the configured duration, allowing precise counting of requests in the last N seconds.

Suitable Scenarios : Like the token bucket, it can handle burst traffic while providing accurate rate control over a sliding period.

Go Implementation

package main

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

var winMu map[string]*sync.RWMutex

func init() { winMu = make(map[string]*sync.RWMutex) }

type timeSlot struct {
    timestamp time.Time
    count     int
}

func countReq(win []*timeSlot) int {
    var c int
    for _, ts := range win { c += ts.count }
    return c
}

type SlidingWindowLimiter struct {
    SlotDuration time.Duration
    WinDuration  time.Duration
    numSlots     int
    windows      map[string][]*timeSlot
    maxReq       int
}

func NewSliding(slotDuration, winDuration time.Duration, maxReq int) *SlidingWindowLimiter {
    return &SlidingWindowLimiter{SlotDuration: slotDuration, WinDuration: winDuration, numSlots: int(winDuration/slotDuration), windows: make(map[string][]*timeSlot), maxReq: maxReq}
}

func (l *SlidingWindowLimiter) getWindow(uidOrIp string) []*timeSlot {
    win, ok := l.windows[uidOrIp]
    if !ok { win = make([]*timeSlot, 0, l.numSlots) }
    return win
}

func (l *SlidingWindowLimiter) storeWindow(uidOrIp string, win []*timeSlot) { l.windows[uidOrIp] = win }

func (l *SlidingWindowLimiter) validate(uidOrIp string) bool {
    mu, ok := winMu[uidOrIp]
    if !ok {
        var m sync.RWMutex
        mu = &m
        winMu[uidOrIp] = mu
    }
    mu.Lock()
    defer mu.Unlock()

    win := l.getWindow(uidOrIp)
    now := time.Now()
    timeout := -1
    for i, ts := range win {
        if ts.timestamp.Add(l.WinDuration).After(now) { break }
        timeout = i
    }
    if timeout > -1 { win = win[timeout+1:] }

    var result bool
    if countReq(win) < l.maxReq { result = true }

    var last *timeSlot
    if len(win) > 0 {
        last = win[len(win)-1]
        if last.timestamp.Add(l.SlotDuration).Before(now) {
            last = &timeSlot{timestamp: now, count: 1}
            win = append(win, last)
        } else { last.count++ }
    } else {
        last = &timeSlot{timestamp: now, count: 1}
        win = append(win, last)
    }
    l.storeWindow(uidOrIp, win)
    return result
}

func (l *SlidingWindowLimiter) getUidOrIp() string { return "127.0.0.1" }

func (l *SlidingWindowLimiter) IsLimited() bool { return !l.validate(l.getUidOrIp()) }

func main() {
    limiter := NewSliding(100*time.Millisecond, time.Second, 10)
    for i := 0; i < 5; i++ { fmt.Println(limiter.IsLimited()) }
    time.Sleep(100 * time.Millisecond)
    for i := 0; i < 5; i++ { fmt.Println(limiter.IsLimited()) }
    fmt.Println(limiter.IsLimited())
    for _, v := range limiter.windows[limiter.getUidOrIp()] { fmt.Println(v.timestamp, v.count) }
    fmt.Println("a thousand years later...")
    time.Sleep(time.Second)
    for i := 0; i < 7; i++ { fmt.Println(limiter.IsLimited()) }
    for _, v := range limiter.windows[limiter.getUidOrIp()] { fmt.Println(v.timestamp, v.count) }
}

The three implementations demonstrate how to enforce rate limits in pure Go without relying on third‑party libraries, allowing developers to select the most appropriate algorithm based on traffic patterns and system constraints.