Boulder: Improve renewal rate limiting

[jsha]

Right now, we have an overall rate limit for "Certificates per Domain," and then an exemption for that limit for certificates that count as a renewal. However, this exemption only goes one way: If you've already hit the rate limit, you can still issue certificates that count as renewals. However, if you fill up the rate limit with renewals first, and then try to do new issuances, you will still be rate limited. This is undesirable because it means that large organizations sharing a registered domain (e.g. stanford.edu) have to coordinate new issuances and renewals across departments in order to get the most out of their available rate limit. In practice, it's difficult for departments to coordinate, and the organization's limit winds up continually used up by renewals, making new issuance impossible.

Currently, when checking the "Certificates per domain" limit, we query the issuedNames table for serial numbers of certificates that contain the registered domains in the certificate we are trying to issue, and count the unique serial numbers. Then, if that count returns a value over the threshold, we make a second query to the fqdnSets table to see if there was any previous certificate with the same exact same set of FQDNs (i.e., a renewal).

One approach would be to add a boolean field renewal to the issuedNames table that gets set at issuance time if a given certificate was a renewal. We would also add this field to an index. Currently the index on the table is:

KEY `reversedName_notBefore_Idx` (`reversedName`,`notBefore`)

We would change this to:

KEY `reversedName_renewal_notBefore_Idx` (`reversedName`,`renewal`, `notBefore`)

However, this would require running a database migration, which is somewhat time-consuming.

Another approach: After querying the issuedNames table for serial numbers, we can then query the fqdnSets table for the setHashes associated with those serial numbers, and de-duplicate across those setHashes. For instance, if we have find three serial numbers that match a given registered domain, but each of those serial numbers corresponds to the same setHash, that should only count as one issuance for the purpose of rate limiting, and two renewals (which are discounted). We would be querying by serial number without regard to issuance date, and there is already a UNIQUE KEY on the serial field of the fqdnSets table, so this would be a reasonably efficient query.

I'm leaning towards the second implementation option. Thoughts?

[jsha]

The tables look like this:

CREATE TABLE `issuedNames` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `reversedName` varchar(640) CHARACTER SET ascii NOT NULL,
  `notBefore` datetime NOT NULL,
  `serial` varchar(255) NOT NULL,
  PRIMARY KEY (`id`),
  KEY `reversedName_notBefore_Idx` (`reversedName`,`notBefore`)
) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8

CREATE TABLE `fqdnSets` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `setHash` binary(32) NOT NULL,
  `serial` varchar(255) NOT NULL,
  `issued` datetime NOT NULL,
  `expires` datetime NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `serial` (`serial`),
  KEY `setHash_issued_idx` (`setHash`,`issued`)
) ENGINE=InnoDB AUTO_INCREMENT=2 DEFAULT CHARSET=utf8

[rocketraman]

However, if you fill up the rate limit with renewals first, and then try to do new issuances, you will still be rate limited. This is undesirable because it means that large organizations sharing a registered domain (e.g. stanford.edu) have to coordinate new issuances and renewals across departments in order to get the most out of their available rate limit.

Furthermore, requiring the timing of renewals and new certificates to be coordinated implies using non-automated renewal processes.

[jsha]

Another approach: After querying the issuedNames table for serial numbers, we can then query the fqdnSets table for the setHashes associated with those serial numbers, and de-duplicate across those setHashes. For instance, if we have find three serial numbers that match a given registered domain, but each of those serial numbers corresponds to the same setHash, that should only count as one issuance for the purpose of rate limiting, and two renewals (which are discounted). We would be querying by serial number without regard to issuance date, and there is already a UNIQUE KEY on the serial field of the fqdnSets table, so this would be a reasonably efficient query.

On further consideration, this approach doesn't work: It would only discount duplicate certificates if the duplication happened within the time window for which CountCertificatesByNames was being called (generally 1 week). So it would correctly discount this scenario:

issuedNames:
reversedName     notBefore  serial
com.example      2017-06-20 123
com.example      2017-06-21 567
com.example      2017-06-22 789
com.example.www  2017-06-20 123
com.example.www  2017-06-21 567
com.example.www  2017-06-22 789

fqdnSets:
issued      serial setHash
2017-06-20  123    4EEC25932B8
2017-06-21  567    4EEC25932B8
2017-06-22  789    4EEC25932B8

Assuming setHash "4EEC25932B8" corresponds to the set of domains [example.com, www.example.com]. If someone then tried to issue a certificate for [blog.example.com] on 2017-06-22, the approach described above would say "there was 1 new (non-renewal) certificate issued for domains under example.com within the last week," which is what we want.

However, in a more typical scenario, where a renewal happens two months after the first issuance, this technique would not work:

issuedNames:
reversedName     notBefore  serial
com.example      2017-04-15 123
com.example      2017-06-21 567
com.example      2017-06-22 789
com.example.www  2017-04-15 123
com.example.www  2017-06-21 567
com.example.www  2017-06-22 789

fqdnSets:
issued      serial setHash
2017-06-20  123    4EEC25932B8
2017-06-21  567    4EEC25932B8
2017-06-22  789    4EEC25932B8

