Rate

A high-performance rate limiter library for Go applications with multiple rate limiting strategies.

Features

• Ultra-Fast: Core operations execute in single digit nanoseconds with zero allocations, enabling hundreds of millions of operations per second
• Thread-Safe: All operations are designed to be thread-safe using optimized atomic operations
• Zero External Dependencies: Relies solely on the Go standard library
• Memory Efficient: Uses compact data structures and optimized storage
  • Packed representations for token buckets
  • Custom 56-bit timestamp implementation
  • Efficient atomic slice implementations
• Multiple Rate Limiting Strategies:
  • TokenBucketLimiter: Classic token bucket algorithm with multiple buckets
  • AIMDTokenBucketLimiter: Additive-Increase/Multiplicative-Decrease algorithm inspired by TCP congestion control
  • RotatingTokenBucketLimiter: Collision-resistant rate limiter with periodic hash seed rotation
• Highly Scalable: Designed for high-throughput concurrent systems
  • Multiple buckets distribute load across different request IDs
  • Low contention design for concurrent access patterns

Installation

go get github.com/webriots/rate

Quick Start

Token Bucket Rate Limiter

package main

import (
	"fmt"
	"time"

	"github.com/webriots/rate"
)

func main() {
	// Create a new token bucket limiter:
	// - 1024 buckets (automatically rounded to nearest power of 2 if
	//   not already a power of 2)
	// - 10 tokens burst capacity
	// - 100 tokens per second refill rate
	limiter, err := rate.NewTokenBucketLimiter(1024, 10, 100, time.Second)
	if err != nil {
		panic(err)
	}

	// Try to take a token for a specific ID
	id := []byte("user-123")

	if limiter.TakeToken(id) {
		fmt.Println("Token acquired, proceeding with request")
		// ... process the request
	} else {
		fmt.Println("Rate limited, try again later")
		// ... return rate limit error
	}

	// Check without consuming
	if limiter.CheckToken(id) {
		fmt.Println("Token would be available")
	}

	// Take multiple tokens at once
	if limiter.TakeTokens(id, 5) {
		fmt.Println("Successfully took 5 tokens")
	}

	// Check if multiple tokens would be available
	if limiter.CheckTokens(id, 3) {
		fmt.Println("3 tokens would be available")
	}
}

Go Playground

AIMD Rate Limiter

package main

import (
	"fmt"
	"time"

	"github.com/webriots/rate"
)

func main() {
	// Create an AIMD token bucket limiter:
	// - 1024 buckets (automatically rounded to nearest power of 2 if
	//   not already a power of 2)
	// - 10 tokens burst capacity
	// - Min rate: 1 token/s, Max rate: 100 tokens/s, Initial rate: 10
	//   tokens/s
	// - Increase by 1 token/s on success, decrease by factor of 2 on
	//   failure
	limiter, err := rate.NewAIMDTokenBucketLimiter(
		1024,  // numBuckets
		10,    // burstCapacity
		1.0,   // rateMin
		100.0, // rateMax
		10.0,  // rateInit
		1.0,   // rateAdditiveIncrease
		2.0,   // rateMultiplicativeDecrease
		time.Second,
	)
	if err != nil {
		panic(err)
	}

	id := []byte("api-client-123")

	// Try to take a token
	if limiter.TakeToken(id) {
		// Process the request
		success := processRequest()

		if success {
			// If successful, increase the rate
			limiter.IncreaseRate(id)
		} else {
			// If failed (e.g., downstream service is overloaded), decrease
			// the rate to back off
			limiter.DecreaseRate(id)
		}
	} else {
		// We're being rate limited
		fmt.Println("Rate limited, try again later")
	}
}

func processRequest() bool {
	// Your request processing logic
	fmt.Println("Processing request")
	return true
}

Go Playground

Rotating Token Bucket Rate Limiter

package main

import (
	"fmt"
	"time"

	"github.com/webriots/rate"
)

func main() {
	// Create a rotating token bucket limiter:
	// - 1024 buckets (automatically rounded to nearest power of 2 if
	//   not already a power of 2)
	// - 10 tokens burst capacity
	// - 100 tokens per second refill rate
	// - Rotation interval automatically calculated: (10/100)*5 = 0.5
	//   seconds
	limiter, err := rate.NewRotatingTokenBucketLimiter(
		1024,        // numBuckets
		10,          // burstCapacity
		100,         // refillRate
		time.Second, // refillRateUnit
	)
	if err != nil {
		panic(err)
	}

	// Use just like TokenBucketLimiter
	id := []byte("user-456")

	if limiter.TakeToken(id) {
		fmt.Println("Token acquired, proceeding with request")
		// ... process the request
	} else {
		fmt.Println("Rate limited, try again later")
		// ... return rate limit error
	}

	// Check without consuming
	if limiter.CheckToken(id) {
		fmt.Println("Token would be available")
	}

	// The rotating limiter also supports multi-token operations
	if limiter.TakeTokens(id, 3) {
		fmt.Println("Successfully took 3 tokens")
	}
}

