ratelimits

package
v0.0.0-...-1d2dbbd Latest Latest
Warning

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

 Go to latest Published: Apr 30, 2024 License: MPL-2.0 Imports: 19 Imported by: 0

README

Configuring and Storing Key-Value Rate Limits

Rate Limit Structure

All rate limits use a token-bucket model. The metaphor is that each limit is represented by a bucket which holds tokens. Each request removes some number of tokens from the bucket, or is denied if there aren't enough tokens to remove. Over time, new tokens are added to the bucket at a steady rate, until the bucket is full. The burst parameter of a rate limit indicates the maximum capacity of a bucket: how many tokens can it hold before new ones stop being added. Therefore, this also indicates how many requests can be made in a single burst before a full bucket is completely emptied. The count and period parameters indicate the rate at which new tokens are added to a bucket: every period, count tokens will be added. Therefore, these also indicate the steady-state rate at which a client which has exhausted its quota can make requests: one token every (period / count) duration.

Default Limit Settings

Each key directly corresponds to a Name enumeration as detailed in //ratelimits/names.go. The Name enum is used to identify the particular limit. The parameters of a default limit are the values that will be used for all buckets that do not have an explicit override (see below).

NewRegistrationsPerIPAddress:
  burst: 20
  count: 20
  period: 1s
NewOrdersPerAccount:
  burst: 300
  count: 300
  period: 180m

Override Limit Settings

Each entry in the override list is a map, where the key is a limit name, corresponding to the Name enum of the limit, and the value is a set of overridden parameters. These parameters are applicable to a specific list of IDs included in each entry. It's important that the formatting of these IDs matches the ID format associated with their respective limit's Name. For more details on the relationship of ID format to limit Names, please refer to the documentation of each Name in the //ratelimits/names.go file or the ratelimits package documentation.

- NewRegistrationsPerIPAddress:
    burst: 20
    count: 40
    period: 1s
    ids:
      - 10.0.0.2
      - 10.0.0.5
- NewOrdersPerAccount:
    burst: 300
    count: 600
    period: 180m
    ids:
      - 12345678
      - 87654321

The above example overrides the default limits for specific subscribers. In both cases the count of requests per period are doubled, but the burst capacity is explicitly configured to match the default rate limit.

Id Formats in Limit Override Settings

Id formats vary based on the Name enumeration. Below are examples for each format:

ipAddress

A valid IPv4 or IPv6 address.

Examples:

  • 10.0.0.1
  • 2001:0db8:0000:0000:0000:ff00:0042:8329
ipv6RangeCIDR

A valid IPv6 range in CIDR notation with a /48 mask. A /48 range is typically assigned to a single subscriber.

Example: 2001:0db8:0000::/48

regId

An ACME account registration ID.

Example: 12345678

domain

A valid eTLD+1 domain name.

Example: example.com

fqdnSet

A comma-separated list of domain names.

Example: example.com,example.org

Bucket Key Definitions

A bucket key is used to lookup the bucket for a given limit and subscriber. Bucket keys are formatted similarly to the overrides but with a slight difference: the limit Names do not carry the string form of each limit. Instead, they apply the Name enum equivalent for every limit.

So, instead of:

NewOrdersPerAccount:12345678

The corresponding bucket key for regId 12345678 would look like this:

6:12345678

When loaded from a file, the keys for the default/override limits undergo the same interning process as the aforementioned subscriber bucket keys. This eliminates the need for redundant conversions when fetching each default/override limit.

How Limits are Applied

Although rate limit buckets are configured in terms of tokens, we do not actually keep track of the number of tokens in each bucket. Instead, we track the Theoretical Arrival Time (TAT) at which the bucket will be full again. If the TAT is in the past, the bucket is full. If the TAT is in the future, some number of tokens have been spent and the bucket is slowly refilling. If the TAT is far enough in the future (specifically, more than burst * (period / count)) in the future), then the bucket is completely empty and requests will be denied.

Additional terminology:

  • burst offset is the duration of time it takes for a bucket to go from empty to full (burst * (period / count)).
  • emission interval is the interval at which tokens are added to a bucket (period / count). This is also the steady-state rate at which requests can be made without being denied even once the burst has been exhausted.
  • cost is the number of tokens removed from a bucket for a single request.
  • cost increment is the duration of time the TAT is advanced to account for the cost of the request (cost * emission interval).

