krate

package module
v0.0.0-...-a513f06 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 17, 2026 License: MIT Imports: 20 Imported by: 0

README

Krate Banner



The Ultra-Fast Distributed Rate Limiter for Go

🚀 Up to 5,100x Faster Latency  •  📈 Up to 50x Higher Throughput  •  📉 99% Less Redis Traffic

Powered by Local Token Borrowing, Map-based Top-N Delta Gossip, and Mesh Peer Routing.

Go Reference Go Report Card

⚡ Why Krate?

Traditional distributed rate limiters hit Redis on every single request. At scale, this introduces massive latency (~1ms+ per request), creates a single point of failure, and heavily inflates your infrastructure costs.

Krate acts as an intelligent, predictive, local-first proxy that buffers tokens directly in your application memory.

How Krate Compares

Approach Latency (p99) Redis CPU Load Accuracy (Hard Limits) Complex Skewed Traffic
Redis-only (Traditional) High (~5-15ms) High ($O(N)$ calls) Perfect Good
Static Partitioning Low (~30ns) Zero Poor (False Rejections) Terrible
Async Write-Back Low (~30ns) Low Terrible (Massive Leakage) Poor
Krate (Segment Borrowing) Low (p50: ~1.5μs) Very Low (95%+ reduction) Tight (~1% variance) Excellent (Peer Transfer)

🚀 Zero-Redis Hot Path

Tokens are consumed locally yielding nanosecond latency. Say goodbye to network bottlenecks on your critical path.

📉 99% Less Redis Load

Background goroutines asynchronously batch-borrow tokens ahead of demand, dramatically cutting cloud bills.

🌐 Mesh Peer Discovery

Instances seamlessly form a cluster, sharing real-time metrics and routing surplus tokens to peers over ultra-fast, compressed gRPC.

🛡️ Singleflight Optimization

Thousands of concurrent requests for the same key trigger only one Redis network call, preventing thundering herds.

🚀 Benchmark Performance (Production Grade)

Krate provides a staggering performance boost over standard Redis rate limiters. In our aggressive benchmark suites, Krate handles millions of requests per second and provides microsecond p50 latencies, but can exhibit higher tail latencies (p99.9) during heavy lock contention for pre-borrowing.

Hardware: Standard developer machine (localhost Redis)
Traffic pattern: Zipfian distribution (real-world skew)
Setup: 4 Instances, 10,000 Keys

What are we benchmarking?

To prove Krate handles every edge case, we test it against distinct workload profiles:

  1. Global API Gateway (Power-law Traffic): 1% of hot keys (e.g., your biggest customers) generate 50% of the total traffic. Tests Krate's ability to cache hot keys aggressively.
  2. Multi-Tenant SaaS (High Concurrency): Heavy throughput spread evenly across tenants. Tests amortized borrowing.
  3. Bot IP Throttling (Massive Cardinality): Millions of unique IPs with very tight limits (e.g., 60 req/min). Tests how Krate handles memory pressure and rapid eviction.
  4. Mesh Peer-to-Peer Transfer (Zero Redis Fallback): Intentionally starves one instance to force it to ask a neighboring peer for tokens via gRPC. Tests the mesh network's ability to keep Redis traffic at 0.

Throughput & Cost Reduction

Scenario Krate Throughput Redis-Only Throughput Speedup Redis Load Reduction
API Gateway 2.74M req/s 57.5K req/s 47.7x 99%
Multi-Tenant SaaS 1.67M req/s 57.6K req/s 29.0x 99%
Peer Token Flow 2.93M req/s 58.5K req/s 50.1x 100%
IP Throttling 608.3K req/s 55.4K req/s 11.0x 96%
Per-User Limiting 581.6K req/s 47.5K req/s 12.2x 97%
Peer Transfer 147.4K req/s 55.8K req/s 2.6x 94%

Latency Profile & The Tail Trade-off

While Krate is up to 5,100x faster on average (p50), the asynchronous pre-borrowing engine can introduce lock contention at the extreme tail (p99.9).

