What do we want from a cache implementation?

[Geal]

related:

• Faster Caching #42
• Warm the query planner cache with hot queries #174
• Parse & cache queries #205
• Create a single caching implementation #217

there has been a lot of discussion recently on caching, following up on #42 where we wanted to move from a hashmap to anything that resembled a cache, and settled on lru in #174 and #205. We now want to refactor both in a single type in #217.

It is now a good time to discuss the features we would want from a cache implementation, considering that this part of the Rust ecosystem is not well developed (example: stretto is very young), and this will likely be a crucial part of our graphql implementation.

[Geal]

1- which parts of the router will need cache:

• query plan result
• query selection sets results (for now, separated from the query plan result because we use the gateway's query planner)
• subgraph responses
• ...?

[BrynCooke]

We need to cache the parsed query.
What is query selection sets results?

[Geal]

it is used for the final validation of the response, to eliminate the fields that we do not use:

router/apollo-router/src/apollo_router.rs

Line 114 in 4bfa64a

query.format_response(&mut response, request.operation_name.as_deref())

[Geal]

2- where do we want to store the cache:

• in memory (what we do right now)
• external service: redis
• external service: memcached
• ...?

[BrynCooke]

Would be interested to know what the impact is if we just use redis and don't give any other option.

[garypen]

I have done work in route caching recently where we used redis as a shared external cache and the performance compared to an in-memory cache implementation was within a few %.
I would note:

• redis was configured as a cluster for high availability
• read/write ratio was very high (i.e. cache entries were high)
• cache entries were expired after a fixed period of idleness (60 seconds I think...)

[Geal]

using an external cache would allow us to delay decisions on the cache's features, that would be managed by well tested tools and, more importantly, probably well known by future router admins

[Geal]

one important feature that appeared: if we get a lot of similar queries at the same time, when the cache does not have the value, we should do the work once and have all queries wait on it. In async code

[garypen]

That's quite an unusual requirement which our implementation does handle without blocking the entire cache.

[Geal]

this is actually common in web caches like Varnish: https://info.varnish-software.com/blog/request-coalescing-and-other-reasons-to-use-varnish-as-an-origin-shield

[Geal]

3- which caching strategy do we use:

• LRU = Least Recently Used: the least recently used element is discarded when we insert a new one
• LFU = Least Frequently Used: we track usage of each item, and the ones used les frequently are discarded first
• ...?

See https://en.wikipedia.org/wiki/Cache_replacement_policies for a list of the main ones

[BrynCooke]

Suggest LFU. In terms of autotuning I think this will get us most of the way there and also helps prevent against denial of service by a malicious client.

[garypen]

Not sure how LFU prevents DoS... Can you clarify that?

[Geal]

yup, LFU won't prevent DoS. If You have a 100 entries cache and you do 100 different queries in a loop, you'll still evict everything else from the cache and will be able to add new ones at will to trigger some CPU work.

I think the cache eviction algorithm will be highly dependent on the workload, so this is something we could decide after looking at production data.

Personally, I think we'll need to support multiple strategies depending on the cache:

• client applications will send the same queries frequently, the distribution will follow a power law. So the most frequent queries should stay -> LFU. We should also have an expiration date (because applications update and change their queries)
• for subgraph responses, this will depend on the workload, but there will be a lot more variations, and a lot of queries will be done only once -> LRU

[BrynCooke]

I was thinking of a situation where a malicious client could randomly modify their query on every request causing real frequent queries to be evicted.
We should probably only have multiple cache implementations as a last resort. LFU with some sort of decaying frequency is likely to be good enough. At least we should wait until there is actually a user who can articulate why they should have a separate cache implementation.

[Geal]

we need a way to keep some of the elements always present in cache, like introspection queries

[BrynCooke]

Suggest wait and see if this is actually an issue. If introspection queries don't get called often then they deserve to be evicted.

[Geal]

4- how do we choose the limit for the cache?

• by number of elements
• for in memory caches, by the size in memory (note that I know a way to calculate the full memory footprint of data in async rust)
• by age
• ...?

[Geal]

by cost of creating an element? (ie count how much time it took to create it)

[BrynCooke]

Assuming LFU it'd be good to be able to use memory usage for the limit. However, would definitely be OK with a hard limit for number of elements as a first step.

[Geal]

5- how do we configure it? Do we make it configurable?

• set a default value, large enough
• make it configurable, expose it through the configuration file
• offload the choice to another system (ex: store in memcached)
• autotuning: the router chooses a value depending on available memory, info from Apollo Studio, and usage frequency is its current cache

[BrynCooke]

Suggest not allowing config until we have got metrics in place to allow the user to actually set config in an informed way.
Without this there is no benefit to the user to having this setting.

[Geal]

if we only focus on query plan and query cache for now, we could get away with a 10MN or 100MB cache easily

[Geal]

6- if we cache data from subgraphs, some of the data might be private, so cache access could depend on a variable (user id, auth token, etc)