limiter

README

Throttle

A Redis-backed, distributed token bucket rate limiter for Go.

This repo ships:

• A reusable library (root limiter package) with a small, testable API
• A Redis Lua script embedded in the binary for atomic token-bucket updates
• A runnable example server (cmd/example-server)
• Mermaid diagrams in docs/

Contents

• Throttle
  • Contents
  • Features
  • Requirements
  • Installation
  • Quick start (Redis-backed)
  • Core Concepts
    • Core types
    • Interface + implementations
    • Redis key format
  • Usage patterns
    • In-memory limiter (tests / single-instance)
    • HTTP integration (returning 429)
    • Fail open vs fail closed
  • Configuration
  • Observability (metrics)
  • How it works
    • Token bucket (conceptual)
    • Redis atomic update (implementation)
    • Redis data model
  • Architecture
  • Sequence
  • Example server
  • Docker
  • Testing
  • Performance
    • MemoryLimiter results
    • RedisLimiter results

Features

• Redis-backed distributed state: enforce one global limit across many app instances.
• Atomicity via Lua: token refill + deduction happens server-side as a single atomic operation.
• Context cancellation support: caller controls timeouts/deadlines for Allow().
• Pluggable metrics: bring your own Prometheus/DataDog/Otel adapter via a tiny interface.
• In-memory implementation: dependency-free MemoryLimiter for tests and local dev.

Requirements

• Go 1.24.5 (see go.mod)
• Redis (only required for RedisLimiter; MemoryLimiter is dependency-free)

Installation

go get github.com/erfderdfg/throttle

Import the library package:

import "github.com/erfderdfg/throttle"

If you prefer to be explicit about versions:

go get github.com/erfderdfg/throttle@latest

Quick start (Redis-backed)

client := redis.NewClient(&redis.Options{Addr: "localhost:6379"})

l, err := limiter.NewRedisLimiter(
    client,
    limiter.WithPrefix("myapp:"), // Redis key prefix (optional)
)
if err != nil {
    // Redis unreachable or SCRIPT LOAD failed
    log.Fatal(err)
}

id := limiter.Identity{Namespace: "user", Key: "123"}
limit := limiter.Limit{Rate: 10, Period: time.Second, Burst: 20}

dec, err := l.Allow(ctx, id, limit)
if err != nil {
    // Choose your policy: fail-open (availability) or fail-closed (protection)
    return
}
if !dec.Allow {
    // e.g., in HTTP: return 429
    return
}

Note: Each Allow() call currently has a fixed cost of 1 token.

Core Concepts

Core types

• Limit{Rate, Period, Burst}: policy definition (tokens per Period, with max capacity Burst).
• Identity{Namespace, Key}: who you are rate limiting (user, api key, ip, tenant, ...).
• Decision{Allow, Remaining, RetryAfter, ResetTime}: result + timing hints for callers.

Interface + implementations

classDiagram
    class RateLimiter {
        <<interface>>
        +Allow(ctx, id, limit)
    }
    class RedisLimiter
    class MemoryLimiter

    RateLimiter <|.. RedisLimiter
    RateLimiter <|.. MemoryLimiter

Redis key format

By default, Redis keys are:

limiter:<namespace>:<key>

You can override the prefix via WithPrefix("myapp:").

Usage patterns

In-memory limiter (tests / single-instance)

l := limiter.NewMemoryLimiter()

id := limiter.Identity{Namespace: "user", Key: "123"}
limit := limiter.Limit{Rate: 10, Period: time.Second, Burst: 10}

dec, err := l.Allow(context.Background(), id, limit)
if err != nil {
    panic(err)
}
_ = dec

HTTP integration (returning 429)

// Optional: put an upper-bound on Redis time per request.
ctx, cancel := context.WithTimeout(r.Context(), 50*time.Millisecond)
defer cancel()

dec, err := l.Allow(ctx, id, limit)
if err != nil {
    // Choose your policy:
    // - fail closed: w.WriteHeader(429/503); return
    // - fail open: continue to serve the request
}
if !dec.Allow {
    // Retry-After uses whole seconds in HTTP; rounding up is typical.
    w.Header().Set("Retry-After", fmt.Sprintf("%.0f", math.Ceil(dec.RetryAfter.Seconds())))
    w.WriteHeader(http.StatusTooManyRequests)
    return
}

Fail open vs fail closed

This library returns errors; it does not force a policy. In your application you typically pick:

• Fail closed when you must protect an upstream (strict quota enforcement).
• Fail open when availability matters more than perfect limiting.