Scenario Latency p50
(Krate / Redis)		 Latency p99
(Krate / Redis)		 Latency p99.9
(Krate / Redis)
API Gateway 1.8μs / 6.9ms 2.0ms / 9.8ms 22.4ms / 60.9ms
Multi-Tenant SaaS 1.9μs / 6.9ms 3.0ms / 9.4ms 18.8ms / 20.8ms
Peer Token Flow 1.9μs / 1.7ms 6.0μs / 2.5ms 3.3ms / 5.4ms
IP Throttling 2.0μs / 10.3ms 17.7ms / 22.6ms 175.2ms / 46.2ms
Per-User Limiting 2.2μs / 6.9ms 7.9ms / 17.8ms 73.1ms / 686.6ms
Peer Transfer 594.1μs / 3.4ms 4.2ms / 8.5ms 52.2ms / 20.2ms

The Trade-off Verdict: You are trading extreme tail consistency (which occasionally blocks a goroutine for ~200ms while it waits for a Redis pre-borrow batch to finish under heavy lock contention) for an overall system throughput increase of 2x-50x+ and a massive reduction in database costs.

🎯 Accuracy & Policy Enforcement (Why Krate Has Fewer False Rejections)

When building local-caching distributed rate limiters, developers usually fear two fatal issues:

  1. Token Leakage (Over-admission): Caching allows users to burst far beyond their limit before nodes sync.
  2. False Rejections (Under-admission): Legitimate requests are rejected because one node runs out of tokens while sibling nodes hold a surplus.

Krate solves both using a conservative segment-borrowing model and gRPC-based peer token donations. Under an aggressive Zipfian-skewed load test on 4 instances:

Metric Krate Redis-Only (Traditional) Why Krate Wins
Leakage (Over-admission) ~1.33% 0.00% Segment locks and local bypass flags prevent bursts.
False Rejections ~0.80% 0.00% Peer donations transfer surplus tokens to dry nodes, keeping false rejections under 1%.

By gossiping state changes and transferring spare tokens directly between nodes, Krate preserves the accuracy of a centralized database while operating at memory speed.

💾 Zero-Allocation Local Hot Path

Rate limiters sit directly on the hot path of high-performance API gateways. Any memory allocation on this path causes Garbage Collection (GC) pauses and elevates tail latencies.

Krate's local hot-path check (which handles 80-99% of requests under normal operation) is designed to be completely allocation-free:

BenchmarkAllow_LocalHit-10             9.6M ops/s   121.2 ns/op     0 B/op     0 allocs/op
BenchmarkAllow_LocalHit_Parallel-10    5.7M ops/s   205.4 ns/op     0 B/op     0 allocs/op
  • 0 Heap Allocations on token hits.
  • Executes in ~120ns per request (single-threaded) or ~200ns (parallel).

🌐 HTTP Middleware Load Test (Vegeta / wrk)

To verify how Krate performs under real network conditions (TCP overhead, HTTP parsing, context switching), you can run a load test against the fully functional HTTP server example included in the repository:

  1. Spin up the Redis instance: 
    docker run -d --name redis -p 6379:6379 redis:alpine
  2. Start the example HTTP gateway server: 
    REDIS_ADDR=localhost:6379 go run cmd/krate-example/main.go
  3. Execute an aggressive HTTP load test using Vegeta: 
    echo "GET http://localhost:8080/" | vegeta attack -header "X-API-Key: my-bench-key" -rate=30000 -duration=10s | vegeta report
    Or using wrk: 
    wrk -t12 -c400 -d10s -H "X-API-Key: my-bench-key" http://localhost:8080/

This runs the rate limiter directly inside high-performance fasthttp middleware, proving that Krate maintains microsecond p50 response times even under real network stress at 30,000+ RPS.

🧠 Architecture & Request Flow

Krate uses a combination of advanced techniques to keep your cluster perfectly in sync without punishing the database.

Decision Flow Diagram