For the purposes of this example, subscribers originating from a specific IPv4 address are allowed 20 requests to the newFoo endpoint per second, with a maximum burst of 20 requests at any point-in-time, or:

- NewFoosPerIPAddress:
    burst: 20
    count: 20
    period: 1s
    ids:
      - 172.23.45.22

A subscriber calls the newFoo endpoint for the first time with an IP address of 172.23.45.22. Here's what happens:

  1. The subscriber's IP address is used to generate a bucket key in the form of 'NewFoosPerIPAddress:172.23.45.22'.

  2. The request is approved and the 'NewFoosPerIPAddress:172.23.45.22' bucket is initialized with 19 tokens, as 1 token has been removed to account for the cost of the current request. To accomplish this, the initial TAT is set to the current time plus the cost increment (which is 1/20th of a second if we are limiting to 20 requests per second).

  3. Bucket 'NewFoosPerIPAddress:172.23.45.22':

    • will reset to full in 50ms (1/20th of a second),
    • will allow another newFoo request immediately,
    • will allow between 1 and 19 more requests in the next 50ms,
    • will reject the 20th request made in the next 50ms,
    • and will allow 1 request every 50ms, indefinitely.

The subscriber makes another request 5ms later:

  1. The TAT at bucket key 'NewFoosPerIPAddress:172.23.45.22' is compared against the current time and the burst offset. The current time is greater than the TAT minus the cost increment. Therefore, the request is approved.

  2. The TAT at bucket key 'NewFoosPerIPAddress:172.23.45.22' is advanced by the cost increment to account for the cost of the request.

The subscriber makes a total of 18 requests over the next 44ms:

  1. The current time is less than the TAT at bucket key 'NewFoosPerIPAddress:172.23.45.22' minus the burst offset, thus the request is rejected.

This mechanism allows for bursts of traffic but also ensures that the average rate of requests stays within the prescribed limits over time.

Documentation

Index

Constants

View Source 
const (
	// Allowed is used for rate limit metrics, it's the value of the 'decision'
	// label when a request was allowed.
	Allowed = "allowed"

	// Denied is used for rate limit metrics, it's the value of the 'decision'
	// label when a request was denied.
	Denied = "denied"
)

Variables

View Source 
var ErrBucketNotFound = fmt.Errorf("bucket not found")

ErrBucketNotFound indicates that the bucket was not found.

View Source 
var ErrInvalidCost = fmt.Errorf("invalid cost, must be >= 0")

ErrInvalidCost indicates that the cost specified was < 0.

View Source 
var ErrInvalidCostOverLimit = fmt.Errorf("invalid cost, must be <= limit.Burst")

ErrInvalidCostOverLimit indicates that the cost specified was > limit.Burst.

Functions

func DomainsForRateLimiting 

func DomainsForRateLimiting(names []string) []string

DomainsForRateLimiting transforms a list of FQDNs into a list of eTLD+1's for the purpose of rate limiting. It also de-duplicates the output domains. Exact public suffix matches are included.

Types

type Decision 

type Decision struct {
	// Allowed is true if the bucket possessed enough capacity to allow the
	// request given the cost.
	Allowed bool

	// Remaining is the number of requests the client is allowed to make before
	// they're rate limited.
	Remaining int64

	// RetryIn is the duration the client MUST wait before they're allowed to
	// make a request.
	RetryIn time.Duration

	// ResetIn is the duration the bucket will take to refill to its maximum
	// capacity, assuming no further requests are made.
	ResetIn time.Duration
	// contains filtered or unexported fields
}

type Limiter 

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

Limiter provides a high-level interface for rate limiting requests by utilizing a leaky bucket-style approach.

func NewLimiter 

func NewLimiter(clk clock.Clock, source source, stats prometheus.Registerer) (*Limiter, error)

NewLimiter returns a new *Limiter. The provided source must be safe for concurrent use.

func (*Limiter) BatchRefund 

func (l *Limiter) BatchRefund(ctx context.Context, txns []Transaction) (*Decision, error)