Configuration

NewRedisLimiter uses the functional options pattern:

l, err := limiter.NewRedisLimiter(
    client,
    limiter.WithPrefix("myapp:rate:"),
    limiter.WithTimeout(2*time.Second),
    limiter.WithRecorder(myMetrics),
)

Supported options:

• WithPrefix(string) (default: limiter:)
• WithTimeout(time.Duration) (default: 5s, used by NewRedisLimiter during PING and SCRIPT LOAD)
• WithRecorder(MetricsRecorder) (default: NoOpMetricsRecorder)

Observability (metrics)

To avoid locking you into a specific telemetry stack, the library exposes a tiny interface:

type MetricsRecorder interface {
    Add(name string, value float64, tags map[string]string)
    Observe(name string, value float64, tags map[string]string)
}

The Redis-backed limiter emits:

• Counter: ratelimit.call with tags {namespace, status=allowed|denied}
• Counter: ratelimit.errors with tags {namespace, type=redis_eval|invalid_format}
• Histogram/Distribution: ratelimit.latency (seconds) with tags {namespace, status=allowed|denied|error}

MetricsRecorder methods are called inline as part of Allow(). Keep your implementation fast (or make it non-blocking) to avoid adding latency to admission checks.

How it works

Token bucket (conceptual)

Limit is a token-bucket policy:

• Refill rate: Rate / Period tokens per second
• Capacity: Burst tokens
• Cost per request: 1 token

flowchart LR
    Req["Request"] --> Check{"Tokens >= 1?"}
    Check -- Yes --> Consume["Consume 1 token"] --> Allow["Allow"]
    Check -- No --> Deny["Deny"] --> Hint["RetryAfter / ResetTime hints"]

    Refill["Time passes"] --> Add["Add tokens at rate"] --> Cap["Cap at Burst"]
    Add --> Check
    Cap --> Check

Redis atomic update (implementation)

For each Allow() call, the limiter runs an embedded Lua script via EVALSHA:

• Reads {tokens, last_refill} for the identity
• Computes refill since last_refill
• Deducts cost=1 if possible
• Writes the updated state (on allow) and sets a TTL to avoid key leaks
• Returns {allowed, remaining, retry_after, reset_time}

flowchart TD
    A["Allow(ctx, id, limit)"] --> B["EVALSHA token_bucket.lua"]
    B --> C["HMGET tokens,last_refill"]
    C --> D["Compute refill + cap"]
    D --> E{"tokens >= cost?"}
    E -- yes --> F["HMSET tokens,last_refill"]
    F --> G["EXPIRE key ttl"]
    E -- no --> H["No write"]
    G --> I["Return Decision"]
    H --> I["Return Decision"]

Redis data model

Each identity maps to a single Redis key holding a hash:

flowchart TD
    K["key = {prefix}{namespace}:{key}"] --> H["Redis Hash"]
    H --> T["tokens (float)"]
    H --> R["last_refill (unix seconds, float)"]
    K --> X["TTL ~= ceil(2 * (Burst / refill_rate))"]

Architecture

Full diagram: docs/architecture.md

graph TD
    Client["Client Traffic"] --> LB["Load Balancer"]

    subgraph "Application Cluster"
        NodeA["App Instance A"]
        NodeB["App Instance B"]
        NodeC["App Instance C"]
    end

    LB --> NodeA
    LB --> NodeB
    LB --> NodeC

    subgraph "Shared State"
        Redis["Redis Primary"]
    end

    NodeA -- "Allow()" --> Redis
    NodeB -- "Allow()" --> Redis
    NodeC -- "Allow()" --> Redis

    note["Lua script ensures atomic token deduction"]
    Redis --- note

Sequence

Full diagram: docs/sequence.md

sequenceDiagram
    participant App
    participant Limiter as RedisLimiter
    participant Metrics as MetricsRecorder
    participant Redis as Redis Server

    App->>Limiter: Allow(ctx, id, limit)
    activate Limiter

    Limiter->>Limiter: Start Timer

    rect rgb(200, 255, 200)
    Note right of Limiter: Network I/O
    Limiter->>Redis: EVALSHA (Token Bucket)

    Redis-->>Limiter: {allowed, remaining, retry_after, reset_time}
    end

    Limiter->>Metrics: Add("ratelimit.call", ...)
    Limiter->>Metrics: Add("ratelimit.errors", ...) (if applicable)

    Limiter-->>App: Decision {Allow: true/false, ...}

    deactivate Limiter
    Limiter->>Metrics: Observe("ratelimit.latency", duration)