graph TD
    A[Incoming Request] --> B{Local Bucket?}
    B -- "Yes: Tokens Available (~30ns)" --> C[Allow Request]
    B -- "No: Empty" --> D{Local Bypass Active?}
    D -- "Yes: Target Rate Exhausted (~1ns)" --> E[Reject Request]
    D -- "No" --> F{Predictive Router}
    F -- "Option A: gRPC Peer Transfer" --> G[Acquire spare tokens from Peer Node]
    F -- "Option B: Redis Borrow" --> H[Borrow segment via Lua script]
    G --> I[Refill Local Bucket]
    H --> I
    I --> B

Network Sequence Diagram

sequenceDiagram
    participant Client
    participant Krate as Krate (Local Node)
    participant Peer as Peer Node (gRPC)
    participant Redis as Redis (Global)
    
    Client->>Krate: Allow("user:123")
    
    alt Local Tokens Available (Fast Path)
        Krate-->>Client: ✅ Allowed (~30ns)
    else Local Exhausted, Peer has Surplus (Mesh Path)
        Krate->>Peer: gRPC TransferTokens
        Peer-->>Krate: Tokens Granted
        Krate-->>Client: ✅ Allowed (~3ms)
    else Peer Exhausted, Request from Redis (Slow Path)
        Krate->>Redis: Lua Borrow Script
        Redis-->>Krate: Tokens Granted
        Krate-->>Client: ✅ Allowed (~5ms)
    end

The Secret Sauce

  • 🔄 Adaptive Token Borrowing: Krate borrows chunks of tokens from Redis. If a key is hot, it pre-borrows before running out, ensuring the critical path is strictly in-memory.
  • 📊 Map-Based Top-N Delta Gossiping: Every instance tracks key consumption locally at the bucket level. These consumption and borrowing statistics are filtered to the Top N hottest keys, and only changes (deltas) are transmitted over the mesh network to peers.
  • ⚡ Peer Forwarding: If Instance A exhausts its tokens but Instance B has a surplus, Instance A will directly forward the request to Instance B over lightning-fast gRPC, completely bypassing Redis.
  • 🔀 Extensible Routing: Decouples borrowing logic from the request pipeline into a routing package, supporting customizable routing decisions (e.g. standard fallback, custom priority trees, or ML-based predictions).
  • 🧹 Automatic Inactive Lease Cleanup: Key state is kept alive via lease-based expiration. Any borrowed state inactive for longer than the lease TTL is automatically purged, preventing memory leaks.
  • 🤐 gRPC Transport Compression: Enables gzip compression on mesh connections, minimizing network bandwidth when gossiping states.

🛠 Installation

go get github.com/krigsherre/krate

💻 Quick Start

Drop Krate into your existing Go application with just a few lines of code:

package main

import (
	"context"
	"fmt"
	"time"

	"github.com/krigsherre/krate"
	"github.com/redis/go-redis/v9"
)

func main() {
	rdb := redis.NewUniversalClient(&redis.UniversalOptions{
		Addrs: []string{"localhost:6379"},
	})

	limiter, err := krate.New(rdb,
		krate.WithLimit(10000),             // 10,000 requests
		krate.WithWindow(time.Minute),      // per minute
		krate.WithPeerListen(":7100"),      // Start gRPC server for peer mesh
		krate.WithGossipInterval(100 * time.Millisecond),
	)
	if err != nil {
		panic(err)
	}
	defer limiter.Close()

	ctx := context.Background()

	// ⚡ Allow() returns in ~30ns! 
	allowed, err := limiter.Allow(ctx, "user:123")
	if err != nil {
		panic(err)
	}

	if allowed {
		fmt.Println("Request allowed!")
	} else {
		fmt.Println("Rate limit exceeded.")
	}
}

⚙️ Advanced Configuration

Krate is highly tunable for your specific workload:

Click to expand configuration options & workload recipes

