Deep Caching

Deep caching is Readyset's dataflow-based caching engine. It turns even the most complex SQL reads into lightning fast lookups with no extra code by maintaining query results incrementally as your data changes, rather than recomputing them on each read.

Readyset slots between your application and database. It is wire-compatible with both MySQL and Postgres, so all you have to do to start using Readyset is swap out your database connection string. Readyset gives you fine-grained control over which queries are cached. Queries that aren't cached are proxied through Readyset.

Research origins

Deep caching grew out of Noria, a research project from MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL). Noria introduced partially-stateful dataflow: a long-lived dataflow graph that incrementally maintains query results as the underlying data changes, while materializing only the subset of state that queries actually demand and evicting the rest under memory pressure. This is the partial materialization model that lets Readyset cache complex queries without holding entire result sets in memory.

Noria was published as "Noria: dynamic, partially-stateful dataflow for high-performance web applications" at OSDI 2018. Readyset is the production system built on those ideas.

How does deep caching work under the hood?

Imagine a basic online forum application with posts, users, and upvotes. A simple database schema for this application might look like:

You can imagine a query like the one below, which returns all of the posts authored by a particular user:

    SELECT
      posts.title, posts.id, users.username
    FROM
        posts
    INNER JOIN
        users
    WHERE
        posts.author_id = users.id AND users.id = ?;

Under the hood, Readyset constructs a dataflow graph for the query. Each node of the graph is updated when writes occur, keeping the query results up to date.

The graph for the query would look something like this:

Once the graph is constructed, if a user queries all of the posts authored by user id 4, Readyset has the results ready so reads can be performed with no additional compute. Results are therefore returned instantaneously, regardless of the size of your database.

How does Readyset handle more complex queries?

One of the biggest advantages of this model is that latencies are not affected by query complexity. Let's take a look at a few more queries in this application:

Here's a point query for an article:

SELECT * FROM posts WHERE id = ?;

And here's a query for the total upvote count of an article:

SELECT
    id, author_id, title, vcount
FROM
    posts
JOIN
    (SELECT post, COUNT(*) AS vcount
                FROM upvotes GROUP BY post)
AS
    VoteCount
ON
    VoteCount.post = posts.id WHERE posts.id = ?;

In traditional database settings, as queries get more complex, performance can seriously suffer. To work around this, developers denormalize data or implement out-of-band caching solutions that require extra application logic to keep in sync with the database. With Readyset, read performance is not impacted by the size of the base tables or query complexity.

Streaming Dataflow

The basic premise of streaming dataflow is that a series of operations is applied to each element of a stream (a given sequence of data).

Stream

The stream that Readyset deals with is the sequence of inserts of new records to your database and updates of existing records in the database.

Databases typically refer to the stream as either the binary log or replication stream.

Readyset receives this stream as input by registering itself as a read replica of your primary database.

Operations

Operations transform the stream in some way.

Readyset applies SQL operations over this data change stream to compute the results of the SQL queries you want to cache. When Readyset receives a new SQL query, it first creates a query plan, which consists of the ordered sequence of transformations over the data in the base tables that needs to be applied to compute the correct query result. Readyset then instantiates a long-lived dataflow graph that actually executes these operations in the query plan over the incoming data stream.

The entry points of Readyset's dataflow graph are referred to as base table nodes, which represent the underlying database tables. Incoming data changes enter the graph via the base tables, before flowing through the rest of the operators in the graph.

Below the base table nodes are internal nodes. Each internal node computes a specific SQL operator (e.g., joins, aggregates, projections, and filters) over the incoming stream of data changes. Each node tracks the results of these operations, keeping them up to date in real-time in memory.

Whenever a new element in the stream is received by Readyset, it is first updated in the base table node. The change then "flows" downstream, through the internal nodes of the graph. Each internal node updates its in-memory state before passing the change downstream through the graph.

Leaf nodes in the graph have no downstream nodes. These nodes are called reader nodes, storing the result set associated with a given query.

Things to consider

Memory Overhead

There's no free lunch– Readyset trades off the cost of maintaining the dataflow graph in memory for excellent read performance. However, there are a few key ways we can mitigate this cost, such as through partial materialization. You can think of partial materialization as a demand-driven cache-filling mechanism. With it, only a subset of the query results are stored in memory based on common input parameters to the query. For example, if a query is parameterized on user IDs, then Readyset would only cache the results of that query for the active subset of users, since they are the ones issuing requests. Once Readyset surpasses a developer-specified memory limit, cache entries are evicted from memory based on a specified eviction strategy (e.g., LRU).

Readyset also makes it easy to cache only the subset of your queries that have the highest impact on read performance. You can use the Readyset dashboard to profile your existing workload and make caching decisions based on query frequency and the current latencies. If some of your queries don't need additional read performance boosts, you can continue proxying them to the customer database. As a result, they won't take up any memory real estate in your Readyset deployment.

No Strong Consistency

Readyset is eventually consistent. There will be a small delay between when the write is issued and the cached result is updated in Readyset to reflect that write. This might not be suitable for all applications, or all parts of an application.

Example

To illustrate these concepts, we will walk through an example of using Readyset for a news forum application inspired by HackerNews.

Schema

First we define two tables to keep track of HackerNews stories and votes.

CREATE TABLE stories (id int, author text, title text, url text);

CREATE TABLE votes (user int, story_id int);

Query

Next, we'll write a query that computes the vote count for each story and joins the vote counts with other story metadata such as the author, title, and ID.

SELECT id, author, title, url, vcount
FROM stories
JOIN (SELECT story_id, COUNT(*) AS vcount
            FROM votes GROUP BY story_id)
AS VoteCount
ON VoteCount.story_id = stories.id WHERE stories.id = ?;

Caching with Readyset

Traditional databases would compute the results of this query from scratch every time it was issued. Readyset takes a different approach and instead precomputes and incrementally maintains the results of this query for commonly read keys. To accomplish this, Readyset creates a streaming dataflow graph, as described in the Streaming Dataflow section above. At a high level, the dataflow graph would look as follows:

Under the hood, here's what some of the internal state might look like for this graph.

Now, we'll take a look at what happens when the data changes. Let's say that we add a record to the Votes table to reflect the fact that Justin voted for the story with ID 2. This update would first be applied to the Votes base table at the root of the graph, and then be propagated through the graph, updating all children nodes along that way. The figure below shows the modified state at each node as the result of this write.

When performing a read (i.e., executing the prepared statement), we're essentially just doing a key-value lookup for the parameter value on the relevant column of the reader node.

In this case, we're doing a lookup for key 2 on the ID column of the reader node. These lookups are blazingly fast, since reader nodes are lock-free, in-memory data structures.