Example server

The repo includes a minimal HTTP server that demonstrates how to apply the limiter to an endpoint:

• Entry point: cmd/example-server/main.go
• Endpoint: GET /ping
• Identity: Namespace="ip", Key=r.RemoteAddr (demo choice)
• Env var: REDIS_ADDR (default localhost:6379)

Run locally:

docker run --rm -p 6379:6379 redis:7-alpine
REDIS_ADDR=localhost:6379 go run ./cmd/example-server
curl -i http://localhost:8080/ping

Docker

Build the example server image:

docker build -t throttle-example .

Run Redis + the example server on a shared Docker network:

docker network create rl-demo || true
docker run -d --name rl-redis --network rl-demo redis:7-alpine

docker run --rm --network rl-demo -p 8080:8080 \
  -e REDIS_ADDR=rl-redis:6379 \
  throttle-example

Testing

Run unit tests:

go test ./...

Redis integration tests will automatically skip if Redis is not reachable at localhost:6379.

Performance

Benchmarks were run on standard developer hardware (M1 / Dell XPS) using:

go test -bench=. -benchmem .

MemoryLimiter results

BenchmarkMemoryLimiter_Allow-10    15492812    76.4 ns/op    0 B/op    0 allocs/op

• ~76 nanoseconds per operation.
• Zero allocations (GC friendly hot path).

RedisLimiter results

• Dominated by network RTT (Redis round-trip).
• Lua script execution time is < 50µs on the server side.
• End-to-end latency is typically < 1ms depending on network proximity.

Documentation

Overview

Package limiter provides local and distributed rate limiting based on the Token Bucket algorithm.

The primary entry point is the RateLimiter interface:

dec, err := limiter.Allow(ctx, id, limit)

The returned Decision contains whether the request is allowed, how many whole tokens remain, and timing hints for callers that want to set rate-limit headers (for example, Retry-After).

Overview

This package implements a Token Bucket:

• Each identity has a "bucket" holding tokens.
• The bucket refills over time up to a maximum capacity (Burst).
• Each Allow call consumes 1 token when available.

Unlike fixed-window counters, token buckets naturally support bursts while still enforcing a long-term average rate.

Core Types

Limit defines the policy:

• Rate: tokens earned per Period (for example, 10 per second or 60 per minute)
• Period: the time window Rate is measured over
• Burst: maximum number of tokens the bucket can hold (also the maximum immediate burst)

Identity defines "who" is being rate-limited. It is split into:

• Namespace: a logical grouping (for example, "user", "ip", "api_key")
• Key: the identifier within that namespace (for example, "user_123")

Backends

The package provides two implementations with the same Allow API:

• MemoryLimiter: an in-process limiter backed by a Go map. This is useful for unit tests, local development, and single-instance deployments. Because its state is local to the process, it does not enforce a global limit across multiple replicas.

• RedisLimiter: a distributed limiter backed by Redis. It uses a Lua script to perform the read/compute/write cycle atomically, which makes it safe to use across many application instances while enforcing a single global budget per identity.

Recommendation: use RedisLimiter in production when you need a global limit, and MemoryLimiter in tests (as a fast, dependency-free stand-in).

Concurrency

MemoryLimiter is safe for concurrent use by multiple goroutines (it uses a mutex to protect its internal map and per-identity state). RedisLimiter delegates concurrency safety to Redis and the go-redis client.

Context and Error Policy

Allow accepts a context.Context. RedisLimiter passes this context through to Redis operations so callers can enforce deadlines and cancel work to avoid cascading failures during partial outages.

This package does not impose a "fail open" vs "fail closed" policy. If Redis is unavailable or the context expires, Allow returns a non-nil error and the caller decides whether to deny traffic (protect the backend) or allow traffic (maximize availability).

Decision Semantics

Decision fields are intended to be directly consumable by application code:

• Allow reports whether the current request is permitted.
• Remaining is the number of whole tokens remaining after the decision is applied (floored to an int64).
• RetryAfter is 0 when allowed; when denied it is the approximate duration until a single token is expected to be available.
• ResetTime is the absolute timestamp corresponding to time.Now()+RetryAfter.

Usage

For a runnable example using MemoryLimiter, see ExampleMemoryLimiter in example_test.go.

Storage Details

MemoryLimiter stores state in a process-local map keyed by:

"{namespace}:{key}"

RedisLimiter stores state in Redis under keys prefixed with "limiter:" and uses a Redis hash with two fields:

• "tokens": current token balance (float)
• "last_refill": last update time as seconds since epoch (float)