Go Playground

Detailed Usage

Common Interface

All rate limiters in this package implement the Limiter interface:

type Limiter interface {
	CheckToken([]byte) bool         // Check if a single token is available
	CheckTokens([]byte, uint8) bool // Check if n tokens are available
	TakeToken([]byte) bool          // Take a single token
	TakeTokens([]byte, uint8) bool  // Take n tokens atomically
}

This allows you to write code that works with any rate limiter implementation:

func processRequest(limiter rate.Limiter, clientID []byte, tokensNeeded uint8) error {
	// Check if we have enough tokens without consuming them
	if !limiter.CheckTokens(clientID, tokensNeeded) {
		return fmt.Errorf("rate limited: need %d tokens", tokensNeeded)
	}

	// Actually take the tokens
	if !limiter.TakeTokens(clientID, tokensNeeded) {
		return fmt.Errorf("rate limited: tokens no longer available")
	}

	// Process the request...
	return nil
}

TokenBucketLimiter

The token bucket algorithm is a common rate limiting strategy that allows for controlled bursting. It maintains a "bucket" of tokens that refills at a constant rate, and each request consumes a token.

limiter, err := rate.NewTokenBucketLimiter(
    numBuckets,     // Number of buckets (automatically rounded to nearest power of 2 if not already a power of 2)
    burstCapacity,  // Maximum number of tokens in each bucket
    refillRate,     // Rate at which tokens are refilled
    refillRateUnit, // Time unit for refill rate
)

Parameters:

• numBuckets: Number of token buckets (automatically rounded up to the nearest power of two if not already a power of two)
• burstCapacity: Maximum number of tokens that can be consumed at once
• refillRate: Rate at which tokens are refilled
• refillRateUnit: Time unit for refill rate calculations (e.g., time.Second)

Input Validation:

The constructor performs validation on all parameters and returns descriptive errors:

• refillRate must be a positive, finite number (not NaN, infinity, zero, or negative)
• refillRateUnit must represent a positive duration
• The product of refillRate and refillRateUnit must not overflow when converted to nanoseconds

Methods:

• CheckToken(id []byte) bool: Checks if a token would be available without consuming it
• CheckTokens(id []byte, n uint8) bool: Checks if n tokens would be available without consuming them
• TakeToken(id []byte) bool: Attempts to take a single token, returns true if successful
• TakeTokens(id []byte, n uint8) bool: Attempts to take n tokens atomically, returns true if all n tokens were taken

Multi-token operations: The TakeTokens and CheckTokens methods support atomic multi-token operations. When requesting multiple tokens:

• The operation is all-or-nothing: either all requested tokens are taken/available, or none are
• The maximum number of tokens that can be requested is limited by the burst capacity
• These methods are useful for operations that require multiple "units" of rate limiting

Token Bucket Algorithm Explained

The token bucket algorithm uses a simple metaphor of a bucket that holds tokens:

┌─────────────────────────────────────┐
│                                     │
│  ┌───┐  ┌───┐  ┌───┐  ┌   ┐  ┌   ┐  │
│  │ T │  │ T │  │ T │  │   │  │   │  │
│  └───┘  └───┘  └───┘  └   ┘  └   ┘  │
│    │      │      │                  │
│    ▼      ▼      ▼                  │
│  avail  avail  avail                │
│                                     │
│  Available: 3 tokens │ Capacity: 5  │
└─────────────────────────────────────┘
      ▲
      │ Refill rate: 100 tokens/second
    ┌───┐  ┌───┐
    │ T │  │ T │  ...  ← New tokens added at constant rate
    └───┘  └───┘

How it works:

1. Bucket Initialization:

   • Each bucket starts with burstCapacity tokens (full)
   • A timestamp is recorded when the bucket is created

2. Token Consumption:

   • When a request arrives, it attempts to take a token
   • If a token is available, it's removed from the bucket and the request proceeds
   • If no tokens are available, the request is rate-limited

3. Token Refill:

   • Tokens are conceptually added to the bucket at a constant rate (refillRate per refillRateUnit)
   • In practice, the refill is calculated lazily only when tokens are requested
   • The formula is: refill = (currentTime - lastUpdateTime) * refillRate
   • Tokens are never added beyond the maximum burstCapacity

4. Burst Handling:

   • The bucket can temporarily allow higher rates up to burstCapacity
   • This accommodates traffic spikes while maintaining a l