Handle rate limit headers more reliably

[jcharaoui]

As one of the maintainers of https://support.torproject.org, I'm looking into options for incorporating dead link checking into our CI pipeline, and this project seems very promising so far.

I've hit a snag however related to crawling links specifically to gitlab.torproject.org, our self-hosted GitLab instance: it seems like when lychee hits that host it immediately goes into retry-backoff mode with a 1 minute delay between each request, which pretty much kills the performance of the whole process. If I exclude all gitlab.torproject.org links (and other links that redirect to that domain), it goes through something like 16 thousands links in a matter of seconds.

Given a bogus test.html file containing a small sample of such links:

<a href="https://gitlab.torproject.org/">foo</a>
<a href="https://gitlab.torproject.org/tpo/applications/vpn/-/issues/new">bar</a>
<a href="https://gitlab.torproject.org/tpo/applications/vpn-leak-test/-/blob/main/app/src/main/java/org/torproject/vpnleaktest/tests/DeviceIDsTest.kt#L235">baz</a>

Running lychee on this file takes several minutes:

$ podman run --init --rm -it -v $PWD:/app --workdir /app docker.io/lycheeverse/lychee:master test.html -vvv --max-concurrency 1
   [DEBUG] Following redirect to https://gitlab.torproject.org/tpo/team
    [WARN] Host gitlab.torproject.org sent an unexpectedly big rate limit backoff duration of 584542046years 1month 2days 15h 52m 15s 615ms. Capping the duration to 1m instead.
   [DEBUG] Host gitlab.torproject.org applying backoff delay of 60000ms due to previous rate limiting or errors
     [200] https://gitlab.torproject.org/ | Redirect: Followed 1 redirect resolving to the final status of: OK. Redirects: https://gitlab.torproject.org/ --[302]--> https://gitlab.torproject.org/tpo/team
   [DEBUG] Following redirect to https://gitlab.torproject.org/users/sign_in
    [WARN] Host gitlab.torproject.org sent an unexpectedly big rate limit backoff duration of 584542046years 1month 2days 15h 52m 15s 615ms. Capping the duration to 1m instead.
   [DEBUG] Host gitlab.torproject.org applying backoff delay of 60000ms due to previous rate limiting or errors
     [200] https://gitlab.torproject.org/tpo/applications/vpn/-/issues/new | Redirect: Followed 1 redirect resolving to the final status of: OK. Redirects: https://gitlab.torproject.org/tpo/applications/vpn/-/issues/new --[302]--> https://gitlab.torproject.org/users/sign_in
    [WARN] Host gitlab.torproject.org sent an unexpectedly big rate limit backoff duration of 584542046years 1month 2days 15h 52m 15s 615ms. Capping the duration to 1m instead.
     [200] https://gitlab.torproject.org/tpo/applications/vpn-leak-test/-/blob/main/app/src/main/java/org/torproject/vpnleaktest/tests/DeviceIDsTest.kt#L235
🔍 3 Total (in 2m 1s) ✅ 1 OK 🚫 0 Errors 🔀 2 Redirects

I'm not really sure what's happening here: where is this "584542046years 1month 2days 15h 52m 15s 615ms" duration coming from? From looking into the code a little but, it seems related to a Retry-After HTTP header, but as far as I can tell, no such header is actually sent from this host. It also mentions "previous rate limiting errors" but it's unclear where these errors were encountered, eg. is the 302 redirect being considered an error here?

I've tried running with RUST_LOG=trace hoping I could look at the actual HTTP headers sent and received by lynchee but I couldn't decipher those logs...

[thomas-zahner]

Thank you for reporting, this change hasn't been released yet and I'm glad that you are using our master version. It's seems like we made wrong or overly-generic assumptions on the rate limit headers.

The problem is that this is not standardised yet and many websites use different approaches to rate limiting, while potentially reusing
the same header names for different purposes.

These assumptions seem to be wrong in your case with these headers sent by GitLab

ratelimit-limit: 60
ratelimit-name: throttle_unauthenticated_web
ratelimit-observed: 10
ratelimit-remaining: 3590
ratelimit-reset: 1770116400

If I run lychee on your provided HTML input in debug mode I lychee even crashes:

thread 'tokio-runtime-worker' (90227) panicked at lychee-lib/src/ratelimit/host/host.rs:260:31:
attempt to subtract with overflow
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
Error: Task failed to execute to completion

Caused by:
    task 52 panicked with message "attempt to subtract with overflow"

caused by this line. In release mode we should get an overflow instead.

let usage_ratio = (limit - remaining) as f64 / limit as f64;

Maybe we can handle this with better error handling. Alternatively, we could consider fully removing "support" for these rate limit headers, as they are not standardised well enough at this point.

@mre What are your thoughts on this?

[jcharaoui]

The problem is that this is not standardised yet and many websites use different approaches to rate limiting, while potentially reusing the same header names for different purposes.

Yeah I understand that's probably not easy to pin down, but that said at least GitLab isn't totally making things up here: those headers are actually generated by the Rack::Attack Ruby library, which I guess could be an attempt at some form of standarisation?

GitLab itself documents those headers here: https://docs.gitlab.com/administration/settings/user_and_ip_rate_limits/#headers-returned-for-all-requests

Maybe we can handle this with better error handling. Alternatively, we could consider fully removing "support" for these rate limit headers, as they are not standardised well enough at this point.

A knob in the per-host settings would probably be quite useful here.

[mre]

Thanks for raising this and for testing with master in the first place.