Redis keys are set to expire to avoid leaking memory for identities that stop sending requests.

Limitations and Notes

• MemoryLimiter does not evict old identities; for long-lived processes with high-cardinality keys you likely want RedisLimiter or a custom in-memory store with TTL/LRU eviction.
• RedisLimiter requires a reachable Redis instance and returns errors directly; callers must decide their availability vs protection tradeoff.
• This package currently models each Allow call as a cost of 1 token.
• RedisLimiter uses EVALSHA; if Redis is restarted and script cache is cleared, Allow may return a NOSCRIPT error until the script is reloaded (recreating the limiter via NewRedisLimiter will load it).

Configuration

RedisLimiter is configured using the Functional Options pattern:

limiter, _ := NewRedisLimiter(client,
	WithPrefix("myapp:rate:"),
	WithTimeout(2*time.Second),
	WithRecorder(myMetrics),
)

Supported options:

• WithPrefix(string): Sets the key prefix (default "limiter:").
• WithTimeout(time.Duration): Sets the context timeout for Redis operations (default 5s).
• WithRecorder(MetricsRecorder): Injects a custom metrics backend.

Index

• type Decision
• type Identity
• type Limit
• type MemoryLimiter
  • func NewMemoryLimiter() *MemoryLimiter
  • func (m *MemoryLimiter) Allow(ctx context.Context, id Identity, limit Limit) (Decision, error)
• type MetricsRecorder
• type Namespace
• type NoOpMetricsRecorder
  • func (n *NoOpMetricsRecorder) Add(name string, value float64, tags map[string]string)
  • func (n *NoOpMetricsRecorder) Observe(name string, value float64, tags map[string]string)
• type Option
  • func WithPrefix(prefix string) Option
  • func WithRecorder(recorder MetricsRecorder) Option
  • func WithTimeout(timeout time.Duration) Option
• type PrometheusRecorder
  • func NewPrometheusRecorder(reg prometheus.Registerer) *PrometheusRecorder
  • func (p *PrometheusRecorder) Add(name string, value float64, tags map[string]string)
  • func (p *PrometheusRecorder) Observe(name string, value float64, tags map[string]string)
• type RateLimiter
• type RedisLimiter
  • func NewRedisLimiter(client *redis.Client, opts ...Option) (*RedisLimiter, error)
  • func (r *RedisLimiter) Allow(ctx context.Context, id Identity, limit Limit) (Decision, error)
• type SlidingWindowLimiter
  • func NewSlidingWindowLimiter(client *redis.Client, opts ...Option) (*SlidingWindowLimiter, error)
  • func (l *SlidingWindowLimiter) Allow(ctx context.Context, id Identity, limit Limit) (Decision, error)

Examples

• MemoryLimiter

Types

type Decision

type Decision struct {
	Allow      bool
	Remaining  int64
	RetryAfter time.Duration
	ResetTime  time.Time
}

Decision is the result of a rate-limit check.

type Identity

type Identity struct {
	Namespace Namespace
	Key       string
}

Identity uniquely identifies the subject being rate-limited (for example, a user ID, an API key, or an IP address).

type Limit

type Limit struct {
	Rate   int64
	Period time.Duration
	Burst  int64
}

Limit defines a token-bucket policy.

Rate is measured as tokens per Period. Burst is the maximum token capacity of the bucket and controls how many requests can be allowed immediately.

type MemoryLimiter

type MemoryLimiter struct {
	// contains filtered or unexported fields
}

MemoryLimiter is an in-process token-bucket rate limiter.

It is safe for concurrent use by multiple goroutines, but its state is local to the process and is not shared across replicas. Use RedisLimiter when you need a single global limit across multiple instances.

Example

l := NewMemoryLimiter()

limit := Limit{
	Rate:   10,
	Period: time.Second,
	Burst:  10,
}
id := Identity{Namespace: "user", Key: "user_123"}

dec, err := l.Allow(context.Background(), id, limit)
if err != nil {
	panic(err)
}

fmt.Println(dec.Allow)

Output:
true

func NewMemoryLimiter

func NewMemoryLimiter() *MemoryLimiter

NewMemoryLimiter constructs a MemoryLimiter with empty state.

func (*MemoryLimiter) Allow

func (m *MemoryLimiter) Allow(ctx context.Context, id Identity, limit Limit) (Decision, error)

Allow checks whether a request for the given identity should be allowed under the provided limit. Each call has a fixed cost of 1 token.

type MetricsRecorder