🎛️ Tunable Options

  • WithPreBorrowThreshold(float64): Triggers async background fetch when tokens dip below this percentage (e.g., 0.2 for 20%).
  • WithProbeK(int): The number of healthy peers to query via gRPC when falling back to peer borrowing (Mesh mode).
  • WithMaxGossipKeys(int): The maximum number of keys to include in gossip payloads (limits payload to Top N hottest keys).
  • WithRouter(routing.Router): Plug in custom routing strategies for token acquisition.
  • WithMetrics(prometheus.Registerer): Easily export deep insights into cache hits, Redis latency, and peer forwarding.

🍳 Workload Recipes

1. API Gateway (Power-law / Zipfian Traffic) For massive, uneven traffic where 1% of keys handle 50% of the load, aggressive pre-borrowing keeps the hot path purely in-memory:

krate.WithPreBorrowThreshold(0.3), // Fetch early (at 30% remaining)
krate.WithMaxBorrow(2500),         // Allow large batch borrows for hot keys

2. IP Throttling (Massive Cardinality, Bot Tail) For millions of unique IPs with low limits (e.g., 60 req/min), prioritize mesh peer discovery over heavy Redis writes:

krate.WithProbeK(3),               // Query 3 peers before falling back to Redis
krate.WithPreBorrowThreshold(0.1), // Delay background fetches for low-frequency IPs
krate.WithMaxBorrow(15),           // Keep batch borrows small to prevent token hoarding

3. Multi-Tenant SaaS (High Throughput per Tenant) When dealing with tight, high-volume limits per tenant, you want fast gossip state propagation:

krate.WithGossipInterval(100 * time.Millisecond), // Fast state propagation
krate.WithMaxGossipKeys(500),                     // Gossip Top 500 hot tenants

🤝 Contributing

Contributions, issues, and feature requests are welcome! Feel free to check the issues page.

📄 License

This project is MIT licensed.

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrPoolExhausted  = errors.New("krate: redis pool exhausted")
	ErrNoPeerTokens   = errors.New("krate: no peer tokens available")
	ErrGlobalLimit    = errors.New("krate: global rate limit reached")
	ErrInstanceExists = errors.New("krate: instance already registered")
	ErrKeyNotFound    = errors.New("krate: rate limit key not found")
	ErrClosed         = errors.New("krate: limiter is closed")
	ErrCycle          = errors.New("krate: request cycle detected")
)

Functions

This section is empty.

Types

type Clock 

type Clock interface {
	Now() time.Time
	Since(t time.Time) time.Duration
	NewTicker(d time.Duration) *time.Ticker
	After(d time.Duration) <-chan time.Time
}

type EvictionPolicy 

type EvictionPolicy interface {
	ShouldEvict(b *bucket, nowMs int64) bool
}

type IdleEvictionPolicy 

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

func NewIdleEvictionPolicy 

func NewIdleEvictionPolicy(timeout time.Duration) *IdleEvictionPolicy

func (*IdleEvictionPolicy) ShouldEvict 

func (p *IdleEvictionPolicy) ShouldEvict(b *bucket, nowMs int64) bool

type Janitor 

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

func NewJanitor 

func NewJanitor(interval time.Duration, evictFn func(nowMs int64)) *Janitor

func (*Janitor) Start 

func (j *Janitor) Start(ctx context.Context, clock Clock)

type Limiter 

type Limiter interface {
	Allow(ctx context.Context, key string) (bool, error)
	AllowN(ctx context.Context, key string, n uint64) (bool, error)
	Close() error
}

func New 

func New(rdb redis.UniversalClient, opts ...Option) (Limiter, error)

type LocalBucket 

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

func NewLocalBucket 

func NewLocalBucket(_ string, initial uint64) *LocalBucket

func (*LocalBucket) Drain 

func (b *LocalBucket) Drain() uint64

func (*LocalBucket) Refill 

func (b *LocalBucket) Refill(n uint64)

func (*LocalBucket) Remaining 

func (b *LocalBucket) Remaining() uint64

func (*LocalBucket) TryConsume 

func (b *LocalBucket) TryConsume(n uint64) bool

type Member 

type Member struct {
	ID       string
	Addr     string
	Metadata map[string]string
}

type Option 

type Option func(*options)

func WithAdaptiveBorrow 

