ratelimit

README

This package contains code for dealing with rate limiting. See the reference for more info.

Documentation

Index

• func ChooseTokenBucketCapacity(rateHz float64, window time.Duration) (capacity uint64, err error)
• func NewThrottledBucket(opThrottle Throttle, egressThrottle Throttle, wrapped gcs.Bucket) (b gcs.Bucket)
• func ThrottledReader(ctx context.Context, r io.Reader, throttle Throttle) io.Reader
• type MonotonicTime
• type Throttle
  • func NewThrottle(rateHz float64, capacity uint64) (t Throttle)
• type TokenBucket
  • func NewTokenBucket(rateHz float64, capacity uint64) (tb TokenBucket)

Functions

func ChooseTokenBucketCapacity

func ChooseTokenBucketCapacity(
	rateHz float64,
	window time.Duration) (capacity uint64, err error)

Choose a token bucket capacity that ensures that the action gated by the token bucket will be limited to within a few percent of `rateHz * window` for any window of the given size.

This is not be possible for all rates and windows. In that case, an error will be returned.

func NewThrottledBucket

func NewThrottledBucket(
	opThrottle Throttle,
	egressThrottle Throttle,
	wrapped gcs.Bucket) (b gcs.Bucket)

Create a bucket that limits the rate at which it calls the wrapped bucket using opThrottle, and limits the bandwidth with which it reads from the wrapped bucket using egressThrottle.

func ThrottledReader

func ThrottledReader(
	ctx context.Context,
	r io.Reader,
	throttle Throttle) io.Reader

Create a reader that limits the bandwidth of reads made from r according to the supplied throttler. Reads are assumed to be made under the supplied context.

Types

type MonotonicTime

type MonotonicTime time.Duration

A measurement of the amount of real time since some fixed epoch.

TokenBucket doesn't care about calendar time, time of day, etc. Unfortunately time.Time takes these things into account, and in particular time.Now() is not monotonic -- it may jump arbitrarily far into the future or past when the system's wall time is changed.

Instead we reckon in terms of a monotonic measurement of time elapsed since the bucket was initialized, and leave it up to the user to provide this. See SystemTimeTokenBucket for a convenience in doing so.

type Throttle

type Throttle interface {
	// Return the maximum number of tokens that can be requested in a call to
	// Wait.
	Capacity() (c uint64)

	// Acquire the given number of tokens from the underlying token bucket, then
	// sleep until when it says to wake. If the context is cancelled before then,
	// return early with an error.
	//
	// REQUIRES: tokens <= capacity
	Wait(ctx context.Context, tokens uint64) (err error)
}

A simple interface for limiting the rate of some event. Unlike TokenBucket, does not allow the user control over what time means.

Safe for concurrent access.

func NewThrottle

func NewThrottle(
	rateHz float64,
	capacity uint64) (t Throttle)

Create a throttle that uses time.Now to judge the time given to the underlying token bucket.

Be aware of the monotonicity issues. In particular:

• If the system clock jumps into the future, the throttle will let through a burst of traffic.

• If the system clock jumps into the past, it will halt all traffic for a potentially very long amount of time.

type TokenBucket

type TokenBucket interface {
	CheckInvariants()

	// Return the maximum number of tokens that the bucket can hold.
	Capacity() (c uint64)

	// Remove the specified number of tokens from the token bucket at the given
	// time. The user should wait until sleepUntil before proceeding in order to
	// obey the rate limit.
	//
	// REQUIRES: tokens <= Capacity()
	Remove(
		now MonotonicTime,
		tokens uint64) (sleepUntil MonotonicTime)
}

A bucket of tokens that refills at a specific rate up to a particular capacity. Users can remove tokens in sizes up to that capacity, can are told how long they should wait before proceeding.

If users cooperate by waiting to take whatever action they are rate limiting as told by the token bucket, the overall action rate will be limited to the token bucket's fill rate.

Not safe for concurrent access; requires external synchronization.

Cf. http://en.wikipedia.org/wiki/Token_bucket

func NewTokenBucket

func NewTokenBucket(
	rateHz float64,
	capacity uint64) (tb TokenBucket)

Create a token bucket that fills at the given rate in tokens per second, up to the given capacity. ChooseTokenBucketCapacity may help you decide on a capacity.

The token bucket starts full at time zero. If you would like it to start empty, call tb.Remove(0, capacity).

REQUIRES: rateHz > 0 REQUIRES: capacity > 0