type MetricsRecorder interface {
	// Add increments a counter (e.g., requests_total)
	Add(name string, value float64, tags map[string]string)

	// Observe records a value in a histogram/distribution (e.g., latency)
	Observe(name string, value float64, tags map[string]string)
}

MetricsRecorder defines the interface for collecting telemetry. We abstract this so we aren't tied to Prometheus, Datadog, or any specific vendor.

type Namespace

type Namespace string

type NoOpMetricsRecorder

type NoOpMetricsRecorder struct{}

NoOpMetricsRecorder is a placeholder that does nothing. It ensures we never have to check 'if r.recorder != nil' in our hot path.

func (*NoOpMetricsRecorder) Add

func (n *NoOpMetricsRecorder) Add(name string, value float64, tags map[string]string)

func (*NoOpMetricsRecorder) Observe

func (n *NoOpMetricsRecorder) Observe(name string, value float64, tags map[string]string)

type Option

type Option func(*limiterConfig)

Option configures a Redis-backed rate limiter.

func WithPrefix

func WithPrefix(prefix string) Option

WithPrefix sets the Redis key prefix. Default is "limiter:".

func WithRecorder

func WithRecorder(recorder MetricsRecorder) Option

WithRecorder sets the metrics recorder. Default is NoOpMetricsRecorder.

func WithTimeout

func WithTimeout(timeout time.Duration) Option

WithTimeout sets the timeout for Redis operations during initialization. Default is 5s.

type PrometheusRecorder

type PrometheusRecorder struct {
	// contains filtered or unexported fields
}

PrometheusRecorder implements MetricsRecorder using Prometheus counters and histograms. Inject it via WithRecorder to expose per-namespace allow/deny counters and p99 admission latency on a /metrics endpoint.

func NewPrometheusRecorder

func NewPrometheusRecorder(reg prometheus.Registerer) *PrometheusRecorder

NewPrometheusRecorder creates a PrometheusRecorder and registers its metrics with reg. Pass prometheus.DefaultRegisterer for the default global registry.

func (*PrometheusRecorder) Add

func (p *PrometheusRecorder) Add(name string, value float64, tags map[string]string)

Add increments a counter metric. Recognised names: "ratelimit.call", "ratelimit.errors".

func (*PrometheusRecorder) Observe

func (p *PrometheusRecorder) Observe(name string, value float64, tags map[string]string)

Observe records a histogram sample. Recognised names: "ratelimit.latency".

type RateLimiter

type RateLimiter interface {
	Allow(ctx context.Context, id Identity, limit Limit) (Decision, error)
}

RateLimiter performs token-bucket admission control.

type RedisLimiter

type RedisLimiter struct {
	// contains filtered or unexported fields
}

RedisLimiter is a distributed rate limiter backed by Redis.

It uses a Lua script to perform the token-bucket update atomically, which allows multiple application instances to enforce a single shared limit.

func NewRedisLimiter

func NewRedisLimiter(client *redis.Client, opts ...Option) (*RedisLimiter, error)

NewRedisLimiter validates connectivity and loads the embedded Lua script into Redis (SCRIPT LOAD). The returned limiter is ready to use.

func (*RedisLimiter) Allow

func (r *RedisLimiter) Allow(ctx context.Context, id Identity, limit Limit) (Decision, error)

Allow checks whether a request for the given identity should be allowed under the provided limit. Each call has a fixed cost of 1 token.

type SlidingWindowLimiter

type SlidingWindowLimiter struct {
	// contains filtered or unexported fields
}

SlidingWindowLimiter is a distributed rate limiter using a strict sliding window backed by a Redis sorted set. Each request is recorded with its timestamp as the score; expired entries are pruned on every call. Unlike a token bucket, this algorithm does not accumulate burst capacity — it enforces an exact count over a rolling window, making it well-suited for security-sensitive routes.

func NewSlidingWindowLimiter

func NewSlidingWindowLimiter(client *redis.Client, opts ...Option) (*SlidingWindowLimiter, error)

NewSlidingWindowLimiter validates connectivity and loads the embedded Lua script into Redis (SCRIPT LOAD). The returned limiter is ready to use.

Accepts the same Option values as NewRedisLimiter (WithPrefix, WithTimeout, WithRecorder).

func (*SlidingWindowLimiter) Allow

func (l *SlidingWindowLimiter) Allow(ctx context.Context, id Identity, limit Limit) (Decision, error)

Allow checks whether a request for the given identity should be allowed within the rolling window defined by limit.Period. The window holds at most limit.Rate requests; limit.Burst is not used. Each call has a fixed cost of 1.