rate
High-performance rate limiting library with token bucket and AIMD strategies
About rate
This large README is shown as a plain-text preview. Read the full README at the source
# Rate
[](https://pkg.go.dev/github.com/webriots/rate)
[](https://coveralls.io/github/webriots/rate?branch=main)
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
```shell
go get github.com/webriots/rate
```
## Quick Start
### Token Bucket Rate Limiter
```go
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](https://go.dev/play/p/oDQlxRe75g_H)
### AIMD Rate Limiter
```go
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](https://go.dev/play/p/UDslvGAPG-O)
### Rotating Token Bucket Rate Limiter
```go
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](https://go.dev/play/p/nTlCGSHtQ7j)
## Detailed Usage
### Common Interface
All rate limiters in this package implement the `Limiter` interface:
```go
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:
```go
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.
```go
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 long-term average rate
**Implementation Details:**
- This library uses a sharded approach with multiple buckets to reduce contention
- Each request ID is consistently hashed to the same bucket
- The bucket stores both token count and timestamp in a single uint64 for efficiency
### AIMDTokenBucketLimiter
The AIMD (Additive Increase, Multiplicative Decrease) algorithm provides dynamic rate adjustments inspired by TCP congestion control. It gradually increases token rates during successful operations and quickly reduces rates when encountering failures.
```go
limiter, err := rate.NewAIMDTokenBucketLimiter(
numBuckets, // Number of buckets (automatically rounded to nearest power of 2 if not already a power of 2)
burstCapacity, // Maximum tokens per bucket
rateMin, // Minimum token refill rate
rateMax, // Maximum token refill rate
rateInit, // Initial token refill rate
rateAdditiveIncrease, // Amount to increase rate on success
rateMultiplicativeDecrease, // Factor to decrease rate on failure
rateUnit, // Time unit for rate calculations
)
```
#### 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
- `rateMin`: Minimum token refill rate
- `rateMax`: Maximum token refill rate
- `rateInit`: Initial token refill rate
- `rateAdditiveIncrease`: Amount to increase rate by on success
- `rateMultiplicativeDecrease`: Factor to decrease rate by on failure
- `rateUnit`: Time unit for rate calculations (e.g., time.Second)
#### Input Validation:
The constructor performs comprehensive validation on all parameters and returns descriptive errors:
- `rateInit` must be a positive, finite number (not NaN, infinity, zero, or negative)
- `rateUnit` must represent a positive duration
- `rateMin` must be a positive, finite number
- `rateMax` must be a positive, finite number
- `rateMin` must be less than or equal to `rateMax`
- `rateInit` must be between `rateMin` and `rateMax` (inclusive)
- `rateAdditiveIncrease` must be a positive, finite number
- `rateMultiplicativeDecrease` must be a finite number greater than or equal to 1.0
- The product of `rateInit`, `rateMin`, `rateMax`, or `rateAdditiveIncrease` with `rateUnit` 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
- `IncreaseRate(id []byte)`: Additively increases the rate for the given ID (on success)
- `DecreaseRate(id []byte)`: Multiplicatively decreases the rate for the given ID (on failure)
#### AIMD Algorithm Explained
The AIMD algorithm dynamically adjusts token refill rates based on success or failure feedback, similar to how TCP adjusts its congestion window:
```
Rate
▲
│
│
│
rateMax ─────────────────────────────────────────
│ ╱ │
│ ╱ │
│ ╱ │ ╱
│ ╱ │ ╱
│ ╱ │ ╱
│ ╱ │ ╱
│ ╱ │ ╱
│ ╱ │ ╱
│ ╱ ▼ Multiplicative
│ ╱ Decrease
│ ╱ (rate / 2)
│ ╱
rateInit
│ ↑
│ Additive
│ Increase
│ (+1)
rateMin ─────────────────────────────────────────
│
└─────────────────────────────────────────────► Time
Success Failure
```
**How it works:**
1. **Initialization**:
- Each bucket starts with a rate of `rateInit` tokens per time unit
- Token buckets are created with `burstCapacity` tokens
2. **Adaptive Rate Adjustment**:
- When operations succeed, the rate increases linearly by `rateAdditiveIncrease`
- `newRate = currentRate + rateAdditiveIncrease`
- When operations fail, the rate decreases multiplicatively by `rateMultiplicativeDecrease`
- `newRate = rateMin + (currentRate - rateMin) / rateMultiplicativeDecrease`
- Rates are bounded between `rateMin` (lower bound) and `rateMax` (upper bound)
3. **Practical Applications**:
- Gracefully adapts to changing capacity of backend systems
- Quickly backs off when systems are overloaded (multiplicative decrease)
- Slowly probes for increased capacity when systems are healthy (additive increase)
- Maintains stability even under varying load conditions
**Implementation Details:**
- Each ID has its own dedicated rate that adjusts independently
- The actual token bucket mechanics remain the same as TokenBucketLimiter
- Rate changes are applied atomically using lock-free operations
- Rate information is stored alongside token information in the bucket
### RotatingTokenBucketLimiter
The Rotating Token Bucket Rate Limiter addresses a fundamental limitation of hash-based rate limiters: hash collisions between different IDs can cause unfair rate limiting. This limiter maintains two TokenBucketLimiters with different hash seeds and automatically rotates between them to minimize collision impact while ensuring correctness.
```go
limiter, err := rate.NewRotatingTokenBucketLimiter(
numBuckets, // Number of buckets (automatically rounded to nearest power of 2 if not already a power of 2)
burstCapacity, // Maximum tokens per bucket
refillRate, // Rate at which tokens are refilled
refillRateUnit, // Time unit for refill rate
)
```
#### Parameters:
- `numBuckets`: Number of token buckets per limiter (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)
#### Automatic Rotation Calculation:
The rotation interval is automatically calculated to ensure 99.99% statistical convergence of all token buckets to steady state before rotation occurs. This eliminates state inconsistency issues and guarantees correctness:
```
rotationInterval = (burstCapacity / refillRate * refillRateUnit) * 5.0
```
For example:
- `burstCapacity=100, refillRate=250/second` → rotation every 2 seconds
- `burstCapacity=10, refillRate=1/second` → rotation every 50 seconds
#### 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
- `RotationInterval() time.Duration`: Returns the automatically calculated rotation interval
#### Collision-Resistant Algorithm Explained
The rotating limiter solves the hash collision problem by maintaining two token bucket limiters and periodically rotating their roles:
```
Time: 0s Time: 30s (rotation) Time: 60s (rotation)
┌─────────────────────────┐ ┌─────────────────────────┐ ┌─────────────────────────┐
│ Limiter A (checked) │ │ Limiter B (checked) │ │ Limiter C (checked) │
│ - seed: 0x1234 │→│ - seed: 0x5678 │→│ - seed: 0x9ABC │
│ - decision: ✓ enforced │ │ - decision: ✓ enforced │ │ - decision: ✓ enforced │
│ │ │ │ │ │
│ Limiter B (ignored) │ │ Limiter C (ignored) │ │ Limiter D (ignored) │
│ - seed: 0x5678 │ │ - seed: 0x9ABC │ │ - seed: 0xDEF0 │
│ - decision: ✗ discarded │ │ - decision: ✗ discarded │ │ - decision: ✗ discarded │
└─────────────────────────┘ └─────────────────────────┘ └─────────────────────────┘
Hash Collision Scenario:
┌─────────────────────────────────────────────────────────────────────────────────┐
│ ID "user-123" and "user-456" both hash to bucket 42 in Limiter A (collision!) │
│ They compete for the same tokens → unfair rate limiting │
│ │
│ After rotation (30s later): │
│ - Limiter B becomes "checked" with seed 0x5678 │
│ - Very likely: "user-123" → bucket 15, "user-456" → bucket 73 (no collision!) │
│ - Collision resolved! Each ID now has independent rate limiting │
└─────────────────────────────────────────────────────────────────────────────────┘
```
**How it works:**
1. **Dual Limiter Architecture**:
- Maintains two identical TokenBucketLimiters with different hash seeds
- "Checked" limiter: its result determines rate limiting decisions
- "Ignored" limiter: maintains state but its result is discarded
2. **Token Consumption Strategy**:
- Each `TakeToken()` call consumes tokens from **both** limiters
- Only the "checked" limiter's success/failure determines the result
- **Trade-off**: 2x token consumption rate for collision resistance
3. **Periodic Rotation**:
- Every `rotationRate` duration, the limiters rotate roles:Frequently Asked Questions
What is rate?
rate is a Utilities library for the Go programming language. High-performance rate limiting library with token bucket and AIMD strategies
How do I install rate?
Install rate with the Go module system using `go get webriots/rate`. Check the repository for the current installation instructions.
What category does rate belong to?
rate is listed under Utilities, specifically Utilities.