karnstack/byox-rate-limiter-go

Starter template (Go) for the Rate Limiter primitive on karnstack.

Five stages. Paper- and engineering-backed tests. You implement the interface; karnstack tells you what to read at each stage.

Prerequisites

mise is the only thing you need installed globally. It pins Go 1.26 for this repo and runs the stage tasks. If you do not want to install mise, the equivalent go test commands are documented under Without mise below.

Install mise:

curl https://mise.run | sh

Quick start

mise trust              # allow this repo's .mise.toml (one time)
mise install            # installs Go 1.26 if you do not have it
mise run stage 1        # runs the tests for stage 1 (they fail until you implement)

Open stage 1 on karnstack. Implement ratelimit/ratelimit.go until mise run stage 1 passes. Then move on:

mise run stage 2

mise run all runs every stage in one go. mise run bench runs the benchmarks used by stage 5.

Layout

.
├── .mise.toml                                       # toolchain + tasks
├── go.mod
└── ratelimit/
    ├── ratelimit.go                                 # you implement here
    ├── stage01_token_bucket_test.go
    ├── stage02_sliding_window_test.go
    ├── stage03_counter_test.go
    ├── stage04_burst_retry_after_test.go
    └── stage05_jitter_test.go

Tests live in the ratelimit package as *_test.go files (Go convention). The test files declare package ratelimit_test so they only see the exported API, which is the same surface a real consumer would use.

Stages

1. Token bucket (single-process)
2. Sliding-window counter behind a shared Limiter interface
3. Pluggable Counter backend (in-memory; Redis Lua documented)
4. Burst budget and Retry-After math
5. Client jitter strategies (full, equal, decorrelated)

Each stage is described on karnstack. Read first, then implement.

What you are building

A rate limiter with two interchangeable algorithms behind a single interface, a swappable counter backend so multi-process production wiring is a constructor change, exact and conservative Retry-After math, and the three client-side jitter strategies that prevent the next thundering-herd.

Papers and engineering references

• IETF (1999). RFC 2698: A Two Rate Three Color Marker.
• IETF (2022). RFC 9110: HTTP Semantics, section 10.2.3 Retry-After.
• Brooker, M. (2015). Exponential Backoff and Jitter. AWS Architecture Blog.
• Cloudflare (2017). How we built rate limiting capable of scaling to millions of domains.
• Tarjan, P. (2017). Scaling your API with rate limiters. Stripe Engineering Blog.

Without mise

If you do not want to install mise, ensure you have Go 1.26+ installed and run:

# Stage 1
go test -race -v -run '^TestStage01_' ./ratelimit/...

# Stage N (replace 01 with the zero-padded stage number)
go test -race -v -run '^TestStageNN_' ./ratelimit/...

# All stages
go test -race -v ./ratelimit/...

License

MIT. See LICENSE. Your fork is yours.