Introducing Adaptive Cache for Dynamically Managing Freshness

Readyset's shallow caches make a number of improvements over typical TTL-based caches. Typical TTL-based caches force a coarse grained decision upon you for your entire workload. On the one hand, picking a TTL lets your workload benefit from the speed of a cache up to that duration. On the other hand, picking a TTL often means you'll see stale data for that entire duration. Below, we'll talk about some of the improvements we've already made, as well as a new one we're releasing this week.

Background

In addition to a TTL, Readyset's shallow caches already had the concept of a cache refresh, which is a mechanism that preemptively refreshes the value in the cache with a fresh value from the upstream database. If you aren't already familiar with it, consider the following definition for a query cache:

CREATE SHALLOW CACHE
POLICY TTL 10 SECONDS
REFRESH 2 SECONDS
FROM SELECT * FROM orders WHERE id = ?;

The REFRESH parameter specifies how long a result can sit in the cache before Readyset considers refreshing it from the upstream database. In this example, if another request is made for the same key and that key's value is older than two seconds, Readyset immediately returns the existing value and simultaneously refreshes it from the upstream database.

The idea behind this mechanism is that a request for a key indicates interest in it, so the REFRESH parameter is a way of saying, "I generally want results to stay in the cache for 10 seconds, but also, for hot keys, I want to refresh them more often so consumers are able to see more recent data more frequently."

For workloads where freshness is even more important, we provide an even stricter guarantee of freshness via scheduled refresh (REFRESH EVERY <n> SECONDS), which performs refreshes on a hard schedule, not tied to cache access.

This refresh mechanism allows for increased result freshness, driven by your workload, which dynamically responds to your workload on a per-key basis.

When you create a shallow cache in Readyset, you can specify a TTL (how long a result set will persist in the cache if not accessed) and a refresh interval (how frequently within the TTL the result set will be automatically refreshed, defaulting to half of the TTL). For some workloads, this degree of configuration may be enough.

But what if the results of a single query don't all change at the same rate? Maybe, within a single cache, some results can change frequently while others are relatively static. Until now, you could only tune the refresh interval for the whole cache, so if you wanted to increase freshness for some results, you had to also refresh everything within that cache, maybe more often than needed.

Adaptive refresh

Today's new feature closes that gap and allows refresh intervals to vary within a single cache. You can now use the ADAPTIVE keyword to configure the refresh interval to be adaptive, indicating that the refresh interval should change for each cached result according to how frequently a given cached result changes.

CREATE SHALLOW CACHE
POLICY TTL 10 SECONDS
REFRESH 2 SECONDS
ADAPTIVE
FROM SELECT * FROM orders WHERE id = ?;

With the adaptive option, every time a result is refreshed, the cache examines whether the result changed or not. For a result that changes, Readyset will automatically decrease the refresh interval so as to increase the freshness of that specific result. Conversely for a result that doesn't change, Readyset will increase the refresh interval so that execution time spent on refreshing can be allocated to results that would benefit from being refreshed more often.

The big win from this feature is decreased staleness (or increased freshness, depending on your perspective), which we define as the length of time that the cache doesn't reflect what's in the upstream database.

This feature is available to both caches using on-access refresh and scheduled refresh. The refresh interval range of an adaptive cache is clamped to a minimum of 10% and a maximum of 100% of the originally configured refresh interval. Thus refresh will never go to near-zero, nor will it exceed the freshness originally specified.

Equality is determined by an order-insensitive hash of the result set's content, so a query without an ORDER BY clause will not cause the refresh interval to shrink merely because the same result set was returned by the upstream database in a different order.

What does this mean in practice? In our testing, comparing an adaptive cache to a non-adaptive cache, we saw p95 staleness decrease by 86% compared to a cache with scheduled refresh. If you compare against a traditional TTL-based cache, the adaptive cache is 97% better than a straight TTL.

To do that with a non-adaptive cache, you'd need to decrease the refresh interval by 70%, which would mean the upstream database load from those refreshes would be 5.9x what it originally was (a 490% increase). But due to the fact that adaptive refresh works on a per-key basis, the refresh load was only 1.6x (a 60% increase).