func WithAdaptiveBorrow(b bool) Option

func WithCMSDepth 

func WithCMSDepth(d uint32) Option

func WithCMSSeed 

func WithCMSSeed(s uint64) Option

func WithCMSWidth 

func WithCMSWidth(w uint32) Option

func WithClock 

func WithClock(c Clock) Option

func WithEMAAlpha 

func WithEMAAlpha(a float64) Option

func WithEvictionInterval 

func WithEvictionInterval(d time.Duration) Option

func WithEvictionPolicy 

func WithEvictionPolicy(p EvictionPolicy) Option

func WithGossipAddr 

func WithGossipAddr(addr string) Option

func WithGossipInterval 

func WithGossipInterval(d time.Duration) Option

func WithGzipCompression 

func WithGzipCompression(b bool) Option

func WithHeartbeatInterval 

func WithHeartbeatInterval(d time.Duration) Option

func WithHeartbeatTimeout 

func WithHeartbeatTimeout(d time.Duration) Option

func WithIdleTimeout 

func WithIdleTimeout(d time.Duration) Option

func WithInstanceID 

func WithInstanceID(id string) Option

func WithLeaseTTL 

func WithLeaseTTL(d time.Duration) Option

func WithLimit 

func WithLimit(n uint64) Option

func WithLogger 

func WithLogger(l *slog.Logger) Option

func WithMaxBorrow 

func WithMaxBorrow(n uint64) Option

func WithMaxGossipKeys 

func WithMaxGossipKeys(n int) Option

func WithMetrics 

func WithMetrics(m prometheus.Registerer) Option

func WithMinBorrow 

func WithMinBorrow(n uint64) Option

func WithPeerGRPCAddr 

func WithPeerGRPCAddr(addr string) Option

func WithPeerListen 

func WithPeerListen(addr string) Option

func WithPeerStrategy 

func WithPeerStrategy(ps PeerStrategy) Option

func WithPreBorrowEnabled 

func WithPreBorrowEnabled(b bool) Option

func WithPreBorrowThreshold 

func WithPreBorrowThreshold(f float64) Option

func WithProbeK 

func WithProbeK(k int) Option

func WithProbeMode 

func WithProbeMode(pm ProbeMode) Option

func WithProbeTimeout 

func WithProbeTimeout(d time.Duration) Option

func WithReservedMinimum 

func WithReservedMinimum(f float64) Option

func WithRouter 

func WithRouter(r routing.Router) Option

func WithWindow 

func WithWindow(d time.Duration) Option

func WithWindowType 

func WithWindowType(wt WindowType) Option

type PeerInfo 

type PeerInfo struct {
	ID       string
	Addr     string
	GRPCAddr string
}

type PeerStrategy 

type PeerStrategy int
const (
	Highest PeerStrategy = iota
	Random
)

type PoolState 

type PoolState struct {
	Remaining   uint64
	WindowStart int64
	Limit       uint64
	WindowMs    int64
}

type ProbeMode 

type ProbeMode int
const (
	Parallel ProbeMode = iota
	Sequential
)

type Window 

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

func NewWindow 

func NewWindow(windowType WindowType, windowSize time.Duration, limit uint64) *Window

func (*Window) EffectiveLimit 

func (w *Window) EffectiveLimit(elapsedMs, windowMs int64, prevCount, currCount uint64) uint64

func (*Window) Limit 

func (w *Window) Limit() uint64

func (*Window) NeedsReset 

func (w *Window) NeedsReset(nowUnixMs int64) bool

func (*Window) UpdateWindowStart 

func (w *Window) UpdateWindowStart(startMs int64)

func (*Window) WindowSize 

func (w *Window) WindowSize() time.Duration

func (*Window) WindowStartMs 

func (w *Window) WindowStartMs() int64

type WindowType 

type WindowType int
const (
	Fixed WindowType = iota
	Sliding
)

Source Files

View all Source files

Directories

Path Synopsis
cmd
krate-bench command
krate-example command
internal
borrow
clock
cluster
metrics
peer
peer/peerpb
sketch

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.