The original bug is that we don't handle underflows correctly in the parser in that case. That should be an easy fix, though, and it should then work correctly for your use-case. (Right now, the rate limit handling is completely off for GitLab servers because of that.) I haven't worked on the fix yet, but I can create a PR.

The bigger problem is that parsing rate-limit headers is hard. That's why I put some work into https://github.com/mre/rate-limits yesterday, which is my library to parse all sorts of rate-limit header formats. It also handles overflows/underflows correctly.

It has always been my goal to integrate it into lychee. Maybe now is the time. We could move the crate to the lycheeverse organization and maintain it here. Any thoughts?

Side note: It looks like GitLab changed their rate-limit config recently; I remember that the headers were named differently a few years back. Probably this happened with the switch to Rack::Attack. I've updated the code in the rate-limit crate to reflect that and will release a new version.

[thomas-zahner]

@mre That's absolutely great! I think this is the optimal approach. Moving the crate to lycheeverse makes sense, although I'm also fine if you keep it.

What happend when rate-limits encountered the headers by GitLab before you updated the vendor specific handling? Was it caught by error handling? This might be worth a test and maybe some documentation. I would suspect that there are many websites out there abusing/reusing the rate limit headers with their own definition of what the values mean, as the standard is still only a draft, as opposed to the standardised Retry-After header. (correct me if I'm wrong)

Would it maybe make sense to be pessimistic and only try to parse the rate limit headers if we trust the website to follow the old draft? I feel like this will be much less of an issue with the newer draft using the RateLimit-Policy header, as it's much more specific and not as easy to "abuse".

Also should we temporarily remove the feature from master and re-add it only once we are using rate-limits and have full confidence that the feature works reliably? I this would make sense in my opinion.

[mre]

Thanks!

What happened when rate limits were encountered in the headers returned by GitLab before you updated the vendor-specific handling?

It returned an error, yes. I’ve added some tests for that now.

I would suspect that there are many websites out there abusing/reusing the rate-limit headers with their own definition of what the values mean, as the standard is still only a draft, as opposed to the standardised Retry-After header.

My impression is that most APIs don’t return rate-limit headers at all. Other websites use those headers even less. That said, we could return an Unknown variant that simply wraps whatever we find, but that could easily lead to dangerous guesswork. I’m still undecided on this.

Would it maybe make sense to be pessimistic and only try to parse the rate-limit headers if we trust the website to follow the old draft?

I’m not 100% sure I understand this part. Do you mean the old Polli IETF draft? I don’t think many websites use that. In practice, most sites use their own, organically grown headers, or a library that existed before the draft. Correct me if I misunderstood. 😉

Also, should we temporarily remove the feature from master and re-add it only once we are using rate limits and have full confidence that the feature works reliably? I think this would make sense in my opinion.

The fix for this particular issue should be a single line. (Preventing the underflow.) It’s also the only case we’ve found so far, so we could start by fixing it on master and giving the functionality a bit more time to mature.

In general, it’s hard to find all edge cases without testing in the wild, and not many people use master regularly anyway. There's a high chance that we will encounter more errors, but at some point we may just have to release a new version and wait for feedback. As long as we proactively fix those bugs, we should be good.

We can mention this in the release notes and ask people to report issues if they find any. It would help make the parsing logic more robust. We could also add a --disable-rate-limit flag, but I’d prefer to avoid that. It mostly just shifts responsibility to the user and isn’t very discoverable. Most users won’t know the error is related to rate limiting, and they probably won’t care. This feels like a case where lychee should do the right thing out of the box, but we should still handle these use-reports carefully.

My proposal is to fix the bug in the code and then work on integrating the rate-limits in a separate PR.

[thomas-zahner]

I’m not 100% sure I understand this part. Do you mean the old Polli IETF draft? I don’t think many websites use that. In practice, most sites use their own, organically grown headers, or a library that existed before the draft. Correct me if I misunderstood. 😉

No I mean the old and not well standardised X-RateLimit-X headers, just as it happens to be with this GitLab issue.
I definitely agree that we should fix the overflow issue, which I now did in #2030.
However, I think we are still handling the rate limit headers the wrong way in this example, as GitLab uses a different approach than our lychee implementation assumes. This would be fixed by using your rate-limit crate as you did a GitLab specific implementation, right?

My question / confusion probably is; do you only support your vendor specific implementations, or do you also have the same (depending on the website potentially wrong) algorithm we currently have in lychee, which is used as a fallback for when no vendor matches?

[thomas-zahner]

I've merged #2030 now, so in your specific use-case you should no longer see this insanely big number cause by the overflowing subtraction. But I still think that the handling of the rate limit headers of GitLab are not handled the right way. It just so happens that usage_ratio is 0, so it will not negatively affect us normally.

I'm keeping this issue open, to remind us that we should switch to @mre's rate-limits crate at some point, so that rate limiting header handling is more reliable.

[jcharaoui]

Thanks. I've tried again using the latest docker.io/lycheeverse/lychee:master image but the problem unfortunately still occurs as I described initially.

[thomas-zahner]

This is probably because the Docker release wasn't properly updated yet. If you retry in a few days or if you build run lychee from source directly or build the docker image yourself it should ideally work. The issue that the docker image is outdated is tracked in #2037

[jcharaoui]

Indeed, I built the container myself from latest HEAD and can confirm the issue doesn't occur anymore. Thanks!

[mre]

Glad to hear that.

For future reference, the outstanding work is to

• Test the rate-limits crate and migrate to it if useful.