Rate limit and horizontal scaling: how about a persistent cache?

[iainlane]

One thing we're struggling with at our organisation, is the GitHub API rate limit. We've managed to get GitHub to raise it once or twice for us but it's a struggle. We're occasionally coming uncomfortably close to hitting it again now.

I'm thinking about strategies to help with this.

I have had a decent look through Policy Bot's code, and I didn't manage to find anywhere that unnecessary API requests are being made. It seems like we're already sufficiently careful. Caching within an instance seems to work too, as far as I can see.

A relevant thing: since the bot is stateless, it's no problem at all to run multiple replicas. That's a really great property which makes it much more pleasant to operate. Having it as a required check in CI means that we can't really tolerate much downtime and this is an easy way to reduce that risk. We currently run two replicas. The downside of this is that each replica has to build up its own cache. They can't share what they know.

So what I am thinking about is adding some kind of cache persistence. This would make it so that each instance (e.g. after a pod eviction) doesn't start with a blank slate. It would also mean that parallel instances would have the chance of sharing state. In the most ideal case we'd only need to make 1 request for each resource (for us that would mean 50% fewer requests).

Of course, this comes with a bit of complexity in the codebase and the config. As far as I can see, since we're using httpcache, this could likely be done by adding extra backends there, which is fairly self-contained. But still they'd be in tree and need to be exposed in documentation.

So I thought I'd ask - does this sound like an acceptable direction? I'd love to hear any alternative approaches.

[bluekeyes]

I've also thought about some kind of shared cache, but have so far been avoiding it, mostly to keep things as simple as possible. While an optional remote cache for HTTP responses isn't all that complicated, it does add more variables between different installations and opens the door to requests to support everyone's personal favorite cache backend. Once it exists, there's also a bit of temptation to add state in other parts of the app where it would be convenient, turning an optional performance enhancement in to a required component.

That said, it might be the only option to continue to scale giving rate limits after a certain point. Did you have a particular backend in mind?

Before exploring the shared cache, I think there are still some other avenues for optimization. The discussion in #1030, highlighted some optimization other users made in their fork that haven't been contributed upstream yet. The part that seems the most beneficial to me is analyzing the actual cost of our GraphQL queries because:

• It's not always obvious how expensive a query will be from looking at it
• GraphQL queries do not use the existing HTTP cache, so optimizing them provides extra benefits

There's definitely room to make our GraphQL queries less expensive and there might also be places where we should make different tradeoffs between GraphQL and the REST API based on query cost, number of requests, and cachability.

Separately, palantir/go-githubapp#437 has some discussion about the limitations of GitHub's cache implementation which also links to https://github.com/bored-engineer/github-conditional-http-transport. I'm not sure how relevant this is to Policy Bot, since we're more concerned with short-term caching when a PR is active, but it shows there could be ways to improve the effectiveness of the existing cache. Our internal instance seems to sit at about a 45% hit rate for the cache, but I've never really looked at if it is possible to get that higher.

I don't know if it's possible to figure this out from our existing logs and metrics, but it would be interesting to know what percentage of cache hits are duplicated between two instances of Policy Bot. That could give some sense of how beneficial (or not) a shared cache would be.

[denysvitali-kaiko]

Related: #1152 - there is a bug where the GH Actions run cache is not used.

Adding tracing (via OTEL, #1154) is definitely the key to better understand where the inefficiencies are.
For example, with #1152 we save $N$ requests per policy - in our specific case bringing down the time it takes to perform a policy evaluation from ~8s to ~1s. This also comes with a reduction of requests to the GitHub API from 15 to 7.