BatchRefund attempts to refund all or some of the costs to the provided buckets' capacities. Non-existent buckets will NOT be initialized. The new bucket state is persisted to the underlying datastore, if applicable, before returning. Spend-only Transactions are assumed to be refundable. Check-only Transactions are never refunded. The following rules are applied to merge the Decisions for each Transaction into a single batch Decision:

  • Allowed is true if all Transactions where check is true were allowed,
  • RetryIn and ResetIn are the largest values of each across all Decisions,
  • Remaining is the smallest value of each across all Decisions, and
  • Decisions resulting from spend-only Transactions are never merged.

func (*Limiter) BatchSpend 

func (l *Limiter) BatchSpend(ctx context.Context, txns []Transaction) (*Decision, error)

BatchSpend attempts to deduct the costs from the provided buckets' capacities. If applicable, new bucket states are persisted to the underlying datastore before returning. Non-existent buckets will be initialized WITH the cost factored into the initial state. The following rules are applied to merge the Decisions for each Transaction into a single batch Decision:

  • Allowed is true if all Transactions where check is true were allowed,
  • RetryIn and ResetIn are the largest values of each across all Decisions,
  • Remaining is the smallest value of each across all Decisions, and
  • Decisions resulting from spend-only Transactions are never merged.

func (*Limiter) Check 

func (l *Limiter) Check(ctx context.Context, txn Transaction) (*Decision, error)

Check DOES NOT deduct the cost of the request from the provided bucket's capacity. The returned *Decision indicates whether the capacity exists to satisfy the cost and represents the hypothetical state of the bucket IF the cost WERE to be deducted. If no bucket exists it will NOT be created. No state is persisted to the underlying datastore.

func (*Limiter) Refund 

func (l *Limiter) Refund(ctx context.Context, txn Transaction) (*Decision, error)

Refund attempts to refund all of the cost to the capacity of the specified bucket. The returned *Decision indicates whether the refund was successful and represents the current state of the bucket. The new bucket state is persisted to the underlying datastore, if applicable, before returning. If no bucket exists it will NOT be created. Spend-only Transactions are assumed to be refundable. Check-only Transactions are never refunded.

Note: The amount refunded cannot cause the bucket to exceed its maximum capacity. Partial refunds are allowed and are considered successful. For instance, if a bucket has a maximum capacity of 10 and currently has 5 requests remaining, a refund request of 7 will result in the bucket reaching its maximum capacity of 10, not 12.

func (*Limiter) Reset 

func (l *Limiter) Reset(ctx context.Context, bucketKey string) error

Reset resets the specified bucket to its maximum capacity. The new bucket state is persisted to the underlying datastore before returning.

func (*Limiter) Spend 

func (l *Limiter) Spend(ctx context.Context, txn Transaction) (*Decision, error)

Spend attempts to deduct the cost from the provided bucket's capacity. The returned *Decision indicates whether the capacity existed to satisfy the cost and represents the current state of the bucket. If no bucket exists it WILL be created WITH the cost factored into its initial state. The new bucket state is persisted to the underlying datastore, if applicable, before returning.

type Name 

type Name int

Name is an enumeration of all rate limit names. It is used to intern rate limit names as strings and to provide a type-safe way to refer to rate limits.

IMPORTANT: If you add a new limit Name, you MUST add:

  • it to the nameToString mapping,
  • an entry for it in the validateIdForName(), and
  • provide the appropriate constructors in bucket.go.