The algorithm above would still say "there was 1 new (non-renewal) certificate issued for domains under example.com within the last week," when really the answer we want is "0 new certificates," because both of the certificates issued this week were renewals.

An alternate approach: After querying with a time constraint in the issuedNames table, look up those serials in the fqdnSets table (with no issued constraint, because it's not relevant when we're looking up by serials). From that, get a list of setHashes. Then do a second query in the fqdnSets table to find all serials that match any setHash in the list. Then de-duplicate by setHash, keeping the earliest issuance for each setHash, and prune any issuances older than a week (i.e. the query window). The result is the count of new (non-renewal) issuances within the last week.

[cpu]

For the alternate approach: to clarify my own understanding in-ticket we need the second query of fqdnSets by setHashes because we might have found the first set of setHashes using a query based on an incomplete list of serial #s. That is, the first query to issuedNames to get serials for a reversedDomain might return an incomplete set of serials because of the notBefore constraint.

[rocketraman]

Great to see this merged and deployed. Will the docs at https://letsencrypt.org/docs/rate-limits/ be updated to match?

[cpu]

@rocketraman Yes. The change hasn't been activated in production yet but should be happening this week. Once that has been done I will post in the API announcements section of the community forum & submit a PR to update the rate limit documentation.

[MikeLund]

Hello, I see this was undone last month (reference), and ran into it today because of renewals.

Is there any new public issue related to re-enabling of this feature? I dug around open issues and couldn't find anything relating to it, so a link would be appreciated that I can follow. Thank you!

[jsha]

Thanks for the ping, @MikeLund. It looks like the status of this was living mostly in our heads, so I'm glad you reminded us to write it down. In our first pass at this, we tried to manage it without any database migrations, because those can be quite slow. Unfortunately, the current database schema isn't ideal. We thought we'd found a way to make it work efficiently, but it turns out our technique falls apart for domains that have many many subdomains with a certificate for each, and we started timing out those requests.

The current plan is that we need to add an "isRenewal" bit to the issuedNames table and adjust the indexes appropriately, so we can more easily discount renewals when checking the rate limit. This will require a migration, plus some code to start filling that bit, and a change to our rate limit queries so they check the bit. We probably won't backfill old data, since future data will converge pretty rapidly. We may want to split this into two changes: One to do the migration and start filling the field, then another to start checking the field.

Reopening this issue for tracking.

[rocketraman]

Any updates? Just ran into another situation in which a bunch of renewals made me unable to issue new certs due to the rate limit exemption.

[WouterTinus]

This issue is really frustrating our operations. We're running a SaaS and have deployed Let's Encrypt certificates on many of our customer environments, which are all running as sub domains under a single root, so renewals are happening regularly from a lot of different servers.

We had to create a backlog of websites that we still need to encrypt and manually check every once in a while if we can get a couple of new certificates, because it's unpredictable when we'll be able to get them and how many. Obviously, the more customers we get, the worse this problem will become.

If there are no near-term plans to fix this behavior, could I at least get an increase of the rate limit on our root domain? We've requested this through the official channel some time ago but have received no response.

[evlrbot]

+1

This issue is the number 1 reason I stopped using LetsEncypt certificates for the IoT platform I am developing.

As the original post points out, it makes scaling to a large number of certs under a single domain very difficult to manage, maybe even impossible in practice.

I think we got to around 50 certs before we regularly ran into issues creating new ones. NOT SCALABLE!

[jsha]

Thanks for the input. Reminder to all: Please don't post +1 comments. Instead use the thumbs-up emoji on the top post. We know this issue is important to a lot of people, and it's important to us too. At the moment we are prioritizing CT-related work, but we do intend to complete this work.

[TomCan]

I've learned here (https://community.letsencrypt.org/t/how-is-the-20-certificates-per-domain-per-week-counted/63639) that the rate-limit is not on a per-week basis, but a running average over the last 168 hours.

First off, it might be usefull to clarify that in the docs, as that makes planning for renewals very difficult, if not impossible once you hit a certain amount of certificates.

Now what I understand from this issue, is that changing the way that LE currenly processes renewals isn't that simple as it requires changes to the databasestructure. Would (for the time being) changing to using a fixed window (eg. mon-sun) to calculate the limit be an option? That would allow for better planning of renewals, not blocking the issuance of new certificates. I do realize that this might put some stress on the systems near the end of the period, as many renewals would take place on the same time.

[herrold]

If the calendar seven days of hours is causing operations problems, why not simply ask that it be set to a * five * day lookback in hours ?

Or that a test be done, to gather stats, and change it to * eight* day lookback in hours ?

Nothing beats committing code to gather real data answer questions, rather than speculating

[mhmeadows63]

Is there any schedule update for this issue?

[cpu]

I'm happy to share that this issue has been addressed by https://github.com/letsencrypt/boulder/commit/d0b6524fa238fb9b763d3f9fa8ce40bb4bf99dc1 and https://github.com/letsencrypt/boulder/commit/a04342e3a9f715cec6ed29bfcd1a15314faf922a .

Both feature flags were deployed to production yesterday and the order of renewals vs new certificate issuance should no longer affect the certificates per name rate limit.

Thanks for your patience everyone,