1# Configuring and Storing Key-Value Rate Limits
2
3## Rate Limit Structure
4
5All rate limits use a token-bucket model. The metaphor is that each limit is
6represented by a bucket which holds tokens. Each request removes some number of
7tokens from the bucket, or is denied if there aren't enough tokens to remove.
8Over time, new tokens are added to the bucket at a steady rate, until the bucket
9is full. The _burst_ parameter of a rate limit indicates the maximum capacity of
10a bucket: how many tokens can it hold before new ones stop being added.
11Therefore, this also indicates how many requests can be made in a single burst
12before a full bucket is completely emptied. The _count_ and _period_ parameters
13indicate the rate at which new tokens are added to a bucket: every period, count
14tokens will be added. Therefore, these also indicate the steady-state rate at
15which a client which has exhausted its quota can make requests: one token every
16(period / count) duration.
17
18## Default Limit Settings
19
20Each key directly corresponds to a `Name` enumeration as detailed in `//ratelimits/names.go`.
21The `Name` enum is used to identify the particular limit. The parameters of a
22default limit are the values that will be used for all buckets that do not have
23an explicit override (see below).
24
25```yaml
26NewRegistrationsPerIPAddress:
27 burst: 20
28 count: 20
29 period: 1s
30NewOrdersPerAccount:
31 burst: 300
32 count: 300
33 period: 180m
34```
35
36## Override Limit Settings
37
38Each override key represents a specific bucket, consisting of two elements:
39_name_ and _id_. The name here refers to the Name of the particular limit, while
40the id is a client identifier. The format of the id is dependent on the limit.
41For example, the id for 'NewRegistrationsPerIPAddress' is a subscriber IP
42address, while the id for 'NewOrdersPerAccount' is the subscriber's registration
43ID.
44
45```yaml
46NewRegistrationsPerIPAddress:10.0.0.2:
47 burst: 20
48 count: 40
49 period: 1s
50NewOrdersPerAccount:12345678:
51 burst: 300
52 count: 600
53 period: 180m
54```
55
56The above example overrides the default limits for specific subscribers. In both
57cases the count of requests per period are doubled, but the burst capacity is
58explicitly configured to match the default rate limit.
59
60### Id Formats in Limit Override Settings
61
62Id formats vary based on the `Name` enumeration. Below are examples for each
63format:
64
65#### ipAddress
66
67A valid IPv4 or IPv6 address.
68
69Examples:
70 - `NewRegistrationsPerIPAddress:10.0.0.1`
71 - `NewRegistrationsPerIPAddress:2001:0db8:0000:0000:0000:ff00:0042:8329`
72
73#### ipv6RangeCIDR
74
75A valid IPv6 range in CIDR notation with a /48 mask. A /48 range is typically
76assigned to a single subscriber.
77
78Example: `NewRegistrationsPerIPv6Range:2001:0db8:0000::/48`
79
80#### regId
81
82The registration ID of the account.
83
84Example: `NewOrdersPerAccount:12345678`
85
86#### regId:domain
87
88A combination of registration ID and domain, formatted 'regId:domain'.
89
90Example: `CertificatesPerDomainPerAccount:12345678:example.com`
91
92#### regId:fqdnSet
93
94A combination of registration ID and a comma-separated list of domain names,
95formatted 'regId:fqdnSet'.
96
97Example: `CertificatesPerFQDNSetPerAccount:12345678:example.com,example.org`
98
99## Bucket Key Definitions
100
101A bucket key is used to lookup the bucket for a given limit and
102subscriber. Bucket keys are formatted similarly to the overrides but with a
103slight difference: the limit Names do not carry the string form of each limit.
104Instead, they apply the `Name` enum equivalent for every limit.
105
106So, instead of:
107
108```
109NewOrdersPerAccount:12345678
110```
111
112The corresponding bucket key for regId 12345678 would look like this:
113
114```
1156:12345678
116```
117
118When loaded from a file, the keys for the default/override limits undergo the
119same interning process as the aforementioned subscriber bucket keys. This
120eliminates the need for redundant conversions when fetching each
121default/override limit.
122
123## How Limits are Applied
124
125Although rate limit buckets are configured in terms of tokens, we do not
126actually keep track of the number of tokens in each bucket. Instead, we track
127the Theoretical Arrival Time (TAT) at which the bucket will be full again. If
128the TAT is in the past, the bucket is full. If the TAT is in the future, some
129number of tokens have been spent and the bucket is slowly refilling. If the TAT
130is far enough in the future (specifically, more than `burst * (period / count)`)
131in the future), then the bucket is completely empty and requests will be denied.
132
133Additional terminology:
134
135 - **burst offset** is the duration of time it takes for a bucket to go from
136 empty to full (`burst * (period / count)`).
137 - **emission interval** is the interval at which tokens are added to a bucket
138 (`period / count`). This is also the steady-state rate at which requests can
139 be made without being denied even once the burst has been exhausted.
140 - **cost** is the number of tokens removed from a bucket for a single request.
141 - **cost increment** is the duration of time the TAT is advanced to account
142 for the cost of the request (`cost * emission interval`).
143
144For the purposes of this example, subscribers originating from a specific IPv4
145address are allowed 20 requests to the newFoo endpoint per second, with a
146maximum burst of 20 requests at any point-in-time, or:
147
148```yaml
149NewFoosPerIPAddress:172.23.45.22:
150 burst: 20
151 count: 20
152 period: 1s
153```
154
155A subscriber calls the newFoo endpoint for the first time with an IP address of
156172.23.45.22. Here's what happens:
157
1581. The subscriber's IP address is used to generate a bucket key in the form of
159 'NewFoosPerIPAddress:172.23.45.22'.
160
1612. The request is approved and the 'NewFoosPerIPAddress:172.23.45.22' bucket is
162 initialized with 19 tokens, as 1 token has been removed to account for the
163 cost of the current request. To accomplish this, the initial TAT is set to
164 the current time plus the _cost increment_ (which is 1/20th of a second if we
165 are limiting to 20 requests per second).
166
1673. Bucket 'NewFoosPerIPAddress:172.23.45.22':
168 - will reset to full in 50ms (1/20th of a second),
169 - will allow another newFoo request immediately,
170 - will allow between 1 and 19 more requests in the next 50ms,
171 - will reject the 20th request made in the next 50ms,
172 - and will allow 1 request every 50ms, indefinitely.
173
174The subscriber makes another request 5ms later:
175
1764. The TAT at bucket key 'NewFoosPerIPAddress:172.23.45.22' is compared against
177 the current time and the _burst offset_. The current time is greater than the
178 TAT minus the cost increment. Therefore, the request is approved.
179
1805. The TAT at bucket key 'NewFoosPerIPAddress:172.23.45.22' is advanced by the
181 cost increment to account for the cost of the request.
182
183The subscriber makes a total of 18 requests over the next 44ms:
184
1856. The current time is less than the TAT at bucket key
186 'NewFoosPerIPAddress:172.23.45.22' minus the burst offset, thus the request
187 is rejected.
188
189This mechanism allows for bursts of traffic but also ensures that the average
190rate of requests stays within the prescribed limits over time.
View as plain text