const (
	// Unknown is the zero value of Name and is used to indicate an unknown
	// limit name.
	Unknown Name = iota

	// NewRegistrationsPerIPAddress uses bucket key 'enum:ipAddress'.
	NewRegistrationsPerIPAddress

	// NewRegistrationsPerIPv6Range uses bucket key 'enum:ipv6rangeCIDR'. The
	// address range must be a /48. RFC 3177, which was published in 2001,
	// advised operators to allocate a /48 block of IPv6 addresses for most end
	// sites. RFC 6177, which was published in 2011 and obsoletes RFC 3177,
	// advises allocating a smaller /56 block. We've chosen to use the larger
	// /48 block for our IPv6 rate limiting. See:
	//   1. https://tools.ietf.org/html/rfc3177#section-3
	//   2. https://datatracker.ietf.org/doc/html/rfc6177#section-2
	NewRegistrationsPerIPv6Range

	// NewOrdersPerAccount uses bucket key 'enum:regId'.
	NewOrdersPerAccount

	// FailedAuthorizationsPerDomainPerAccount uses two different bucket keys
	// depending on the context:
	//  - When referenced in an overrides file: uses bucket key 'enum:regId',
	//    where regId is the ACME registration Id of the account.
	//  - When referenced in a transaction: uses bucket key 'enum:regId:domain',
	//    where regId is the ACME registration Id of the account and domain is a
	//    domain name in the certificate.
	FailedAuthorizationsPerDomainPerAccount

	// CertificatesPerDomain uses bucket key 'enum:domain', where domain is a
	// domain name in the certificate.
	CertificatesPerDomain

	// CertificatesPerDomainPerAccount uses two different bucket keys depending
	// on the context:
	//  - When referenced in an overrides file: uses bucket key 'enum:regId',
	//    where regId is the ACME registration Id of the account.
	//  - When referenced in a transaction: uses bucket key 'enum:regId:domain',
	//    where regId is the ACME registration Id of the account and domain is a
	//    domain name in the certificate.
	//
	// When overrides to the CertificatesPerDomainPerAccount are configured for a
	// subscriber, the cost:
	//   - MUST be consumed from each CertificatesPerDomainPerAccount bucket and
	//   - SHOULD be consumed from each CertificatesPerDomain bucket, if possible.
	CertificatesPerDomainPerAccount

	// CertificatesPerFQDNSet uses bucket key 'enum:fqdnSet', where fqdnSet is a
	// hashed set of unique eTLD+1 domain names in the certificate.
	//
	// Note: When this is referenced in an overrides file, the fqdnSet MUST be
	// passed as a comma-separated list of domain names.
	CertificatesPerFQDNSet
)

func (Name) EnumString 

func (n Name) EnumString() string

EnumString returns the string representation of the Name enumeration.

func (Name) String 

func (n Name) String() string

String returns the string representation of the Name. It allows Name to satisfy the fmt.Stringer interface.

type RedisSource 

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

RedisSource is a ratelimits source backed by sharded Redis.

func NewRedisSource 

func NewRedisSource(client *redis.Ring, clk clock.Clock, stats prometheus.Registerer) *RedisSource

NewRedisSource returns a new Redis backed source using the provided *redis.Ring client.

func (*RedisSource) BatchGet 

func (r *RedisSource) BatchGet(ctx context.Context, bucketKeys []string) (map[string]time.Time, error)

BatchGet retrieves the TATs at the specified bucketKeys using a pipelined Redis Transaction in order to reduce the number of round-trips to each Redis shard. An error is returned if the operation failed and nil otherwise. If a bucketKey does not exist, it WILL NOT be included in the returned map.

func (*RedisSource) BatchSet 

func (r *RedisSource) BatchSet(ctx context.Context, buckets map[string]time.Time) error

BatchSet stores TATs at the specified bucketKeys using a pipelined Redis Transaction in order to reduce the number of round-trips to each Redis shard. An error is returned if the operation failed and nil otherwise.

func (*RedisSource) Delete 

func (r *RedisSource) Delete(ctx context.Context, bucketKey string) error

Delete deletes the TAT at the specified bucketKey ('name:id'). It returns an error if the operation failed and nil otherwise. A nil return value does not indicate that the bucketKey existed.

func (*RedisSource) Get 

func (r *RedisSource) Get(ctx context.Context, bucketKey string) (time.Time, error)

Get retrieves the TAT at the specified bucketKey. An error is returned if the operation failed and nil otherwise. If the bucketKey does not exist, ErrBucketNotFound is returned.

func (*RedisSource) Ping 

func (r *RedisSource) Ping(ctx context.Context) error

Ping checks that each shard of the *redis.Ring is reachable using the PING command. It returns an error if any shard is unreachable and nil otherwise.

type Transaction 

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

