pacemaker

package module
v0.7.3 Latest Latest
Warning

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

 Go to latest Published: Dec 11, 2022 License: MIT Imports: 10 Imported by: 0

README

PaceMaker

Rate limit library

Implemented rate limits:

Fixed window rate limit

Fixed window limits—such as 3,000 requests per hour or 10 requests per day—are easy to state, but they are subject to have spikes at the edges of the window, as available quota resets. Consider, for example, a limit of 3,000 requests per hour, which still allows for a spike of all 3,000 requests to be made in the first minute of the hour, which might overwhelm the service.

Starts counting time windows when the first request arrives.

Example

Fixed truncated window rate limit

Same as Fixed Window rate limit but truncates the rate limit window to the rate interval configured in order to adjust to real time intervals passing. E.g:

  1. Rate limit interval is configured for new windows every 10 seconds
  2. First request arrives at 2022-02-05 10:23:23
  3. Current rate limit window: from 2022-02-05 10:23:20 to 2022-02-05 10:23:30

Example

Fixed window with token bucket variant (token refill at window's rate)

Works as any other fixed-window rate limiter. However, the meaning of 'capacity' of the inner fixed-window rate limiter changes from the total amount of requests that can be made to the total amount of tokens (points) that can be spent in that same window. This variant is particularly useful, for instance, when working on the crypto game field as many crypto exchanges employ this strategy. Take for example, binance.

Example

You can refer to google architecture docs to read more about rate limits.

Storages

  • Memory. Useful for non-distributed applications and testing purposes. Do not use on production unless you deliberately don't care about keeping rate limit state.
  • Redis. github.com/go-redis/redis is employed as Redis client
TODO:
  • Token bucket rate limit
  • Leaky bucket rate limit
  • Composite rate limit
  • Service rate limit

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrRateLimitExceeded         = errors.New("rate limit exceeded")
	ErrTokensGreaterThanCapacity = errors.New("tokens are greater than capacity")
	ErrCannotLoadScript          = errors.New("cannot load LUA script")
)
View Source 
var (
	ScriptHash = Sha1Hash(script)
)

Functions

func AtLeast added in v0.5.1 

func AtLeast(n int64) func(int64) int64

func Sha1Hash added in v0.6.0 

func Sha1Hash(s string) string

func TimeGTE added in v0.7.1 

func TimeGTE(from time.Time, target time.Time) bool

TimeGTE returns true if `target` is greater than or equals `from`

Types

type FixedTruncatedWindowArgs 

type FixedTruncatedWindowArgs struct {
	Capacity int64
	Rate     Rate

	Clock clock

	DB fixedTruncatedWindowStorage
}

type FixedTruncatedWindowMemoryStorage added in v0.1.0 

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

FixedTruncatedWindowMemoryStorage is an in-memory storage for the rate limit state. Preferred option when testing and working with standalone instances of your program and do not care about it restarting and not being exactly compliant with the state of rate limits at the server

func NewFixedTruncatedWindowMemoryStorage added in v0.1.0 

func NewFixedTruncatedWindowMemoryStorage() *FixedTruncatedWindowMemoryStorage

NewFixedTruncatedWindowMemoryStorage returns a new instance of FixedTruncatedWindowMemoryStorage

func (*FixedTruncatedWindowMemoryStorage) Get added in v0.5.1 

func (s *FixedTruncatedWindowMemoryStorage) Get(
	ctx context.Context,
	window time.Time,
) (int64, error)

func (*FixedTruncatedWindowMemoryStorage) Inc added in v0.1.0 

func (s *FixedTruncatedWindowMemoryStorage) Inc(
	ctx context.Context,
	args FixedWindowIncArgs,
) (int64, error)

type FixedTruncatedWindowRateLimiter 

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

FixedTruncatedWindowRateLimiter limits how many requests check be make in a time window. This window is calculated by truncating the first request's time of to the limit rate in order to adjust to real time passing. E.g: First request time: 2022-02-05 10:23:23 Rate limit interval: new window every 10 seconds First request window: from 2022-02-05 10:23:20 to 2022-02-05 10:23:30

