tokenrate

README

tokenrate

A library that rate limits Callers using the Rate Capabilities in their Tokens.

Summary

A rate limiter whose subject and limits come from an authenticated Token. It limits how fast each Caller (the Token's principal) may make requests, using the Rate Capabilities the Token carries, e.g. prefix:rate:50/1m. A Token may carry several, such as 1000/1m and 100000/24h, and every one applies. A deployment's own policy, such as a ceiling for everyone or an override for one Caller, is a function it supplies with WithResolver.

tokenrate depends on nothing beyond the standard library: no bascule, no JWT library, no HTTP framework. A service passes in the principal and capability strings after authenticating a request, and decides how to apply the decision it gets back.

Install

go get github.com/xmidt-org/tokenrate

Usage

Place the middleware after the one that validates the request's credentials. It must never run before: the limiter keeps state per principal, so an unauthenticated caller who could choose the principal could fill memory with one request per name. It checks the Caller, writes one warning header per Capability Warning, and answers 429 Too Many Requests (with Retry-After) or 403 Forbidden itself. The only service-specific part is finding the principal and capabilities in the request. A Token with no rate is unlimited unless a Resolver says otherwise:

limiter, err := tokenrate.New(
	tokenrate.WithPrefixes("prefix:rate:"),
)
if err != nil {
	return err
}

handler := tokenrate.Middleware{
	Limiter: limiter,
	Extract: func(r *http.Request) (string, []string) {
		token, ok := bascule.Get(r.Context())
		if !ok {
			return "", nil // unauthenticated: Unrestricted unless the Resolver says otherwise
		}

		caps, _ := bascule.GetCapabilities(token)
		return token.Principal(), caps
	},
}.Wrap(next)

// With bascule's own middleware, which stores the Token in the context:
protected := basculeMiddleware.Then(handler)

Outside HTTP, call limiter.Check(ctx, principal, capabilities) and apply the Decision yourself.

A Resolver has the final say over the rates a Token counts as carrying, so policy lives in your code, not in options. The library always enforces what it returns: no rates means no limit, the zero rate refuses, and an error denies the request. DefaultResolver handles malformed rates and the Window Bounds; call it from yours to keep that.

tokenrate.WithResolver(func(ctx context.Context, principal string, provided []tokenrate.Rate) ([]tokenrate.Rate, error) {
	if override, ok := overrides[principal]; ok {
		return override, nil // replaces whatever the Token says
	}

	rates, _ := tokenrate.DefaultResolver(ctx, principal, provided)
	if len(rates) == 0 {
		return nil, errors.New("no rate capability") // every Token must carry a rate
	}

	return append(rates, ceiling), nil // nobody exceeds the ceiling
})

See the examples for all three.

Try it

examples/server is a small service limited by tokenrate, with a table of API keys standing in for credential validation, and examples/client makes a burst of requests and prints each answer. Both are standard library only.

go run ./examples/server

$ go run ./examples/client -key key-abc -n 7
 1  200 OK
 2  200 OK
 3  200 OK
 4  200 OK
 5  200 OK
 6  429 Too Many Requests  Retry-After: 12s
 7  429 Too Many Requests  Retry-After: 12s

key-ghi carries a malformed rate alongside a valid one, so every answer carries a warning; key-def carries no rate and is Unrestricted.

• CONTEXT.md defines the terms.
• docs/design.md describes the behavior.
• ADR 0002 explains why a Caller is held to every rate that applies.
• ADR 0003 explains why the library always enforces and a Resolver decides policy.

Code of Conduct

This project and everyone participating in it are governed by the XMiDT Code Of Conduct. By participating, you agree to this Code.

Contributing

Refer to CONTRIBUTING.md.

Documentation

Overview

Package tokenrate limits how fast each Caller may make requests, using the Rate Capabilities carried by the Caller's authenticated Token.

tokenrate never sees the Token. After authenticating a request, a service passes its principal and capability strings to Limiter.Check, or lets Middleware do so, and applies the Decision it gets back. A Resolver lets the service adjust the rates first, for ceilings, overrides and the like. See CONTEXT.md for the terms used here and docs/design.md for the behavior.

Check must run only after the request's credentials have been validated. The Limiter keeps state per principal, so an attacker who can choose the principal could fill memory with one request per name.

Index

• Constants
• Variables
• type Decision
• type Extractor
• type Limiter
  • func New(opts ...Option) (*Limiter, error)
  • func (l *Limiter) Check(ctx context.Context, principal string, capabilities []string) Decision
• type Middleware
  • func (m Middleware) Wrap(next http.Handler) http.Handler
• type Option
  • func WithPrefixes(prefixes ...string) Option
  • func WithResolver(r Resolver) Option
• type Rate
  • func DefaultResolver(_ context.Context, _ string, provided []Rate) ([]Rate, error)
  • func ParseRate(s string) (Rate, error)
  • func (r Rate) IsZero() bool
  • func (r Rate) String() string
• type Reason
  • func (r Reason) String() string
• type Resolver
• type Warning
  • func (w Warning) String() string

Examples

• Limiter.Check
• Middleware
• WithResolver

Constants

const DefaultWarningHeader = "X-Webpa-Capability-Warning"

DefaultWarningHeader is the header Middleware writes Capability Warnings to unless Middleware.WarningHeader says otherwise.

const WarningMalformed = "malformed"

WarningMalformed is the Reason of a Warning about a Rate Capability whose rate cannot be parsed.

Variables

var (
	// ErrNoPrefixes is returned by New when no Capability Prefix was
	// configured.
	ErrNoPrefixes = errors.New("at least one capability prefix is required")

	// ErrEmptyPrefix is returned by New when a Capability Prefix is empty.
	ErrEmptyPrefix = errors.New("a capability prefix cannot be empty")

	// ErrInvalidRate is the Decision.Err when a Resolver returns a rate that
	// is neither valid nor the zero Rate, which denies the request.
	ErrInvalidRate = errors.New("resolver returned an invalid rate")
)

Errors from New and Check.

var ErrMalformedRate = errors.New("malformed rate")

ErrMalformedRate is returned by ParseRate when a rate cannot be parsed.

Types

type Decision

type Decision struct {
	// Allowed is whether the request may proceed.
	Allowed bool

	// Reason is why the check failed, or None.
	Reason Reason

	// Limits are the rates applied, shortest window first.  The request had
	// to fit every one.  It is empty when the Token is Unrestricted or the
	// Resolver denied the request.  It holds zero Rates, each reading back
	// as the client wrote it, when the Token counts as carrying them, e.g.
	// its only Rate Capabilities were malformed.  Otherwise the rates are
	// the Caller's allowances, which read back formatted.
	Limits []Rate

	// Limit is the rate that refused the request: when Reason is
	// RateExceeded, the one of Limits with the longest wait, or the zero
	// Rate when that is what refused.  It is the zero Rate otherwise.
	Limit Rate

	// RetryAfter is how long until the Caller has allowance for another
	// call at Limit.  It is set only when Reason is RateExceeded and Limit
	// is not zero; a zero limit never recovers by waiting.
	RetryAfter time.Duration

	// Warnings are Capability Warnings for the Caller.  They are returned
	// whether or not the request is Allowed.
	Warnings []Warning

	// Err is the Resolver's error when Reason is Denied, or ErrInvalidRate
	// if it returned an invalid rate.  It is for the service to log, not
	// for the Caller.
	Err error
}

Decision is the result of one Check.

type Extractor

type Extractor func(*http.Request) (principal string, capabilities []string)

Extractor returns the principal and capabilities of an authenticated request, however the service stores them, e.g. from the Token in the request's context. The principal must come from validated credentials, never from anything the client can choose freely. Returning an empty principal and no capabilities for an unauthenticated request leaves it Unrestricted, unless the Resolver returns rates for it or denies it.

type Limiter

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

Limiter decides, for each request, whether its Caller is within their Caller Rates. It is safe for concurrent use.

It keeps state for each Caller whose Token carries a rate, until twice the longest window after their last request: at most 48 hours under DefaultResolver. There is no cap on how many Callers it tracks, since forgetting a Caller early would give them a fresh allowance.

It needs no starting or stopping. A check that finds expired state starts a goroutine to sweep it, unless one is running, which exits when done.

func New

func New(opts ...Option) (*Limiter, error)

New creates a Limiter. WithPrefixes is required.

func (*Limiter) Check

func (l *Limiter) Check(ctx context.Context, principal string, capabilities []string) Decision

Check decides one request from principal, whose Token carries capabilities, and spends one call from each of the Caller's allowances. ctx is passed to the Resolver.

Example

package main

import (
	"context"
	"fmt"

	"github.com/xmidt-org/tokenrate"
)

func main() {
	limiter, err := tokenrate.New(tokenrate.WithPrefixes("prefix:rate:"))
	if err != nil {
		panic(err)
	}

	// Without HTTP, apply the Decision yourself.  Every rate in the Token
	// applies: this Caller may burst 1000, and make at most 100000 a day.
	d := limiter.Check(context.Background(), "abc", []string{"prefix:rate:1000/1m", "prefix:rate:100000/24h"})
	fmt.Println(d.Allowed, d.Limits, d.Reason)

	// A Token with no rate is Unrestricted, unless a Resolver says otherwise.
	d = limiter.Check(context.Background(), "def", nil)
	fmt.Println(d.Allowed, d.Limits, d.Reason)

}

Output:
true [1000/1m 100000/24h] none
true [] none

type Middleware

type Middleware struct {
	// Limiter decides each request.  Required.
	Limiter *Limiter

	// Extract finds the principal and capabilities in a request.  Required.
	Extract Extractor

	// WarningHeader is the header Capability Warnings are written to.  Empty
	// means DefaultWarningHeader.
	WarningHeader string

	// OmitWarnings, if set, writes no Capability Warnings.  Observe still
	// sees them in the Decision.
	OmitWarnings bool

	// Observe, if set, is called with every Decision, for metrics or
	// logging.  It runs before the response is written.
	Observe func(*http.Request, Decision)
}

Middleware applies a Limiter to HTTP requests. Place it after the middleware that validates the request's credentials. It needs the Token's principal and capabilities, and the Limiter keeps state per principal, so running it before authentication would let an attacker fill memory with one request per made-up principal.

For each request it checks the Caller and, unless OmitWarnings is set, adds one WarningHeader per Capability Warning, whether or not the request goes on. An allowed request is passed to the next handler. A rejected one gets 429 Too Many Requests, with Retry-After when waiting would help, or 403 Forbidden when the Resolver denied it, which Observe can log from Decision.Err.

Example

package main

import (
	"context"
	"errors"
	"fmt"
	"net/http"
	"net/http/httptest"
	"strings"

	"github.com/xmidt-org/tokenrate"
)

// A service's authentication middleware normally leaves the Token in the
// request's context.  This stand-in reads it from headers instead.
func principalAndCapabilities(r *http.Request) (string, []string) {
	return r.Header.Get("Principal"), strings.Split(r.Header.Get("Capabilities"), ",")
}

func main() {
	// Every Token must carry a rate; the Resolver denies the ones that don't.
	requireRate := func(ctx context.Context, principal string, provided []tokenrate.Rate) ([]tokenrate.Rate, error) {
		rates, _ := tokenrate.DefaultResolver(ctx, principal, provided)
		if len(rates) == 0 {
			return nil, errors.New("no rate capability")
		}

		return rates, nil
	}

	limiter, err := tokenrate.New(
		tokenrate.WithPrefixes("prefix:rate:"),
		tokenrate.WithResolver(requireRate),
	)
	if err != nil {
		panic(err)
	}

	handler := tokenrate.Middleware{
		Limiter: limiter,
		Extract: principalAndCapabilities,
	}.Wrap(http.HandlerFunc(func(w http.ResponseWriter, _ *http.Request) {
		w.WriteHeader(http.StatusNoContent)
	}))

	// The Token allows 2 calls per minute, so the third is refused.  Its
	// second capability is malformed, which every response warns about.
	for range 3 {
		r := httptest.NewRequest(http.MethodGet, "/", nil)
		r.Header.Set("Principal", "abc")
		r.Header.Set("Capabilities", "prefix:rate:2/1m,prefix:rate:5/0s")

		w := httptest.NewRecorder()
		handler.ServeHTTP(w, r)

		fmt.Println(w.Code, w.Header().Get("Retry-After"), w.Header().Get(tokenrate.DefaultWarningHeader))
	}

	// A Token with no rate is denied by the Resolver.
	r := httptest.NewRequest(http.MethodGet, "/", nil)
	r.Header.Set("Principal", "def")
	w := httptest.NewRecorder()
	handler.ServeHTTP(w, r)
	fmt.Println(w.Code)

}

Output:
204  malformed; kind=rate; cap="prefix:rate:5/0s"
204  malformed; kind=rate; cap="prefix:rate:5/0s"
429 30 malformed; kind=rate; cap="prefix:rate:5/0s"
403

func (Middleware) Wrap

func (m Middleware) Wrap(next http.Handler) http.Handler

Wrap returns a handler that checks each request with m before passing it to next. It panics if Limiter or Extract is nil, since the Middleware cannot work without them.

type Option

type Option interface {
	// contains filtered or unexported methods
}

Option configures a Limiter.

func WithPrefixes

func WithPrefixes(prefixes ...string) Option

WithPrefixes adds Capability Prefixes, which select the Rate Capabilities among a Token's capabilities. At least one is required.

A prefix is a plain string, matched exactly at the start of the capability, and whatever follows it is the rate. A capability that starts with no prefix is ignored; one that starts with several is read using the first configured. A prefix cannot be empty, since every capability would then count as a rate.

func WithResolver

func WithResolver(r Resolver) Option

WithResolver sets the Resolver, replacing DefaultResolver.

Example

package main

import (
	"context"
	"fmt"
	"time"

	"github.com/xmidt-org/tokenrate"
)

func main() {
	ceiling := tokenrate.Rate{Count: 500, Window: time.Minute}
	overrides := map[string][]tokenrate.Rate{
		"partner": {{Count: 10000, Window: time.Minute}},
	}

	// The Resolver has the final say over the rates a Token counts as
	// carrying, so the deployment's special cases live in one place.
	resolve := func(ctx context.Context, principal string, provided []tokenrate.Rate) ([]tokenrate.Rate, error) {
		if override, ok := overrides[principal]; ok {
			return override, nil // replaces whatever the Token says
		}

		rates, _ := tokenrate.DefaultResolver(ctx, principal, provided)
		if len(rates) == 0 {
			return nil, nil // a Token with no rate stays Unrestricted
		}

		return append(rates, ceiling), nil // nobody else exceeds the ceiling
	}

	limiter, err := tokenrate.New(
		tokenrate.WithPrefixes("prefix:rate:"),
		tokenrate.WithResolver(resolve),
	)
	if err != nil {
		panic(err)
	}

	ctx := context.Background()
	fmt.Println(limiter.Check(ctx, "abc", []string{"prefix:rate:1000/1m"}).Limits)
	fmt.Println(limiter.Check(ctx, "partner", []string{"prefix:rate:1000/1m"}).Limits)
	fmt.Println(limiter.Check(ctx, "def", nil).Limits)

}

Output:
[500/1m 1000/1m]
[10000/1m]
[]

type Rate

type Rate struct {
	Count  int
	Window time.Duration
	// contains filtered or unexported fields
}

Rate is a number of calls allowed per window. Its Burst is always Count.

A zero Rate, with no Count and no Window, allows nothing. It is how a Malformed Capability reaches a Resolver, and how a Resolver refuses a Token without denying the Caller.

func DefaultResolver

func DefaultResolver(_ context.Context, _ string, provided []Rate) ([]Rate, error)

DefaultResolver is the Resolver unless WithResolver says otherwise. It ignores a Malformed Capability when the Token has valid rates, so a typo in one rate doesn't void the others, and holds a Token whose rates are all malformed to those zero Rates, so a typo never means no limit.

It also holds each valid rate within the Window Bounds, one minute to 24 hours. A rate outside them is rescaled to the nearer bound at the same calls per second, rounded to the nearest call but at least one, so 100/1s is held as 6000/1m and 100/48h as 50/24h. This keeps a tiny window from churning state and a long one from allowing a huge Burst at once. A rescaled rate is no longer what the client wrote, so it reads back formatted.

It never returns an error.

func ParseRate

func ParseRate(s string) (Rate, error)

ParseRate parses a rate written <count>/<window>, e.g. 50/1m or 100/24h.

The count is a positive base-10 integer. The window is a positive Go duration (see time.ParseDuration). ParseRate checks only the grammar; a Limiter rescales rates whose window is outside its Window Bounds.

The Rate returned reads back as s from String. On failure it is zero.

func (Rate) IsZero

func (r Rate) IsZero() bool

IsZero reports whether r is a zero Rate, one with no Count and no Window, which allows nothing. The text it was parsed from does not matter.

func (Rate) String

func (r Rate) String() string

String returns the rate as the client wrote it, when r was parsed. A Rate built in code is formatted the way ParseRate reads it, e.g. 50/1m, 600/1h or 100/24h, or written as nothing at all if it is invalid.

type Reason

type Reason int

Reason says why a check failed.

const (
	// None means the check passed.
	None Reason = iota

	// RateExceeded means the Caller has no allowance left at Limit.
	RateExceeded

	// Denied means the Resolver returned an error, or an invalid rate.  The
	// error is in Err.
	Denied
)

func (Reason) String

func (r Reason) String() string

String returns the reason in kebab case, e.g. rate-exceeded.

type Resolver

type Resolver func(ctx context.Context, principal string, provided []Rate) ([]Rate, error)

A Resolver has the final say over the rates a Token counts as carrying. It is called on every check, outside any lock, with the request's context, the Token's principal and the rates of its Rate Capabilities, in Token order and as parsed. Each reads back as the client wrote it from String. A Malformed Capability arrives as a zero Rate, which allows nothing.

Whatever the Resolver returns is used instead, as if the Token had carried those rates: they are remembered for the Caller, and they are trusted, so they are used as returned. Returning no rates leaves the Token Unrestricted. Returning a zero Rate refuses the request as RateExceeded, with nothing remembered. Returning an error denies the request, whatever the reason: the error is returned in the Decision for the service to log, and is not shown to the Caller.

That covers the policy a deployment needs, without options for each case:

• A ceiling for every Caller: return append(provided, ceiling).
• An Override for one Caller: ignore provided and return the Override.
• Requiring a rate: return an error when provided is empty.
• Vouching for a Caller whose Token has no rate: return rates for it.
• Blocking a Caller: return an error.

The Limiter keeps state for every principal the Resolver returns rates for. Returning a rate that is neither valid nor zero denies the request with ErrInvalidRate.

type Warning

type Warning struct {
	// Reason is WarningMalformed.
	Reason string

	// Params are ordered key/value pairs giving the details.
	Params [][2]string
}

Warning is a Capability Warning: a note for the Caller describing a problem with their Token or request.

func (Warning) String

func (w Warning) String() string

String formats w the same way as bascule's Capability Warnings, e.g.

malformed; kind=rate; cap="prefix:rate:10/0s"

A value that is an HTTP token is written bare; anything else is quoted, escaping only '"' and '\'.