Transaction represents a single rate limit operation. It includes a bucketKey, which combines the specific rate limit enum with a unique identifier to form the key where the state of the "bucket" can be referenced or stored by the Limiter, the rate limit being enforced, a cost which MUST be >= 0, and check/spend fields, which indicate how the Transaction should be processed. The following are acceptable combinations of check/spend:

  • check-and-spend: when check and spend are both true, the cost will be checked against the bucket's capacity and spent/refunded, when possible.
  • check-only: when only check is true, the cost will be checked against the bucket's capacity, but will never be spent/refunded.
  • spend-only: when only spend is true, spending is best-effort. Regardless of the bucket's capacity, the transaction will be considered "allowed".
  • allow-only: when neither check nor spend are true, the transaction will be considered "allowed" regardless of the bucket's capacity. This is useful for limits that are disabled.

type TransactionBuilder 

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

TransactionBuilder is used to build Transactions for various rate limits. Each rate limit has a corresponding method that returns a Transaction for that limit. Call NewTransactionBuilder to create a new *TransactionBuilder.

func NewTransactionBuilder 

func NewTransactionBuilder(defaults, overrides string) (*TransactionBuilder, error)

NewTransactionBuilder returns a new *TransactionBuilder. The provided defaults and overrides paths are expected to be paths to YAML files that contain the default and override limits, respectively. Overrides is optional, defaults is required.

func (*TransactionBuilder) CertificatesPerDomainTransactions 

func (builder *TransactionBuilder) CertificatesPerDomainTransactions(regId int64, orderDomains []string, maxNames int) ([]Transaction, error)

CertificatesPerDomainTransactions returns a slice of Transactions for the provided order domain names. An error is returned if any of the order domain names are invalid. When a CertificatesPerDomainPerAccount override is configured, two types of Transactions are returned:

  • A spend-only Transaction for each per domain bucket. Spend-only transactions will not be denied if the bucket lacks the capacity to satisfy the cost.
  • A check-and-spend Transaction for each per account per domain bucket. Check- and-spend transactions will be denied if the bucket lacks the capacity to satisfy the cost.

When a CertificatesPerDomainPerAccount override is not configured, a check- and-spend Transaction is returned for each per domain bucket.

func (*TransactionBuilder) CertificatesPerFQDNSetTransaction 

func (builder *TransactionBuilder) CertificatesPerFQDNSetTransaction(orderNames []string) (Transaction, error)

CertificatesPerFQDNSetTransaction returns a Transaction for the provided order domain names.

func (*TransactionBuilder) FailedAuthorizationsPerDomainPerAccountCheckOnlyTransactions 

func (builder *TransactionBuilder) FailedAuthorizationsPerDomainPerAccountCheckOnlyTransactions(regId int64, orderDomains []string, maxNames int) ([]Transaction, error)

FailedAuthorizationsPerDomainPerAccountCheckOnlyTransactions returns a slice of Transactions for the provided order domain names. An error is returned if any of the order domain names are invalid. This method should be used for checking capacity, before allowing more authorizations to be created.

func (*TransactionBuilder) FailedAuthorizationsPerDomainPerAccountSpendOnlyTransaction 

func (builder *TransactionBuilder) FailedAuthorizationsPerDomainPerAccountSpendOnlyTransaction(regId int64, orderDomain string) (Transaction, error)

FailedAuthorizationsPerDomainPerAccountSpendOnlyTransaction returns a spend- only Transaction for the provided order domain name. An error is returned if the order domain name is invalid. This method should be used for spending capacity, as a result of a failed authorization.

func (*TransactionBuilder) OrdersPerAccountTransaction 

func (builder *TransactionBuilder) OrdersPerAccountTransaction(regId int64) (Transaction, error)

OrdersPerAccountTransaction returns a Transaction for the NewOrdersPerAccount limit for the provided ACME registration Id.

func (*TransactionBuilder) RegistrationsPerIPAddressTransaction 

func (builder *TransactionBuilder) RegistrationsPerIPAddressTransaction(ip net.IP) (Transaction, error)

RegistrationsPerIPAddressTransaction returns a Transaction for the NewRegistrationsPerIPAddress limit for the provided IP address.

func (*TransactionBuilder) RegistrationsPerIPv6RangeTransaction 

func (builder *TransactionBuilder) RegistrationsPerIPv6RangeTransaction(ip net.IP) (Transaction, error)

RegistrationsPerIPv6RangeTransaction returns a Transaction for the NewRegistrationsPerIPv6Range limit for the /48 IPv6 range which contains the provided IPv6 address.

Source Files

View all Source files

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.