func NewFixedTruncatedWindowRateLimiter 

func NewFixedTruncatedWindowRateLimiter(
	args FixedTruncatedWindowArgs,
) *FixedTruncatedWindowRateLimiter

NewFixedTruncatedWindowRateLimiter returns a new instance of FixedTruncatedWindowRateLimiter from struct of args

func (*FixedTruncatedWindowRateLimiter) Check 

func (l *FixedTruncatedWindowRateLimiter) Check(ctx context.Context) (Result, error)

Check return how many free slots remain without increasing the token counter. This testMethod is typically used to assert there are available requests prior try an increase the counter

func (*FixedTruncatedWindowRateLimiter) Dump added in v0.7.0 

func (l *FixedTruncatedWindowRateLimiter) Dump(ctx context.Context) (r Result, err error)

func (*FixedTruncatedWindowRateLimiter) Try added in v0.5.1 

func (l *FixedTruncatedWindowRateLimiter) Try(ctx context.Context) (Result, error)

Try returns how much time to wait to perform the request and an error indicating whether the rate limit was exhausted or any kind or error happened when updating the backend. Typically, you would do

ttw, err := limiter.Try(ctx) 

if errors.Is(ErrRateLimitExceeded) {
		<-time.After(ttw) // Wait, or enqueue your request
}

type FixedWindowArgs added in v0.1.0 

type FixedWindowArgs struct {
	Capacity int64
	Rate     Rate
	Clock    clock
	DB       fixedWindowStorage
}

type FixedWindowIncArgs added in v0.6.0 

type FixedWindowIncArgs struct {
	Window   time.Time
	TTL      time.Duration
	Tokens   int64
	Capacity int64
}

type FixedWindowMemoryStorage added in v0.1.0 

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

FixedWindowMemoryStorage is an in-memory storage for the rate limit state. Preferred option when testing and working with standalone instances of your program and do not care about it restarting and not being exactly compliant with servers rate limits

func NewFixedWindowMemoryStorage added in v0.1.0 

func NewFixedWindowMemoryStorage() *FixedWindowMemoryStorage

NewFixedWindowMemoryStorage returns a new instance of FixedWindowMemoryStorage

func (*FixedWindowMemoryStorage) Get added in v0.5.1 

func (s *FixedWindowMemoryStorage) Get(ctx context.Context, window time.Time) (int64, error)

func (*FixedWindowMemoryStorage) Inc added in v0.1.0 

func (s *FixedWindowMemoryStorage) Inc(
	ctx context.Context,
	args FixedWindowIncArgs,
) (int64, error)

type FixedWindowRateLimiter added in v0.1.0 

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

FixedWindowRateLimiter limits how many requests check be make in a time window. This window is calculated by considering the start of the window the exact same moment the first request came. E.g: First request time: 2022-02-05 10:23:23 Rate limit interval: new window every 10 seconds First request window: from 2022-02-05 10:23:23 to 2022-02-05 10:23:33 FIXME: This rate limiter is not consistent across restarts, as there are no

func NewFixedWindowRateLimiter added in v0.1.0 

func NewFixedWindowRateLimiter(args FixedWindowArgs) *FixedWindowRateLimiter

NewFixedWindowRateLimiter returns a new instance of FixedWindowRateLimiter from struct of args

func (*FixedWindowRateLimiter) Check added in v0.1.0 

func (l *FixedWindowRateLimiter) Check(ctx context.Context) (Result, error)

func (*FixedWindowRateLimiter) Dump added in v0.7.0 

func (l *FixedWindowRateLimiter) Dump(ctx context.Context) (Result, error)

Dump returns the state of rate limit according storage. It never returns a ErrRateLimit error.

func (*FixedWindowRateLimiter) Try added in v0.5.1 