Adaptive refresh is subject to an overall load cap so that a large amount of frequently changing results can't push the load on the upstream database to infinity. An adaptive cache tracks the additional load put on the upstream database as a result of adaptive refresh, tracking actual execution time, and by default it limits changes to refresh intervals as a result of adaptive refresh to 100% of the original total refresh load, as determined by actual execution time of all the result sets in the cache.

Finally, if you're using auto caching, good news: adaptive refresh is on by default, and you don't have to do anything!

Observability

We're pleased to introduce new metrics related both to adaptive refresh and general caching performance:

Within the readyset.shallow_cache_refresh_stats and readyset.shallow_cache_coalesce_stats virtual relations:

• Per-cache adaptive refresh load
• Refresh scheduler queue depth
• Hit rate to SQL clients

There's also a new readyset.shallow_caches virtual relation with configuration information and whole-cache statistics on hit rate, miss rate, refreshes, and coalesces.

If you use request coalescing to eliminate thundering herds on cache misses, we've added new Prometheus metrics to show you how many upstream executions we've avoided and how much upstream execution time has been saved as a result of coalescing. The coalescing metrics also include a counter of timeouts to show if the coalescing interval may be too short.

Additionally, we've added counters for how often we refresh data within a TTL and how often refreshes are wasted (data not served before a refresh or eviction). Whereas a typical cache would be stale for the entire TTL, these metrics let you see the degree to which intra-TTL refreshing is delivering fresher data sooner while also indicating when the configuration may have gone too far and have refresh intervals that may be too short or TTLs that may be too long.

All of these new metrics are designed to help operators tune cache behavior toward what they want.

Performance

We've also been working to make shallow caching more effective and more efficient.

A simpler cache might make eviction decisions based on recency of use or frequency of use, but we didn't think that was good enough for all workloads. For example, a result that is less frequently used might be worth caching if it's more expensive to recompute. To account for this factor, we've modified our low-level cache to make eviction decisions based on cost-weighted frequency of use. Thus rather than considering simple recency or frequency, the cache is thinking about total execution time saved on the upstream database when deciding what to keep and what to evict.

We've also taken a further step in a long term project to migrate our internal query parsing framework by disabling the old parser for shallow cached queries. Removing that code reduces the CPU load of shallow caching by about 75%, making a Readyset server capable of serving even more load.

Finally, we've also augmented our safety features with the ability to cap result set size (default 1 GB) and with automatic rejection of queries that involve non-determinism or that could produce side effects that need to occur on the upstream database.

Demo

If you'd like to see a demo of the effects of adaptive refresh, you can check out our git repository on Github and run cargo run --release --bin readyset-shallow-bench. This test runs a simple select and update workload. In the following run, it ran about 26k QPS of reads and about 2k QPS of updates. If you run the test, you'll see are results similar to the following:

=== scenario 1: baseline TTL ===
readyset read latency (us):
  hot cache hit            mean=57       p50=56       p95=87
upstream read latency (us):
  hot                      mean=408      p50=339      p95=845
sampled staleness of shallow-served rows (ms):
  hot                      mean=4583     p50=4714     p95=9040

=== scenario 3: scheduled refresh ===
readyset read latency (us):
  hot cache hit            mean=74       p50=63       p95=150
upstream read latency (us):
  hot                      mean=693      p50=451      p95=1831
sampled staleness of shallow-served rows (ms):
  hot                      mean=619      p50=550      p95=1597

=== scenario 4: adaptive refresh ===
readyset read latency (us):
  hot cache hit            mean=77       p50=66       p95=157
upstream read latency (us):
  hot                      mean=766      p50=512      p95=1973
sampled staleness of shallow-served rows (ms):
  hot                      mean=29       p50=0        p95=215

p95 sampled staleness falls from 9040 ms (baseline TTL) to 1597 ms (scheduled refresh) to 215 ms (adaptive refresh).

(The actual output contains more numbers, so the above was edited to elide some of them, but these numbers are all from a single, real test run.)

Thanks to adaptive refresh, that 97% reduction in staleness cost only 10% more refreshes!

A few weeks ago, Adaptive Cache became available as part of Readyset Platform. Adaptive Cache works seamlessly with QueryPilot, adding even more granular self-tuning capabilities to the platform. This is a key step in our journey to offer a truly invisible database caching approach and we couldn't be more excited for you to give it a try.