func (l *FixedWindowRateLimiter) Try(ctx context.Context) (Result, error)

type FixedWindowRedisStorage added in v0.3.0 

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

func NewFixedWindowRedisStorage added in v0.3.0 

func NewFixedWindowRedisStorage(
	cli *redis.Client,
	opts FixedWindowRedisStorageOpts,
) FixedWindowRedisStorage

func (FixedWindowRedisStorage) Get added in v0.5.1 

func (s FixedWindowRedisStorage) Get(
	ctx context.Context,
	window time.Time,
) (counter int64, err error)

func (FixedWindowRedisStorage) Inc added in v0.3.0 

func (s FixedWindowRedisStorage) Inc(
	ctx context.Context,
	args FixedWindowIncArgs,
) (counter int64, err error)

Inc will increase, if there is room to, the rate limiting counter for the bucket specified by window argument.

func (FixedWindowRedisStorage) Load added in v0.6.0 

func (s FixedWindowRedisStorage) Load(ctx context.Context) error

Load will prepare this storage to be ready for usage, such as load into redis needed lua scripts. Calling to this method is not mandatory, but highly recommended.

type FixedWindowRedisStorageOpts added in v0.3.0 

type FixedWindowRedisStorageOpts struct {
	Prefix string
}

type Rate 

type Rate struct {
	Amount int
	Unit   time.Duration
}

func (Rate) Duration 

func (r Rate) Duration() time.Duration

func (Rate) TruncateDuration added in v0.7.2 

func (r Rate) TruncateDuration() time.Duration

TruncateDuration returns, for windows smaller than a minute, the sole unit as they scape the sexagesimal counting mode. Otherwise, return the product of amount and unit to produce the full rate limit window.

type RealClock 

type RealClock struct{}

func NewClock 

func NewClock() *RealClock

func (RealClock) Now 

func (c RealClock) Now() time.Time

type Result added in v0.6.0 

type Result struct {
	TimeToWait time.Duration
	FreeSlots  int64
}

type TestClock 

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

func NewMockClock 

func NewMockClock(startAt time.Time) *TestClock

func (*TestClock) Forward 

func (c *TestClock) Forward(duration time.Duration)

func (TestClock) Now 

func (c TestClock) Now() time.Time

type TokenFixedWindowRateLimiter added in v0.2.0 

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

TokenFixedWindowRateLimiter behaves the same as a fixed-window rate limiter. However, it allows requests to hold an arbitrary weight, consuming as much as weight from the capacity of the inner fixed-window rate limiter. When using this rate limiter, keep in mind that the `capacity` attribute of the inner rate limit means the total tokens usable for every window, and not the total amount of requests doable on that window.

func NewTokenFixedWindowRateLimiter added in v0.2.0 

func NewTokenFixedWindowRateLimiter(inner fixedWindowRateLimiter) TokenFixedWindowRateLimiter

NewTokenFixedWindowRateLimiter returns a new instance of TokenFixedWindowRateLimiter by receiving an already created fixed-window rate limiter as argument.

func (*TokenFixedWindowRateLimiter) Check added in v0.2.0 

func (l *TokenFixedWindowRateLimiter) Check(ctx context.Context, tokens int64) (Result, error)

Check returns whether further requests check be made by returning the number of free slots

func (*TokenFixedWindowRateLimiter) Dump added in v0.7.0 

func (l *TokenFixedWindowRateLimiter) Dump(ctx context.Context) (Result, error)

Dump returns the actual rate limit state according to data stores

func (*TokenFixedWindowRateLimiter) Try added in v0.5.1 

func (l *TokenFixedWindowRateLimiter) Try(ctx context.Context, tokens int64) (Result, error)

Try returns the amount of time to wait when the rate limit has been exceeded. The total amount of tokens consumed by the requests check be given as argument

Source Files

View all Source files

Directories

Path Synopsis
examples
fixed_window
fixed_window_token_bucket_variant
fixed_window_truncated
it module

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.